文法G: E->E+T|T T->T*F|F F->i|(E) 用预测分析法分析的步骤如 构造FIRST集和FOLLOW集然后构造预测分析表
时间: 2024-02-16 14:01:16 浏览: 167
已经在前面回答了如何构造FIRST集和FOLLOW集,下面我们来构造预测分析表:
1. 构造预测分析表
首先,我们需要先将文法G转换为LL(1)文法。因为E和T都可以推导出E和T,所以文法G不是LL(1)文法。我们需要对文法进行改写,将左递归消除,并对每个非终结符号的产生式进行提取左公因式。改写后的文法如下:
E -> TE'
E' -> +TE' | ε
T -> FT'
T' -> *FT' | ε
F -> i | (E)
然后,我们可以根据FIRST集和FOLLOW集来构造预测分析表。预测分析表的行表示非终结符号,列表示终结符号(包括$符号)。表格中的每个元素,都是一个产生式。构造预测分析表的步骤如下:
(1)对于每个产生式A->α,找到FIRST(α)中的所有终结符号a,将A->α加入M[A, a]中。
(2)如果ε在FIRST(α)中,则对于每个b∈FOLLOW(A),将A->α加入M[A, b]中。
根据上述规则,我们可以得到预测分析表如下:
| + | * | i | ( | ) | $ |
| -------- | ------- | ------ | ------ | ------ | ------ |
| E -> TE' | | E -> TE' | E -> TE' | | |
| | T' -> *FT' | | | T' -> ε | T' -> ε |
| T -> FT' | | T -> FT' | T -> FT' | | |
| | F -> ε | F -> i | F -> (E) | | |
2. 预测分析过程
有了预测分析表,我们就可以进行预测分析了。例如,对于输入串i*(i+i):
| 栈 | 剩余输入串 | 推导式 |
| -------- | --------------- | ------------ |
| $ | i*(i+i)$ | - |
| E | i*(i+i)$ | E -> TE' |
| T | i*(i+i)$ | T -> FT' |
| F | i*(i+i)$ | F -> i |
| i | *(i+i)$ | - |
| * | (i+i)$ | - |
| T | (i+i)$ | T -> FT' |
| F | (i+i)$ | F -> (E) |
| (E) | i+i)$ | - |
| E | i+i)$ | E -> TE' |
| T | i+i)$ | T -> FT' |
| F | i+i)$ | F -> i |
| i | +i)$ | - |
| + | i)$ | - |
| E | i)$ | E -> TE' |
| T | i)$ | T -> FT' |
| F | i)$ | F -> i |
| i | )$ | - |
| ) | $ | - |
| | $ | - |
最后,我们得到了一个推导式E -> TE' -> T -> FT' -> F -> (E) -> E -> TE' -> T -> FT' -> F -> i,说明输入串i*(i+i)符合文法G的语法规则。
阅读全文