设文法G(S): S→Sb S→Ab S→b A→Aa A→a (1)消除左递归和回溯; (5分) (2)构造相应的FIRST和FOLLOW集合;(5分) (3)构造预测分析表 ;(5分) (4)请使用预测分析法完成对串aabbb和bbbb的语法分析过程 。(5分)
时间: 2023-10-05 11:05:26 浏览: 92
(1) 消除左递归和回溯:
消除左递归:
S → AbS'
S' → bS' | ε
A → aA'
A' → aA' | ε
消除回溯:
S → bS' | aAS'
S' → bS' | ε
A → aA'
A' → aA' | ε
(2) 构造相应的FIRST和FOLLOW集合:
FIRST(S) = {a, b}
FIRST(S') = {b, ε}
FIRST(A) = {a}
FIRST(A') = {a, ε}
FOLLOW(S) = {$}
FOLLOW(S') = {b, $}
FOLLOW(A) = {b}
FOLLOW(A') = {b}
(3) 构造预测分析表:
| a | b | $
----|---|---|--
S | aAS' | bS' |
S' | | bS' | ε
A | aA' | |
A' | aA' | | ε
(4) 使用预测分析法完成对串aabbb和bbbb的语法分析过程:
对于串aabbb:
| | | | | | | | | | |
|--|--|--|--|--|--|--|--|--|--|
|步骤| | | | | | | | | |
|1|STACK$|S | | | | | | | |
|2| | aAS' | | | | | | | |
|3| | aA' | | | | | | | |
|4| | a | | | | | | | |
|5| | | | | | | | | |
|6| | | bS' | | | | | | |
|7| | | | bS' | | | | | |
|8| | | | ε | | | | | |
|9| | | | | bS' | | | | |
|10| | | | | | bS' | | | |
|11| | | | | | | ε | | |
|12| | | | | | | | $ | |
对于串bbbb:
| | | | | | | | | | |
|--|--|--|--|--|--|--|--|--|--|
|步骤| | | | | | | | | |
|1|STACK$|S | | | | | | | |
|2| | bS' | | | | | | | |
|3| | ε | | | | | | | |
|4| | | $ | | | | | | |