编译原理 – 文法与语言练习题

1. 文法G＝({A,B,S},{a,b,c},P,S), 其中P 为：

       S→Ac|aB

       A→ab

       B→bc

写出L(G[S])的全部元素。

答案：

全部元素只有一个，即abc

2. 文法G[S]为：

        S→Ac|aB

        A→ab

        B→bc

该文法是否为二义的？为什么？

答案：

该文法是二义的，因为可以根据该文法构造以下两棵不同的文法树：

3. 考虑下面上下文无关文法：

    S→SS*|SS+|a

(1)表明通过此文法如何生成串aa+a*，并为该串构造语法树。

(2)G[S]的语言是什么？

答案：

(1)该文法生成串aa+a*：

S->SS*->Sa*->SS+a*->Sa+a*->aa+a*

语法树为：

(2)该语言是后置+、*运算符的表达式

4. 给出生成下述语言的三型文法（形如A->aB|a）：

 (1) {aⁿbⁿ | n >=0 }                    

 (2) { a^mbⁿ | m≥n ≥0 }  

 (3)  {uawb | u,w ∈{a,b}*∧|u|=|w| }           

 (4) { aⁿb^m | n≥2m ≥0 }  

 (5) { aⁿb^m | n ≥ 0, m ≥ 0,3n≥m≥2n }   

 (6) {ww^R|w∈{a,b}*，w^R 表示w的逆}

 (7) {uvwv^R|u,v,w∈{a,b}⁺=1 }

答案：

(1)G[S]:S-> ε |aSb

(2)G[S]:S-> ε |aSb|aS

(3) G[S]:S-> Ab

A->a|aAa|bAb|aAb|bAa

(4)G[S]:S-> ε |a|aS|aaSb

(5) G[S]:S-> ε |aSbb|aSbbb

(6)G[S]:S-> ε |aSa|bSb

(7)

5. 给出生成下述语言的三型文法：

 (1)  {aⁿ | n >=0 }

 (2)  { aⁿb^m | n,m>=1 }

 (3)  {aⁿb^mc^k | n,m,k>=0 }

答案：

(1) G[S]:S-> ε |Sa|a

(2) G[S]:S->aAb

A->a|b| ε

(3)G[S]:S-> ε |aS|bS|cS