第91集：二义性文法的处理
学习目标
- 理解二义性文法的概念和特点
- 掌握优先级声明的使用方法
- 学习结合性声明的使用方法
- 理解
%left、%right、%nonassoc声明的作用 - 通过实际案例学习二义性文法的处理
- 了解二义性文法在编译器中的处理方法
- 掌握二义性文法处理的最佳实践
一、二义性文法的概念
1. 什么是二义性文法？
二义性文法是指存在至少一个句子有两种或两种以上不同的最左推导（或最右推导）的文法。换句话说，二义性文法可以为同一个句子生成多个不同的语法树。
2. 二义性文法的例子
最经典的二义性文法例子是算术表达式文法：
expr → expr + expr
| expr * expr
| ( expr )
| number对于句子 1 + 2 * 3，这个文法可以生成两种不同的语法树：
- 加法先于乘法：
(1 + 2) * 3 - 乘法先于加法：
1 + (2 * 3)
3. 二义性文法的问题
二义性文法会导致以下问题：
- 语法分析歧义：语法分析器无法确定使用哪种推导方式
- 语义不确定：同一个句子可能有不同的语义解释
- 编译结果不一致：可能导致编译结果不一致
- 错误处理困难：二义性会使错误处理更加困难
4. 二义性文法的判断
判断一个文法是否是二义性的是一个不可判定问题，即不存在一个算法可以在有限时间内判断任意一个文法是否是二义性的。但是，对于一些常见的二义性模式，我们可以通过经验来识别和处理。
二、优先级声明
1. 为什么需要优先级声明？
当文法中存在二义性时，我们需要通过优先级声明来消除二义性。例如，在算术表达式文法中，我们需要指定乘法的优先级高于加法，以消除二义性。
2. 优先级声明的语法
在 Yacc/Bison 中，优先级声明的语法为：
%left 终结符1 终结符2 ... /* 左结合，优先级较低 */
%left 终结符3 终结符4 ... /* 左结合，优先级较高 */
%right 终结符5 终结符6 ... /* 右结合，优先级更高 */
%nonassoc 终结符7 终结符8 ... /* 不可结合，优先级最高 */3. 优先级的顺序
在 Yacc/Bison 中，后面声明的优先级高于前面的。例如：
%left PLUS MINUS /* 优先级较低 */
%left TIMES DIVIDE /* 优先级较高 */
%right UMINUS /* 优先级最高 */这里的优先级顺序是：UMINUS > TIMES/DIVIDE > PLUS/MINUS
4. 优先级声明的作用
优先级声明的作用是：
- 消除移进-归约冲突：当分析器遇到移进-归约冲突时，根据优先级决定是移进还是归约
- 指定运算顺序：为运算符指定计算顺序，如乘法先于加法
- 提高文法可读性：优先级声明使文法更加清晰易读
三、结合性声明
1. 为什么需要结合性声明？
结合性声明用于指定相同优先级运算符的结合方向，以消除二义性。例如，对于表达式 a - b - c，我们需要指定减法是左结合的，即 (a - b) - c，而不是右结合的 a - (b - c)。
2. 结合性声明的类型
Yacc/Bison 支持三种结合性声明：
- **
%left**：左结合，如a + b + c解析为(a + b) + c - **
%right**：右结合，如a = b = c解析为a = (b = c) - **
%nonassoc**：不可结合，如a < b < c是不允许的
3. 结合性声明的作用
结合性声明的作用是：
- 消除移进-归约冲突：当分析器遇到相同优先级运算符的移进-归约冲突时，根据结合性决定是移进还是归约
- 指定计算顺序：为相同优先级运算符指定计算顺序
- 避免无效表达式：使用
%nonassoc可以避免无效的表达式，如a < b < c
四、%left、%right、%nonassoc 声明的使用
1. %left 声明
%left 声明用于指定左结合运算符。左结合意味着相同优先级的运算符从左到右计算。
例如：
%left PLUS MINUS
/* 表达式 a - b - c 解析为 (a - b) - c */
expr : expr MINUS expr { $$ = $1 - $3; }
;2. %right 声明
%right 声明用于指定右结合运算符。右结合意味着相同优先级的运算符从右到左计算。
例如：
%right ASSIGN
/* 表达式 a = b = c 解析为 a = (b = c) */
expr : expr ASSIGN expr { $$ = $3; }
;3. %nonassoc 声明
%nonassoc 声明用于指定不可结合运算符。不可结合意味着相同优先级的运算符不能连续使用。
例如：
%nonassoc LT GT EQ NEQ
/* 表达式 a < b < c 会被拒绝 */
expr : expr LT expr { $$ = $1 < $3; }
;五、二义性文法的处理案例
案例1：算术表达式文法
1. 原始二义性文法
expr : expr PLUS expr
| expr MINUS expr
| expr TIMES expr
| expr DIVIDE expr
| LPAREN expr RPAREN
| NUMBER
;这个文法是二义性的，因为对于表达式 1 + 2 * 3 有两种不同的解析方式。
2. 使用优先级和结合性声明消除二义性
/* 优先级和结合性声明 */
%left PLUS MINUS /* 左结合，优先级较低 */
%left TIMES DIVIDE /* 左结合，优先级较高 */
%right UMINUS /* 右结合，优先级最高 */
/* 消除二义性后的文法 */
expr : expr PLUS expr { $$ = $1 + $3; }
| expr MINUS expr { $$ = $1 - $3; }
| expr TIMES expr { $$ = $1 * $3; }
| expr DIVIDE expr { $$ = $1 / $3; }
| MINUS expr %prec UMINUS { $$ = -$2; }
| LPAREN expr RPAREN { $$ = $2; }
| NUMBER { $$ = $1; }
;案例2：if-else 语句文法
1. 原始二义性文法
stmt : IF expr THEN stmt
| IF expr THEN stmt ELSE stmt
| other_stmt
;这个文法是二义性的，因为对于句子 if e1 then if e2 then s1 else s2，有两种不同的解析方式：
- else 匹配第一个 if：
if e1 then (if e2 then s1 else s2) - else 匹配第二个 if：
if e1 then (if e2 then s1) else s2
2. 使用结合性声明消除二义性
/* 结合性声明 */
%nonassoc THEN
%nonassoc ELSE
/* 消除二义性后的文法 */
stmt : IF expr THEN stmt
| IF expr THEN stmt ELSE stmt
| other_stmt
;由于 ELSE 的优先级高于 THEN，所以 else 会匹配最近的 then，即第二种解析方式。
案例3：赋值表达式文法
1. 原始二义性文法
expr : expr ASSIGN expr
| expr PLUS expr
| NUMBER
;这个文法是二义性的，因为对于表达式 a = b + c，有两种不同的解析方式：
- 赋值先于加法：
(a = b) + c - 加法先于赋值：
a = (b + c)
2. 使用优先级和结合性声明消除二义性
/* 优先级和结合性声明 */
%left PLUS /* 左结合，优先级较低 */
%right ASSIGN /* 右结合，优先级较高 */
/* 消除二义性后的文法 */
expr : expr ASSIGN expr { $$ = $3; }
| expr PLUS expr { $$ = $1 + $3; }
| NUMBER { $$ = $1; }
;六、二义性文法在编译器中的处理方法
1. 重写文法消除二义性
最直接的方法是重写文法，使其成为无歧义文法。例如，对于算术表达式文法，我们可以重写为：
expr : expr PLUS term
| expr MINUS term
| term
;
term : term TIMES factor
| term DIVIDE factor
| factor
;
factor : NUMBER
| LPAREN expr RPAREN
;这种方法通过引入不同优先级的非终结符来消除二义性，但是会使文法变得更加复杂。
2. 使用优先级和结合性声明
在 Yacc/Bison 中，我们可以使用优先级和结合性声明来消除二义性，而不需要重写文法。这种方法更加简洁，易于理解和维护。
3. 二义性文法的优势
虽然二义性文法会导致歧义，但是在某些情况下，使用二义性文法并通过优先级和结合性声明来消除二义性，比使用无歧义文法更加简洁和易于理解。
例如，对于算术表达式，使用二义性文法并通过优先级声明来指定运算符的优先级，比使用分层的无歧义文法更加直观。
七、二义性文法处理的最佳实践
1. 文法设计的最佳实践
- 合理使用二义性：对于一些常见的结构（如算术表达式、if-else 语句），可以使用二义性文法并通过优先级和结合性声明来消除二义性
- 保持简洁：使用二义性文法可以使文法更加简洁，易于理解
- 明确优先级：为所有运算符明确指定优先级和结合性
- 测试覆盖：确保测试覆盖各种优先级和结合性的情况
2. 优先级和结合性声明的最佳实践
- 顺序正确：按照优先级从低到高的顺序声明
- 分组合理：将相同优先级的运算符放在一起声明
- 结合性适当：为每个优先级组指定适当的结合性
- **使用
%nonassoc**：对于不应该连续使用的运算符，使用%nonassoc声明
3. 错误处理的最佳实践
- 提供清晰的错误消息：当用户使用了不可结合的运算符连续使用时，提供清晰的错误消息
- 检测常见错误：检测常见的优先级和结合性错误
- 提供修复建议：对于优先级和结合性错误，提供可能的修复建议
八、自测问题
选择题：以下哪种声明用于指定左结合运算符？
A.%left
B.%right
C.%nonassoc
D.%prec选择题：在 Yacc/Bison 中，优先级声明的顺序是：
A. 前面的优先级高于后面的
B. 后面的优先级高于前面的
C. 所有声明的优先级相同
D. 优先级由声明的位置决定简答题：什么是二义性文法？举例说明。
简答题：如何使用优先级和结合性声明来消除二义性？
实践题：使用 Yacc/Bison 编写一个支持算术表达式、赋值语句和 if-else 语句的简单编译器，使用优先级和结合性声明来消除二义性。
九、小结
本集详细介绍了二义性文法的处理，包括：
- 二义性文法的概念：二义性文法的定义、例子和问题
- 优先级声明：优先级声明的语法和作用
- 结合性声明：结合性声明的类型和作用
%left、%right、%nonassoc声明：这些声明的使用方法- 二义性文法的处理案例：算术表达式、if-else 语句、赋值表达式
- 二义性文法在编译器中的处理方法：重写文法、使用优先级和结合性声明
- 二义性文法处理的最佳实践：文法设计、优先级和结合性声明、错误处理
二义性文法是编译原理中的一个重要概念，虽然它会导致歧义，但是通过合理使用优先级和结合性声明，我们可以有效地消除二义性，同时保持文法的简洁性和可读性。在实际编译器设计中，我们常常使用二义性文法并通过优先级和结合性声明来处理，以提高编译器的开发效率和可维护性。
十、下集预告
下一集我们将学习语法分析器生成器原理，探讨语法分析器生成器（如 Yacc/Bison）的工作原理，包括 LALR(1) 表生成、冲突解决、代码生成等内容。
参考资料
- 《编译原理》（龙书）- Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman
- 《现代编译原理》（虎书）- Andrew W. Appel
- 《编译器设计》- Keith D. Cooper, Linda Torczon
- Yacc/Bison 用户手册
- 二义性文法相关文档和教程
通过本集的学习，你应该对二义性文法的处理有了全面的了解。二义性文法虽然会导致歧义，但是通过合理使用优先级和结合性声明，我们可以有效地消除二义性，同时保持文法的简洁性和可读性。在后续的学习中，我们将继续探讨语法分析器生成器的工作原理，进一步加深对编译原理的理解。