语法分析

语法分析简介

语法分析的任务

语法分析是编译器继词法分析之后的一个重要步骤,主要任务是将输入的源代码转换为语法分析树或者抽象语法树,以便后续的语义分析,中间代码生成和优化等处理.

具体来说,语法分析的任务包括以下几个方面:

1. 识别输入的源代码中是否存在语法错误,即判断输入的源代码是否符合给定的文法规则.如果存在语法错误,语法分析器将报告相应的错误信息.
2. 将输入的源代码转换为语法分析树或者抽象语法树.语法分析树是一个表示源代码语法结构的树形结构,每个节点代表源代码中的一个语法成分,如语句,表达式,运算符等.抽象语法树则是一种去除冗余信息后的语法树,只保留程序的语义信息,用于后续的代码生成和优化.
3. 为每个节点附加语义信息,如数据类型,变量名,函数名等.这些信息将在后续的语义分析和代码生成中用到.
4. 生成错误信息和警告信息,以便提示开发者对源代码进行改正.

强大的语法分析生成器 bison

bison 是 flex 的亲密战友,它是一种强大的语法分析器生成器,可以根据用户提供的上下文无关文法生成相应的语法分析器.

bison 可以通过读取用户提供的语法规则,生成相应的语法分析器,从而将源代码转换为语法分析树或者抽象语法树,并对语法错误进行报告.

同时, bison 还提供了丰富的选项和功能,如语法冲突检查,语法错误处理,语法树的生成和遍历等,方便开发者进行灵活的配置和使用.

bison 的语法规则基于类似于 BNF 的范式,可以包含终结符和非终结符,以及相应的语义动作.它使用 LALR(1) 分析算法,能够高效地处理大规模的语法规则和输入流,同时还提供了一些高级特性,如词法和语法错误处理,优先级和关联性规则,语法树生成和遍历等.

使用 bison

手册1.8节提供了使用 bison 的一般步骤. 使用 bison 生成语法分析器的基本步骤与使用 flex 非常类似,具体步骤如下:

1. 编写语法规则文件,将要分析的程序语言语法描述出来
2. 使用 bison 编译语法规则文件,生成C文件
3. 编译链接这些C文件成一个二进制程序
4. 运行二进制程序,进行语法分析

下面以分析计算器的语法为例,说明一下这四个步骤:

1. 编写语法规则文件（通常使用扩展名为 .y 的文件）,定义计算器的语法规则.以下是一个简单的例子:

   %{
   #include <stdio.h>
   %}
   
   %token NUMBER
   %left '+' '-'
   %left '*' '/'
   %precedence UMINUS
   
   %%
   
   expression: NUMBER
             | expression '+' expression
             | expression '-' expression
             | expression '*' expression
             | expression '/' expression
             | '-' expression %prec UMINUS
             ;
   
   %%
   
   int main() {
     yyparse();
     return 0;
   }
   
   int yyerror(char const *msg) {
     fprintf(stderr, "Error: %s\n", msg);
     return 0;
   }
   
   int yywrap() {
     return 1;
   }
   

   其中,%{ 和 %} 之间的代码是在解析器中使用的C代码,%token 定义了词法分析器生成的符号类型,%left 和 %precedence 定义了运算符的优先级和结合性.%% 之间的是具体的语法规则,这里定义了 expression 表达式的语法规则,包括数字,加减乘除和取负操作.最后, main 函数调用 yyparse() 函数开始解析表达式, yyerror 和 yywrap 分别用于处理错误和结束解析器的工作.

   除了上述这个例子,手册中也给出了一个逆波兰表达式计算器的语法分析器示例,详见手册第2章.

2. 使用 bison 编译语法规则文件,生成解析器的源代码和头文件:

   $ bison -d calc.y
   

   以上命令会生成 calc.tab.c 和 calc.tab.h 两个文件.

3. 编写词法分析器,可以手写或使用词法分析器生成器（如 flex ）.

4. 编译词法分析器和解析器的源代码,生成可执行文件:

   $ gcc -o calc calc.tab.c lex.yy.c -lfl
   

   其中, calc.tab.c 和 lex.yy.c 分别是 Bison 和 Flex 生成的解析器和词法分析器的源代码.

5. 运行可执行文件,并输入表达式进行计算:

   $ ./calc
   

使用 bison 描述 CFG

使用 bison 描述 CFG 有一些细节需要注意:

1. 使用小写字母来表示非终结符,比如 expr, stmt 等,当然这只是一种约定.

2. 使用大写字母来表示终结符,比如 INTEGER, IF 等,当然这也是一种约定.另外, bison 中的终结符被称为 token kind .一个终结符代表了一门语言中的特定的关键字.

   error 由小写字母组成,但是是一个特殊的终结符.

3. 也可以使用类似C语言中的字符常量来表示一个终结符,比如 'c' 表示字符 c 是一个终结符.

4. 也可以使用类似C语言中的字符串常量来表示一个终结符,比如 "string" 表示字符串 string 是一个终结符.

一些形式化的概念

请参考龙书

上下文无关语法

上下文无关语法（ CFG, Context Free Grammer ）的精确定义就不在这里给出了,可以参考龙书 4.2 节.

既然有正则表达式,为什么又需要上下文无关语法？

正则表达式和上下文无关语法都是用于描述语言的形式化工具,但是它们的能力是不同的.

但是正则表达式只能描述正则语言,即只包含简单的模式匹配,字符类,重复等基本操作的语言.正则语言是一类较为简单的语言,可以用 DFA 或 NFA 进行识别和处理.

相比之下, CFG 可以描述更加复杂的语言,包括可以用递归方式定义的语言. CFG 可以描述上下文无关语言,即不受上下文限制的语言,因此可以描述更加复杂的语言结构,如递归结构,嵌套结构,条件语句等.

在编程语言等复杂语言的描述中,正则表达式通常不能描述所有语言特性.例如,在处理括号嵌套结构时,需要记录括号匹配的数量,这是一个上下文相关的问题,不能用正则表达式来描述.因此,需要使用CFG或者其他形式的文法来描述这种语言特性.

语法分析算法

本节并没有详细说明每种算法的步骤,只是概括说明语法分析的大概方法,并且举了几个例子.

自顶向下

自顶向下语法分析（Top-Down Parsing）是一种基于上下文无关文法的语法分析方法,它 从文法的起始符号开始 ,通过不断展开非终结符号,生成语法树,并最终判断输入是否符合文法规则.

最常见的自顶向下语法分析算法是递归下降分析（Recursive Descent Parsing）,该算法通过递归调用自身,从起始符号开始,向下展开非终结符号,同时进行语法匹配.

举个例子,我们有如下的文法:

<expr> ::= <term> '+' <term>
<term> ::= <factor> '*' <factor> | 'a'
<factor> ::= '(' <expr> ')' | 'b'

其中,符号 <expr> , <term> , <factor> 是非终结符号, + , * , ( , ) , a , b 是终结符号.起始符号是 <expr> .

现在,我们要对字符串 a+b*(a+b) 进行自顶向下语法分析.具体步骤如下:

1. 从起始符号<expr>开始,展开为<term> ‘+’ <term>
2. 从左侧的<term>开始展开,展开为<factor> ‘*’ <factor>
3. 从左侧的<factor>开始展开,展开为’a’
4. 匹配输入字符串的第一个字符a,匹配成功
5. 回到步骤2,从右侧的<factor>开始展开,展开为’(’ <expr> ‘)’
6. 匹配输入字符串的下一个字符+,匹配失败,回溯到步骤5
7. 从左侧的<expr>开始展开,展开为<term> ‘+’ <term>
8. 从左侧的<term>开始展开,展开为<factor> ‘*’ <factor>
9. 从左侧的<factor>开始展开,展开为’a’
10. 匹配输入字符串的下一个字符+,匹配失败,回溯到步骤8
11. 从右侧的<factor>开始展开,展开为’(’ <expr> ‘)’
12. 匹配输入字符串的下一个字符(,匹配成功
13. 回到步骤1,从左侧的<term>开始展开,展开为<factor> ‘*’ <factor>
14. 从左侧的<factor>开始展开,展开为’b’
15. 匹配输入字符串的下一个字符b,匹配成功
16. 匹配输入字符串的下一个字符),匹配成功
17. 匹配输入字符串的下一个字符*,匹配成功
18. 回到步骤2,从右侧的<factor>开始展开,展开为’(’ <expr> ‘)’
19. 从左侧的<expr>开始展开,展开为<term> ‘+’ <term>
20. 从左侧的<term>开始展开,展开为<factor> ‘*’ <factor>
21. 从左侧的<factor>开始展开,展开为’a’
22. 匹配输入字符串的下一个字符+,匹配失败,回溯到步骤20
23. 从右侧的<factor>开始展开,展开为’(’ <expr> ‘)’
24. 从左侧的<expr>开始展开,展开为<term> ‘+’ <term>
25. 从左侧的<term>开始展开,展开为<factor> ‘*’ <factor>
26. 从左侧的<factor>开始展开,展开为’b’
27. 匹配输入字符串的下一个字符b,匹配成功
28. 匹配输入字符串的下一个字符),匹配成功
29. 匹配输入字符串结束,语法匹配成功,生成语法树

可以看到,递归下降分析算法实际上就是对文法规则的一种直接翻译,算法简单直观,易于理解和实现.但是,它也存在一些缺点,如无法处理左递归的情况等问题,需要通过一些技巧进行处理.此外,对于一些复杂的文法规则,递归下降分析算法可能会因为回溯出现效率问题.

左递归

自顶向下语法分析器不难实现,但是如果存在 左递归 的产生式,语法分析程序会陷入死递归.

以下是一个左递归产生式的例子:

E -> E + T

其中, T 为终结符, E 为非终结符,如果递归的过程中不断进行最左推导,会导致递归无法返回.

左递归包含了 直接左递归 和 间接左递归, 以下是一个 间接左递归 的例子:

E -> F + T
F -> E - T

如果要通过自顶向下的方法进行语法分析,就要先通过算法消除语法中的左递归.具体细节请参考教科书.

自底向上

与自顶向下语法分析算法不同,自底向上语法分析算法从输入字符串的底部开始逐步向上构建语法分析树.

常见的自底向上语法分析算法包括 LR（Left-to-right Rightmost）分析算法和 LALR（Lookahead LR）分析算法.这里以 LR(1) 分析算法为例进行说明.

以文法规则为 E -> E + T | E * T | T 为例,考虑对输入字符串 “a + b * c” 进行语法分析.下面是 LR(1) 分析算法的执行过程:

1. 初始化状态栈,将初始状态 0 压入栈中
2. 读入输入字符串的第一个符号 a,查找状态 0 中是否有针对 a 的移进（shift）操作
3. 由于状态 0 中不存在针对 a 的移进操作,查找状态 0 中是否有针对 E 的规约（reduce）操作,即 E -> .E+T
4. 由于状态 0 中存在 E -> .E+T 的规约操作,执行规约操作,将栈顶的 3 个状态弹出,并将规约后的 E 符号压入状态栈中,得到状态 1
5. 查找状态 1 中是否有针对 + 的移进操作
6. 由于状态 1 中存在针对 + 的移进操作,执行移进操作,将状态 2 压入状态栈中,输入指针前移一位
7. 读入输入字符串的下一个符号 b,查找状态 2 中是否有针对 b 的移进操作
8. 由于状态 2 中存在针对 b 的移进操作,执行移进操作,将状态 3 压入状态栈中,输入指针前移一位
9. 读入输入字符串的下一个符号 *,查找状态 3 中是否有针对 * 的移进操作
10. 由于状态 3 中存在针对 * 的移进操作,执行移进操作,将状态 4 压入状态栈中,输入指针前移一位
11. 读入输入字符串的下一个符号 c,查找状态 4 中是否有针对 c 的移进操作
12. 由于状态 4 中存在针对 c 的移进操作,执行移进操作,将状态 5 压入状态栈中,输入指针前移一位
13. 读入输入字符串的下一个符号 $,查找状态 5 中是否有针对 $ 的移进操作
14. 由于状态 5 中不存在针对 $ 的移进操作,查找状态 5 中是否有针对 E 的规约操作,即 E -> T,同时将输入指针后退一位
15. 由于状态 5 中存在 E -> T 的规约操作,执行规约操作,将栈顶的 2 个状态弹出,并将规约后的 E 符号压入状态栈中,得到状态 6
16. 查找状态 6 中是否有针对 + 的移进操作
17. 由于状态 6 中不存在针对 + 的移进操作,查找状态 6 中是否有针对 E 的规约操作,即 E -> E+T
18. 由于状态 6 中存在 E -> E+T 的规约操作,执行规约操作,将栈顶的 3 个状态弹出,并将规约后的 E 符号压入状态栈中,得到状态 7
19. 查找状态 7 中是否有针对 $ 的移进操作
20. 由于状态 7 中存在针对 $ 的移进操作,执行移进操作,将状态 8 压入状态栈中,输入指针前移一位
21. 读入输入字符串的下一个符号结束符,查找状态 8 中是否有针对结束符的移进操作
22. 由于状态 8 中不存在针对结束符的移进操作,查找状态 8 中是否有针对 E 的规约操作,即 E -> E+T,同时将输入指针后退一位
23. 由于状态 8 中存在 E -> E+T 的规约操作,执行规约操作,将栈顶的 3 个状态弹出,并将规约后的 E 符号压入状态栈中,得到状态 9
24. 查找状态 9 中是否有针对 $ 的移进操作
25. 由于状态 9 中不存在针对 $ 的移进操作,查找状态 9 中是否有针对 E 的规约操作,即 E -> E+T,同时将输入指针后退一位
26. 由于状态 9 中存在 E -> T 的规约操作,执行规约操作,将栈顶的 2 个状态弹出,并将规约后的 E 符号压入状态栈中,得到状态 10
27. 查找状态 10 中是否有针对 $ 的移进操作
28. 由于状态 10 中存在针对 $ 的移进操作,执行移进操作,将状态 11 压入状态栈中,输入指针前移一位
29. 读入输入字符串的下一个符号结束符,查找状态 11 中是否有针对结束符的移进操作
30. 由于状态 11 中存在针对结束符的移进操作,分析结束

在以上过程中,状态栈的变化情况如下表所示:

从上表中可以看出,自底向上语法分析的过程中,状态栈和符号栈的元素随着分析过程的不断推进和弹出而不断变化.在分析到输入字符串的末尾时,如果状态栈中只有一个状态,且这个状态为文法的起始符号,那么说明分析成功.如果状态栈中不止一个状态,或者起始符号不在栈顶,那么说明分析失败,输入字符串不符合文法.

自底向上语法分析的优点在于可以处理任意上下文无关文法,并且可以处理左递归的文法.而且,由于自底向上语法分析是从输入的最后一个符号开始分析,因此不需要像自顶向下语法分析那样需要将所有可能的推导路径都尝试一遍.这样,在一些复杂的文法中,自底向上语法分析的效率会更高一些.

但是自底向上语法分析在运行过程中需要使用更多的内存来维护状态栈和符号栈,而且需要进行大量的状态转换,因此在一些简单的文法中,可能比自顶向下语法分析效率更低.此外,自底向上语法分析的输出也比较晦涩,很难直观地展示出语法分析树的结构.

TODO 语法分析算法细节

自顶向下 or 自低向上？

在选择自顶向下语法分析还是自底向上语法分析时,需要考虑到所处理的文法的复杂程度和所需的分析效率.

对于简单的文法,自顶向下语法分析可能比较容易实现,并且分析速度比较快.自顶向下语法分析是从文法的起始符号开始推导,可以根据输入符号的类型和文法规则来选择合适的推导路径,因此比较灵活.

而对于复杂的文法,特别是包含左递归和二义性的文法,自顶向下语法分析可能会出现回溯和死循环的情况,分析效率较低.此时,使用自底向上语法分析可能更为合适.自底向上语法分析是从输入符号开始,逐步合并符号并匹配到文法规则,因此可以处理任意上下文无关文法,并且能够处理左递归的文法.自底向上语法分析的效率可能比较低,但是对于复杂的文法,它是一种有效的分析方法.

总而言之,在选择语法分析方法时,需要根据具体的文法和应用场景来进行选择,综合考虑分析效率,分析复杂度和分析输出的易读性等因素.

bison 采用自底向上的分析算法

bison 内部使用的语法分析算法基于 LR 文法分析算法,其中的 L 表示从左到右扫描输入, R 表示使用最右派推导.

bison 支持多种不同的 LR 文法分析算法,包括 SLR , LALR 和 LR1 等.在解析过程中, Bison 使用 LALR 分析器生成分析表,并使用状态机进行语法分析.