asp网站制作免费模板下载,重庆企业网站优化,广告公司主要做什么,做网赌网站得多少钱SQL 语句解析过程详解#xff1a; 1#xff0e;输入SQL语句
2#xff0e;词法分析------flex 使用词法分析器#xff08;由Flex生成#xff09;将 SQL 语句分解为一个个单词#xff0c;这些单词被称为“标记“。标记包括关键字、标识符、运算符、分隔符等。
2.1 flex 原… SQL 语句解析过程详解 1输入SQL语句
2词法分析------flex 使用词法分析器由Flex生成将 SQL 语句分解为一个个单词这些单词被称为“标记“。标记包括关键字、标识符、运算符、分隔符等。
2.1 flex 原理
1、使用 flex 工具定义正则表达式规则来匹配不同类型的词法单元例如可以定义以下规则
匹配关键字SELECT、FROM、WHERE、HAVING等。匹配标识符由字母或下划线开头后跟字母、数字或下划线组成。匹配运算符比如、、、、等。匹配常量包括整数、浮点数、字符串等。
2、生成词法分析器代码根据定义的词法规则使用Flex工具生成对应的词法分析器代码
3、输入查询字符串将要解析的查询字符串作为输入提供给同法分析器
4、扫描和匹配词法分析器从输入字符串中逐个读取字符并尝试将其与定义的词法规则进行匹配
5、生成词法单元当词法分析器匹配到一个词法规则时它会生成相应的词法单元并返回给语法分析器。每个词法单元通常包含两部分信息
词法单元类型(token type)表示该词法单元的种类比如关键字、标识符、运算符等词法单元值(tokenvalue)表示该词法单元具体的取值
6、继续扫描词法分析器会持续从输入字符串中读取字符并重复步骤4和步骤5直到整个查询字符串被完全解析为一系列词法单元
7、返回词法单元序列当整个查询字符串都被解析后词法分析器将返回一个包含所有词法单元的序列给语法分析器供后续的语法分析处理
2.2 flex 文件代码结构
2.2.1 flex 文件介绍
1、flex文件代码
%option noyywrap
%{
definition
%}%%
rules
%%
Code1%option 指定 flex 扫描时的一些特性。yywrap 通常在多文件扫描时定义使用。常用的一些选项有
Noyywrap告诉flex不使用yywrap函数yylineno会告诉flex生成一个名为yylineno的整型变量来保存当前的行号case-insensitive 正则表达式规则大小写无关
2definitio部分为定义部分包括引入头文件变量声明函数声明注释等这部分会被原样拷贝到输出的.c文件中。
3rules部分定义词法规则使用正则表达式定义词法后面{}内则是扫描到对应词法时的动作代码“|”是一个特殊符号表示下一个模式应用相同的动作正则表达式后面不指定动作则相应的模式会被忽略。
4code部分为C语言的代码。yylex为flex的函数使用yylex开始扫描。
2.2.2 flex 文件常用变量
1yytext词法分析程序当前识别到的一些词素与转换规则部分中的某个模式相匹配
2yylength词法分析程序当前识别到的词素的长度
3yylvalyylval是在bison中定义的联合类型变量union因为Flex生成的词法分析程序yylex()需要向bison生成的语法分析器返回识别到的词法单元所以需要使用yylval来保存词法单元的属性值
2.2.3 正则表达式
. 匹配除换行符”\n”以外的任何单个字符* 匹配前面表达式的零个或多个拷贝[] 匹配括号中任意字符的字符类如果第一个字符是 “^”则匹配除括号中的字符以外的任意字符“-” 指示一个字符范围例如“[0-9]”和“[0123456789]”含义相同除了以 “\” 开始的转义序列元字符在括号内没有任何含义^ 作为正则表达式的行首匹配行的开头也用于方括号中的否定$ 作为正则表达式的行尾匹配行的结尾\ 用于转义元字符也作为常用的C转义序列的一部分例如”\n”表示换行“\*” 表示非元字符的星号 匹配前面的正则表达式一次或多次出现 匹配前面的正则表达式零次或一次出现| 匹配前面的正则表达式或随后的正则表达式“…” 引号中的每个字符解释为字面意义除C转义序列外元字符会失去其特殊含义() 将一系列正则表达式组成一个新的正则表达式例如(01)表示字符序列 01{} 当括号中包含一个或两个数字时指示前面的模式允许被匹配多少次例如{13}表示匹配字母一次到三次
2.2.4 flex 文件具体案例
1、创建一个名为 lexer.l 的文件其中包含词法规则
%{
#include stdio.h
%}%%
SELECT { printf(Keyword: SELECT\n); }
FROM { printf(Keyword: FROM\n); }
WHERE { printf(Keyword: WHERE\n); }
AND { printf(Keyword: AND\n); }
OR { printf(Keyword: OR\n); }[0-9] { printf(Number: %s\n yytext); }[A-Za-z_][A-Za-z0-9_]* { printf(Identifier: %s\n yytext); }
[] { printf(Operator: %s\n yytext); }
[ \t\n] ; // Skip whitespace. { printf(Unknown: %s\nyytext); }%%int main() { yylex(); return 0;
}2、使用 flex 命令编译 lexer.l 文件生成词法分析器代码
1执行下列语句生成词法分析器代码
flex lexer.l
2词法分析器生成结果
lex.yy.c
3编译生成的词法分析器代码生成可执行文件
gcc -o lexer lex.yy.c -lfl
4运行可执行文件并输入一些算术表达式进行测试
./lexer输入SELECT * FROM table;
5执行结果如下 说明
-ll 这是旧版本的Flex生成器例如Flex 2.5.4的链接选项。它指示链接器将使用名为 libl.a 或 libl.so 的库文件。在以前的版本中Flex生成的词法分析器的默认名称是 lex.yy.c而库文件的名称以 l 开头因此使用 -ll 是一种传统的方式。-lg 这是新版本的Flex生成器例如Flex 2.5.35的链接选项。类似于旧版本的 -ll它指示链接器使用名为 libg.a 或 libg.so 的库文件。这种新方式是为了避免与其他工具和库发生命名冲突。-lfl 这是一个与Flex生成的词法分析器库相关的选项。-lfl 表示链接器将使用名为 libfl.a 或 libfl.so 的库文件。这个库包含了Flex所需的运行时支持函数。
注意 如果 flex 词法分析器对 .l 进行编译时报错: /opt/h/devtoolset-11/root/usr/ibexec/gcex86.64-redhat-linux/11/ld: cannot find -lfn
解决方案 该错误表明链接器无法找到名为 -if 的库文件。这通常是因为在您的系统上缺少libfl库或者库文件的路径未正确配置。要解决这个问题您可以尝试以下步骤
1、确认库是否已安装:首先请确保您的系统上已安装了libfl库。您可以尝试使用包管理器来安装它。在基于Red Hat的系统中您可能需要执行类似于以下的命令:
yum install flex-devel
2、检查库文件路径:如果库已安装但链接器仍然找不到它可能是因为库文件的路径未正确配置。您可以尝试手动指定库文件的路径。例如假设libfl库文件位于/usr/lib64目录下您可以使用以下方式链接
gcc -o my program lex.yy.c -L/usr/lib64 -1f1
3、更新库文件缓存:如果您最近安装了libfl库但链接器仍然找不到它您可能需要更新库文件缓存。运行以下命令以更新库文件缓存
sudo ldconfig
3语法分析------bison 使用语法分析器由 Bison 生成根据语法规则进行语法分析生成抽象语法树。语法树是一种树形结构它表示 SQL 语句的语法结构。语法分析器会检查语法树是否符合 SQL 语法规则如果不符合则会抛出语法错误。
3.1 bison原理 3.2 bison文件代码结构
1、bison文件代码
%{
// C 代码和头文件的声明
#include stdio.h
// 在这里可以定义全局变量和函数等
%}
// Bison 的选项部分
%option verbose // 控制 Bison 解析器的详细输出// Bison 的声明部分
%token NAME // 定义终结符或标记的名称
%token NUMBER%left ‘’ ‘-‘ // 定义运算符的优先级和结合性
%left ‘*’ ‘/’%{
// 在这里可以编写更多的 C 代码
%}// Bison 的规则部分%%
// 语法规则的定义
expression : expression expression | expression - expression | expression * expression | expression / expression | ( expression ) | NUMBER ;
// 更多的语法规则...
%%// C 代码部分选项中的 %{ ... %} 和规则部分中的 %% 之间的部分
// 在这里可以编写与语法规则相关的 C 代码
int main() { yyparse(); // 调用 Bison 生成的解析函数 return 0;
}bison文件的书写格式与flex文件的书写格式基本一致只是规则的定义语法不同。
3.3 规则语法介绍
1终结符Terminals 终结符是语法规则中的基本符号通常是语言中的关键字、运算符、标识符等。可以使用%token来定义终结符。以下是一个示例
%token NUMBER
%token PLUS MINUS TIMES DIVIDE
%token IDENTIFIER
%token SEMICOLON 在这个示例中我们定义了几个终结符包括数字NUMBER、加号PLUS、减号MINUS、乘号TIMES、除号DIVIDE、标识符IDENTIFIER和分号SEMICOLON等。终结符是语法规则中的基本符号代表语言中的最小单元或词汇元素。终结符在语法分析的过程中与输入字符串的实际内容进行匹配帮助构建解析树或语法分析树。在 Bison 文件中终结符通常以大写字母或使用引号括起来的字符串表示。
2非终结符Non-terminals 非终结符表示语法规则中的抽象结构可以由其他非终结符和/或终结符组成。您可以使用 %type 来定义非终结符的类型。以下是一个示例
%type expr expression%type term term%type factor factor 在这个示例中我们定义了三个非终结符 expression、term 和 factor并指定了它们的类型。这些类型标记可以在产生式的操作部分使用以便对解析树节点进行更复杂的操作。非终结符在语法分析树中代表了一些更高级的结构可以用来执行语义操作、构建解析树并帮助描述语言的抽象语法结构。在 Bison 文件中非终结符通常以小写字母开头。 终结符和非终结符在 Bison 文件中共同定义了语法规则帮助我们描述和分析特定编程语言或语言的一部分。终结符代表了实际的词法单元而非终结符则代表了更高层次的语法结构。通过将终结符和非终结符组合起来我们可以创建复杂的语法规则用于生成和解析语言的有效字符串。
3“文法” “文法”是一组规则用于描述编程语言或语言的语法结构。这些规则定义了语言的句法syntax即哪些组合是有效的、合法的语句和表达式以及它们如何组合在一起。文法规则使用产生式productions的形式来表示其中包含终结符terminals和非终结符non-terminals的组合。 文法规则在 Bison 文件中是使用 BNF巴科斯-诺尔范式或 EBNF扩展巴科斯-诺尔范式的形式表示的。BNF 是一种形式化的表示方法用于定义上下文无关文法Context-Free Grammar这些文法用于指定编程语言的语法规则。
expression : expression term| expression - term| term;
4 %start %start 指令用于指定文法的起始非终结符。起始非终结符是语法分析的入口点也就是从哪个语法规则开始构建解析树或语法分析树。
%start program%%statements : statement| statements statement;statement : assignment| if_statement| while_statement| /* ... other statement types ... */ ; %start program 指定了起始非终结符为 program。这意味着语法分析将从 program 规则开始逐步展开其他非终结符最终构建解析树。在实际语法规则中起始非终结符的选择取决于您想要分析的语言的语法结构。
5$ 在语法规则中$ 用于引用当前产生式的右侧的符号或值。例如在产生式的右侧$1 表示该产生式右侧的第一个元素终结符或非终结符$2表示第二个元素依此类推。这些引用用于将产生式右侧的值传递给产生式左侧。注意生产式的起始下标为1。
6$$ 在语法规则中$$ 用于引用当前产生式的结果。当 Bison 解析器完成一个产生式的分析并计算出其结果时该结果会被赋值给 $$。这通常用于构建解析树的节点或为更高层次的语法规则提供结果。
7| | 用于表示多个产生式之间的选择。它在上下文无关文法中用于定义非终结符的不同产生式形式。每个产生式通过竖线分隔表示它们是该非终结符的可能形式之一。
3.4 bison文件具体案例
1、创建一个名为parser.l的文件其中包含词法规则
%{
#include stdio.h
#include stdlib.h
%}//定义终结符
%token SELECT INSERT UPDATE DELETE FROM WHERE
%token INTO VALUES SET
%token ID INT STRING%%//定义规则statement: SELECT columns FROM table WHERE condition ;| INSERT INTO table ( columns ) VALUES ( values ) ;| UPDATE table SET assignments WHERE condition ;| DELETE FROM table WHERE condition ;;columns: ID| columns ID;table: ID;assignments: ID value| assignments ID value;values: value| values value;value: INT| STRING;condition: ID value;%%int main() {yyparse();return 0;
}int yyerror(const char *s) {printf(Error: %s\n s);return 0;
}2、使用 bison 命令编译 lexer.l 文件
bison -d parser.y 这将生成 parser.tab.c 和 parser.tab.h 两个文件。接下来你可以将这些文件与你的编译器项目一起编译并链接到你的代码中。 3.5 抽象语法树AST
AST构建步骤
1、从前缀表达式构建函数关系表里获取当前Token的构建函数调用该函数构建出一个前缀表达式
2、查看下一个Token的优先级如果下一个Token的优先级比当前Token的优先级更高则说明这可能是一个中缀表达式或后缀表达式
3、如果是中缀表达式则从中缀表达式构建函数关系表里获取下一个Token的构建函数调用该函数构建出一个中缀表达式
4、如果是后缀表达式则从后缀表达式构建函数关系表里获取下一个Token的构建函数调用该函数构建出一个后缀表达式
5、通过递归方式将这些表达式建立起父子关系最终形成一个抽象语法树。
4语义分析 在语法分析的基础上对生成的抽象语法树进行语义分析。语义分析器会检查SQL语句是否符合数据库的语义规则例如表是否存在、列是否存在、数据类型是否匹配等。如果不符合则会抛出语义错误。
5优化器 在语义分析的基础上进行优化。优化器会对SQL语句进行优化以提高查询效率。优化器会选择最优的执行计划包括选择最优的索引、选择最优的连接方式等。
6执行计划生成器 在优化器的基础上生成执行计划。执行计划是一组计算机指令用于执行SQL语句。执行计划包括访问表、过滤数据、排序数据等操作。
7执行计划执行器 执行计划执行器会按照执行计划执行SQL语句。执行计划执行器会访问表、过滤数据、排序数据等操作最终返回查询结果。
8结果集返回 执行计划执行器会将查询结果返回给客户端。查询结果可以是一张表、一组记录或一个标量值。
9清理 在查询结束后数据库管理系统会清理执行计划、释放资源等。 未完writing……
