给定拓展后的文法G如下:1S-S 2S-AS 3S- 4A-aA 5A-ba证明GS是SLR1文法;b构造GS的识别活前缀的LR1项目集及DFA;c构造GS的LR1分析表;d给出输入串abab#的LR1分析过程。
a)首先需要说明一下拓展后的文法G[S]中,S`是一个新的起始符号。接下来,我们分别对G[S]的每个产生式进行分析。
1)S->S:这是一个归约产生式,因为右侧只有一个符号S,所以对于任何一个终结符号a,S->.S, a是一个合法的LR(1)项目。
2)S->AS:这是一个移进-归约产生式。当读入一个终结符a时,可以进行移进操作,此时S->A.S, a是一个合法的LR(1)项目。当读入一个#时,可以进行归约操作,此时S->A, #是一个合法的LR(1)项目。
3)S->ε:这是一个归约产生式。当读入一个#时,可以进行归约操作,此时S->ε, #是一个合法的LR(1)项目。
4)A->aA:这是一个移进-归约产生式。当读入一个终结符a时,可以进行移进操作,此时A->a.A, a是一个合法的LR(1)项目。当读入一个终结符b时,可以进行归约操作,此时A->ε, b是一个合法的LR(1)项目。
5)A->b:这是一个归约产生式。当读入一个终结符a或b时,可以进行归约操作,此时A->b, a或b是一个合法的LR(1)项目。
因此,G[S]是一个SLR(1)文法。
b)构造G[S]的识别活前缀的LR(1)项目集及DFA:
首先,我们需要构造出G[S]的所有LR(1)项目。对于任何一个产生式A->αβ,其中α和β可能为空,以及任何一个LR(1)项目[A->α.β, a],其中a是一个终结符号,我们可以按照以下方式构造出LR(1)项目:
-
若β为空,则对于任何一个终结符号a,都有[A->α., a]是一个LR(1)项目。
-
若β不为空,则对于任何一个终结符号a,都有[A->α.β, a]是一个LR(1)项目。
-
对于任何一个非终结符号B,都有[B->.γ, a]是一个LR(1)项目,其中γ是B能够推导出的任何一个符号串。
接下来,我们按照LR(1)项目的定义,对于G[S]构造出识别活前缀的LR(1)项目集:
I0: S`->.S, # S->.AS, a S->.AS, # A->.aA, a A->.aA, b A->.b, a A->.b, b
I1: S`->S., # S->A.S, a A->.aA, a A->.aA, b A->.b, a A->.b, b
I2: S->A.S., a A->a.A, a A->a.A, b
I3: S->A.S., # A->.aA, a A->.aA, b A->.b, a A->.b, b
I4: A->b., a A->b., b
I5: A->aA., a A->aA., b
接下来,我们按照识别活前缀的LR(1)项目集构造DFA:
DFA:
| | a | b | # | |-------|-------|-------|-------| | I0 | I1 | I4 | | |-------|-------|-------|-------| | I1 | I2 | I4 | acc | |-------|-------|-------|-------| | I2 | I2 | I4 | | |-------|-------|-------|-------| | I3 | I2 | I5 | | |-------|-------|-------|-------| | I4 | | | | |-------|-------|-------|-------| | I5 | | | |
c)构造G[S]的LR(1)分析表:
根据DFA,我们可以构造出G[S]的LR(1)分析表:
| 状态 | a | b | # | |---------|-------|-------|-------| | I0 | s1 | s4 | | |---------|-------|-------|-------| | I1 | s2 | s4 | acc | |---------|-------|-------|-------| | I2 | s2 | s4 | | |---------|-------|-------|-------| | I3 | s2 | s5 | | |---------|-------|-------|-------| | I4 | | | | |---------|-------|-------|-------| | I5 | | | |
d)给出输入串abab#的LR(1)分析过程:
输入串:abab#
根据LR(1)分析表,初始状态为I0,读入a,转移到状态I1,此时栈中的状态为0 1。继续读入b,转移到状态I4,此时栈中的状态为0 1 4。继续读入a,转移到状态I2,此时栈中的状态为0 1 4 2。继续读入b,转移到状态I4,此时栈中的状态为0 1 4 2 4。最后读入#,根据LR(1)分析表,进行归约操作,依次归约为A->b, A->aA, S->AS和S->S。最终状态为I0,栈中只剩下起始符号S,输入串也已经被完全读入,分析成功,接受该输入串
原文地址: https://www.cveoy.top/t/topic/fHoL 著作权归作者所有。请勿转载和采集!