简答题(30.0分) 9将文法G改写成等价的LL(1)文法。并构造相应的 预测分析表。 G[S]: S→S*aTlaTl'aT T→+aT+a (1)将上述文法进行改造。 (2)判断(1)文法是否为LL(1)文法。 (3)构造预测分析表。 (4)写出对符号串a+a的分析过程。

(1) 改写后的文法如下：

S  -> T S'
S' -> * a T l S' | ε
T  -> + a T' 
T' -> a | ε

(2) 判断是否为LL(1)文法：
- 消除左递归：已经消除了左递归
- 提取左公因子：

S  -> T S'
S' -> * a T l S' | ε
T  -> + a T' 
T' -> a T'' 
T''-> ε

- 构造FIRST集和FOLLOW集：

FIRST(S) = {+, ε}

FIRST(S') = {*, ε}

FIRST(T) = {+}

FIRST(T') = {a, ε}

FIRST(T'') = {ε}

FOLLOW(S) = {$}

FOLLOW(S') = {l, $}

FOLLOW(T) = {l, *}

FOLLOW(T') = {l, *}

FOLLOW(T'') = {l, *}

- 构造预测分析表：

| | + | * | a | l | $ |
|---|-------|-------|-------|-------|-------|
| S | | | S -> T S' | | |
| S'| ε | S' -> * a T l S' | | S' -> ε | S' -> ε |
| T | T -> + a T' | | | | |
| T'| ε | | T' -> a T'' | T' -> ε | T' -> ε |
|T''| ε | | T''-> ε | T''-> ε | T''-> ε |

(4) 对符号串a+a的分析过程如下：

| 栈 | 剩余输入 | 动作 |
|----------|----------|--------------------------|
| $S | a+a$l | S -> T S' |
| $T S' | a+a$l | T -> + a T' |
| $+aT' S' | a+a$l | T'-> a T'' |
| $aT'' S' | +a+l | 匹配a，弹出栈顶符号 |
| $T'' S' | +a+l | 匹配+，弹出栈顶符号 |
| $S' | a+l | S'->* a T l S' |
| $*aTlS' | a+l | 匹配a，弹出栈顶符号 |
| $TlS' | +l | 匹配*，弹出栈顶符号 |
| $S' | l | 匹配l，弹出栈顶符号 |
| $S' | +l | 匹配ε，弹出栈顶符号 |
| $S' | $ | 匹配ε，弹出栈顶符号 |
| $ | $ | 分析成功 |