注意,由于对非终结符排序的不同,最 后所得的文法在形式上可能不一样。但 不难证明,它们都是等价的。 例如,若对文法(4.3)的非终结符排序选 为S、Q、R,那么,最后所得的无左递 归文法是: →Qc|c Q→Rb|b r→bcar'car'ar (4.5) r'→bcar' 文法(4.4)和(4.5)的等价性是显然的。 编译原理
编译原理 ◼ 注意，由于对非终结符排序的不同，最 后所得的文法在形式上可能不一样。但 不难证明，它们都是等价的。 ◼ 例如，若对文法(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消除回溯、提左因子 为了消除回溯就必须保证:对文法的任 何非终结符,当要它去匹配输入串时, 能够根据它所面临的输入符号准确地指 派它的一个候选去执行任务,并且此候 选的工作结果应是确信无疑的。 a→a1a2lana. IP .. A .. 编译原理
编译原理 4.3.2 消除回溯、提左因子 ◼ 为了消除回溯就必须保证：对文法的任 何非终结符，当要它去匹配输入串时， 能够根据它所面临的输入符号准确地指 派它的一个候选去执行任务，并且此候 选的工作结果应是确信无疑的。 ◼ A→ 1 | 2 | … | n a…. S IP ... A
令G是一个不含左递归的文法,对G的所 有非终结符的每个候选a定义它的终结首 符集 FIRST(a)为: * FIRST(a)={a|a→a,a∈Vr} * 特别是,若a→,则规定ε E FIRST(a) 如果非终结符A的所有候选首符集两两不相交, 即A的任何两个不同候选a和a FIRST(a) FIRST(a)=中 当要求A匹配输入串时,A就能根据它所面临的 第一个输入符号a,准确地指派某一个候选前去 执行任务。这个候选就是那个终结首符集含a的 编译原理
编译原理 ◼ 令G是一个不含左递归的文法，对G的所 有非终结符的每个候选定义它的终结首 符集FIRST()为： ( ) = { | ..., } * VT FIRST a a a 特别是，若 ，则规定FIRST()。 * • 如果非终结符A的所有候选首符集两两不相交， 即A的任何两个不同候选i和j FIRST(i )∩FIRST(j )＝ 当要求A匹配输入串时，A就能根据它所面临的 第一个输入符号a，准确地指派某一个候选前去 执行任务。这个候选就是那个终结首符集含a的
提取公共左因子: 假定关于A的规则是 A→18nly1ly2ym (其中,每个y不以δ开头) 那么,可以把这些规则改写成 →ay1yYm '→12n 经过反复提取左因子,就能够把每个非终 结符(包括新引进者)的所有候选首符集变 成为两两不相交。 编译原理
编译原理 ◼ 提取公共左因子: 假定关于A的规则是 A→ 1 | 2 | …| n | 1 | 2 | … | m (其中，每个不以开头) 那么，可以把这些规则改写成 A→A | 1 | 2 | … | m A→ 1 | 2 | … | n ◼ 经过反复提取左因子，就能够把每个非终 结符(包括新引进者)的所有候选首符集变 成为两两不相交
4.3.3LL(1)分析条件 →te E'→+te' T→FT T'→ft' F→(E)|i i i 编译原理
编译原理 ◼ E→TE E→+TE | T→FT T→*FT | F→(E) | i ◼ i + i 4.3.3 LL(1)分析条件