最新编译原理期末考试.docx

最新编译原理期末考试.docx

《最新编译原理期末考试.docx》由会员分享，可在线阅读，更多相关《最新编译原理期末考试.docx（41页珍藏版）》请在冰点文库上搜索。

最新编译原理期末考试

一、填空（每题2分，共20分）

1．从功能上说，程序语言的语句大体可分为（执行性）语句和（说明性）语句两大类。

2．扫描器的任务是从（源程序）中识别出一个个（单词符号）。

3．所谓最左派生是指（任何一歩α→β都是对α中最左非终结符进行替换的）。

4．语法分析最常用的两类方法是（自顶向下）和（自底向上）分析法。

5．一个上下文无关文法所含的四个组成部分是（一组终结符号，一组非终结符号、一个开始符号、一组产生式）。

6．所谓语法制导翻译方法是（为每个产生式配上一个翻译子程序，并在语法分析的同时执行这些子程序）。

7．LR分析法中的两种冲突是（移入—归约）和（归约—归约）。

8．产生式是用于定义（语法范畴）的一种书写规则。

9．属性定义中有两种性质的属性，分别是（继承属性）和（综合属性）。

10．常用的两种动态存储分配方法是（栈式动态分配）和（堆式动态分配）。

11.所谓最右推导是指：

任何一步αβ都是对α中最右非终结符进行替换的。

12.一个过程相应的DISPLAY表的内容为（现行活动记录地址和所有外层最新活动记录的地址。

）

13.符号表中的信息栏中登记了每个名字的有关的性质，如（类型、种属、所占单元大小、地址）等等。

14．运行时的DISPLAY表的内容是什么？

它的作用是什么？

答：

DISPLAY表是嵌套层次显示表。

每当进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i，则它的diaplay表含有i+1个单元，自顶向下每个单元依次存放着现行层、直接外层、…、直至最外层（主程序，0层）等每层过程的最新活动记录的起始地址。

通过DISPLAY表可以访问其外层过程的变量。

二、名词解释（每题3分，共15分）

1．编译器预处理：

对于一个编译器，如果要处理的输入是对原编译器的输入的扩充，就把输入中的扩充部分转换成原输入的形式，然后把其结果交给原编译器处理，也就是把扩展的部分转换成标准形式，这就是编译器预处理

2．LL（K）文法――（P89）

3．歧义文法――（p71）

正则表达式――（P47）：

每个正则表达式定义一个正则集。

若用RE表示∑上的正则表达式，并用L（RE）所表示的正则集，则RE的语法定义和相应正则集如下面所述，其中A和B表示正则表达式，并且а表示字母表∑中的任一符号。

4．属性文法――（P260）

三、简答题（每题5分，共15分）

1．设有L（G）＝{a2n+1b2m+1c2p|n>=1,m>＝1,p>=1}

1）给出它的正则表达式。

2）构造识别该语言的DFA。

2．生成语言L（G）＝{apbmcpanbn|p>=0,m>=1,n>=2}的文法G是什么？

它是chomsky的哪型文法。

解：

G（3）文法为

S->AC

A->aAc|B

B->bB|b

C->aCb|ab

它是乔姆斯基2型文法

3．已知文法G（S）：

S→a|b|（T）T→T,S|S写出句子（（a,b）,b）的规范规约过程及每一步的句柄。

解：

句型规约句柄

（（a,b）,b）

（（S,b）,b）S->aa

（（T,b）,b）T->SS

（（T,S）,b）S->bb

（（T）,b）T->T,ST,S

（S,b）S->（T）（T）

（T,b）T->SS

（T,S）S->bb

（T）T->T,ST,S

SS->（T）（T）

四、计算题（每题10分，共20分）

1．已知文法G（E）

E→T|E+T

T→F|T*F

F→（E）|i

给出句型α＝（T*F+i）的最右派生及画出语法树。

解：

1.（4分）

E⇒T⇒F⇒（E）⇒（E+T）⇒（E+F）

⇒（E+i）⇒（T+i）⇒（T*F+i）

2.（4分）

短语：

（T*F+i）,T*F+i,T*F,i

直接短语：

T*F,i

句柄：

T*F

素短语：

T*F,i

2．说明下面的文法不是SLR

（1）文法，并重写一个等价的SLR

（1）文法。

S→Ma|bMc|dc|bda

M→d

解：

S’→SS→Ma|bMc|dc|bdaM→d

因为a是M的后继符号之一，因此在上面最右边一个项目集中有移进-归约冲突。

等价的SLR

（1）文法是

S→da|bdc|dc|bda

五、设计题（每题15分，共30分）

1．下面的文法定义语言L={anbncm|m,n≥1}。

写一个语法制导定义，其语义规则的作用是：

对不属于语言L的子集L1={anbncn|n≥1}的句子，打印出错信息。

S→DCD→aDb|abC→Cc|c

解：

语法制导的定义如下：

S→DCifD.length≠C.lengththenprint（“error”）

D→abD.length:

=1

D→aD1bD.length:

=D1.length+1

C→cC.length:

=1

C→C1cC.length:

=C1.length+1

2.给出文法G（L）的翻译模式，它分别计算字符串中0与1的个数。

（要求ANTLR代码）

S→L.L|L

L→BL

L→ε

B→0|1

GrammerL01

@members{intn0;intn1;}

Start:

{n0=0;n1=0;}j{system.out.println（n0）;system.out.println（n1）;}

;

j:

‘0’j{n0+=1;}

|‘1’j{n1+=1;}

|‘a’

;

ws:

（‘’|‘\t’|‘\n’|‘\r’）+{skip（）;};

名词解释

1．遍－－指编译程序对源程序或中间代码程序从头到尾扫描一次。

2．无环路有向图（DAG）－－如果有向图中任一通路都不是环路，则称庐有向图为无环路有向图，简称DAG。

3．语法分析－－按文法的产生式识别输入的符号串是否为一个句子的分析过程。

4．短语－－令G是一个文法。

S划文法的开始符号，假定αβδ是文法G的一个句型，如果有SαAδ且AB，则称β是句型αβ相对非终结符A的短语。

5．后缀式－－一种把运算量写在前面，把算符写在后面的表示表达式的方法。

简述题

1、写出表达式（a＋b*c）/（a＋b）－d的逆波兰表示及三元式序列。

2、已知文法G（S）

   S→a|∧|（T）

   T→T，S|S

  写出句子（（a，a），a）的规范归约过程及每一步的句柄。

3、何谓优化？

按所涉及的程序范围可分为哪几级优化？

4、目标代码有哪几种形式？

生成目标代码时通常应考虑哪几个问题？

答案：

1、逆波兰表示：

abc*＋ab＋/d－　　

  三元式序列：

　①（*，b，c）

　②（＋，a，①）

　③（＋，a，b）

　④（/，②，③）

　⑤（－，④，d）　

3、优化：

对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。

  三种级别：

局部优化、循环优化、全局优化。

4、目标代码通常采用三种形式：

机器语言，汇编语言，待装配机器语言模块。

  应着重考虑的问题：

（1）如何使生成的目标代码较短；

（2）如何充分利用寄存器，以减少访问内存次数；

　（3）如何充分利用指仅系统的的特点。

计算题：

1、写一个文法，使其语言是奇数集，且每个奇数不以0开头。

（5分）

　　解：

文法G（N）：

　　　　　　　　N→AB|B

　　　　　　　　A→AC|D

　　　　　　　　B→1|3|5|7|9

　　　　　　　　D→B|2|4|6|8

　　　　　　　　C→0|D　　　　　（5分）

　　2、设文法G（S）：

　　　　S→（L）|aS|a

　　　　L→L，S|S

（1）消除左递归和回溯；

（2）计算每个非终结符的FIRST和FOLLOW；

　　　　（3）构造预测分析表。

　　解：

（1）

　　　　　　　　　S→（L）|aS’

　　　　　　　　　S’→S|ε

　　　　　　　　　L→SL’

　　　　　　　　　L’→SL’|ε

　　　　　　评分细则：

消除左递归2分，提公共因子2分。

（2）　FIRST）S）＝{（，a}　　　　FOLLOW（S）＝{#，，，）}

　　　　FIRST（S’）＝{，a,ε}　　FOLLOW（S’）＝{#，，，）}

　　　　FIRST（L）＝{（，a}　　　　FOLLOW（L）＝{）}

　　　　FIRST（L’）＝{，，ε}　　FOLLOW（L’〕＝{）}

　　3、While　a＞0∨b＜0　do

　　　　Begin

　　　　　　X：

＝X＋1；

　　　　　　ifa＞0thena：

＝a－1

　　　　　　　　　　elseb：

＝b＋1

　　　　End；

　　　　翻译成四元式序列。

（7分）

　　　　解：

（1）（j＞，a，0，5）

（2）（j，－，－，3）

　　　　　（3）（j＜，b，0，5）

　　　　　（4）（j，－，－，15）

　　　　　（5）（＋，×，1，T1）

　　　　　（6）（：

＝，T1，－，×）

　　　　　（7）（j≥，a，0，9）

　　　　　（8）（j，－，－，12）

　　　　　（9）（－，a，1，T2）

　　　　　（10）（：

＝，T2，－，a）

　　　　　（11）（j，－，－，1）

　　　　　（12）（＋，b，1，T3）

　　　　　（13）（：

＝，T3，－，b）

　　　　　（14）（j，－，－，1）

　　　　　（15）

　　　　评分细则：

控制结构4分，其它3分。

　　4、已知文法G（E）

　　　　E→T|E＋T

　　　　T→F|T*F

　　　　F→（E）|i

（1）给出句型（T*F＋i）的最右推导及画出语法树；

（2）给出句型（T*F＋i）的短语、素短语。

（7分）

　　解：

（1）最右推导：

　　　　　　　ETF（E）（E＋T）（E＋F）（E＋i）

　　　　　　（T＋i）（T*F＋i）

（2）短语：

（T*F＋i），T*F＋i，T*F，i　　　　（2分）

　　　　　　　　　素短语：

T*F,i　　　　　　　　　　　　（1分）

　　5、设布尔表达式的文法为

　　　　E→E

（1）∨E

（2）

　　　　E→E

（1）∧E

（2）

　　　　E→i

　　　　假定它们将用于条件控制语句中，请

（1）改写文法，使之适合进行语法制导翻译和实现回填；

（2）写出改写后的短个产生式的语义动作。

（6分）

　　解：

（1）E0→E

（1）

　　　　　　　　　E→E0E

（2）

　　　　　　　　　EA→E

（1）

　　　　　　　　　E→EAE

（2）

　　　　　　　　　E→i　　　　　　　　　　　　　　　　　　（3分）

（2）E→E

（1）

　　　　　　　　　{BACKPATCH（E

（1）·FC，NXQ）；

　　　　　　　　　　　E0·TC：

＝E

（1）·TC}

　　　　　　　　　E→E0E

（2）

　　　　　　　　　{E·FC：

＝E

（2）·FC；

　　　　　　　　　　　E·TC：

＝MERG（E0·TC，E

（2）·TC）}

　　　　　　　　　EA→E

（1）

　　　　　　　　　{BACKPATCH（E

（1）·TC，NXQ）；

　　　　　　　　　　　E0·FC：

＝E

（1）·FC}

　　　　　　　　　E→EAE

（2）

　　　　　　　　　{E·TC：

＝E

（2）·TC；

　　　　　　　　　　　E·FC：

＝MERG（EA·FC，E

（2）·FC}

　　　　　　　　　E→i

　　　　　　　　　{E·TC：

＝NXQ；E·FC：

＝NXQ＋1；

　　　　　　　　　　　GEN（jn2，entry（i），－0）；

　　　　　　　　　　　GEN（j，－，－，0）　　　　　　　　　（3分）

　　6、设有基本块

　　　　T1：

＝2

　　　　T2：

＝10/T

　　　　T3：

＝S－R

　　　　T4：

＝S＋R

　　　　A：

＝T2*T4

　　　　B：

A

　　　　T5：

＝S＋R

　　　　T6：

＝T3*T5

　　　　B：

＝T6

（1）画出DAG图；

（2）假设基本块出口时只有A，B还被引用，请写出优化后的四元序列。

（6分）

　　解：

（1）DAG：

（2）优化后的四元式

　　　　　　　　　T3：

＝S－R

　　　　　　　　　T4：

＝S＋R

　　　　　　　　　A：

＝5*T4

　　　　　　　　　B：

＝T3＋T4　　　　　　　　　　　　（3分）

 例题3

若正规表达式r=（a|b|c）（0|1）*，则L（r）中有__D__个元素。

（12）A．12       B．18        C．6         D．无穷

解析：

本题考察的是程序的语言的组成句子与文法之间的关系；正规表达式r=（a|b|c）（0|1）*表示的是a,b,c中的任意一个与0、1串的连接，由于0、1串的长度和组成是不固定的，所以整个句子的数据就是不固定的，也就是说语言L（r）的组成元素是无穷的。

 试题4：

编译器和解释器是两种高级语言处理程序，与编译器相比， B。

编译器对高级语言源程序的处理过程可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等几个阶段：

其中，代码优化和C并不是每种编译器都必需的。

词法分析的作用是识别源程序中的 B；语法分析中的预测分析法是 B的一种语法分析方法；编译器在 C阶段进行表达式的类型检查及类型转换。

（13）A、解释器不参与运行控制，程序执行的速度慢

      B、解释器参与运行控制，程序执行的速度慢

      C、解释器参与运行控制，程序执行的速度快

      D、解释器不参与运行控制，程序执行的速度快

（14） A、词法分析   B、语法分析   C、中间代码生成   D、语义分析

（15） A、字符串   B、单词   C、标识符   D、语句

（16） A、自左至右   B、自顶向下   C、自底向上   D、自右至左

（17） A、词法分析   B、语法分析   C、语义分析   D、目标代码生成

例题5：

假设某程序语言的文法如下：

S→a|b|（T）

T→TdS|S

其中，VT={a,b,d,（,）}，VN={S,T}，S是开始符号。

考查该文法，称句型（Sd（T）db）是S的一个A。

其中B是句柄；C是素短语；D是该句型的直接短语；E是短语。

A：

①最左推导          ②最右推导         ③规范推导         ④推导

B：

①S                 ②b                ③（T）              ④Sd（T）

C：

①S                 ②b                ③（T）              ④Sd（T）

D：

①S                 ②S,（T）,b         ③S,（T）,TdS,b  ④（Sd（T）db）

E：

①（Sd（T）db）      ②d（T）             ③Td               ④Sd（T）d

此句型的语法树如下所示：

 S

（T）

（T d  S）

（T d S  b）

（S  （T））

   从语法树我们可以看出，短语就是位于同一个非终端结点的所有叶子结点，比如S、Sd（T）、Sd（T）db就是是相对于T的短语，b、（T）、（Sd（T）db）是相对于S的短语。

而直接短语则进一步要求这些叶子结点的非终端结点是它们的直接父结点。

因此可以S、（T）、b都是该句型的直接短语。

语法树上最左的直接短语就是句柄，本题中是S。

    所谓素短语是指这样一个短语，它至少含有一个终结符，并且除它自身之外不再含任何更小的素短语。

最左素短语则指处于句型最左边的那个素短语。

    最左推导是指任何一步推导过程σ→β，都是对σ中的最左非终结符进行替换。

因此，在语法树中也很容易看出，如果语法树中的只有最左的非终结符结点（包括各级结点）具有其子树，则它就是最左推导。

最右推导与之类似，最右推导也称规范推导。

本题从语法推导树可以看出，既不是最左推导也不是最右推导，就是一般的推导。

A：

④   B：

①   C：

③   D：

②   E：

①

1、算符优先关系表不一定存在对应的优先函数。

正确

2、数组元素的地址计算与数组的存储方式有关。

正确

3、仅考虑一个基本块，不能确定一个赋值是否真是无用的。

正确

4、每个文法都能改写为LL

（1）文法。

不正确

5、对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。

不正确

一、回答下列问题：

（30分）

1．什么是S-属性文法？

什么是L-属性文法？

它们之间有什么关系？

解答：

S-属性文法是只含有综合属性的属性文法。

（2分）

L-属性文法要求对于每个产生式A→X1X2…Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj的一个继承属性，且该属性仅依赖于：

（1）产生式Xj的左边符号X1,X2…Xj-1的属性；

（2）A的继承属性。

（2分）

S-属性文法是L-属性文法的特例。

（2分）

2．什么是句柄？

什么是素短语？

一个句型的最左直接短语称为该句型的句柄。

（3分）素短语是这样的一个短语，它至少包含一个终结符并且不包含更小的素短语。

（3分）

3．划分程序的基本块时，确定基本块的入口语句的条件是什么？

解答：

（1）程序第一个语句，或

（2）能由条件转移语句或无条件转移语句转移到的语句，或

（3）紧跟在条件转移语句后面的语句。

4．（6分）运行时的DISPLAY表的内容是什么？

它的作用是什么？

答：

DISPLAY表是嵌套层次显示表。

每当进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i，则它的diaplay表含有i+1个单元，自顶向下每个单元依次存放着现行层、直接外层、…、直至最外层（主程序，0层）等每层过程的最新活动记录的起始地址。

通过DISPLAY表可以访问其外层过程的变量。

5．（6分）对下列四元式序列生成目标代码：

A:

=B*C

D:

=E+F

G:

=A+D

H:

=G*2

其中，H是基本块出口的活跃变量，R0和R1是可用寄存器

答：

LDR0，B

MULR0，C

LDR1，E

ADDR1，F

ADDR0，R1

MULR0，2

STR0，H

二、设∑={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。

（8分）

答：

构造相应的正规式：

（0|1）*1（0|1）（3分）

NFA:

（2分）

11

εεεε1

00

确定化：

（3分）

I

{0,1,2}

{1,2}

{1,2,3}

{1,2}

{1,2}

{1,2,3}

{1,2,3}

{1,2,4}

{1,2,3,4}

{1,2,4}

{1,2}

{1,2,3}

{1,2,3,4}

{1,2,4}

{1,2,3,4}

0

1

0100

01

1

三、（6分）写一个文法使其语言为L（G）={anbmambn|m,n≥1}。

答：

文法G（S）:

S→aSb|B

B→bBa|ba

四、对于文法G（E）:

（8分）

E→T|E+T

T→F|T*F

F→（E）|i

1.写出句型（T*F+i）的最右推导并画出语法树。

2.写出上述句型的短语，直接短语、句柄和素短语。

答：

1.（4分）

E⇒T⇒F⇒（E）⇒（E+T）⇒（E+F）

⇒（E+i）⇒（T+i）⇒（T*F+i）

2.（4分）短语：

（T*F+i）,T*F+i,T*F,i直接短语：

T*F,i

句柄：

T*F素短语：

T*F,i

五、设文法G（S）：

（12分）

1．构造各非终结符的FIRSTVT和LASTVT集合；

2．构造优先关系表和优先函数。

（12分）

答：

（6分）

FIRSTVT（S）={i，+，），（}

FIRSTVT（A）={+，），（}

FIRSTVT（B）={），（}

LASTVT（S）={i，+，*，（}

LASTVT（A）={+，*，（}

LASTVT（B）={*，（}

优先关系表:

（3分）

i

+

（

）

*

i

>

<

<

<

+

>

>

<

<

>

（

>

>

>

）

<

<

<

*

>

>

>

优先函数:

（3分）

i

+

（

）

*

f

2

6

6

1

6

g

1

4

6

6

1

六、设某语言的do-while语句的语法形式为（9分）

S→doS

（1）WhileE

其语义解释为：

针对自下而上的语法分析器，按如下要求构造该语句的翻译模式：

（1）写出适合语法制导翻译的产生式；

（2）写出每个产生式对应的语义动作。

答：

（1）.适合语法制导翻译的文法（3分）

G（S）:

R→do

U→RS

（1）While

S→UE

（2）.（6分）

R→do

{R.QUAD:

=NXQ}

U→RS

（1）While

{U.QUAD:

=R.QUAD;

BACKPATCH（S.CHAIN,NXQ）}

S→UE

{BACKPATCH（E.TC,U.QUAD）;

S.CHAIN:

=E.FC}

答案二：

（1）S→doM1S

（1）WhileM2E

M→ε（3分）

（2）M→ε{M.QUAD:

=NXQ}（6分）

S→doM1S

（1）WhileM2E

{

BACKPATCH（S

（1）.CHAIN,M2.QUAD）;

BACKPATCH（E.TC,M1.QUAD）;

S.CHAI