将S—>S S + | S S * | a 以及串aa=a* 改写为LL文法
时间: 2024-05-19 10:15:17 浏览: 20
将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
该正则表达式可以改写为以下 LL(1) 文法:
```
S -> A (aa | bb) B
A -> aA | bA | ε
B -> a | b
```
其中,非终结符 S 对应原正则表达式中的 (a|b)*(aa|bb)(a|b) 部分,非终结符 A 对应 (a|b)* 部分,非终结符 B 对应 (a|b) 部分。注意,由于原正则表达式中允许空串出现,因此需要在文法中对 A 非终结符的产生式中加入 ε 产生式。