设文法G(A): A→B e B→B b | a (1)判定该文法是否为LL(1)文法,说明理由。(5分) (2)若不是则将其转化为LL(1)文法,最后给出其分析表;(10分) (3)请完成对串aabbe的语法分析过程 。(5分)
时间: 2023-08-23 18:04:57 浏览: 30
(1) 该文法不是LL(1)文法,因为在B产生式的选择上存在二义性,即当下一个输入符号为b时,无法确定应该使用B→Bb还是B→a产生式。
(2) 将文法G(A)转化为LL(1)文法的步骤如下:
首先,消除左递归:
A → B e
B → a B'
B' → b B' | ε
然后,求出FIRST集和FOLLOW集:
FIRST(A) = {a}
FIRST(B) = {a}
FIRST(B') = {b, ε}
FOLLOW(A) = {$}
FOLLOW(B) = {e, b}
FOLLOW(B') = {e}
接着,构造LL(1)分析表:
| | a | b | e | $ |
|----|-----|-----|-----|-----|
| A | A → B e | | | |
| B | B → a B' | | | |
| B' | | B' → b B' | B' → ε | |
最后,进行语法分析。
(3) 对串aabbe进行语法分析的过程如下:
输入符号串:aabbe$
初始符号栈:$A
初始输入串:aabbe$
| 预测输入符号 | 当前符号栈 | 输入符号串 | 所用产生式 |
|--------------|-------------|------------|------------|
| a | $A | aabbe$ | A → Be |
| a | $B e | aabbe$ | B → a B' |
| a | $a B' e | aabbe$ | |
| | $a B' e | abbe$ | |
| a | $a B' | abbe$ | |
| a | $a B' b B' | abbe$ | B' → b B' |
| a | $a B' b B' | bbe$ | |
| a | $a B' b B' | be$ | B' → ε |
| a | $a B' | be$ | |
| | $a B' | e$ | |
| | $B e | e$ | B → ε |
| | $A | e$ | A → Be |
| | $B e | $ | |
| | $A | $ | |
因此,该输入符号串aabbe可以被成功地语法分析。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)