编译原理第3章文法和语言

第3章文法和语言 第1题

文法G＝({A,B,S},{a,b,c},P,S)其中P为： S→Ac|aB A→ab B→bc

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

L(G[S])={abc} 第2题

文法G[N]为： N→D|ND

D→0|1|2|3|4|5|6|7|8|9 G[N]的语言是什么？ 答案:

G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD....=>NDDDD...D=>D......D 或者：允许0开头的非负整数？ 第３题

为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。答案： G[S]:

S->S+D|S-D|D

D->0|1|2|3|4|5|6|7|8|9 第4题

已知文法G[Z]： Z→aZb|ab

写出L(G[Z])的全部元素。 答案：

Z=>aZb=>aaZbb=>aaa..Z...bbb=>aaa..ab...bbb L(G[Z])={anbn|n>=1} 第5题

写一文法，使其语言是偶正整数的集合。要求： (1)允许0打头； (2)不允许0打头。 答案：

(1)允许0开头的偶正整数集合的文法 E→NT|D T→NT|D

N→D|1|3|5|7|9 D→0|2|4|6|8

(2)不允许0开头的偶正整数集合的文法 E→NT|D T→FT|G

N→D|1|3|5|7|9 D→2|4|6|8 F→N|0 G→D|0 第6题

已知文法G：

<表达式>::=<项>｜<表达式>＋<项> <项>::=<因子>｜<项>*<因子> <因子>::=（<表达式>）｜i

试给出下述表达式的推导及语法树。 （５）i+(i+i) （６）i+i*i

答案：

(5)<表达式>

=><表达式>＋<项> =><表达式>＋<因子>

=><表达式>＋（<表达式>）

=><表达式>＋（<表达式>＋<项>） =><表达式>＋（<表达式>＋<因子>） =><表达式>＋（<表达式>＋i） =><表达式>＋（<项>＋i） =><表达式>＋（<因子>＋i） =><表达式>＋（i＋i） =><项>＋（i＋i） =><因子>＋（i＋i） =>i＋（i＋i） (6)<表达式>

=><表达式>＋<项>

=><表达式>＋<项>*<因子> =><表达式>＋<项>*i =><表达式>＋<因子>*i =><表达式>＋i*i =><项>＋i*i =><因子>＋i*i =>i＋i*i <表达式>

<表达式>+<项> <因子> <表达式>

<表达式>+<项> <因子> i <项>

<因子> i <项> <因子> i （)

<表达式>

<表达式>+<项> <项>*<因子> <因子>i <项> <因子> i i

第7题

证明下述文法G[〈表达式〉]是二义的。 〈表达式〉∷=a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉 〈运算符〉∷=+|-|*|/ 答案：

可为句子a+a*a构造两个不同的最右推导: 最右推导1〈表达式〉〈表达式〉〈运算符〉〈表达式〉 〈表达式〉〈运算符〉a 〈表达式〉*a 〈表达式〉〈运算符〉〈表达式〉*a 〈表达式〉〈运算符〉a*a 〈表达式〉+a*a a+a*a

最右推导2〈表达式〉〈表达式〉〈运算符〉〈表达式〉 〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉 〈表达式〉〈运算符〉〈表达式〉〈运算符〉a 〈表达式〉〈运算符〉〈表达式〉*a 〈表达式〉〈运算符〉a*a 〈表达式〉+a*a a+a*a

第8题

文法G[S]为： S→Ac|aB A→ab B→bc

该文法是否为二义的？为什么？ 答案： 对于串abc

(1)S=>Ac=>abc(2)S=>aB=>abc

即存在两不同的最右推导。所以，该文法是二义的。 或者：

对输入字符串abc，能构造两棵不同的语法树，所以它是二义的。 第9题

考虑下面上下文无关文法： S→SS*|SS+|a

(1)表明通过此文法如何生成串aa+a*，并为该串构造语法树。 (2)G[S]的语言是什么？ 答案：

(1)此文法生成串aa+a*的最右推导如下

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

(2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。 S A c a b S a B b c S S S* S S+a a a 第10题

文法S→S(S)S|ε

(1)生成的语言是什么？

(2)该文法是二义的吗？说明理由。 答案：

（１）嵌套的括号

（２）是二义的，因为对于（）（）可以构造两棵不同的语法树。 第11题

令文法G[E]为： E→T|E+T|E-T T→F|T*F|T/F F→(E)|i

证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。 答案：

此句型对应语法树如右，故为此文法一个句型。 或者：因为存在推导序列:E=>E+T=>E+T*F，所 以E+T*F句型

此句型相对于E的短语有:E+T*F；相对于T的短语 有T*F

直接短语为：T*F 句柄为：T*F 第13题

一个上下文无关文法生成句子abbaa的推导树如下： (1)给出串abbaa最左推导、最右推导。

(2)该文法的产生式集合P可能有哪些元素？ (3)找出该句子的所有短语、直接短语、句柄。 B a S A B S a S B A εb b a

答案：

(1)串abbaa最左推导:

S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa 最右推导：

S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa (2)产生式有：S→ABS|Aa|εA→a B→SBB|b 可能元素有：εaa ab abbaa aaabbaa…… (3)该句子的短语有： a是相对A的短语 ε是相对S的短语 b是相对B的短语 εbb是相对B的短语 aa是相对S的短语

aεbbaa是相对S的短语 直接短语有：aεb 句柄是：a 第14题

给出生成下述语言的上下文无关文法： （1）{anbnambm|n，m>=0} （2）{1n0m 1m0n|n，m>=0}

（3）{WaWr|W属于{0|a}*，Wr表示W的逆} 答案： （１） S→AA A→aAb|ε （２） S→1S0|A A→0A1|ε （３）

S→0S0|1S1|ε 第16题

给出生成下述语言的三型文法： (1){an|n>=0}

(2){anbm|n,m>=1} (3){anbmck|n,m,k>=0} 答案： (1)S→aS|ε (2) S→aA A→aA|B B→bB|b (3)

A→aA|B

B→bB|C C→cC|ε 第17题

习题７和习题11中的文法等价吗？ 答案： 等价。 第18题

解释下列术语和概念： （１）字母表

（２）串、字和句子 （３）语言、语法和语义 答案：

（１）字母表：是一个非空有穷集合。 （２）串：符号的有穷序列。 字：字母表中的元素。

句子：如果Z x,x∈V*T则称x是文法G的一个句子。+

（３）语言：它是由句子组成的集合，是由一组记号所构成的集合。程序设计的语言就是所

有该语言的程序的全体。语言可以看成在一个基本符号集上定义的，按一定规 则构成的一切基本符号串组成的集合。

语法：表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。

语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。 附加题

问题1：

给出下述文法所对应的正规式： S→0A|1B A→1S|1 B→0S|0 答案：

R=(01|10)(01|10)* 问题2：

已知文法G[A]，写出它定义的语言描述 G[A]:A→0B|1C B→1|1A|0BB C→0|0A|1CC 答案:

G[A]定义的语言由0、1符号串组成，串中0和1的个数相同. 问题3：

给出语言描述，构造文法.

构造一文法,其定义的语言是由算符+,*,(,)和运算对象a构成的算术表达式的集合. 答案一：

G[E]E→E+T|T T→T*F|F F→(E)|a 答案二：

G[E]E→E+E|E*E|(E)|a 问题4：

已知文法G[S]: S→dAB A→aA|a B→ε|bB

相应的正规式是什么？G[S]能否改写成为等价的正规文法？ 答案：

正规式是daa*b*；

相应的正规文法为(由自动机化简来)： G[S]:S→dA A→a|aB B→aB|a|b|bC C→bC|b

也可为(观察得来):G[S]:S→dA A→a|aA|aB B→bB|ε 问题5：

已知文法G： E→E+T|E-T|T T→T*F|T/F|F F→(E)|i

试给出下述表达式的推导及语法树 (1)i; (2)i*i+i (3)i+i*i (4)i+(i+i) 答案：

(1)E=>T=>F=>i

(2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i (3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i

(4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T) =>i+(i+T)=>i+(i+F)=>i+(i+i) (2) (3) (4) E+T i T F i F i E E+T E+T i T F

F (E) i T F i F

问题6：

已知文法G[E]: E→ET+|T T→TF*|F F→F^|a

试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄. 答案：

该句型对应的语法树如下： 该句型相对于E的短语有FF^^* 相对于T的短语有FF^^*,F 相对于F的短语有F^;F^^ 简单短语有F;F^ 句柄为F. 问题7：

适当变换文法，找到下列文法所定义语言的一个无二义的文法： S→SaS.SbS.ScS.d 答案：

该文法的形式很典型，可以先采用优先级联规则变换文法，然后再规定结合性对文法做 进一步变换，即可消除二义性。

设a、b和c的优先级别依次增高，根据优先级联规则将文法变换为： S→SaS.A A→AbA.C C→CcC.d

规定结合性为左结合，进一步将文法变换为： S→SaA.A A→AbC.C C→CcF.F F→d

该文法为非二义的。

问题8：

构造产生如下语言的上下文无关文法： （1）{anb2ncm|n，m≥0} （2）{anbmc2m|n，m≥0} （3）{ambn.m≥n}

（4）{a m b n c p d q.m+n=p+q} （5）{uawb.u,w∈{a,b}*∧|u|=|w|} 答案： （1）根据上下文无关文法的特点，要产生形如anb2ncm的串，可以分别产生形如anb2n和

形如cm的串。设计好的文法是否就是该语言的文法？严格地说，应该给出证明。但若不是

特别指明，通常可以忽略这一点。

对于该语言，存在一个由以下产生式定义的上下文无关文法G[S]： S→AB

A→ε.aAbb B→ε.cB

（2）同样，要产生形如anbmc2m的串，可以分别产生形如an和形如bmc2m的串。对于该语

言，存在一个由以下产生式定义的上下文无关文法G[S]： S→AB A→ε.aA B→ε.bBcc

（3）考虑在先产生同样数目的a,b，然后再生成多余的a。以下G[S]是一种解法： S→aSb.aS.ε

（4）以下G[S]是一种解法： S→aSd.A.D A→bAd.B D→aDc.B B→bBc.ε

注：a不多于d时，b不少于c；反之，a不少于d时，b不多于c。前一种情形通过 对应A，后一种情形对应D。 （5）以下G[S]是一种解法： S→Ab A→BAB.a

B→a.b 问题9：

下面的文法G(S)描述由命题变量p、q，联结词∧（合取）、∨（析取）、.（否定）构 成的命题公式集合： S→S∨T.T T→T∧F.F F→.F.p.q

试指出句型.F∨.q∧p的直接短语（全部）以及句柄。 答案：

直接短语：p，q，.F 句柄：.F 问题10：

设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及A+. 答案：

x0=(aaa)0=ε|x0|=0 xx=aaaaaa|xx|=6

x5=aaaaaaaaaaaaaaa|x5|=15

A+=A1∪A2∪….∪A n∪…={a,aa,aaa,aaaa,aaaaa…}

A*=A0∪A1∪A2∪….∪A n∪…={ε,a,aa,aaa,aaaa,aaaaa…} 问题11：

令Σ={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，

（xy）3 答案：

xy=abcb|xy|=4

xyz=abcbaab|xyz|=7

(xy)3=(abcb)3=abcbabcbabcb|(xy)3|=12 问题12：

已知文法G[Z]：Z∷=U0∣V1、U∷=Z1∣1、V∷=Z0∣0,请写出全部由此文 法描述的只含有四个符号的句子。 答案：

Z=>U0=>Z10=>U010=>1010 Z=>U0=>Z10=>V110=>0110 Z=>V1=>Z00=>U000=>1000 Z=>V1=>Z00=>V100=>0100 问题13：

已知文法G[S]：S∷=AB A∷=aA︱εB∷=bBc︱bc,写出该文法描述的语言。 答案：

A∷=aA︱ε描述的语言:{an|n>=0} B∷=bBc︱bc描述的语言:{,bncn|n>=1} L(G[S])={anbmcm|n>=0,m>=1} 问题14：

已知文法E∷=T∣E+T∣E-T、T∷=F∣T*F∣T/F、F∷=(E)∣i，写出该文法的开 始符号、终结符号集合VT、非终结符号集合VN。 答案：

开始符号：E

VT={+,-,*,/,（,）,i} VN={E,F,T} 问题15：

设有文法G[S]：S∷=S*S|S+S|(S)|a，该文法是二义性文法吗？ 答案：

根据所给文法推导出句子a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。 问题16：

写一文法，使其语言是奇正整数集合。 答案：

A::=1|3|5|7|9|NA

N::=N0|N1|N2|N3|N4|N5|N6|N7|N8|N9| N::=0|1|2|3|4|5|6|7|8|9 S S*S S+S a a a S S+S a S*S a a

第4章词法分析 第1题

构造下列正规式相应的DFA. （１）1(0|1)*101

（２）１(1010*|1(010)*1）*0 （３）a((a|b)*|ab*a)*b （４）b((ab)*|bb)*ab 答案：

(1)先构造NFA：

用子集法将NFA确定化 . 0 1 X . A A A AB AB AC AB AC A ABY ABY AC AB 除X，A外，重新命名其他状态，令AB为B、AC为C、ABY为D，因为D含有Y（NFA 的终态），所以D为终态。 . 0 1 X . A A A B B C B C

A D D C B

DFA的状态图：: (2)先构造NFA：

用子集法将NFA确定化 ε 0 1 X X T0=X A A ABFL T1=ABFL Y CG Y Y CG CGJ T2=Y T3=CGJ DH K DH DH K

ABFKL T4=DH EI EI

ABEFIL T5=ABFKL Y CG

T6=ABEFIL EJY CG EJY

ABEFGJLY

T7=ABEFGJLY EHY CGK EHY

ABEFHLY CGK

ABCFGJKL T8=ABEFHLY EY CGI EY

ABEFLY CGI CGJI

T9=ABCFGJKL DHY CGK DHY DHY

T10=ABEFLY EY CG

T11=CGJI DHJ K DHJ DHJ

T12=DHY EI

T13=DHJ EIK EIK

ABEFIKL

T14=ABEFIKL EJY CG X 1 A εB

1 C 0 D 1 E 0 ε

F 1 G 0 H 1 I 0 J 1 K L εε

4 3 5 4 2 3 5 2 3

DFA的状态图： X A b εB a

F b G b H E ε Y a ε

C D bε I b ε ε ε ε

0 b 1 b 2 a 4 5 3 b b a b a b

第２题 已知NFA＝（｛x,y,z｝,{0,1},M,{x},{z}），其中：M(x,0)={z}，M(y,0)={x,y}，,M(z,0)={x,z}， M(x,1)={x}，M(y,1)=φ，M(z,1)={y}，构造相应的DFA。 答案：

先构造其矩阵 0 1 x z x y x,y z x,z y

用子集法将NFA确定化： 0 1 x z x z xz y xz xz xy y xy xy xyz x xyz xyz xy

将x、z、xz、y、xy、xyz重新命名，分别用A、B、C、D、E、F表示。因为B、C、F 中含有z，所以它为终态。 0 1 A B A B

C D C C E D E E F A F F E

DFA的状态图： A 0 1 0 F E D 0 B 1 0 1 0 1 0 1 C

第3题

将下图确定化： 答案：

用子集法将NFA确定化： . 0 1 S VQ QU VQ VZ QU QU V QUZ VZ Z Z V Z . QUZ VZ QUZ Z Z Z

重新命名状态子集，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。 . 0 1 S A B A C B B D E C F

状态转换表1 a b X124 1234 124Y 1234 1234 124Y 124Y 1234 124Y

状态转换表2 a B 1 2 3 2 2 3 3 2 3

由于2与3完全一样，将两者合并，即见下表 a b 1 2 3 2 3 a b X12 12 12Y 12 12 12Y 12Y 12 12Y

可化简得下表 a b 1 2 3 2 2 3

得DFA图

两图完全一样，故两个自动机完全一样，所以两个正规文法等价。 对相应正规文法,令A对应1，B对应2 故为： A→aA|bB|b B→aA|bB|b

即为S→aS|bS|B,此即为所求正规文法。 问题6：

考虑正规表达式r=a*b(a|b)，构造可以生成语言L(r)的一个正规文法。 答案： S→a*b(a|b)

变换为S→aA,S→b(a|b),A→aA,A→b(a|b)

变换为S→aA,S→bB,B→(a|b),A→aA,A→bC,C→(a|b)

变换为S→aA,S→bB,B→a,B→b,A→aA,A→bC,C→a,C→b 所以，一个可能的正规文法为G[S]：

S→aA,S→bB,B→a,B→b,A→aA,A→bC,C→a,C→b 或表示为：

S→aA|bB,B→a|b,A→aA|bC,C→a|b

（适当等价变换也可以，但要作说明，即要有步骤）

问题7：

考虑下图所示的NFA N，构造可以生成语言L(N)的一个正规文法。 答案： G[P]:

P→0 P.1 P.1 Q Q→0 R.1 R R→ε 问题8：

考虑如下文法G[S]： S→0S.1S.1A A→0B.1B B→ε

a)试构造语言为L(G)的一个正规表达式。 b)试构造语言为L(G)的一个有限自动机。 答案： a)

由A→0B，B→ε得A→0; 由A→1B，B→ε得A→1; 由A→0，A→1得A→0.1;

由S→1A，A→0.1得S→1(0.1); 由S→1A，A→0.1得S→1(0.1); 由S→0S，S→1(0.1)得S→0*1(0.1); 由S→1S，S→1(0.1)得S→1*1(0.1);

由S→0*1(0.1)，S→1*1(0.1)得S→0*1(0.1).1*1(0.1); 所以，一个可能的正规表达式为：

0*1(0.1).1*1(0.1) b)

第5章自顶向下语法分析方法 第1题

对文法G[S] S→a|∧|(T) T→T,S|S

(1)给出(a,(a,a))和(((a,a),∧,(a)),a)的最左推导。

(2)对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。 (3)经改写后的文法是否是LL(1)的?给出它的预测分析表。

(4)给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。 答案：

(1)对(a,(a,a)的最左推导为： S(T) (T,S) (S,S) (a,S) (a,(T)) (a,(T,S)) (a,(S,S)) (a,(a,S)) (a,(a,a))

对(((a,a),∧,(a)),a)的最左推导为： S(T) (T,S) (S,S) ((T),S) ((T,S),S) ((T,S,S),S) ((S,S,S),S) (((T),S,S),S) (((T,S),S,S),S) (((S,S),S,S),S) (((a,S),S,S),S) (((a,a),S,S),S) (((a,a),∧,S),S) (((a,a),∧,(T)),S) (((a,a),∧,(S)),S)

(((a,a),∧,(a)),S) (((a,a),∧,(a)),a) (2)改写文法为： 0)S→a 1)S→∧ 2)S→(T) 3)T→S N 4)N→,S N 5)N→ε 非终结符 FIRST集 FOLLOW集 S

{a,∧,(} {#,,,)} T

{a,∧,(} {)}.... N {,,ε}. {)}....

对左部为N的产生式可知： FIRST（→,S N）={，} FIRST（→ε）={ε} FOLLOW（N）={)}

由于SELECT(N→,S N)∩SELECT(N→ε)={，}∩{)}= 所以文法是LL(1)的。

预测分析表（Predicting Analysis Table） a ∧ ( ) , # S →a →∧ →(T) T →S N →S N →S N N

→ε →,S N

也可由预测分析表中无多重入口判定文法是LL(1)的。

(3)对输入串（a,a）#的分析过程为： 栈（STACK） 当前输入符

（CUR_CHAR） 剩余输入符

（INOUT_STRING） 所用产生式

（OPERATION） #S #)T( #)T #)NS #)Na #)N #)NS, #)NS #)Na #)N #) # ( ( a a a , , a a ) ) #

a,a)#... a,a)#... ,a)#... ,a)#... ,a)#... a)#... a)#... )#... )#... #... #...

S→(T) .

T→SN S→a .

N→,SN . S→a .

N→ε

可见输入串（a,a）#是文法的句子。

第3题

已知文法G[S]： S→MH|a H→LSo|ε K→dML|ε L→eHf M→K|bLM

判断G是否是LL(1)文法，如果是，构造LL(1)分析表。 答案：

文法展开为： 0）S→M H 1）S→a 2）H→L S o 3）H→ε 4）K→d M L 5）K→ε 6）L→e H f 7）M→K 8）M→b L M 非终结符 FIRST集 FOLLOW集 S

{a,d,b,ε,e} {#,o}........ M

{d,ε,b}.... {e,#,o}...... H

{ε,e}...... {#,f,o}...... L

{e}......... {a,d,b,e,o,#} K

{d,ε}...... {e,#,o}......

对相同左部的产生式可知：

SELECT(S→M H)∩SELECT(S→a)={d,b,e，#,o}∩{a}= SELECT(H→L S o)∩SELECT(H→ε)={e}∩{#,f,o}= SELECT(K→d M L)∩SELECT(K→ε)={d}∩{e,#,o}= SELECT(M→K)∩SELECT(M→b L M)={d，e,#,o}∩{b}= 所以文法是LL(1)的。

本文来源：https://www.bwwdw.com/article/xbb8.html