设有文法G(S): S->E E->aA|bB A->cA|d B->cB|d 构造其LR(0)分析表,并利用此分析表判断符号串acccd是否为文法G(S)的句子。
时间: 2023-06-10 20:04:54 浏览: 217
可以使用以下步骤来构造G(S)的LR(0)分析表:
1. 首先计算出文法G(S)的所有LR(0)项目,即对于每个产生式A -> α,生成以下项目:
- A -> .α
- A -> α.
2. 构造LR(0)自动机,将所有LR(0)项目加入到初始状态中,并根据项目中的点所在位置,添加状态转移。
对于A -> .α这样的项目,需要添加从该状态到所有能推导出α的状态的边;
对于A -> α.这样的项目,需要添加从该状态到该项产生式左边的状态的边。
3. 对于每个状态,计算出它的LR(0)闭包。对于一个状态的LR(0)项目集合,如果其中有一个项目的形如A -> α.Bβ,
则需要添加所有能够推导出B的产生式的LR(0)项目到该状态,直到不能再添加为止。这样得到的项目集合就是该状态的LR(0)闭包。
4. 根据状态转移和LR(0)闭包,构造LR(0)分析表。对于每个状态i和终结符a,如果在状态i的LR(0)闭包中包含一个项目A -> α.aβ,
则在(i,a)的表格中填写“移进j”,其中j是状态i通过终结符a转移到的状态。对于每个状态i和非终结符A,如果在状态i的LR(0)闭包中
包含一个项目A -> α,则在(i,A)的表格中填写“归约A -> α”。
根据以上步骤,可以得到文法G(S)的LR(0)分析表如下:
状态 | a | b | c | d | A | B | E | S |
--------|-------|-------|-------|-------|-------|-------|-------|-------|
0 | s2 | s3 | | | | | | |
1 | | | | | | | | acc |
2 | | | | | | | s4 | |
3 | | | | | | | s5 | |
4 | s2 | s3 | | | | r2 | | |
5 | r4 | r4 | | | r4 | | | |
6 | r3 | r3 | s7 | s8 | | | | |
7 | s9 | s10 | | | | | | |
8 | s11 | s12 | | | | | | |
9 | | | | | | r1 | | |
10 | | | | | | r3 | | |
11 | | | | | | | | r0 |
12 | | | | | | | | r0 |
其中si表示状态i,s表示移进,r表示归约,数字表示状态的编号。例如,在状态0中,当接收到终结符a时,状态将转移至2,
即填写s2;当读到终结符b时,状态将转移至3,即填写s3。在状态7中,当接收到非终结符A时,需要归约A->cB,因此在表格中填写r1。
根据LR(0)分析表,能够判断符号串acccd是否为文法G(S)的句子。具体步骤如下:
1. 将符号串acccd末尾添加一个结束符$,形成a c c c d $。
2. 初始状态为0,将$入栈,读入a,根据表格可知,状态将转移至2。将a和2入栈。
3. 读入c,根据表格可知,状态将转移至4。将c和4入栈。
4. 读入c,根据表格可知,状态将转移至6。将c和6入栈。
5. 读入c,根据表格可知,状态将转移至7。将c和7入栈。
6. 读入d,根据表格可知,状态将转移至8。将d和8入栈。
7. 读入$,根据表格可知,需要进行归约操作。查表可知,在状态8中归约E->aA,因此弹出栈顶元素a和状态2,将A入栈,状态转移至
状态5。
8. 查表可知,在状态5中需要归约操作,而此时栈顶为A,因此进行归约。更具表格,在该状态中归约B->d,并且状态将转移到状态6。
因此,将两个d和6从栈中弹出,将B入栈,状态转移至状态2。
9. 查表可知,需要填写s11,因此将d和11入栈,状态转移至状态4。
10. 查表可知,需要填写s12,因此将$和12入栈,状态转移至状态3。
11. 查表可知,在状态3中需要归约操作。此时栈顶为S,因此进行归约。根据文法,S->E,因此,将E出栈,将S入栈,并将状态转移到状态0。
12. 最后查表可知,在状态0中需要接收符号$,因此无需进行任何操作,接受该符号串作为文法G(S)的句子。
因此,符号串acccd是文法G(S)的句子。