二义性的消除(2) ·为了保证“else和最近未匹配的then匹配”,我们要 求在then分支的语旬必须是匹配好的。 ·引入 matched stn表示匹配好的语句,有如下文法 stmt matched stmt open stmt matched stmt )if expr then matched stmt else matched stmt l other open stmt if expr then stmt if expr then matched stmt else open stmt 二义性的消除方法没有规律可循。 通常并不是通过改变文法来消除二义性
二义性的消除(2) • 为了保证“else和最近未匹配的then匹配”，我们要 求在then分支的语句必须是匹配好的。 • 引入matched_stmt表示匹配好的语句，有如下文法： stmt → matched_stmt | open_stmt matched_stmt → if expr then matched_stmt else matched_stmt | other open_stmt → if expr then stmt | if expr then matched_stmt else open_stmt • 二义性的消除方法没有规律可循。 • 通常并不是通过改变文法来消除二义性
左递归的诮除 ·左递归的定义 如果一个文法中有非终结符号A使得A=*>A 那么这个文法就是左递归的。 立即左递归(规则左递归) 文法中存在一个形如A→AQ的产生式。 ·自顶向下的语法分析技术不能处理左递归 的情况。因此需要消除左递归:但是自底 向上的技术可以处理左递归
左递归的消除 • 左递归的定义： – 如果一个文法中有非终结符号A使得A=*=>Aα， 那么这个文法就是左递归的。 • 立即左递归（规则左递归） – 文法中存在一个形如A→Aα的产生式。 • 自顶向下的语法分析技术不能处理左递归 的情况，因此需要消除左递归；但是自底 向上的技术可以处理左递归
立即左递归的消除 ·假设非终结符号A存在立即左递归 的情形,假设以A为左部的规则有 A→Aax1|Aa2|.|Aam|β1|β21…|βn 可以替换为 A→B1A|β2A-.|βnA A→01A|a2A2||anA|e 由A生成的串总是以某个阝开头, 然后跟上零个或者多个的重复。 Baa…ac
立即左递归的消除 • 假设非终结符号A存在立即左递归 的情形，假设以A为左部的规则有： A→ Aα1 | Aα2 |…| Aαm | β1 | β2 |… | βn 可以替换为 A→β1A’ | β2A’|… | βn A’ A’→α1A’ | α2A’ |…| αmA’ | ε • 由A生成的串总是以某个βi开头， 然后跟上零个或者多个αi的重复
通用的左递归消除方法 ·输入:没有环和ε产生式的文法G 输出:等价的无左递归的文法 步骤: 将大法的非终纪 for i=1 to n do 内层循环的每一次迭代保证了A的 for j= l to i-1 生式的右部首符号都比A更加靠后。 {将形如A.2.当内层循环结束时,A的产生式的右 其中A→81 部首符号不先于A 3.消除立即左递归就保证了A的产生式 消除A的立即 的右部首符号必然比A后。(不能有 环和产生式) 4.当外层循环结束时,所有的产生式都 是如此。使用这些产生式当然不会产 生左递归的情形
通用的左递归消除方法 • 输入：没有环和ε产生式的文法G • 输出：等价的无左递归的文法 • 步骤： 将文法的非终结符号任意排序为A1 ,A2 ,…,An for i=1 to n do { for j = 1 to i-1 do {将形如Ai→ Ajγ的产生式替换为Ai→δ1γ| δ2γ | … |δnγ， 其中Aj→ δ1 | δ2 |…| δm}是以Aj为左部的所有产生式； } 消除Ai的立即左递归； } 1. 内层循环的每一次迭代保证了Ai的产 生式的右部首符号都比Aj更加靠后。 2. 当内层循环结束时，Ai的产生式的右 部首符号不先于Ai。 3. 消除立即左递归就保证了Ai的产生式 的右部首符号必然比Ai后。（不能有 环和ε产生式） 4. 当外层循环结束时，所有的产生式都 是如此。使用这些产生式当然不会产 生左递归的情形
通用左递归消除的例子 S> Aab A,Ac Sd e 步骤1:排列为S,A 1=1时:內层循环不运行,S没有立即左递归; i=2时:j=1,处理规则A→Sd;替换得到 A→Ac| Aad bd|e 消除A的立即左递归 本例子中的￡产生式恰好 S→Aa|b 没有影响算法的正确性 a>bdA'A A→cA|adA|e 通用左递归消除的问题在于很难找到新文法和旧文法的推 导之间的对应关系,因此很难依据新文法进行语义处理
通用左递归消除的例子 • S → Aa | b A→Ac | Sd | ε • 步骤1：排列为S，A • i=1时：内层循环不运行，S没有立即左递归； • i=2时：j=1，处理规则A→Sd；替换得到 – A→Ac | Aad | bd | ε • 消除A的立即左递归 – S→Aa | b – A→bdA’ | A’ – A’→cA’ | adA’ | ε 通用左递归消除的问题在于很难找到新文法和旧文法的推 导之间的对应关系，因此很难依据新文法进行语义处理。 本例子中的ε产生式恰好 没有影响算法的正确性