编译原理练习
设文法为：
| $E’ \rightarrow $#$E$# | $T \rightarrow F$ |
|---|---|
| $E \rightarrow E+T$ | $F \rightarrow P \uparrow F \vert P $ |
| $E \rightarrow T$ | $P \rightarrow (E)$ |
| $T \rightarrow T*F$ | $P\rightarrow i$ |
求算符优先关系表，并分析$i+i$#是否为该文法的句子。
解：
$bool\space array$:
求$FIRSTVT$:
| + | * | $ \uparrow $ | $i$ | ( | ) | # | |
|---|---|---|---|---|---|---|---|
| $E’$ | 1 | ||||||
| $E$ | 1 | 1 | 1 | 1 | 1 | ||
| $T$ | 1 | 1 | 1 | 1 | |||
| $F$ | 1 | 1 | 1 | ||||
| $P$ | 1 | 1 |
求$LASTVT$:
| + | * | $\uparrow$ | $i$ | ( | ) | # | |
|---|---|---|---|---|---|---|---|
| $E’$ | 1 | ||||||
| $E$ | 1 | 1 | 1 | 1 | 1 | ||
| $T$ | 1 | 1 | 1 | 1 | |||
| $F$ | 1 | 1 | 1 | ||||
| $P$ | 1 | 1 |
$FIRSTVT$与$LASTVT$如表所示：
| $VN$ | $FIRSTVT$ | $LASTVT$ |
|---|---|---|
| $E$ | +,*,$\uparrow$,(,$i$ | +,*,$\uparrow$,),$i$ |
| $E’$ | # | # |
| $T$ | *,$\uparrow$,(,$i$ | *,$\uparrow$,),$i$ |
| $F$ | $\uparrow$,(,$i$ | $\uparrow$,),$i$ |
| $T$ | (,$i$ | ),$i$ |
| 步骤 | 栈 | 优先关系 | 当前符号 | 剩余输出串 | 移进或规约 |
|---|---|---|---|---|---|
| 1 | # | < | $i$ | +$i$# | 移进 |
| 2 | #$i$ | > | + | $i$# | 规约 |
| 3 | #$F$ | < | + | $i$# | 移进 |
| 4 | #$F+$ | < | $i$ | # | 移进 |
| 5 | #$F+i$ | > | # | 规约 | |
| 6 | #$F+F$ | > | # | 规约 | |
| 7 | #$F$ | = | # | Accepted |
综上，$i+i$# 是该文法的句子。
