对文法G(S): S→(T) | aS | a T→T,S | S (1)消去文法的左递归和提取公共左因子; (2)构造化简后的文法中各非终结符的First和Follow集合
时间: 2024-03-21 18:41:45 浏览: 79
好的,我来回答你的问题。
(1)消去文法的左递归和提取公共左因子:
首先,我们可以将G(S)改写为如下形式:
```
S → (T)S' | aS'
S' → ,S | ε
T → TS' | S
```
接下来,我们来消除左递归:
```
S → (T)S' | aS'
S' → ,S | ε
T → ST'
T' → ,T' | ε
```
然后,我们来提取公共左因子:
```
S → aS'' | (T)S'
S' → ,S | ε
T → ST'
T' → ,T' | ε
S'' → S' | ε
```
(2)构造化简后的文法中各非终结符的First和Follow集合:
首先,我们来计算非终结符S''的First集合,根据定义,S''的First集合为{a, (}。
接下来,我们来计算非终结符S的Follow集合,根据定义,S的Follow集合为{), $}。其中,$表示输入串的结束符号。
然后,我们来计算非终结符S的First集合,根据产生式得知,S的First集合为{a, (}。
接着,我们来计算非终结符S'的First集合,根据产生式得知,S'的First集合为{,, ε}。
然后,我们来计算非终结符T的First集合,根据产生式得知,T的First集合为{a, (}。
接着,我们来计算非终结符T'的First集合,根据产生式得知,T'的First集合为{,, ε}。
最后,我们来计算非终结符S''的Follow集合,根据定义和产生式得知,S''的Follow集合为{,, ), $}。
综上,化简后文法中各非终结符的First和Follow集合如下:
```
First(S'') = {a, (}
Follow(S'') = {,, ), $}
First(S) = {a, (}
Follow(S) = {), $}
First(S') = {,, ε}
Follow(S') = {), $}
First(T) = {a, (}
Follow(T) = {,), $}
First(T') = {,, ε}
Follow(T') = {), $}
```
阅读全文