期中考试市公开课一等奖省名师优质课赛课一等奖课件

期中考试西安邮电学院计算机学院联络方式：amei_wcm@王春梅讲师一、填空题（15分，每空1分）1.一个经典编译系统包含

和

两部分。2.编译方式与解释方式根本区分在于

。3.乔姆斯基将文法分为四种，其中，2型文法也称为

，

3型文法也称为

。4.某文法产生

全体是该文法描述语言。5.确定有限自动机（DFA）是一个五元组，它包含

。6.设有文法G[S]：S→S*S|S+S|(S)|a，该文法

二义性文法。

编译程序运行系统是否有目标代码产生上下文无关文法正则文法/线性文法句子(S,∑,f,S0,{Z})是7.预测分析程序是一个自上而下分析程序，预测分析要求文法是

，它主要由

、预测分析表和总控程序三部分组成。8.自下而上分析方法也称为“移进—归约”法，是指从

.

开始，查找当前句柄进行归约，直到最终归约为

.

一个分析方法。9.给定文法G[S]：S→aAcBe，句型aAbcde句柄为

。

A→b|AbB→d10.算符优先分析法每次都是对

进行归约。11.设有文法G[S]：S→b|bB，该文法所描述语言

B→bS

是

。

Ab最左素短语L(G[S])={b2i+1|i}

LL(1)文法分析栈输入符号串开始符号②

语法分析(SyntaxAnalysis)：

在词法分析基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表示式”等等。①词法分析(LexicalAnalysis)：

从左到右一个字符一个字符读入源程序，对组成源程序字符串进行扫描和分解，从而识别出一个个单词（也称单词符号或简称符号）。

二、简答题（20分，每小题5分）1.简述一个编译程序工作过程能够划分为几个阶段，每个阶段任务是什么？编译程序语法分析语义分析与中间代码生成优化目标代码生成词法分析⑤

代码优化(Optimizationofcode)：

为了使生成目标代码更为高效，能够对产生中间代码进行变换或进行改造，这就是代码优化。⑥

代码生成(Generationofcode)：

目标代码生成是编译器最终一个阶段。在生成目标代码时要考虑以下几个问题：计算机系统结构、指令系统、存放器分配以及内存组织等。④

中间代码生成(Generationofintermediatecode)：

完成语法分析和语义处理工作后，编译程序将源程序变成一个内部表示形式，这种内部表示形式叫做中间语言或称中间代码，它是一个结构简单、含义明确记号系统。③

语义分析(SyntacticAnalysis)：

语义分析是在语法分析程序确定出语法短语后，审查有没有语义错误，并为代码生成阶段搜集类型信息。2.“文法规则左部一定是非终止符号”，这句话对吗？说明理由。不对。对于上下文无关文法而言，非终止符号是只在规则左部出现符号，对于其它类型文法而言，并非全部在规则左部出现内容都是非终止符号。什么是规范推导,规范归约？每个句型都有规范推导吗？说明理由。规范推导就是最右推导，即任何一步α

β都是对α中最右非终止符进行替换；规范归约就是最左归约,实质上就是最右推导逆过程。对于文法中每一个句子都必定有规范推导或最左推导，而对一句型则不一定。4.简述LR分析器工作过程。

在总控程序控制下，从左到右扫描输入串依据分析栈和输入符号情况，查分析表确定分析动作；分析表是LR分析器关键，它跟文法相关，它包含动作表(Action)和状态转换表(Goto)两部分，总控程序依据分析表确定分析动作；分析栈包含文法符号栈X[i]和对应状态栈S[i]两部分(状态是指能识别活前缀自动机状态)，LR分析器经过判断栈顶元素和输入符号查分析表确定下一步分析动作。三、解答题（30分）1.已知文法G[S]：S→a|∧|(T)

T→T，S|S

写出句子((a，a)，a)规范归约过程及每一步句柄。

句型归约规则句柄((a，a)，a)

S→a

a((S，a)，a)

T→S

S((T，a)，a)

S→a

a((T，S)，a)

T→T，S

T，S((S)，a)

T→S

S((T)，a)

S→(T)

(T)(S，a)

T→S

S(T，a)

S→a

a(T，S)

T→T，S

T，S(T)

S→(T)

(T)S

2、消除以下文法左递归。

G[S]：

S→Sa|Ab|b|cA→Bc|aB→Bb|bG[S]：

S→(Ab|b|c)S’S’→aS’|ε

A→Bc|a

B→bB|b

3、给出描述语言L={a2m+1bm+1|m≥0}∪{a2mbm+2|m≥0}文法。将语言描述稍做变形，得：

L={a2mabbm|m≥0}∪{a2mbbbm|m≥0}G[Z]：Z→aaZb得到文法以下：|ab|bb4、结构正规式（0|1）*0（0|1）对应DFA。12(0|1)*3040|11ε5ε20|1304010041ε5ε23011001ε5ε230114①结构转换系统图：

②状态转换矩阵001ε5ε230114II0I1{1,5,2}{5,2,3}{5,2}{5,2,3}{5,2,3,4}{5,2,4}{5,2}{5,2,3}{5,2}{5,2,3,4}{5,2,3,4}{5,2,4}{5,2,4}{5,2,3}{5,2}012121442412333I1I0I{1,5,2}{5,2,3}{5,2}{5,2,3}{5,2,3,4}{5,2,4}{5,2}{5,2,3}{5,2}{5,2,3,4}{5,2,3,4}{5,2,4}{5,2,4}{5,2,3}{5,2}0121214424123330011201400011131.首次划分：

Π0=({0,1,2,3},{4})2.在G={0,1,2,3}中:f(0,0)=1f(2,0)=1f(1,0)=3f(3,0)=3f(0,1)=2f(2,1)=2f(1,1)=4f(3,1)=4（终态）（终态）0011201400011131.首次划分：

Π0=({0,1,2,3},{4})2.在G={0,1,2,3}中:f(0,0)=1f(2,0)=1f(1,0)=3f(3,0)=3f(0,1)=2f(2,1)=2f(1,1)=4f(3,1)=4（终态）（终态）故{0,1,2,3}可划分为{0,2}和{1,3}Π1=({0,2},{1,3},{4})0,2等价故Π2=({0,2},{1},{3},{4})3.在{0,2}中:1,3不等价在{1,3}中:120140001113四、综合题1.已知文法

G[E]：E→-E|(E)|VE’E’→-E|εV→iV’V’→(E)|ε求每个非终止符FIRST集和FOLLOW集，并结构预测分析表。FIRST(E)={-,(,i}FIRST(E’)={-,ε}FIRST(V)={i}FIRST(V’)={(,ε}FOLLOW(E)={)}FOLLOW(E’)={)}FOLLOW(V)={-,)}FOLLOW(V’)={-,)}-()iEE’VV’E→-EE→(E)E→VE’E’→-EE→εV→iV’V’→εV’→(E)V’→ε2、已知文法G[S]:S→SaF|F结构该文法算符优先关系矩阵。

F→FbP|PP→c|dFIRSTVT(S)={a,b,c,d}FIRSTVT(F)={b,c,d}FIRSTVT(P)={c,d}LASTVT(S)={a,b,c,d}LASTVT(F)={b,c,d}LASTVT(P)={c,d}SaaFab,ac,a

d<.<.<.LASTVT(S)a>.aa,ba,ca,d

a>.>.>.>.aFIRSTVT(F)<.FbLASTVT(F)b>.bb,cb,db>.>.>.bPbc,bd<.<.bFIRSTVT(P)<.S#LASTVT(S)#>.a#,b#,c#,d#>.>.>.>.#S#FIRSTVT(S)<.#a,#b,#c,#

d<.<.<.<.#S###