编译原理与实践第三章答案.pdf

编译原理与实践第三章答案

TheexercisesofChapterThree

3.2GiventhegrammarA→AA|(A)|ε

a.Describethelanguageitgenerates;

b.Showthatitisambiguous.

[Solution]:

a.Generatesastringofbalancedparenthesis,includingthe

emptystring.

b.parsetreesof():

3.3Giventhegrammar

exp→expaddopterm|term

addop→+|-

term→termmulopfactor|factor

mulop→*

factor→(exp)|number

Writedownleftmostderivations,parsetrees,andabstract

syntaxtreesforthefollowingexpression:

a.3+4*5-6

b.3*(4-5+6)

c.3-(4+5*6)

[Solution]:a.Theleftmostderivationsfortheexpression

3+4*5-6:

Exp=expaddopterm=expaddoptermaddopterm

=termaddoptermaddopterm=factoraddoptermaddop

term

=3addoptermaddopterm=3+termaddopterm

=3+termmulopfactoraddopterm=3+factormulop

factoraddopterm

=3+4mulopfactoraddopterm=3+4*factoraddopterm

A()εAA

AAA()εε

=3+4*5addopterm=3+4*5-term=3+4*5-

factor=3+4*5-6

3.5WriteagrammarforBooleanexpressionsthatincludes

theconstantstrueandfalse,theoperatorsand,orandnot,and

parentheses.Besuretogiveoralowerprecedencethanandand

andalowerprecedencethatnotandtoallowrepeatednot’s,as

intheBooleanexpressionnotnottrue.Alsobesreyourgrammar

isnotambiguous.

[solution]

bexp→bexporA|A

A→AandB|B

B→notB|C

C→(bexp)|true|false

Ex:notnottrue

boolExp→A

→B

→notB

→notnotB

→notnotC

→notnottrue

3.8Giventhefollowinggrammar

statement→if-stmt|other|ε

if-stmt→if(exp)statementelse-part

else-part→elsestatement|ε

exp→0|1

a.Draw