文法G(S)及其LR分析表如下,请给出串hmhm#的LR分析过程(即状态,符号,输入串的变化过程)。 文法G(S):(1) S → XhY (2) X → k (3) X → ε (4) Y → m (5) Y → Yhm (6) Y → ε
时间: 2024-04-01 21:34:29 浏览: 62
LR分析表如下:
| 状态 | k | h | m | # |
|:--------:|:----:|:----:|:----:|:----:|
| 0 | s2 | | | |
| 1 | | | | acc |
| 2 | | s3 | | |
| 3 | | | s4 | |
| 4 | | | | r3 |
| 5 | | | | r2 |
| 6 | s2 | | | |
| 7 | | | | r1 |
| 8 | | s6 | | |
| 9 | | | s7 | |
| 10 | | | | r6 |
| 11 | | | | r6 |
| 12 | | | | r6 |
| 13 | | | | r5 |
| 14 | | | | r5 |
| 15 | | | | r5 |
分析过程如下:
初始状态为0,栈中放入状态0。读入h,查表得到应该转移到状态3,于是将状态3和h压入栈中,输入指针指向下一个字符m。此时栈中为0h3m,输入串为hmhm#。
接下来读入m,查表得到应该转移到状态4,于是将状态4和m压入栈中,输入指针指向下一个字符h。此时栈中为0h3mh4,输入串为mhm#。
接下来读入h,查表得到应该转移到状态5,并将状态5和h压入栈中,输入指针指向下一个字符m。此时栈中为0h3mh4h5m,输入串为hm#。
接下来读入m,查表得到应该转移到状态4,但是状态4对应的动作是规约3号产生式Y → m,因此需要进行规约操作。栈中弹出3个状态和3个符号,然后按照Y → m进行规约,将Y替换为m。此时栈中为0h,输入串为hm#。
接下来读入h,查表得到应该转移到状态3,将状态3和h压入栈中,输入指针指向下一个字符#。此时栈中为0h3#,输入串为m#。
接下来读入#,查表得到应该转移到状态1,但是状态1对应的动作是规约1号产生式S → XhY,因此需要进行规约操作。栈中弹出3个状态和3个符号,然后按照S → XhY进行规约,将XhY替换为S。此时栈中为0S#,输入串为m#。
接下来读入#,查表得到应该转移到状态7,但是状态7对应的动作是规约6号产生式Y → ε,因此需要进行规约操作。栈中弹出1个状态和1个符号,然后按照Y → ε进行规约,将Y替换为ε。此时栈中为0S#,输入串为#。
接下来读入#,查表得到应该转移到状态7,但是状态7对应的动作是规约5号产生式Y → Yhm,因此需要进行规约操作。栈中弹出3个状态和3个符号,然后按照Y → Yhm进行规约,将Yhm替换为Y。此时栈中为0S#,输入串为#。
接下来读入#,查表得到应该转移到状态7,但是状态7对应的动作是规约4号产生式X → ε,因此需要进行规约操作。栈中弹出1个状态和1个符号,然后按照X → ε进行规约,将X替换为ε。此时栈中为0S#,输入串为#。
接下来读入#,查表得到应该转移到状态1,但是状态1对应的动作是规约2号产生式X → k,因此需要进行规约操作。栈中弹出1个状态和1个符号,然后按照X → k进行规约,将X替换为k。此时栈中为0Sk#,输入串为#。
接下来读入#,查表得到应该转移到状态1,但是状态1对应的动作是规约1号产生式S → XhY,因此需要进行规约操作。栈中弹出3个状态和3个符号,然后按照S → XhY进行规约,将XhY替换为S。此时栈中只剩下0和S两个符号,输入串为#。
最后在状态1中,查表得到应该接受这个串,分析结束。
阅读全文