160 翁译原理及实践 China-pub.Co 下载 表5-4例5.9中的文法的分析表 状态 动作 规则 输入 Goto 0 4-A 2 归约 A-a 3 移进 移进 归约 A-(A) 在这样的分析表中的空白项表示的是错误。当必须要进行错误恢复时，则需要准确地指出 分析程序要为每个这些空白项采取什么动作。后面一节将讨论这个问题。 5.3SLR(1)分析 5.3.1SLR(1)分析算法 简单LR(I)分析，或SLR(I)分析，也如上一节中一样使用了LR(O)项目集合的DFA。但是 通过使用输入串中下一个记号来指导它的动作，它大大地提高了LR(O)分析的能力。它通过两 种方法做到这一点。首先，它在一个移进之前先考虑输入记号以确保存在着一个恰当的DFA 其次，它使用如4.3节所构造的非终结符的Foow集合来决定是否应执行一个归约。令人吃惊 的是，先行的这个简单应用的能力强大得足以分析几乎所有的一般的语言构造。 定义：SLR(I)分析算法(SLR(I)parsing algorithm)。令s为当前状态（位于分析栈的顶 部)。则动作可定义如下： 1.若状态s包含了格式A一Q.邓的任意项目，其中X是一个终结符，且X是输入串 中的下一个记号，则动作将当前的输入记号移进到栈中，且被压入到栈中的新 状态是包含了项目A一XB的状态 2.若状态s包含了完整项目A一Y.,则输入串中的下一个记号是在Follow(4)中，所 以动作是用规则A→y归约。用规则S→S归约与接受等价，其中S是开始状态： 只有当下一个输入记号是$时，这才会发生⊙。在所有的其他情况中，新状态都 是如下计算的：别除串α和所有它的来自分析栈中的对应状态。相对应地， DFA回到α开始构造的状态。通过构造，这个状态必须包括格式B一Y.AB的 个项目。将A压入到栈中，并将包含了项目B一aA.B的状态压入。 3.若下一个输入记号都不是上面两种情况所提到的，则声明一个错误 若上述的SLR(I)分析规则并不导致二义性，则文法为SLR()文法(SLR(I)grammar)。特别 地，当且仅当对于任何状态5，以下的两个条件： I)对于在s中的任何项目A一a邓，当X是一个终结符，且X在Follow(B)中时，s中没有完 整的项目B→y,。 2)对于在s中的任何两个完整项目A→a.和B→B,Follow(A)Follow(B)为空。 。实际上，任何文法扩充的开始状态了的Fow集合总是只由S组成，这是因为S只出现在文法规则S一S中。 表5-4 例5 . 9中的文法的分析表 状 态 动 作 规 则 输 入 G o t o ( a ) A 0 移进 3 2 1 1 归约 A¢→ A 2 归约 A→ a 3 移进 3 2 4 4 移进 5 5 归约 A→ ( A ) 在这样的分析表中的空白项表示的是错误。当必须要进行错误恢复时，则需要准确地指出 分析程序要为每个这些空白项采取什么动作。后面一节将讨论这个问题。 5.3 SLR(1)分析 5.3.1 SLR(1)分析算法 简单L R ( 1 )分析，或S L R ( 1 )分析，也如上一节中一样使用了 L R ( 0 )项目集合的D FA。但是， 通过使用输入串中下一个记号来指导它的动作，它大大地提高了 L R ( 0 )分析的能力。它通过两 种方法做到这一点。首先，它在一个移进之前先考虑输入记号以确保存在着一个恰当的 D FA。 其次，它使用如 4 . 3节所构造的非终结符的 F o l l o w集合来决定是否应执行一个归约。令人吃惊 的是，先行的这个简单应用的能力强大得足以分析几乎所有的一般的语言构造。 定义：S L R ( 1 )分析算法(SLR(1) parsing algorithm)。令s 为当前状态(位于分析栈的顶 部)。则动作可定义如下： 1. 若状态s 包含了格式A→a.Xb的任意项目，其中X是一个终结符，且X是输入串 中的下一个记号，则动作将当前的输入记号移进到栈中，且被压入到栈中的新 状态是包含了项目A→aX.b的状态。 2. 若状态s 包含了完整项目A→g.，则输入串中的下一个记号是在F o l l o w (A)中，所 以动作是用规则A→g 归约。用规则S¢→S归约与接受等价，其中S是开始状态； 只有当下一个输入记号是 $时，这才会发生 。在所有的其他情况中，新状态都 是如下计算的：删除串 a和所有它的来自分析栈中的对应状态。相对应地， D FA回到a开始构造的状态。通过构造，这个状态必须包括格式 B→g. Ab的一 个项目。将A压入到栈中，并将包含了项目B→aA.b的状态压入。 3. 若下一个输入记号都不是上面两种情况所提到的，则声明一个错误。 若上述的S L R ( 1 )分析规则并不导致二义性，则文法为 S L R ( 1 )文法(SLR(1) grammar)。特别 地，当且仅当对于任何状态s，以下的两个条件： 1) 对于在s 中的任何项目A→a.Xb，当X是一个终结符，且X在Follow (B) 中时，s 中没有完 整的项目B→g.。 2) 对于在s 中的任何两个完整项目A→a.和B→b.，F o l l o w (A) Follow(B)为空。 1 6 0 编译原理及实践 实际上，任何文法扩充的开始状态S¢ 的F o l l o w集合总是只由$组成，这是因为S¢ 只出现在文法规则S¢ →S中。 下载