158 翁译原理及实践 China-pub.co 下载 LR(O)分析算法根据当前的DFA状态选择一个动作，这个状态总是出现在栈的顶部。 定义：LR(O)分析算法(LR(O)parsing algorithm)。令s为当前的状态（位于分析栈的顶 部)。则动作定义如下： 1.若状态s包含了格式A→α邓的任何项目，其中X是一个终结符，则动作就是将 当前的输入记号移进到栈中。若这个记号是X,且状态s包含了项目A一→αX郑， 则压入到栈中的新状态就是包含了项目A→αXB的状态。若由于位于刚才所描 述的格式的状态s中的某个项目，这个记号不是X,则声明一个错误。 2.若状态s包含了任何完整的项目（格式A→a.的一个项目），则动作是用规则A→α 归约。假设输入为空，用规则S一S归约（其中S是开始状态）与接受相等价：若输 入不为空，则出现错误。在所有的其他情况中，新状态的计算如下：将串α及它 的所有对应状态从分析栈中删去（根据DFA的构造方式，串α必须位于栈的顶部）。 相应地，在DFA中返回到由a开始构造的状态中（这须是由α的刷除所揭示的状 态)。由于构造DFA,这个状态就还须包含格式B一QAB的一个项目。将A压入到 栈中，并压入包含了项目B一AB的状态（作为新状态）。（请注意，由于正将 压入到栈中，所以这与在DFA中跟随A的转换相对应（这实际上是合理的）。 若以上的规则都是无歧义的，则文法就是LR(O)文法(LR(O)grammar)。这就意味着若 状态包含了完整项目A→α.，那么它就不能再包含其他项目了。实际上，若这样的状态还包含 了一个“移进的”项目A→α郑(X是一个终结符)，就会出现一个到底是执行动作(1)还是执 行动作(2)的二义性。这种情况称作移进-归约冲突(shift-reduce confliet)。类似地，如果这样 的状态包含了另一个完整项目B一B.,那么也会出现一个关于为该归约使用哪个产生式(4→α 或B一B)二义性。这种情况称作归约-归约冲突(reduce-reduce conflict))。所以，当仅当每个 状态都是移进状态（仅包含了“移进”项目的状态）或包含了单个完整项目的归约时，该文法才 是LR(O). 我们注意到上面例子中所用到的两个文法都不是LR(O)文法。在图5-3中，状态0、状态2和 状态4都包括了对于LR(O)分析算法的移进-归约冲突：在图5-4的DFA中，状态1包含了一个移 进-归约冲突。由于几乎所有“真正的”文法都不是LR(O),所以这并不奇怪。但下面将会给出 一个文法是LR(O)的示例。 例5.9考虑文法 A-(A)川a 扩充的文法具有如图5-5所示的项目集合的DFA,而这就是LR(O)。为了看清LR(O)分析算法 是如何工作的，可考虑一下串(a)。该串的分析是根据表5-3各步骤所给出的LR(O)分析算 法进行。分析开始于状态0，因为这个状态是一个移进状态，所以将第1个记号（移进到栈中。 接着，由于DFA指出了在符号（上从状态0到状态3的转换，所以将状态3压入到栈中。状态3 也是一个移进状态，所以下一个（也被移进到栈中，而且在（上的转换返回到状态3。移进再 一次将a放入到栈中，而且a上的转换由状态3进入到状态2。现在位于表5-3的第4步，而且 己到达了第1个归约状态。这里的状态2和符号a都是由栈弹出的，并回到处理中的状态3。接 着，将A压入到栈中，且得到由状态3到状态4的4转换。状态4是一个移进状态，所以)被移 进到栈中，且)上的转换使分析转到状态5。这里发生了一个由规则A一(A)进行的归约 它从栈中弹出状态5、状态4、状态3以及符号)、A和)。现在的分析位于状态3中，而且A和 L R ( 0 )分析算法根据当前的D FA状态选择一个动作，这个状态总是出现在栈的顶部。 定义：L R ( 0 )分析算法(LR(0) parsing algorithm)。令s 为当前的状态(位于分析栈的顶 部)。则动作定义如下： 1. 若状态s 包含了格式A→a.Xb的任何项目，其中X是一个终结符，则动作就是将 当前的输入记号移进到栈中。若这个记号是 X，且状态s 包含了项目A→a.Xb， 则压入到栈中的新状态就是包含了项目 A→aX.b的状态。若由于位于刚才所描 述的格式的状态s 中的某个项目，这个记号不是X，则声明一个错误。 2. 若状态s 包含了任何完整的项目(格式A→a. 的一个项目)，则动作是用规则A→a 归约。假设输入为空，用规则S¢→S归约(其中S是开始状态)与接受相等价；若输 入不为空，则出现错误。在所有的其他情况中，新状态的计算如下：将串a及它 的所有对应状态从分析栈中删去（根据DFA的构造方式，串a必须位于栈的顶部）。 相应地，在D FA中返回到由a开始构造的状态中（这须是由a的删除所揭示的状 态）。由于构造D FA，这个状态就还须包含格式B→a.Ab的一个项目。将A压入到 栈中，并压入包含了项目B→aA.b的状态（作为新状态）。（请注意，由于正将A 压入到栈中，所以这与在DFA中跟随A的转换相对应(这实际上是合理的)。 若以上的规则都是无歧义的，则文法就是 L R ( 0 )文法(LR(0) grammar)。这就意味着若一个 状态包含了完整项目A→a.，那么它就不能再包含其他项目了。实际上，若这样的状态还包含 了一个“移进的”项目 A→a.Xb（X是一个终结符 )，就会出现一个到底是执行动作 ( 1 )还是执 行动作( 2 )的二义性。这种情况称作移进-归约冲突 (shift-reduce conflict)。类似地，如果这样 的状态包含了另一个完整项目 B→b.，那么也会出现一个关于为该归约使用哪个产生式 (A→a 或B→b）二义性。这种情况称作归约-归约冲突 (reduce-reduce conflict)。所以，当仅当每个 状态都是移进状态(仅包含了“移进”项目的状态 )或包含了单个完整项目的归约时，该文法才 是L R ( 0 )。 我们注意到上面例子中所用到的两个文法都不是 L R ( 0 )文法。在图5 - 3中，状态0、状态2和 状态4都包括了对于L R ( 0 )分析算法的移进-归约冲突；在图 5 - 4的D FA中，状态1包含了一个移 进-归约冲突。由于几乎所有“真正的”文法都不是 L R ( 0 )，所以这并不奇怪。但下面将会给出 一个文法是L R ( 0 )的示例。 例5.9 考虑文法 A→ ( A ) | a 扩充的文法具有如图 5 - 5所示的项目集合的 D FA，而这就是 L R ( 0 )。为了看清 L R ( 0 )分析算法 是如何工作的，可考虑一下串 ( ( a ) )。该串的分析是根据表 5 - 3各步骤所给出的 L R ( 0 )分析算 法进行。分析开始于状态 0，因为这个状态是一个移进状态，所以将第 1个记号(移进到栈中。 接着，由于 D FA指出了在符号 (上从状态0到状态3的转换，所以将状态 3压入到栈中。状态 3 也是一个移进状态，所以下一个 (也被移进到栈中，而且在 (上的转换返回到状态 3。移进再 一次将a放入到栈中，而且 a上的转换由状态 3进入到状态 2。现在位于表 5 - 3的第4步，而且 已到达了第1个归约状态。这里的状态 2和符号a都是由栈弹出的，并回到处理中的状态 3。接 着，将A压入到栈中，且得到由状态 3到状态4的A转换。状态 4是一个移进状态，所以 )被移 进到栈中，且 )上的转换使分析转到状态 5。这里发生了一个由规则 A→ ( A ) 进行的归约， 它从栈中弹出状态 5、状态 4、状态3以及符号)、A和)。现在的分析位于状态 3中，而且A和 1 5 8 编译原理及实践 下载