试构造文法的LR(1)分析表 (1) SL=R (2) SR (3) L*R (4) Lid (5) RL
时间: 2024-06-08 11:07:08 浏览: 11
首先,我们需要将文法转化为标准形式,也就是消除左递归和提取左公因子:
(1) S -> LR
(2) S -> R
(3) L -> L*R
(4) L -> id
(5) R -> RL
消除左递归后得到:
(1) S -> LR
(2) S -> R
(3) L -> idL'
(4) L' -> *RL'
(5) L' -> ε
(6) R -> RL
提取左公因子后得到:
(1) S -> R S'
(2) S' -> L R S'
(3) S' -> ε
(4) L -> id L'
(5) L' -> * R L'
(6) L' -> ε
(7) R -> R L
接下来,我们需要求出文法的 FIRST 和 FOLLOW 集合:
FIRST(S) = {id}
FIRST(S') = {id, ε}
FIRST(L) = {id}
FIRST(L') = {* , ε}
FIRST(R) = {id}
FOLLOW(S) = {$}
FOLLOW(S') = { $ }
FOLLOW(L) = {* , $}
FOLLOW(L') = {R, $}
FOLLOW(R) = {id, $}
然后,我们可以根据 LR(1) 分析表的构造方法来构造分析表:
状态 0:
id 移进 2
S GOTO 1
状态 1:
$ 接受
状态 2:
= 移进 3
状态 3:
id 移进 4
状态 4:
* 移进 5
R GOTO 6
状态 5:
id 移进 7
状态 6:
* 移进 5
L GOTO 8
状态 7:
* 移进 5
R GOTO 9
状态 8:
* 移进 5
L' GOTO 10
状态 9:
* 移进 5
L GOTO 11
状态 10:
id 移进 12
状态 11:
* 移进 5
L' GOTO 13
状态 12:
* 移进 5
R GOTO 14
状态 13:
* 移进 5
L' GOTO 15
状态 14:
$ 规约 R -> id
* 移进 5
L' GOTO 16
状态 15:
$ 规约 L' -> ε
* 规约 L' -> ε
状态 16:
$ 规约 L' -> ε
* 规约 L' -> ε
在分析表中,状态 0 代表初始状态,$ 代表输入串的结束符。对于每个状态,我们需要考虑可能的输入符号和可能的转移或规约操作。例如,在状态 0 中,如果输入符号是 id,那么我们应该移进到状态 2;如果输入符号是 S,那么我们应该进行 GOTO 操作,转移到状态 1。
最后,我们可以使用该分析表来分析输入串。例如,对于输入符号串 id=id*id,我们可以从状态 0 开始,依次执行移进和规约操作,直到接受状态。详细的分析过程如下:
符号栈 输入符号串 动作
0 id=id*id$ 移进 id,转移到状态 2
0 id 2 =id*id$ 移进 =,转移到状态 3
0 id 2 = 3 id*id$ 移进 id,转移到状态 4
0 id 2 = 3 id 4 * 5 移进 *,转移到状态 5
0 id 2 = 3 L' 10 * 5 规约 L' -> ε,转移到状态 10
0 id 2 = 3 L 8 * 5 转移到状态 8
0 id 2 = 3 L 8 * 5 id 7 移进 id,转移到状态 9
0 id 2 = 3 L 8 * 5 R 14 规约 R -> id,转移到状态 14
0 id 2 = 3 L 8 * 5 L' 16 规约 L' -> ε,转移到状态 16
0 id 2 = 3 L 8 * 5 L' 15 规约 L' -> ε,转移到状态 15
0 id 2 = 3 L 8 * 5 R 14 L' 16 规约 L' -> ε,转移到状态 16
0 id 2 = 3 L 8 * 5 R 14 L' 15 规约 L' -> ε,转移到状态 15
0 id 2 = 3 L 8 * 5 L 11 * 5 转移到状态 11
0 id 2 = 3 L 8 * 5 L 11 L' 13 规约 L' -> ε,转移到状态 13
0 id 2 = 3 L 8 * 5 L 11 L' 15 规约 L' -> ε,转移到状态 15
0 id 2 = 3 L 8 * 5 L 11 R 9 规约 R -> id,转移到状态 9
0 id 2 = 3 L 8 * 5 L 11 L' 13 规约 L' -> ε,转移到状态 13
0 id 2 = 3 L 8 * 5 L 11 L' 15 规约 L' -> ε,转移到状态 15
0 id 2 = 3 L 8 * 5 L 11 L' 15 规约 L' -> ε,转移到状态 15
0 id 2 = 3 L 8 * 5 L 11 L' 15 规约 L' -> ε,转移到状态 15
0 id 2 = 3 L 8 * 5 R 14 L' 16 规约 L' -> ε,转移到状态 16
0 id 2 = 3 L 8 * 5 L' 10 * 5 规约 L' -> ε,转移到状态 10
0 id 2 = 3 L 8 * 5 R 14 L' 16 规约 S' -> ε,转移到状态 16
0 id 2 = 3 L 8 * 5 S' 1 规约 S -> RS',转移到状态 1
0 id 2 = 3 S 1 规约 S -> R,转移到状态 1
0 S 1 接受
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![exe](https://img-home.csdnimg.cn/images/20210720083343.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)