编译原理试题及答案

编译原理试题

一、填空题

1、汇编程序将翻译成;编译程序将

翻译成O

2、编译程序工作工程可以划分为、、、

和等5个根本阶段，同时还会伴有和

3、对编译程序而言，输入数据是,输出数据是o

4、文法G[E]：E—>T|E+T|E-F,T->F|T*F|T/F,F—>（E）|l,

（“，〃是间隔符号，不是文法中的符号）。该文法的开场符号（识

别字符）是，终结符号集合片是,非终结符号结合

网是,句型T+T*F+i的短语有o该文法消除

直接左递归，改写后的文法为E—>,T->,F

—>o

5、Chomsky定以来寺中形式语言的文法分别为：

文法（又称文法）、文法（又称文法）、

文法（又称文法）、文法（又称

________文法）o

6、编译过程中扫描器所完成的任务是从中识别出

一个个具有o

7、确定的有穷自动机是一个，通常表示为

8、LL(k)分析中，第一个L的含义是,第二个L的

含义是,“k〃的含义是o

9、LL(1)分析中，第一个L的含义是,第二个L的

含义是，“1〃的含义是o

10、LR(0)分析中，“L〃的含义是,“R〃的含义

是,“0〃的含义是o

IKSLR(l)分析中，“L〃的含义是，“R〃的含义

是，“1〃的含义是。

12、LR(1)分析中，“L〃的含义是,“R〃的含义

是,“1〃的含义是。

13、算术表达式：a*(-b+c)的逆波兰式表示为：o

14、算术表达式：a+b*(c+d/e)的逆波兰式表示为：

15、在编译程序中安排中间代码生成的目的是和

16、语法制导的翻译程序能同时进展分析和

________分析。

17、根据所涉及的程序范围，优化可分为、

、三种。

二、简答题

1、有人认为编译程序的词法分析、语法分析、语义分析和

中间代码生成、代码优化、目标代码生成五个组成局部是缺一不

可的，这种看法正确吗？说明理由。

2、多边扫描的程序是高质量的编译程序，优于单遍扫描的

编译程序，对吗？为什么？

3,LR分析器及优先分析器在识别被归约串时的主要异同时

什么？

三、给出生成下述语言的上下文无关的文法

{lnOn,rnO"|n,m>=0}

{WaW「|W属于卬表示W的逆}

四、给出生成以下语言的三型文法：

{an|n>=0}

{anb'"n,m>0}

{a"b"'ck|n,m,k>=0}

五、构造正规式1(011)*101相应的最小DFA。

4.给出输入baab#的SLR(1)分析过程。

十、对以下图的流图:

1、求出流图个节点的n的必经节点集D(n)；

2、求出流图的回边；

3、求出流图中的循环。

十一、将下面的程序段划分为根本块并作出其程序流图。

ReadA,B

F:=l

C:二A*A

D:=B*B

IfC<DgotoLI

E=A*A

F=F+l

E:=E+f

WriteE

Halt

LI:E:=B*B

F:=F+2

WriteE

IfE>100gotoL2

Halt

L2:F:=F-1

GotoLI

十二、有下面根本块：

So：=2

Si:=3/So

S2：=T-C

S3：=T+C

R:=So/S3

H:二R

Si：=3/Si

S5:=T+C

1I:=S6*S2

1、应用DAG对其进展优化，写出优化后的根本块中四元式；

2、假定只有R、H在根本块出口式活泼的，写出优化后的四

元式序列。

十三、翻译以下关于LEX一点介绍的英文。

2、LexSource.

ThegeneralformatofLexsourceis:

{definitions}

{rules)

{usersubroutines)

wherethedefinitionsandtheusersubroutinesare

oftenomitted.Thesecond%%isoptional,butthefirstis

requiredtomarkthebeginningoftherules.Theabsolute

minimumLexprogramisthus

(nodefinitions,norules)whichtranslatesintoa

programwhichcopiestheinputtotheoutputunchanged.

IntheoutlineofLexprogramsshownabove,therules

representtheuser'scontroldecisions;theyareatable,

inwhichtheleftcolumncontainsregularexpressions(see

section3)andtherightcolumncontainsactions,program

fragmentstobeexecutedwhentheexpressionsare

recognized.Thusanindividualrulemightappear

integerprintf(z，foundkeywordINT");

tolookforthestringintegerintheinputstreamand

printthemessage''foundkeywordINT''wheneverit

appears.Inthisexamplethehostprocedurallanguageis

CandtheClibraryfunctionprintfisusedtoprintthe

string.Theendoftheexpressionisindicatedbythefirst

blankortabcharacter.Iftheactionismerelyasingle

Cexpression,itcanjustbegivenontherightsideofthe

line;ifitiscompound,ortakesmorethanaline,itshould

beenclosedinbraces.Asaslightlymoreusefulexample,

supposeitisdesiredtochangeanumoerofwordsfrom

BritishtoAmericanspelling.Lexrulessuchas

colourprintf("color");

mechaniseprintf("mechanize");

petrolprintf(〃gas〃)；

wouldbeastart.Theserulesarenotquiteenough,

sincethewordpetroleumwouldbecomegaseum\awayof

dealingwiththiswillbedescribedlater.

十四、翻译以下有关yacc的一些英文介绍。

Introduction

YACCisshortforYetAnotherCompilerCompiler.Apun

onthenumberofcompiler,orparser,constructiontools

thatwerebeingcreatedatthetime.Itisatoolthat,given

aBNF(Backus-NaurForm)stylespecificationofagrammar,

cangenerateacorrespondingparser.Itisworthnoting

thatYACCwillnotaccepteverygrammarpresentedtoit.

Farfromit.Howevertheclassofgrammarsthatitdoes

acceptisgenerallypowerfulenoughformostprogramming

needs.

YACCwasoriginallywrittenbyS.C.JohnsononaUNIX

platform.ItiscloselytiedinwithLex.Alexicalanalyser

generatingtool.Sincethentherehavebeenmanyflavours

ofYACCimplemented.PerhapsthemostnotablebeingBISON

andBYACC.

YACCgenerateswhataretermedLRparsers.Thismeans

thattheyscantheinputfromlefttoright,theLbit,and

producearightmostderivationfromthebottomup,theR

bit.LRparsersarealsocalledbottom-upparsers.Theyare

somewhatdifferenttoLLparsers.SimilartoLRparsers

thesealsoscantheinputfromlefttoright,butthistime

constructaleftmostderivationinstead.LLparsersare

alsocalledtopdownparsers.Theyhavethedistinct

advantagethattheycangenerallybeimplementedbyhand.

Thereareanumberoftechniquesfordoingthisincluding

predictiveparsingandrecursivedescentparsing.There

arenowalsoanumberoftoolswhichcanconstructLL

parsersautomatically.Havingsaidallthis,itis

generallyatimeconsumingtasktocodeaparserbyhand,

andanLRparserconstructiontechniqueisinherentlymore

powerfulthananLLone.

Forbothtypesofparser,eitherLRorLL,thereis

generallyanextrapieceofinformationwhichspecifieshow

manylookaheadtokenstheparserusestodecidewhataction

toperform.ForinstanceanLR(1)parserusesonetokenof

lookahead.ThisanimportantpointbecauseYACCgenerates

aparserwhichusesonetokenoflookaheadaswell.That

istheparsermustdecide,giventhesymbolsthatithas

alreadyseen,andthecurrentlookaheadtokenwhatitneeds

todonext.

1.汇编语言的程序，机器语言的程序；高级语言的程序，汇

编语言或机器语言的程序。

2.源程序，目标程序。

3.E,{+,i,(,)},{E,T,F},短语:T+W+i,

T+T*F,T,T*F,i

4.从左到右的扫描，分析过程采用最左推导，需要向右查看

一个符号便可决定如何推导。

5.从左到右的扫描，分析过程采用最右推导的逆过程-最左

规约，向后查看0个符号决定分析动作。

6.ab!c+*

7.局部优化，循环优化，全局优化

二、错。在这5个局部中，词法分析，语法分析，语义分析

和目标代码生成是必须的，代码优化是为了提高目标代码的质量

而引入的，不是必须的，没有代码优化编译程序同样生成目标代

码。

三.产生式的集合P：S-0S0|aSa|ao

四、l.SfaS|£>2.S-^aS|aA|ab,A-*bA|£。

五、解：步骤上先NFA,确定化，最小化。对于此题确定化

后即最小了。

六、解：