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

# 词法分析 ## 实验内容 完成 SQL 语言的词法分析器，要求采用课程教授方法，实现有限状态机确定化，最小化算法。词法分析器的输入为 SQL 语言源代码，输出识别出单词的二元属性，填写符号表。单词符号的类型包括关键字、标识符、界符、运算符、整数、浮点数、字符串。 ## 实验过程 在词法分析的实现中我们分别实现了两套机制：手工构造词法分析以及基于 NFA 转 DFA 的确定化以及 DFA 最小化算法，下面我将详细这两种实现方式。 ### 手工构造词法分析 ``` +-------+ +--------+ -- source code --> | lexer | --> token stream --> | parser | --> assembly +-------+ +--------+ ``` 在词法分析中，我们需要输入源代码，进而转化为 token stream。由于采用手工构造词法分析器，因此我们实现了 `next()` 方法来对一串源代码进行识别，并输出当前识别的 token，并将指针移到下一个 token 上，关于 `next()` 的框架如下所示： ```cpp // 获取下一个 token bool Lexer::next(bool show) { char* last_pos; while((token = *src) && *src != 0) { ... } } ``` 在主函数时，我们就可以不断循环调用 `next()` 函数从而不断获取 token。 在进行识别 token 之前，我们首先需要规定 token 的类型，token 类型的定义如下所示： ```cpp enum TokenType { Int, Float, // 整数, 浮点数 Idn, // 标识符 Str, // 字符串 Equal, NonEqual, Less, LessEqual, Great, GreatEqual, SafeEqual, // 比较运算符 And, And2, Or, Or2, Xor, Not, Not2,// 逻辑运算符(AND, &&, OR, || , XOR) Sub, // 算术运算符 Dot, // 属性运算符 Lp, Rp, Comma, // 界符((, ), ,) // 关键字 Select, From, Where, As, WildCard,// 查询表达式 Insert, Into, Values, Value, Default, // 插入表达式 Update, Set, // 更新表达式 Delete, // 删除表达式 Join, Left, Right, On, // 连接操作 Min, Max, Avg, Sum, // 聚合操作 Union, All, // 集合操作 GroupBy, Having, Distinct, OrderBy, // 组操作 True, False, Unknown, Is, Null, // 条件语句 Invalid // 无效的 token }; ``` 关于 token 的值的表示如下所示： ```cpp struct TokenValue { double value; // token value, for Num // used when return a string or a symbol address for assignment Symbol* sym_ptr; char* str_ptr; }; ``` 其中关键字的定义如下，关于关键字如何识别我们将在下文提到： ```cpp const TokenType keywords[] = { TokenType::Select, TokenType::From, TokenType::Where, TokenType::As, TokenType::Insert, TokenType::Into, TokenType::Values, TokenType::Value, TokenType::Default, TokenType::Update, TokenType::Set, TokenType::Delete, TokenType::Join, TokenType::Left, TokenType::Right, TokenType::On, TokenType::Min, TokenType::Max, TokenType::Avg, TokenType::Sum, TokenType::Union, TokenType::All, TokenType::GroupBy, TokenType::Having, TokenType::Distinct, TokenType::OrderBy, TokenType::True, TokenType::False, TokenType::Unknown, TokenType::Is, TokenType::Null, TokenType::And, TokenType::Or, TokenType::Xor, TokenType::Not }; ``` 接下来我们就可以去进行识别 token 了，首先是关于整数与浮点数的识别，由于在这里我们仅仅涉及到 10 进制的整数，因此我们可以简单地将字符串在 '0' - '9' 之间的识别为整数，而中间出现 '.' 的为浮点数，因此我们关于整数与浮点数的识别就很简单了： ```cpp else if(token >= '0' && token <= '9') { this->token_val.value = (double)token - '0'; while(*src >= '0' && *src <= '9') { this->token_val.value = this->token_val.value * 10.0 + ((double)(*src++) - '0'); } if(*src == '.') { this->token_type = TokenType::Float; // 浮点数 src++; int countDig = 1; while(*src >= '0' && *src <= '9') { this->token_val.value = this->token_val.value + ((double)(*src++) - '0')/(10.0 * countDig); countDig++; } this->parser_token.type = "FLOAT"; } else { this->token_type = TokenType::Int; this->parser_token.type = "INT"; } this->parser_token.value.emplace(this->token_val.value); goto OUT; } ``` 随后是字符串的识别，由于在所给的标准中不区分字符和字符串，因此我们可以简单认为以 " 开头并以 " 结尾的源代码可以被识别为字符串，否则将被识别为错误，其中关于字符串识别的实现如下所示： ```cpp else if(token == '"') { // 字符串 int size = 0; while(*src != token) { if(*src == 0) { this->token_type = TokenType::Invalid; goto OUT; } src++; size++; } // 将对应的字符串放入地址中并将其存入符号表中 char* str = new char[size + 5]; memcpy(str, src - size, size); str[size] = '\0'; this->token_type = TokenType::Str; this->token_val.str_ptr = str; src++; // 为 parser 添加 token this->parser_token.type = "STRING"; this->parser_token.str.emplace(str); goto OUT; } ``` 接下来就是我们的重头戏：关于标识符的识别，由于在标识符的识别中，我们需要用到符号表，因此我们先介绍一下符号表及我们的实现。首先符号是为了记录某个标识符的名字以及它所对应的值，而符号表则是记录标识符符号的集合： ```cpp struct Symbol { // Symbol Type: Int, Float, Str,... TokenType type; char name[MAX_NAME_SIZE]; double value; }; std::vector<Symbol> symtab; // 符号表 ``` 在定义了符号与符号表之后我们就可以来实现关于标识符的识别，根据定义，标识符的第一个字符只能由 'a' - 'z'，'A' - 'Z' 和 '_' 来组成，而在第一个字符后除了这些也可以使用 '1' - '9'。 因而我们需要去记录标识符的名字并去符号表进行查找，如果找到了则直接将从符号表取出并传给语法分析器，否则则构造新的标识符并将其加入到符号表中并返回，实现如下所示： ```cpp if((token >= 'a' && token <= 'z') || (token >= 'A' && token <= 'Z') || token == '_') { last_pos = src - 1; // 获取符号名 char nameBuffer[100]; nameBuffer[0] = token; while((*src >= 'a' && *src <= 'z') || (*src >= 'A' && *src <= 'Z') || (*src >= '0' && *src <= '9') || *src == '_') { nameBuffer[src - last_pos] = *src; src++; } nameBuffer[src - last_pos] = 0; if(strcmp(nameBuffer, "ORDER") == 0 || strcmp(nameBuffer, "GROUP") == 0) { char* buf = this->lookdown(3); if(strcmp(buf, " BY") == 0) { // 将指针向后移 3 位 src += 3; memcpy(nameBuffer + (src - last_pos), buf, 3); }else { this->token_type = TokenType::Invalid; goto OUT; } } // 从符号表中查找是否有对应的符号名 for(auto sym: this->symtab) { if(strcmp(sym.name, nameBuffer) == 0) { this->token_val.sym_ptr = &sym; this->token_type = sym.type; char* name = new char[MAX_NAME_SIZE]; strcpy(name, nameBuffer); this->name = std::make_optional(name); // 将标识符添加到 parser_token 中 this->add_idn_to_token(sym); goto OUT; } } # ifdef DEBUG printf("[Debug] next(): name: %s\n", nameBuffer); # endif // 如果未发现的话则需要构建符号 Symbol symbol; strcpy(symbol.name, nameBuffer); symbol.type = TokenType::Idn; symbol.value = 0.0; this->sy