5.2.3 非LL(1)文法的等价变换 在第5.1、5.2.1和5.2.2 中指出确定的自顶向下分析要求对给定语言的文法必须是LL(1)形式。然而,不一定每个语言都有LL(1)文法。对一个语言的非LL(1)文法是否能变换为等价的LL(1)形式以及如何变换是本节讨论的主要问题。由LL(1)文法的定义可知若文法中含有直接或间接左递归,或含有左公共因子则该文法肯定不是LL(1)文法。因而,我们设法消除文法中的左递归,提取左公共因子对文法进行等价变换,在某些特殊情况下可能使其变为LL(1)文法。 1.提取左公共因子 若文法中含有形如:A→αβ|αγ的产生式,这导致了对相同左部的产生式其右部的FIRST集相交,也就是SELECT(A→αβ)∩SELECT(A→αγ) ≠ ![]() ![]() 现将产生式A→αβ|αγ进行等价变换为: A→α(β|γ) 其中'(',')'为元符号,可进一步引进新非终结符A′,去掉'(',')'使产生式变换为: A→αA′ A′→β|γ 写成一般形式为: A→αβ1|αβ2|…|αβn,提取左公共因子后变为: A→α(β1|β2|…|βn),再引进非终结符A′,变为: A→αA′ A′→β1|β2|…|βn 若在βi、βj、βk … (其中1≤i,j,k≤n)中仍含有左公共因子,这时可再次提取,这样反复进行提取直到引进新非终结符的有关产生式再无左公共因子为止。 |