Bison与Yacc：语法分析器生成指南

本教程是关于词法分析器和语法分析器生成器的学习资料，主要讲解了PowerPoint演示中的Bison（GNU版的Yacc）在编译原理中的应用。Bison是一种用于生成LALR(1)语法分析器的工具，它依据巴科斯-诺尔格式（BNF）来设计编程语言的语法。 首先，Bison（或其传统后缀为.y的源文件）的作用是根据编程语言的规则生成相应的解析器。用户需要编写一个`.y`文件，即Yacc源代码，其中定义了语言的文法规则，以及与之相关的C语言动作。Yacc的使用流程包括： 1. 编写`.y`语法文件：这部分描述了语言的句法结构，使用BNF来表示非终结符和终结符，以及它们如何组合形成有效的表达式。例如，对于一个简单的表达式解析器，规则可能涉及加法和乘法运算符。 2. 创建词法分析器（如使用Lex或自定义`yylex()`函数）：这个阶段处理输入流，将输入分割成有意义的词法单元（tokens），并将其传递给解析器。 3. 定义解析函数`yyparse()`的调用：这是解析过程的入口点，通过此函数，Yacc驱动解析器执行文法规则。 4. 错误处理：编写适当的错误处理例程，如`yyerror()`，用于处理解析过程中的错误情况。 5. 配合词法分析器编译：使用Bison编译器`bison`，配合`.y`文件和可能的`.l`或`.ll`（LEX/Lexer）的词法分析器文件，生成目标文件（如`.tab.c`和`.tab.h`）和可执行文件。 在Bison的源程序中，规则部分通常包含%{}区，用于放置C语言声明，而%%符号开始和结束文法规则及翻译规则的定义。例如，对于一个简单的算术表达式解析器，规则如`E:E+T|T`表示表达式可以通过加上一个术语或者直接是一个术语来构成。每个规则的右侧都包含了对应的语义动作，使用$$和$i$引用非终结符和终结符的属性值。 示例中提到的`%token DIGIT`表示识别数字这一终结符，而实际的翻译规则部分则展示了如何处理运算符和数字，如`expr:expr '+' term {$$ = $1 + $3;}`，这意味着遇到"+"运算符时，将两个表达式的值相加并赋值给结果。 本教程涵盖了词法分析和语法分析的基础概念，以及如何使用Bison工具生成自定义语言的解析器，这对于理解和实现编译器和语言处理系统至关重要。