用c语言设计实现文法为G’ 、S’->S 、 S ->rD 、 D ->D,k 、D ->k的SLR(1)分析器
时间: 2024-02-23 15:01:26 浏览: 34
SLR(1)分析器的设计主要包括以下步骤:
1. 构造文法的FIRST集和FOLLOW集。
- FIRST(S') = {r, k}
- FIRST(S) = {r}
- FIRST(D) = {k}
- FOLLOW(S') = {$}
- FOLLOW(S) = {k, $}
- FOLLOW(D) = {r, k, $}
2. 构造DFA状态转移图。
首先,将S'->.S加入初始状态闭包中,即{S'->.S}。然后,对于每个状态,依次考虑每个文法符号X(包括终结符和非终结符),求出它的闭包,并将它们作为出边添加到DFA中。如果某个闭包已经存在于某个状态中,则不需要再次添加。
以状态{S'->S., D->.k, D->.D,k}为例:
- X = S,闭包为{S->.rD},添加出边S->{S->r.D, D->.k, D->.D,k}
- X = D,闭包为{D->.k, D->.D,k},添加出边D->{D->k., D->D.,k}
- X = k,没有闭包,不添加出边
- X = r,没有闭包,不添加出边
最终得到的DFA状态转移图如下所示:
```
+-------+ r +-------+
| 0 |-------->| 1 |
+-------+ +-+---+-+
| k | D->k |
| | D->D,k|
r | +-------+
|
+--+----+
| 2 |
+-------+
```
3. 构造ACTION和GOTO表。
对于每个状态i和每个终结符a,如果存在状态j使得i经过a能够转移到j,则ACTION[i, a]为“shift j”;如果i中存在形如A->α.的项,并且FOLLOW(A)中包含a,则ACTION[i, a]为“reduce A->α”。如果i中同时存在多个形如A->α.的项,则选择最长的α进行规约。
对于每个状态i和每个非终结符A,如果存在状态j使得i经过A能够转移到j,则GOTO[i, A]为j。
根据DFA状态转移图,ACTION和GOTO表可以如下构造:
```
STATE | ACTION | GOTO
------+-----------------------+------
0 | r -> shift 1 | S -> 2
| k -> reduce D -> k |
+-----------------------+
1 | $ -> accept |
+-----------------------+
2 | k -> reduce D -> D,k |
| r -> shift 1 |
+-----------------------+
```
最后,将构造出的SLR(1)分析器实现为C语言程序即可。