`

手写SQL词法分析

阅读更多
要写一个词法分析,首先是要对一段 sql 进行解析,然后将其解析为一个一个的 token.

每个 token 是都特定含义的,固定义 token 结构如下:

/**
* token for sql.
*/
public final class SQLToken {
    // 可能称为类型更合适些, 用于标识解析出来的 token 的类型.
    // 比如 select, insert, 字符串, id 等.
    private final int value;
    // token 在 sql 中的偏移量
    private final int offset;
    // token 的长度
    private final int length;
    private String name; // 用于字符串.

    //用于构造带引号的字符串
    public SQLToken(int value, int offsetStart, int offsetEnd, String name) {
        this.value = value;
        this.offset = offsetStart;
        this.length = offsetEnd - offsetStart;
        this.name = name;
    }

    public SQLToken(int value, int offsetStart, int offsetEnd) {
        this.value = value;
        this.offset = offsetStart;
        this.length = offsetEnd - offsetStart;
    }

    // 返回 token 的类型
    public int getValue() {
        return value;
    }

    // 返回 token 的值.
    public String getName(char[] sql) {
        if(null != this.name) return this.name;
        return new String(sql, this.offset, this.length);
    }
}

定义了 token 结构后,下一步要做的工作是解析 sql. 思路是首先读取一个 char,然后判断是否是注释,如果是注释,则直接跳过,如果不是注释,则进一步判断是否是字符串,判断是否是小数,最后处理 identifier.

实现如下:



public static List<SQLToken> parseSQL(char[] sql) throws SQLException {
        SearchNode node = searchTree;
        ArrayList tokens = new ArrayList();
        int value = 0;
        int tokenStart = 0;
        boolean wasWhiteSpace = true;
        int comment = NOT_COMMENT;
        char quote = 0; //引号
        StringBuffer quoteBuffer = new StringBuffer();

        for(int i=0; i<sql.length; i++){
            char c = sql[i];
            switch(c){
                case '\"':
                case '\'':
                    // 如果是注释, 就直接跳过.
                    if (comment != NOT_COMMENT) {
                        break;
                    }else if(quote == 0){
                        // 将第一次遇到的单引号或双引号赋值给 quote.
                        quote = c;
                    }else if(quote == c){
                        // check on escaped quote
                        // 这一段代码是为了解决单引号和双引号作为字符串中的字符这种情况.
                        // 例如 insert into Person values('xh'', 'xh'''). 这时候, 通过如下这段代码就会把第一个、第二个
                        // ' 当成字符串中的字符.
                        if(i+1<sql.length && sql[i+1] == quote){
                            quoteBuffer.append(quote);
                            i++;
                        }else{
                            // 如果不是上述情况的话, 那么应该就要构造字符串了.
                            // quoteBuffer 就是在 default 处处理的字符.
                            // 这里我我估计该作者认为, 不管是数字还是字符串, 只要是以 ' 结尾的话, 那么就是字符串, 否则
                            // 就是 id.
                            tokens.add( new SQLToken((quote == '\'') ? STRING : IDENTIFIER, tokenStart, i+1, quoteBuffer.toString()));
                            quoteBuffer.setLength(0);
                            quote = 0;
                            tokenStart = i+1;
                            wasWhiteSpace = true;
                        }
                        // 这里还有一个单双引号的问题, 假设如果开始进入的时候是 ", 后来进入的时候是 ',
                        // 那么此时这段代码就能发挥作用了.
                    }else quoteBuffer.append(c);
                    break;
                case '.':
                    // 如果是注释, 就直接跳过.
                    if (comment != NOT_COMMENT) {
                        break;
                    }else if(quote == 0){
                        // there are follow cases with a point
                        // "abc"."abc" --> identifier --> multiple tokens
                        // "5"."3" --> identifier --> multiple tokens
                        // 5.3 --> number --> one token
                        // 5.e3 --> number --> one token
                        // .3 --> number --> one token
                        // .e3 --> identifier --> multiple tokens
                        int k=tokenStart;
                        // 当第一个字符就为 . 时: 检查后续是否为数值.
                        if(k == i){ // point is first character
                            if(sql.length> k+1){
                                char cc = sql[k+1];
                                if((cc >= '0') && cc <= '9') break; // is a number --> break
                            }
                        }else{
                            for(; k<i; k++){
                                char cc = sql[k];
                                if((cc != '-' && cc != '$' && cc < '0') || cc > '9') break; // is identifier --> break
                            }
                            if(k>=i) break; // preceding tokens are only digits that it is not an identifier else a floating number
                        }
                    }
                    // character before is not a digit that it is an identifier
                    // no break;
                case '-':
                    // 如果是注释, 就直接跳过.
                    if (comment != NOT_COMMENT) {
                        break;
                    }
/* start of single line comment */
                    // 如果是单行注释.
                    else if (c == '-' && (i+1 < sql.length) && (sql[i+1] == '-')) {
                        if(!wasWhiteSpace){
                            tokens.add( new SQLToken( value, tokenStart, i) );
                            value = 0;
                        }
                        i++;
                        tokenStart = i+1;
                        // 将 comment 转成单行注释.
                        comment = LINE_COMMENT;
                    }
                    else if(quote == 0 && !wasWhiteSpace){
                        char c1 = sql[tokenStart];
                        char cx = sql[i-1];
                        if(((c1 >= '0' && c1 <= '9') || c1 == '.') && (cx == 'e' || cx == 'E'))
                            //negative exponential number
                            break;
                        if(c1 == '$' && tokenStart+1 == i)
                            // money number
                            break;
                    }
                case ' ':
                case '\t':
                case '\n':
                case '\r':
                case ',':
                case '(':
                case ')':
                case '{':
                case '}':
                case '*':
                case '+':
                case '/':
                case '%':
                case '&':
                case '|':
                case '=':
                case '<':
                case '>':
                case '?':
                case '^':
                case '~':
                /* end of line comment */
                    if (comment == LINE_COMMENT) {
                        // '\r'/'\n' check needed because of fall-through
                        // 当换到下一行时, 需要重置 comment 为 NOT_COMMENT.
                        if (c == '\r' || c == '\n') {
                            comment = NOT_COMMENT;
                            wasWhiteSpace = true;
                        }
                        tokenStart = i+1;
                        break;
                    }
                /* end of multi-line comment */
                    else if (comment == MULTI_COMMENT) {
                        // '*' check needed because of fall-through
                        // 当遇到 */ 时, 需要将 comment 重置为 NOT_COMMENT.
                        if (c == '*' && (i+1 < sql.length) && (sql[i+1] == '/')) {
                            comment = NOT_COMMENT;
                            wasWhiteSpace = true;
                            i++;
                        }
                        tokenStart = i + 1;
                        break;
                    }
                    else if(quote == 0){
                        // 这里是将字符串分割成一个一个的 Token. 同时将 value 置为 0.
                        if(!wasWhiteSpace){
                            tokens.add( new SQLToken( value, tokenStart, i) );
                            value = 0;
                        }
                        switch(c){
                            case ' ':
                            case '\t':
                            case '\n':
                            case '\r':
                                // skip this characters, this are not tokens, this are only source formatter
                                // 跳过 ' '、'\t'、'\n'、'\r' 这些字符, 因为这些是源输入的格式符.
                                break;
                            case '<':
                                if((i+1 < sql.length) && (sql[i+1] == '>')){
                                    tokens.add( new SQLToken( UNEQUALS, i, i+2) );
                                    i++;
                                    break;
                                }
                            case '>':
                                if((i+1 < sql.length) && (sql[i+1] == '=')){
                                    tokens.add( new SQLToken( 100 + c, i, i+2) );
                                    i++;
                                    break;
                                }
                                    /* start of multi-line comment */
                            case '/':
                                // 这种情况是多行注释.
                                if((i+1 < sql.length) && (sql[i+1] == '*')){
                                    i++;
                                    tokenStart = i+1;
                                    comment = MULTI_COMMENT;
                                    break;
                                }
                            default:
                                // 在这里就可以处理类似于 () 等字符.
                                tokens.add( new SQLToken( c, i, i+1) );
                        }
                        wasWhiteSpace = true;
                        tokenStart = i+1;
                    }else{
                        quoteBuffer.append(c);
                    }
                    break;
                default:
                    // 这里处理正常字符串的逻辑.
                    if (comment != NOT_COMMENT) {
                        break;
                    }else if(quote == 0){
                        if(wasWhiteSpace){
                            // 当出现空格的时候, 说明是一个新的字符, 所有这里需要重新将 node 赋值为 searchTree.
                            node = searchTree;
                        }else{
                            // 当 node 为空的时候,就是出现了 searchTree 中没有出现的字符, 这里同样是跳过该字符.
                            // 这里将 wasWhiteSpace 赋值为 false, 就是为了避免 node 被重新初始化为 searchTree.
                            if(node == null){
                                value = 0;
                                wasWhiteSpace = false;
                                break;
                            }
                        }
                        // 将所有的字符全部转换为小写.
                        c |= 0x20; // case insensitive
                        // 从 searchTree 中找到该字符开始的 nextEntry.
                        while(node != null && node.letter != c) node = node.nextEntry;
                        if(node != null){
                            // 这里是找到了那个 node. 假设执行的是 drop table Person 语句的话. 此时: value = 0
                            // node = e.
                            value = node.value;
                            node = node.nextLetter;
                        }else{
                            // 如果没有找到的话,将 value 赋值为 0, 同时 node 置为空. 目的是为了跳过后面的检查.
                            value = 0;
                            node = null;
                        }
                    }else{
                        quoteBuffer.append(c);
                    }
                    // 执行完后, 将 wasWhiteSpace 赋值为 false, 防止 node 被重新初始化为 searchTree.
                    wasWhiteSpace = false;
                    break;
            }
        }
        // 如果 comment 还等于 MULTI_COMMENT 它的话, 说明这没有被重置了, 即: 还没有遇到 */ 也就是注释没有关闭.
        if (comment == MULTI_COMMENT) {
            throw SmallDBException.create(Language.STXADD_COMMENT_OPEN);
        }

        // 如果最后 wasWhiteSpace 不是另一个单词的开始的话, 应该要将最后一个 SQLToken 构造出来.
        if(!wasWhiteSpace) {
            tokens.add( new SQLToken( value, tokenStart, sql.length) );
        }

        return tokens;
    }

上面一段中,其实还有更好的写法,按照空格分隔(将 SearchNode 的搜索过程转换成从 keywords 中获取 token 的类型),然后去 keywords 集合中匹配关键字,这样效率会更高.
0
1
分享到:
评论

相关推荐

    简易sql词法分析器和语法分析器.zip

    完成 SQL 语言的词法分析器,要求采用课程教授方法,实现有限状态机确定化,最小化算法。词法分析器的输入为 SQL 语言源代码,输出识别出单词的二元属性,填写符号表。单词符号的类型包括关键字、标识符、界符、...

    词法分析器 词法分析器

    词法分析器,也称为扫描器或词法分析器,是编译器设计中的关键组成部分。在编程语言处理中,词法分析器的作用是将源代码文本分解成一系列有意义的符号,即词法单元(Token),这些词法单元是构成程序的基本元素。...

    基于java实现的语法分析器及词法分析器

    在编程语言处理领域,语法分析器和词法分析器是至关重要的组成部分,它们主要用于解析源代码,将其转化为计算机可以理解的形式。在这个项目中,我们关注的是一个基于Java实现的语法分析器和词法分析器。Java是一种...

    词法分析器(用VC++6.0写的)

    词法分析器,也称为扫描器或lexical analyzer,在编译原理中扮演着至关重要的角色。它是编译器的第一阶段,负责将源代码转换为一系列有意义的符号,这些符号被称为“词法单元”或“标记”。在本项目中,词法分析器是...

    pl0词法分析

    根据给定的文件信息,我们可以深入探讨“PL0词法分析”这一主题,涉及的知识点主要包括编译原理、词法分析、以及C/C++编程语言的应用。以下是对这些知识点的详细解析: ### 编译原理简介 编译原理是计算机科学中的...

    编译原理实验报告 词法分析器实验报告

    词法分析器是编译器设计中的重要组成部分,它的主要任务是将源代码中的字符流转化为有意义的符号序列,即词法单元。本实验报告详细介绍了如何设计和实现一个简单的词法分析器,用于处理PL/0语言的源代码。 在设计...

    词法分析器实验报告.doc

    通过亲手实现一个词法分析器,学生能够掌握如何将源代码文本转化为可进一步处理的符号流,为后续的语法分析和语义分析奠定基础。实验性质属于理论与实践相结合,旨在提高学生的编程能力和对编译原理的理解。 3....

    compiler_sql:SQL的词法分析器和语法分析器

    SQL的解析是其执行过程中的关键步骤,涉及到词法分析和语法分析。本文将深入探讨这两个概念及其在SQL编译器中的应用。 **词法分析(Lexical Analysis)** 词法分析是编译器的第一步,它的主要任务是将源代码(如...

    编译原理实验二 词法分析

    通过实验,掌握词法分析的基本概念和技术,包括词法分析的定义、词法分析的步骤、词法分析的应用等。 一、实验目的 词法分析是编译过程的第一阶段,它的主要任务是将源程序扫描为单词,包括基本保留字、标识符、...

    词法分析(实验报告)编译原理

    词法分析是编译原理中的一个关键步骤,它在程序设计语言的编译过程中起着基础性的作用。词法分析,又称扫描或Tokenization,是从源代码文本中识别出一个个有意义的、独立的符号,也就是所谓的“词法单元”或“标记”...

    词法分析程序的设计与实现

    词法分析程序的示例,仅供参考。 使用LEX编写。 北邮 大三 编译原理 词法分析 词法分析程序的设计与实现 实验内容设计并实现C语言的词法分析程序,要求如下: 1)可以识别出用C语言编写的源程序中的每个单词符号,...

    java词法分析器java词法分析器.doc

    Java 词法分析器 Java 词法分析器是 Java 程序设计语言的词法分析工具,用于对 Java 源代码进行词法分析。以下是 Java 词法分析器的知识点: 1. Java 词法分析器的组成部分 Java 词法分析器由多个组成部分组成,...

    词法分析器

    词法分析器,也称为扫描器或词法分析程序,是编译器设计中的关键组件。在编译器的工作流程中,它负责将源代码文本分解成一系列有意义的符号,这些符号被称为“记号”(Token)。这个过程被称为词法分析,是编译过程...

    词法分析器 编译原理中词法分析程序

    词法分析器是编译器设计中的重要组成部分,它在编译原理中扮演着至关重要的角色。词法分析器,也称为扫描器或词法分析程序,主要负责将源代码分解成一系列有意义的符号,这些符号被称为“单词”或“标记”,以便后续...

    词法分析器_词法分析器_简单的词法分析器_

    词法分析器,也称为扫描器或词法分析程序,是编译器设计中的一个重要组成部分。它的主要任务是将源代码文本分解成一系列有意义的、独立的单元,这些单元被称为“标记”(Token)。词法分析器的工作原理是通过模式...

    java词法分析举例

    Java词法分析是编程语言处理过程中的重要步骤,它涉及将源代码文本转换为一系列有意义的标记,这些标记称为符号或token。在这个过程中,词法分析器(也称为扫描器或lexer)会识别并分离出诸如关键字、标识符、常量、...

    词法分析器的设计与实现.doc

    词法分析器是编译器的重要组件之一,它负责将源代码转换为机器可读的形式,并对源代码进行词法分析、语法分析和语义分析。以下是词法分析器的设计与实现的知识点: 1. 词法分析器的设计原理: 词法分析器的设计...

    一个超级经典的词法和语法分析程序(附加源代码).从词法分析的输出过渡到语法分析

    在SQL中,词法分析器会识别关键字(如SELECT、FROM、WHERE等)、操作符(如=、&lt;、&gt;)、分隔符(如逗号、分号)、标识符(表名、列名)以及常量(数值、字符串、日期等)。这个过程通过模式匹配实现,通常使用正则...

    编译原理词法分析

    词法分析器,也称为扫描器或词法分析器,主要任务是将源代码分解成一系列有意义的符号,这些符号被称为“词素”或“记号”,为后续的语法分析和语义分析阶段提供输入。 词法分析的目标是从源代码文本中识别出程序...

    词法分析器的设计与实现

    词法分析器的设计与实现 词法分析器是编译器的组成部分,负责将源代码分解成单词符号,以便后续的语法分析和语义分析。设计和实现词法分析器是编译原理和编译技术的重要组成部分。 正规式 正规式是描述语言结构的...

Global site tag (gtag.js) - Google Analytics