6.6 处理二义文法

上面例子中，对表达式的文法描述用一种特别的形式规避了二义文法。然而，在很多情况下，这样的特殊文法很难写，或者很别扭。一个更为自然和舒服的语法表达应该是这样的： ~~~ expression : expression PLUS expression | expression MINUS expression | expression TIMES expression | expression DIVIDE expression | LPAREN expression RPAREN | NUMBER ~~~ 不幸的是，这样的文法是存在二义性的。举个例子，如果你要解析字符串”3 * 4 + 5”，操作符如何分组并没有指明，究竟是表示”(3 * 4) + 5”还是”3 * (4 + 5)”呢？ 如果在yacc.py中存在二义文法，会输出”移进归约冲突”或者”归约归约冲突”。在分析器无法确定是将下一个符号移进栈还是将当前栈中的符号归约时会产生移进归约冲突。例如，对于”3 * 4 + 5”，分析器内部栈是这样工作的： ~~~ Step Symbol Stack Input Tokens Action ---- --------------------- --------------------- ------------------------------- 1 $ 3 * 4 + 5$ Shift 3 2 $ 3 * 4 + 5$ Reduce : expression : NUMBER 3 $ expr * 4 + 5$ Shift * 4 $ expr * 4 + 5$ Shift 4 5 $ expr * 4 + 5$ Reduce: expression : NUMBER 6 $ expr * expr + 5$ SHIFT/REDUCE CONFLICT ???? ~~~ 在这个例子中，当分析器来到第6步的时候，有两种选择：一是按照expr : expr * expr归约，一是将标记’+’继续移进栈。两种选择对于上面的上下文无关文法而言都是合法的。 默认情况下，所有的移进归约冲突会倾向于使用移进来处理。因此，对于上面的例子，分析器总是会将’+’进栈，而不是做归约。虽然在很多情况下，这个策略是合适的（像”if-then”和”if-then-else”），但这对于算术表达式是不够的。事实上，对于上面的例子，将’+’进栈是完全错误的，应当先将expr * expr归约，因为乘法的优先级要高于加法。 为了解决二义文法，尤其是对表达式文法，yacc.py允许为标记单独指定优先级和结合性。需要像下面这样增加一个precedence变量： ~~~ precedence = ( ('left', 'PLUS', 'MINUS'), ('left', 'TIMES', 'DIVIDE'), ) ~~~ 这样的定义说明PLUS/MINUS标记具有相同的优先级和左结合性，TIMES/DIVIDE具有相同的优先级和左结合性。在precedence声明中，标记的优先级从低到高。因此，这个声明表明TIMES/DIVIDE（他们较晚加入precedence）的优先级高于PLUS/MINUS。 由于为标记添加了数字表示的优先级和结合性的属性，所以，对于上面的例子，将会得到： ~~~ PLUS : level = 1, assoc = 'left' MINUS : level = 1, assoc = 'left' TIMES : level = 2, assoc = 'left' DIVIDE : level = 2, assoc = 'left' ~~~ 随后这些值被附加到语法规则的优先级和结合性属性上，这些值由最右边的终结符的优先级和结合性决定： ~~~ expression : expression PLUS expression # level = 1, left | expression MINUS expression # level = 1, left | expression TIMES expression # level = 2, left | expression DIVIDE expression # level = 2, left | LPAREN expression RPAREN # level = None (not specified) | NUMBER # level = None (not specified) ~~~ 当出现移进归约冲突时，分析器生成器根据下面的规则解决二义文法： 1. 如果当前的标记的优先级高于栈顶规则的优先级，移进当前标记 2. 如果栈顶规则的优先级更高，进行归约 3. 如果当前的标记与栈顶规则的优先级相同，如果标记是左结合的，则归约，否则，如果是右结合的则移进 4. 如果没有优先级可以参考，默认对于移进归约冲突执行移进 比如，当解析到”expression PLUS expression”这个语法时，下一个标记是TIMES，此时将执行移进，因为TIMES具有比PLUS更高的优先级；当解析到”expression TIMES expression”，下一个标记是PLUS，此时将执行归约，因为PLUS的优先级低于TIMES。 如果在使用前三种技术解决已经归约冲突后，yacc.py将不会报告语法中的冲突或者错误（不过，会在parser.out这个调试文件中输出一些信息） 使用precedence指定优先级的技术会带来一个问题，有时运算符的优先级需要基于上下文。例如，考虑”3 + 4 * -5”中的一元的’-‘。数学上讲，一元运算符应当拥有较高的优先级。然而，在我们的precedence定义中，MINUS的优先级却低于TIMES。为了解决这个问题，precedene规则中可以包含”虚拟标记”： ~~~ precedence = ( ('left', 'PLUS', 'MINUS'), ('left', 'TIMES', 'DIVIDE'), ('right', 'UMINUS'), # Unary minus operator ) ~~~ 在语法文件中，我们可以这么表示一元算符： ~~~ def p_expr_uminus(p): 'expression : MINUS expression %prec UMINUS' p[0] = -p[2] ~~~ 在这个例子中，%prec UMINUS覆盖了默认的优先级（MINUS的优先级），将UMINUS指代的优先级应用在该语法规则上。 起初，UMINUS标记的例子会让人感到困惑。UMINUS既不是输入的标记也不是语法规则，你应当将其看成precedence表中的特殊的占位符。当你使用%prec宏时，你是在告诉yacc，你希望表达式使用这个占位符所表示的优先级，而不是正常的优先级。 还可以在precedence表中指定”非关联”。这表明你不希望链式运算符。比如，假如你希望支持比较运算符’<’和’>’，但是你不希望支持 `a < b < c`，只要简单指定规则如下： ~~~ precedence = ( ('nonassoc', 'LESSTHAN', 'GREATERTHAN'), # Nonassociative operators ('left', 'PLUS', 'MINUS'), ('left', 'TIMES', 'DIVIDE'), ('right', 'UMINUS'), # Unary minus operator ) ~~~ 此时，当输入形如 a < b < c时，将产生语法错误，却不影响形如 a < b 的表达式。 对于给定的符号集，存在多种语法规则可以匹配时会产生归约/归约冲突。这样的冲突往往很严重，而且总是通过匹配最早出现的语法规则来解决。归约/归约冲突几乎总是相同的符号集合具有不同的规则可以匹配，而在这一点上无法抉择，比如： ~~~ assignment : ID EQUALS NUMBER | ID EQUALS expression expression : expression PLUS expression | expression MINUS expression | expression TIMES expression | expression DIVIDE expression | LPAREN expression RPAREN | NUMBER ~~~ 这个例子中，对于下面这两条规则将产生归约/归约冲突： ~~~ assignment : ID EQUALS NUMBER expression : NUMBER ~~~ 比如，对于”a = 5”，分析器不知道应当按照assignment : ID EQUALS NUMBER归约，还是先将5归约成expression，再归约成assignment : ID EQUALS expression。 应当指出的是，只是简单的查看语法规则是很难减少归约/归约冲突。如果出现归约/归约冲突，yacc()会帮助打印出警告信息： ~~~ WARNING: 1 reduce/reduce conflict WARNING: reduce/reduce conflict in state 15 resolved using rule (assignment -> ID EQUALS NUMBER) WARNING: rejected rule (expression -> NUMBER) ~~~ 上面的信息标识出了冲突的两条规则，但是，并无法指出究竟在什么情况下会出现这样的状态。想要发现问题，你可能需要结合语法规则和`parser.out`调试文件的内容。