文法S->AB A->bB|Aa B->Sb|a的预测分析表
时间: 2023-12-30 14:06:48 浏览: 175
算符优先分析法.doc.rar_E->E+T_E->E+T E->E—T_GME_doc_编译原理
5星 · 资源好评率100%
首先,我们需要求出该文法的FIRST集和FOLLOW集。
FIRST集:
- FIRST(A) = {b, a}
- FIRST(B) = {a, b}
- FIRST(S) = {a, b}
FOLLOW集:
- FOLLOW(A) = {$, b}
- FOLLOW(B) = {$, b}
- FOLLOW(S) = {$}
接下来,我们可以使用预测分析表的构造方法,对该文法进行预测分析表的构造。
| 非终结符 | a | b | $ |
| :-------: | :-: | :-: | :-: |
| S | S→A | S→B | |
| A | A→a | A→b | |
| B | B→a | B→S | |
预测分析表中的每个格子都对应着一条产生式,其中行表示当前处理的非终结符,列表示当前读入的终结符。例如,当处理S非终结符且读入了终结符a时,我们应该使用S→A这个产生式进行推导。
当我们使用这个预测分析表对输入串进行分析时,首先将输入串中的第一个终结符读入,然后查找对应的行和列,找到对应的产生式进行推导。如果遇到空串,直接跳过。如果无法找到对应的产生式,说明该输入串不符合该文法。
例如,对于输入串abab,分析过程如下:
| 栈 | 剩余输入 | 推导所用产生式 |
| :---: | :------: | :------------: |
| S | abab | S→A |
| A | bab | A→b |
| B | ab | B→a |
| a | b | |
| B | b | B→S |
| S | b | S→B |
| B | ε | |
| S | ε | |
因此,该输入串符合该文法。
阅读全文