将S—>S S + | S S * | a 以及串aa=a* 改写为LL文法

将S—>S S | S S * | a改写为LL文法的步骤如下：

1. 消除左递归

S -> aS'
S' -> SS' | ε
S -> S*

2. 提取左公因子

S -> aS'
S' -> S'S'' | ε
S'' -> *S | ε
S -> S*

将串aa=a*改写为LL文法的步骤如下：

1. 加入起始符号S和结束符号#

S -> A#
A -> aA | #

2. 引入新变量

S -> A#
A -> aB | #
B -> aB | #

3. 提取左公因子

S -> aA'
A' -> A | #
A -> B | #
B -> aB | #

这样就得到了LL文法。

相关问题

正则表达式(a|b)*(aa|bb)(a|b)* 改写成ll1文法 并给出select集

这是一个正则表达式，可以转化为以下的 LL(1) 文法：

S -> AB
A -> aA | bA | ε
B -> aaC | bbC
C -> aC | bC | ε

其中 `S` 是起始符号，`A`、`B`、`C` 是非终结符号，`a`、`b` 是终结符号，`ε` 表示空串。

对于该文法，其 SELECT 集合如下：

SELECT(S -> AB) = {a, b}
SELECT(A -> aA) = {a}
SELECT(A -> bA) = {b}
SELECT(A -> ε) = {a, b, aa, bb}
SELECT(B -> aaC) = {a}
SELECT(B -> bbC) = {b}
SELECT(C -> aC) = {a}
SELECT(C -> bC) = {b}
SELECT(C -> ε) = {a, b}

将正则表达式(a|b)*(aa|bb)(a|b)* 改写成ll1文法 并给出 first集 follow集和select集还有预测分析表

这是一个正则表达式，可以转化为以下的 LL(1) 文法：

S -> AB
A -> aA | bA | ε
B -> aaC | bbC
C -> aD | bE
D -> aC | bC | ε
E -> aC | bC | ε

其中 `S` 是起始符号，`A`、`B`、`C`、`D`、`E` 是非终结符号，`a`、`b` 是终结符号，`ε` 表示空串。

该文法的 FIRST 集合和 FOLLOW 集合如下：

FIRST(S) = {a, b}
FIRST(A) = {a, b, ε}
FIRST(B) = {aa, bb}
FIRST(C) = {a, b}
FIRST(D) = {a, b, ε}
FIRST(E) = {a, b, ε}

FOLLOW(S) = {$}
FOLLOW(A) = {aa, bb}
FOLLOW(B) = {a, b}
FOLLOW(C) = {a, b, aa, bb}
FOLLOW(D) = {a, b, aa, bb}
FOLLOW(E) = {a, b, aa, bb}

该文法的 SELECT 集合如下：

SELECT(S -> AB) = {a, b}
SELECT(A -> aA) = {a}
SELECT(A -> bA) = {b}
SELECT(A -> ε) = {aa, bb}
SELECT(B -> aaC) = {aa}
SELECT(B -> bbC) = {bb}
SELECT(C -> aD) = {a}
SELECT(C -> bE) = {b}
SELECT(D -> aC) = {a}
SELECT(D -> bC) = {b}
SELECT(D -> ε) = {aa, bb}
SELECT(E -> aC) = {a}
SELECT(E -> bC) = {b}
SELECT(E -> ε) = {aa, bb}

该文法的预测分析表如下：

| 非终结符 | a | b | aa | bb | $ |
| :------: | :---: | :---: | :---: | :---: | :--: |
| S | A | B | | | √ |
| A | a | b | ε | ε | |
| B | aaC | bbC | | | |
| C | aD | bE | | | |
| D | aC | bC | ε | ε | |
| E | aC | bC | ε | ε | |

其中 `√` 表示对应的产生式可以推导出对应的终结符，空表示无法推导。