二义性和左递归

二义性

二义性（Ambiguity）：如果一个文法可以为某个句子生成多个语法分析树，这个文法就是二义的。

程序设计语言的文法通常是无二义的，否则就会导致一个程序有多种正确的解释。

二义性的根源：多种“正确”推导位于文法同一层

消除二义性的惯用技术：分层

• 改造文法，对于引发二义性的多种推导处于文法同一层的情况，将真正想要的推导提取出来，放到更深的层次

• 最左推导中，最深层的非终结符总是会被优先替换

• 确保只有一种最左推导，消除二义性

左递归

自顶向下的语法分析技术不能处理左递归的情况，因此需要消除左递归，但是自底向上的技术可以处理左递归。

消除直接左递归的方法并不能消除因为多步推导而产生的间接左递归。

提取左公因子

方法如上，目的是为了消除回溯。