国防科技大学：《编译原理》课程电子教案（PPT教学课件）第4章 语法分析——自上而下分析

■注意，由于对非终结符排序的不同，最 后所得的文法在形式上可能不一样。但 不难证明，它们都是等价的。 ■人 例如，若对文法(4.3)的非终结符排序选 为S、Q、R,那么，最后所得的无左递 归文法是： S→Qc|c Q-→Rb|b R→bcaR'|caR'laR' (4.5) R'→bcaR'|e ■文法(4.4)和(4.5)的等价性是显然的。 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ◼ 注意，由于对非终结符排序的不同，最 后所得的文法在形式上可能不一样。但 不难证明，它们都是等价的。 ◼ 例如，若对文法(4.3)的非终结符排序选 为S、Q、R，那么，最后所得的无左递 归文法是： S→Qc | c Q→Rb | b R→bcaR | caR |a R (4.5) R→ bca R |  ◼ 文法(4.4)和(4.5)的等价性是显然的

4.3.2消除回溯、提左因子 为了消除回溯就必须保证：对文法的任 何非终结符，当要它去匹配输入串时， 能够根据它所面临的输入符号准确地指 派它的一个候选去执行任务，并且此候 选的工作结果应是确信无疑的。 uA-→01l2l..|an P 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 4.3.2 消除回溯、提左因子 ◼ 为了消除回溯就必须保证：对文法的任 何非终结符，当要它去匹配输入串时， 能够根据它所面临的输入符号准确地指 派它的一个候选去执行任务，并且此候 选的工作结果应是确信无疑的。 ◼ A→ 1 |  2 | … |  n a…. S IP ... A

令G是一个不含左递归的文法，对G的所 有非终结符的每个候选定义它的终结首 符集FIRST(o)为： FIRST(a)={aac→a.,a∈Vr} 特别是，若a三6，则规定ε∈FIRST(o)。 。如果非终结符A的所有候选首符集两两不相交， 即A的任何两个不同候选c和o; FIRST(a)O FIRST(o)=φ 当要求A匹配输入串时，A就能根据它所面临的 第一个输入符号a,准确地指派某一个候选前去 执行任务。这个候选就是那个终结首符集含a的 0。 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ◼ 令G是一个不含左递归的文法，对G的所 有非终结符的每个候选定义它的终结首 符集FIRST()为： ( ) ={ | ..., } * FIRST  a  a aVT 特别是，若   ，则规定FIRST()。 *  • 如果非终结符A的所有候选首符集两两不相交， 即A的任何两个不同候选i和j FIRST(i )∩FIRST(j )＝ 当要求A匹配输入串时，A就能根据它所面临的 第一个输入符号a，准确地指派某一个候选前去 执行任务。这个候选就是那个终结首符集含a的 

提取公共左因子： 假定关于A的规则是 A→δβ1lδ32l.l83nlY1lY2.|Ym (其中，每个γ不以8开头) 那么，可以把这些规则改写成 A→δA'|Y1lY2l.IYm A'→βlB2l.IBn 经过反复提取左因子，就能够把每个非终 结符（包括新引进者）的所有候选首符集变 成为两两不相交。 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ◼ 提取公共左因子: 假定关于A的规则是 A→ 1 |  2 | …|  n |  1 |  2 | … | m (其中，每个不以开头) 那么，可以把这些规则改写成 A→A |  1 |  2 | … |  m A→ 1 |  2 | … |  n ◼ 经过反复提取左因子，就能够把每个非终 结符(包括新引进者)的所有候选首符集变 成为两两不相交

4.3.3 LL(1)分析条件 ■ E→TE' E'→+TE'|8 T→FT' T'→*FT'|ε F→(E)|i ■i+i 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ◼ E→TE E→+TE |  T→FT T→*FT |  F→(E) | i ◼ i + i 4.3.3 LL(1)分析条件