当前位置：文档之家› 2018编译原理期末复习

2018编译原理期末复习

编译原理期末复习

1、简答题（或者名词解释）

下面涉及到的概念中，加下划线的都是在以往一些试卷中出现的原题，务必掌握。

注：这类题目老师说答案不会超过一百个字，否则写的再多也不给分，有些点到即可，不要重复啰嗦。

（1）简述编译程序的概念及其构成

答：1）编译程序：它特指把某种高级程序设计语言翻译成等价的低级程序设计语言的翻译程序。

2)构成：

（2）简述词法分析阶段的主要任务（也有可能问语法分析阶段主要任务）答：词法分析的任务是输入源程序，对源程序进行扫描，识别其中的单词符号，把字符串形式的源程序转换成单词符号形式的源程序。

语法分析的主要任务是对输入的单词符号进行语法分析（根据语法规则进行推导或者归约），识别各类语法单位，判断输入是不是语法上正确的程序

(3) 简述编译程序的构造过程（这个大家看看，是对（1）和（2）的综合）

答：1）构造词法分析器：用于输入源程序进行词法分析，输出单词符号；

2）构造语法分析器：对输入的单词符号进行语法分析，识别各类语法单位，判断输入是不是语法上正确的程序

3）构造语义分析和中间代码产生器：按照语义规则对已归约出的语法单位进行语义分析并把它们翻译成中间代码。

4）构造优化器：对中间代码进行优化。

5) 构造目标代码生成器：把中间的代码翻译成目标程序。

6) 构造表格管理程序：登记源程序的各类信息和编译各阶段的进展情况。

7)构造错误处理程序：对出错进行处理。

(4) 说明编译和解释的区别：

1)编译要程序产生目标程序，解释程序是边解释边执行，不产生目标程序；

2)编译程序运行效率高而解释程序便于人机对话。

（5）文法：描述语言语法结构的形式规则，一般用一个四元式表示： G=(V T，V N，S，P)，其中V T：终结符集合(非空) V N：非终结符集合(非空)，且V T ?V N=? S：文法的开始符

号，S∈V N P：产生式集合(有限)。

（6）二义性文法：一个文法中存在某个句子，它有两个不同的最左（或者最右推导），则称该文法是二义性的。

例子如文法G：S→if expr then S |other

S→if expr then S else S 句子if e1 then if e2 then s1 else s2是二义性的。

（7）文法的形式（注：文法的形式一定要牢记，特别是2型和3型文法一定要牢记，不仅在概念题中有用，在下面的根据语言写文法题中也有重要作用，如果所写的文法形式不对，一切都是无用功……）

1）0型文法(短语文法，图灵机)：产生式形式为：α→β，其中：α∈ (V T ?V N)*且至少含有一个非终结符；β∈ (V T ?V N)*

2）1型(上下文有关文法，线性界限自动机)：产生式形式为:α→β其中：|α| ≤ |β|，仅 S→ε例外，但是S不得出现在任何产生式右部。

3）2型文法（上下文无关文法，非确定下推自动机)：产生式形式为：P→α， P∈V N，α∈(V T ?V N)*。

4）3型文法(正规文法，有限自动机)：右线性文法：产生式形如：A →αB 或 A →α其中：α∈ V T*；A，B∈V N 左线性文法：产生式形如：A → Bα或 A →α其中：α∈ V T*；A，B∈V N

例题：设G=(V T，V N，S，P)是一个上下文无关文法，产生集合P中的任一个产生式应具有什么样的形式？若G是1型文法呢？若G是正则文法呢？

上下文无关文法，产生式形式为：P→α， P∈V N，α∈ (V T ?V N)*。

1型文法：产生式形式为:α→β其中：|α| ≤ |β|，仅 S→ε例外，但是S不得出现在任何产生式右部。

正则文法：右线性文法：产生式形如：A →αB 或 A →α其中：α∈ V T*；A，B∈V N 左线性文法：产生式形如：A → Bα或 A →α其中：α∈ V T*；A，B∈V N

(8)什么是PDA(下推自动机)?

答：PDA是下推自动机，PDA M用一个七元组表示(K,Σ,f,H,h0,S,Z)

K: 有穷状态集∑：输入字母表(有穷) H:下推栈符号的有穷字母表

h0 :H中的初始符号 f: K ?（Σ?{ε}) ? H –> K ? H* S：属于K是初始状态。

Z:包含于K，是终结状态集合。

(9) 什么是DFA（有穷状态自动机）?

自动机M是一个五元式M=(S, ∑, f, S0, F),其中：

1）S: 有穷状态集， 2）∑：输入字母表(有穷)，

3） f: 状态转换函数，为S?∑→S的单值部分映射，f(s，a)=s’表示：当现行状态为s，输入字符为a时，将状态转换到下一状态s’。我们把s’称为s的一个后继状

态。

4） S0∈S是唯一的一个初态； 5） F?S ：终态集(可空)。

（10）推导：所谓推导就是对于一个含非终结符A的符号串，利用规则A→α，把A替换成α得到新符号串的过程。

最左推导：在推导的每一步，选择符号串最左边的非终结符进行替换。

最右推导：在推导的每一步，选择符号串最右边的非终结符进行替换。

(11)归约：归约是推倒的逆过程，即用产生式的左部非终结符替换右部符号串。

(12)什么是句型？什么称为句子？什么是语言？

句型：从文法的起始符号出发，经过有限步的推导能够推导出来的符号称为句型。

句子：只由终结符构成的句型称为句子。

语言：所有句子的集合构成该文法描述的语言。

(13)什么是短语？什么是直接短语（也称为简单短语）？什么是句柄？什么是素短语？什么是最左素短语？（以下几个概念一定要理解，考试中肯定会考哪些是短语，直接短语，句柄等，具体方法请参见后面的）

短语：如果存在某个文法非终结符P,满足S

?βPγ,并且P+?α则称α为句型βαγ相

对于非终结符P的短语。

直接短语：如果P?α,即从P出发一步推出α，则α称为直接短语。

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

素短语：至少含有一个终结符的短语，并且除了自身外，不包含更小的素短语。

最左素短语：句型中最左边的素短语。

（14）自顶向下的语法分析方法中需要解决的主要问题什么？如何表示？

答：1）主要需要解决回溯和左递归问题。

2）表示方式，回溯：文法中存在形如A→α1|α2|…|αn,即产生式右部存在多个候选，导致推导时不能确定到底应该选择哪个候选式。

左递归：文法中存在形如P→Pα的形式，推导时会导致推导过程无休止的进行下去。

注：解决方法，对回溯采取的是提取左公因子，对左递归使消除左递归（包括直接左递归和间接左递归）。

(15)内情向量：一般编译程序对数组说明的处理是把数组的有关信息汇集在一个叫做“内情向量”或“信息向量”的表格中，以便以后计算数组元素的地址时引用这些信息。每个数组有一个内情向量。其中的信息包括，数组的类型，维数，各维的上、下界，以及数组的首地址。

（16）C语言的活动记录：

Old SP

返回地址

参数个数

形式单元

局部变量

内情向量

临时单元SP

TOP

2、最左最右推导，画语法树，找短语、直接短语、句柄等。

这种题目很简单，送分题，一定不能丢分！

考题：1）文法G[S]为：S→SdT | T T→T

（2）根据所画出的语法树，可以很快的找出短语，直接短语，句柄和最左素短语等，先讲一个简单子树的概念，所谓简单子树是指仅具有单层分支的子树。具体方法如下：

短语：任一子树的树叶全体(具有共同祖先的叶节点符号串)皆为短语；

直接短语：任一简单子树的树叶全体(具有共同父亲的叶节点符号串)皆为简单短语；句柄：最左边的直接短语；

素短语：至少含有一个终结符的短语，并且除了自身外，不包含更小的素短语。最左素短语：最左边的素短语。

答：（1）S ?T ? T

语法树：

（2）短语：G ，SdG, (SdG), a, (SdG)

注:还有一份试卷将句型改为adT<(S)，与这个类似，大家自己做做，答案是短语：a,(S),T<(S),adT<(S) 直接短语：a,(S) 句柄：a 最左素短语：a

下面两道例题大家看看，一定要会找短语，直接短语，句柄等.

※短语、简单短语和句柄示例

【例2.12】图2.3为一个算术表达式(型)的语法树：

?句型： E+F-T/F*i

?短语: E+F-T/F*i ，E+F ，F ，T/F*i ，T/F ，i ?简单短语: F ，T/F ，i ?句柄: F

E E - T E + T T *

F F T / F i 图2.3 E+F-T/F*i 的语法树

※ 一类典型的综合例题：

【例2.13】G(S): S->aAcBe ; A->Ab|b ; B->d ※ 给定符号串： aAbcde ⑴ 证明 = aAbcde 是一个句型； ⑵ 画出句型的语法树；

⑶ 指出中的短语、简单短语和句柄。【题解】

⑴ S=>aAcBe=>aAbcBe=> aAbcde ⑵ 语法树如右图：⑶ 短语、简单短语和句柄: S a A c B e A b d

? 短语: aAbcde ,Ab , d ? 简单短语: Ab , d

? 句柄：Ab

考题：2)文法G[E]的产生式为E →E+T|T T →T*F|F F →i|(E) ①对于句型(i+i)*i ，给出最左最右推导及相应的推导树

②列出句型的所有短语、简单短语。（还有一份试卷上是出句型F+T*F 的所有短语、简单短语和句柄，大家自己做做）

答：（1）最左推导：E ?T ?T*F ?F*F ?(E)*F ?(E+T)*F ?(T+T)*F ?(F+T)*F ?(i+T)*F

?(i+F)*F ?(i+i)*F ?(i+i)*i

最右推导E ?T ?T*F ?T*i ?F*i ?(E)*i ?(E+T)*i ?(E+F)*i ?(E+i)*i ?(T+i)*i

?(F+i)*i ?(i+i)*i

推导树如下：

（2）短语;i,i+i,(i+i),(i+i)*i 直接短语：i 句柄：i

3、根据语言推文法

这类题目首先要看清题目，指定的是什么文法，一般都是2型（上下无关文法）或者3型（正规文法），这两类文法形式一定要记住，具体请参见第2页的文法分类。

掌握几个基本形式{a n

| n>0}对应文法S→aS| a 如果是n>=0则为S→aS|ε(ε是空字) {a n b n

| n>0}对应文法S→aSb| ab

下面这四道题目老是在试卷中重复出现，所以大家好好看看。

考题

1、按指定类型给出下列语言的文法,并指出语言的类型。（10 分） (1)L1={a n b m c n | n ≥0,m>0 } 二型文法：S →aSc|B B →bB|b (2) L2={ 0n a1n b m c m | n>0，m ≥0} 二型文法：S →AB A →0A1|0a1 B →bBc|ε

2、按指定类型给出下列语言的文法。（10 分）

(1)L1={ ca n db m | n≥0,m>0 } 用正规文法。

S →cA A →aA|B B →dC C →bC|b

(2)L2={ 0n a 1n b m c m | n>0,m ≥0}用二型文法。

S →AB A →0A1|0a1 B →bBc|ε

3、按指定的类型给出下列语言的文法（10 分） (1)L1={ ca n b m | n ≥0,m>0 } 用正规文法。 S →cA A →aA|B B →bB|b

(2)L2={ 0n a 1n b m | n>0，m ≥0} 用二型文法。

4、按指定的类型给出下列语言的文法（10

分） (1) L1={a n b m c|n>=0,m>0}用正规文法 S →aS|A A →bA|bB B →c (2) L2={a0n 1n bd m |n>0,m>0}用二型文法

S →AB A →0A1|0a1 B →bB|ε S →AB A →aT T →0T1|01 B →bD D →dD|d

这是书P36 第11题的答案如下：大家作为练习，可以发现比上述题目简单的多了。

或者

G4:

A B

B A A B A S |01|10|→→→ε

4、词法分析———正规式、NFA 和DFA 之间的转化：

（1）这类题目一般是三者之间的转换，正规式→

NFA →确定化的DFA →最小化的DFA ，有时

已经给出NFA 了，则只需要确定化为DFA 和最小化就行了，一般每一步都是五分。具体怎么转换请参照我期中考试时整理的提纲，主要就是下面这幅关系对照图，因时间和篇幅限制不再追溯。

（2）注意优先级关系，闭包运算*最高，连接运算.次之，或运算|最低。 (3)考题1：

1）构造正则式a*b|(ab)*b 对应的DFA 。（15分） ①画出NFA

②确定化DFA

G1: S →AC A →aAb|ab C →cC|ε G2: S →AB A →aA|ε B →bBc|bc

G3: S →AB A →aAb|ε B →aAb|ε

G4:

S →1S0|A A →0A1|ε

X I a I b {X,1,2,3,4} {1,2,5} {Y} {1,2,5} {1,2} {3,4,Y} {Y} - - {1,2} {1,2} {Y} {3,4,Y} {5} {Y} {5} - {3,4} {3,4}

{5}

{Y}

X I a I b A B C B D E C - - D D C E F C F - G G

注：C 和E 是终态

③最小化DFA

首先将集合分为{A,B,D,F,G},{C,E}。{A,B,D,G}都有a,b 作为条件输出，F 只有b 输出，所以分为{A,B,D,G}和{F} 同理{C,E}分为{C},{E}。{A,B,D}a ={B,D} {G}a ={F}所以{A,B,D,G}分为{A,B,D}和{G}。{A}b ={C} {B,D}a ={D}所以分为{A} {B,D} 综上所述：划分的结果为{A},{B,D},{C},{E},{G}.

考题2：将NFA 确定化为DFA(10分)

NFA: DFA:

a b

Ib {X,0,1,3} {0,2,1,3} {3,Y} {0,2,1,3} {0,2,1,3} {1,3,Y} {3,Y} Ф {Y} {1,3,Y} {2} {Y} {2} Ф {1,3} {Y} Ф Ф {1,3} {2}

{Y}

含有Y 的状态子集为DFA 的终态,上例中的终态有B,C,E.

题目中要求是确定化，没有要求最小化，如若最小化，划分的集合为{S,A},{B,C} {F},{D},{E}然后再画出最小化后的DFA 这里不再赘述。

考题3：构造奇数个0和奇数个1组成的自动机。（10分）

1011

状态1：偶数个0 偶数个1 状态2：奇数个0偶数个1 状态3：奇数个0 奇数个1 状态4：偶数个0奇数个1

如果题目改成偶数个0，奇数个1，只要将状态4转换成终态即可，其他类似。

5、语法分析——自顶向下分析法（LL （1）分析法和递归向下构造子程序法）

注：自顶向下分析法本质是由开始符号，按照产生式逐步推导看能否产生需要分析的句子。

（1）自顶向下分析中存在的问题

左递归和回溯（具体请参见简答题中的第（14）题）（2）消除回溯——提取公因子法

提取公共左因子:假定关于A 的规则 A→δβ 1 | δβ 2 | …| δβ n | γ 1 | γ 2 | … | γm (其中，每个γ 不以δ开头) 那么，可以把这些规则改写成A→δA ' | γ 1 | γ 2 | … | γ m

A '→β 1 | β 2 | … | β n

（3）消除左递归

1)消除直接左递归：直接消除见诸于产生式中的左递归：假定关于非终结符P的规则为P→Pα | β，其中β不以P开头。我们可以把P的规则等价地改写为如下的非直接左递归形式：P→βP'P'→αP'|ε

注：一般而言，假定P关于的全部产生式是P→Pα1 | Pα2 | … | Pαm | β1 | β2|…|βn

其中，每个α都不等于ε，每个β都不以P开头那么，消除P的直接左递归性就是把这些规则改写成：P→β1P' | β2P'| … | βn P'P'→α1P' | α2P'|… | αm P' | ε

例：文法G(E):

E→E＋T | T T→T*F | F F→(E) | i

经消去直接左递归后变成：

E→TE'E'→+TE' | εT→FT 'T '→*FT ' | εF→(E) | i

2)消除间接左递归

这个请参见我期中整理的提纲篇幅较多，这里不再重复赘述，请参照下面的考题2。考题1：将文法G[S]改写为等价的G’[S],使得G’[S]不含左递归和左公因子。

S→[A A→B]|AS B→aB|a

答：消除左递归和左公因子后的文法为：

S→[A A→ B]A’A’ → S A’| εB→aB’B’ →B| ε

(2)消除间接左递归：将A,B,C按照B,C,A排序（建议将A放在最后）由于出现C→Bg

形式，将B代入C得：C→dAg|Aeg|fg|h又由于A出现A→Ba A→Cb将B,C带入A得到：A→dAa|Aea|fa|dAgb|Aegb|fgb|hb|c等价于A→Aea|Aegb |dAa|fa|dAgb |fgb|hb|c

此时，对于B→dA|Ae|f，C→dAg|Aeg|fg|h由于未在任何产生式的右部出现，所以是多余的。

综上所述:消除递归后的文法为：A→dAaA’|fa A’|dAgb A’ |fgb A’|hb A’|c A’

A’→ea A’| egb A’|ε

(4)LL(1)分析法

1）含义：LL(1)分析方法（也叫预测分析法）：是指从左到右扫描、最左推导(LL)和只查看一个当前符号（括号中的 1）。

2）判断一个文法是否是LL(1)文法的充要条件：

1. 文法不含左递归，

2. 对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若

A→α 1|α 2|…|α n则FIRST(α i)∩FIRST(α j)＝φ(i≠j)

3. 对文法中的每个非终结符A，若它存在某个候选首符集包含ε，则FIRST(α i)∩FOLLOW(A)=φ i=1,2,...,n如果一个文法G满足以上条件，则称该文法G为LL(1)文法。

(5)LL(1)文法分析表的构造与运用

这类题目，主要就是判断文法是否满足LL(1)文法的三个充要条件，分为以下几步：

1）首先将文法分解，判断是否有左递归好，有的话肯定不是LL(1)文法；

2）算非终结符的First集合和Follow集合，具体方法请参见期中考试的提纲，其实最本质

的要抓住first集合是U

?a…，Follow集合石…Ua…即可。

3）算Select集合，书上没有提到Select集合，计算Select集合实质就是计算First(α)，当然考试时不一定非要写成Select集合形式，可以直接计算First(α)来判断交集是否为空，从而是否为LL(1)文法，请看考题1。

4）至于判断一个句子的分析过程，大家注意一下，所给的句子不一定是能通过该文法分析出来的，实际上在分析之前可以自己根据文法推推看，请看考题1.

5）分析表中没有填的空格代表出错，如果分析时遇到了代表该句子不符合该文法。

考题1：判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表并分析句子aabe 的分析过程。（15分）

S→aD D→STe|εT→bM M→bH H→M|ε

分析：判断一个文法是否为LL(1)文法是否为LL(1)文法，主要就是判断是否满足LL(1)文法的充要条件，有一个不满足就不是LL(1)文法。对于aabe根据文法S?aD?aSTe?aaDTe?aaTe?aabMe由于M不能为空字ε，所以最后肯定推不出来，也就是该句子不能由该文法推出，出错。

当然一般题目都是LL(1)文法，否则题目就不好往下做，没有意义。

答：(1)经分析该文法无左递归；

(2)①非终结符的First和Follow集合如下表所示

非终结符X First(X) Follow(X)

②将文法分解为：S→aD D→Ste D→ε T→bM M→bH H→M H→ε

依次计算：

First(aD)={a} First(Ste)={a}

Follow(D)={# b} First(bM)={b}

First(bH)={b} First(M)={b} Follow(H)={ e }

∵First(Ste)∩Follow(D)=ФFirst(M)∩Follow(H)=Ф

编译原理实验指导

编译原理实验指导实验安排：上机实践按小组完成实验任务。每小组三人，分别完成TEST语言的词法分析、语法分析、语义分析和中间代码生成三个题目,语法分析部分可任意选择一种语法分析方法。先各自调试运行，然后每小组将程序连接在一起调试，构成一个相对完整的编译器。实验报告：上机结束后提交实验报告，报告内容： 1．小组成员； 2．个人完成的任务； 3．分析及设计的过程； 4．程序的连接； 5．设计中遇到的问题及解决方案； 6．总结。

实验一词法分析一、实验目的通过设计编制调试TEST语言的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。二、实验预习提示 1．词法分析器的功能和输出格式词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示成以下的二元式(单词种别码，单词符号的属性值)。 2．TEST语言的词法规则 →|ID|ID →|NUM →a|b|…|z|A|B|…|Z →1|2|…|9|0 →+|-|*|/|=|（|）|{|}|：|，|；|＜|＞|! →＞=|＜=|！=|== →/* →*/ 三、实验过程和指导 1.阅读课本有关章节，明确语言的语法，画出状态图和词法分析算法流程图。 2.编制好程序。 3.准备好多组测试数据。 4.程序要求程序输入/输出示例：

编译原理期末考试习题及答案

一、填空题|（每题4分，共20分） 1. 乔母斯基定义的3型文法（线性文法）产生式形式 A→Ba|a,或A→aB|a，A，B∈Vn, a,b∈Vt 。 2.语法分析程序的输入是单词符号，其输出是语法单位。 3 型为 B → .aB 的LR（0）项目被称为移进项目，型为 B → a.B 的LR（0）项目被称为待约项目， 4.在属性文法中文法符号的两种属性分别为继承属性和综合属性。 5、运行时存贮管理方案有静态存储分配、动态存储分配和堆式存储分配和方案。二.已知文法 G(S) (1) E → T | E+T (2) T → F | F*F (3) F →（E）| i （1）写出句型（T*F+i）的最右推到并画出语法树。（4分）（2）写出上述句型的短语，直接短语和句柄。（4分）答：（1）最右推到（2分） E ==> T ==> F ==> (E) ==> (E+T) ==> (E+F) ==> (E+i) ==> (T+i) ==> (T*F+i) (2) 语法树（2分）（3）（4分）短语：（T*F+i），T*F+i ，T*F ， i 直接短语：T*F ， i 句柄：T*F 三. 证明文法G(S) ：S → SaS |ε是二义的。（6分）答：句子aaa对应的两颗语法树为：

因此，文法是二义文法四.给定正规文法G（S）： (1) S → Sa | Ab |b (2) A → Sa 请构造与之等价的DFA。（6分）答：对应的NFA为：（6分）状态转换表： a b {F} Φ{S} {S} {S,A} Φ {S,A} {S,A} {S} 五. 构造识别正规语言b*a(bb*a)*b* 最小的DFA（要求写出求解过程）。（15分）答：（1）对应的NFA（5分） a b {0} {1，3} {0} {1,3} Φ{2，3} {2,3} {1,3} {2,3} （5分）六. 已知文法G(S) : (1) S → ^ | a | (T) (2) T → T,S | S 试：（1）消除文法的左递归；（4分）（2）构造相应的first 和 follow 集合。（6分）答：（1）消除文法的左递归后文法 G’（S）为： (1) S → ^ | a | (T)

编译原理结课论文.doc

目录 1. 绪论 (2) 1.1概述 (2) 1.2设计目的 (2) 1.3设计题目及要求 (2) 2.背景知识 (3) 2.1语法制导翻译方法 (3) 2.2属性文法 (3) 2.3几种常见的中间语言 (4) 2.4四元式的简介 (4) 3.设计过程 (5) 3.1设计思路 (5) 3.2实现 (6) 4.上机调试运行 (6) 4.1代码调试界面及结果 (7) 4.2执行及结果 (7) 5.注意事项 (8) 6.总结 (9) 参考文献 (10) 附录 (11)

1.绪论 1.1概述 “编译原理”是一门研究设计和构造编译程序原理课程，是计算机各专业的一门重要的专业课。编译原理这门课程蕴含着计算机学科中解决问题的思路和解决问题的方法，对应用软件和系统软件的设计与开发有一定的启发和指导作用。“编译原理”是一门实践性很强的课程，要掌握这门课程中的思想，就必须要把所学到的知识应用于实践当中。而课程设计是将理论与实践相互联系的一种重要方式。1.2设计目的课程设计是对学生的一种全面综合素质训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，设计题中的问题比平时的练习题要复杂很多，但也更接近实际。编译原理这门课程安排的课程设计的目的是旨在要求学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容，选择合适的数据逻辑结构解决问题，然后编制算法和程序完成设计要求，从而进一步培养学生独立思考问题、分析问题、解决实际问题的能力。 1.3设计题目及要求基于这个学期所学习的内容以及自己所掌握到的知识，本次我所要设计的题目是赋值语句的四元式生成。

要求：（1）设计语法制导生成赋值语句的四元式的算法；（2）编写代码并上机调试运行通过；（3）输入一赋值语句；（4）输出相应的表达式的四元式； 2.背景知识 2.1语法制导翻译方法语法制导翻译的方法就是为每个产生式配上一个翻译子程序（称语义动作或语义子程序），并在语法分析的同时执行这些子程序。语义动作是为产生式赋予具体意义的手段，它一方面指出了一个产生式所产生的符号串的意义，另一方面又按照这种意义规定了生成某种中间代码应做哪些基本动作。在语法分析的过程中，当一个产生式获得匹配（对于自顶向下分析）或用于规约（对于自底向上分析）时，此产生式相应的语义子程序就进入工作，完成既定的翻译任务。语法制导翻译分为自底向上语法制导翻译和自顶向下语法制导翻译。 2.2属性文法属性文法是编译技术中用来说明程序语言语义的工具，也是当前实际应用中比较流行的一种语义描述方法。属性是指与文法符号的类型和值等有关的一些信息，在编译中用属性描述处理对象的特征。属性文法是一种适用于定义语义的特殊文法，即在语言的文法中增加了

天津理工大学编译原理期末考试试卷

天津理工大学考试试卷～2010学年度第二学期《编译原理》期末考试试卷课程代码： 0660116 试卷编号： 1-A 命题日期： 2010 年 6 月 15 日答题时限： 120 分钟考试形式：闭卷笔试大题号一二三四总分一、单项选择题（请从4个备选答案中选择最适合的一项，每小题2分，得分 1 2 3 4 5 6 7 8 9 10 D C B D D B C B D C 1. 编译程序是对（） A. 汇编程序的翻译 B. 高级语言程序的解释执行 C. 机器语言的执行 D. 高级语言的翻译 2. 词法分析器的输出结果是（） A．单词的种别编码B．单词在符号表中的位置 C．单词的种别编码和自身值D．单词自身值 3. 在规范规约中，用（）来刻画可规约串。 A．直接短语 B．句柄 C．最左素短语 D．素短语 4. 与正规式(a* | b) * (c | d)等价的正规式是（） A．a* (c | d) | b(c | d) B．a* (c | d) * | b(c | d) * C．a* (c | d)| b* (c | d) D．(a | b) * c| (a | b) * d 含有Aα·，则在状态K时，仅当面临输入符号a∈FOLLOW(A)时，才采 5. 若项目集I K 取Aα·动作的一定是（） A．LALR文法 B．LR(0) 文法C．LR(1)文法 D．SLR(1)文法 6. 四元式之间的联系是通过（）实现的。

A. 指示器 B. 临时变量 C. 符号表 D. 程序变量 7．文法G ：S x Sx | y 所识别的语言是（） A ．xyx B ．(xyx) * C ．x n yx n (n ≥0) D ．x * yx * 8. 有一语法制导翻译如下所示： S b Ab {print “1”} A (B {print “2”} A a {print “3”} B Aa) {print “4”} 若输入序列为b(((aa)a)a)b ，且采用自下而上的分析方法，则输出序列为（） A ．32224441 B. 34242421 C ．12424243 D. 34442212 9．关于必经结点的二元关系，下列叙述不正确的是（） A ．满足自反性 B ．满足传递性 C ．满足反对称型 D ．满足对称性 10．错误的局部化是指（）。 A ．把错误理解成局部的错误 B ．对错误在局部范围内进行纠正 C ．当发现错误时，跳过错误所在的语法单位继续分析下去 D ．当发现错误时立即停止编译，待用户改正错误后再继续编译二、判断题（每小题1分，共5分）得分 1. 文法G 的一个句子对应于多个推导，则G 是二义性的。（× ） 2. 动态的存储分配是指在运行阶段为源程序中的数据对象分配存储单元。（√ ） 3. 算符优先文法采用“移进－规约”技术，其规约过程是规范的。（ × ） 4. 删除归纳变量是在强度削弱以后进行。（ √ ） 5. 在目标代码生成阶段，符号表用于目标代码生成。（ × ） 5分，共15分）得分 1. 构造正规式(0∣1)* 00相应的正规式并化简。（共5分）（1）根据正规式，画出相应的NFA M （2分） I I 0 I 1 {x,1,2} {1,2,3} {1,2} {1,2,3} {1,2,3,4} {1,2} {1,2} {1,2,3} {1,2 } {1,2,3, {1,2,3,4} {1,2 } X 12 3 4 01

编译原理综合实验题

编译原理综合实验指导书一、实验任务设计、编制并调试一个中缀表达转换为后缀表达的实验程序，加深对词法分析、语法分析、语义分析及代码生成的理解。二、实验内容 1、词法输入：扩展ASCII码字符集字符。除大小写26英文字母（letter）和数字0-9（digit）以及+ - * / ^ = ; , ( )以外，所有其他字符一律按等同于空格处理，一般用来分隔单词。输出：识别单词，单词包括关键字、运算符、界符、标识符和整型常数。（1）关键字：var （2）运算符和界符：+ - * / ^ = ; , ( ) 其中：乘除运算符（*， /）返回具有不同属性值的单词mulop，加减运算符（+， -）返回具有不同属性值的单词addop。（3）标识符（id）和整型常数（num）：标识符（id）和整型常数（num）最大长度为8个字符，定义如下。 id = letter (letter | digit)* num = digit digit* 2、语法根据输入的单词序列，分析是否符合语法规则，如果不符合，应指明位置与理由；如果符合，则执行相应的语义子程序完成语义分析及中缀表达转换为后缀表达的过程。需注意的是，这里给出的是二义文法，从语义上考虑，表达式的计算按先幂次运算（^），再乘除运算（*， /）的最后加减运算（+， - ）的优先顺序；括号（(， )）用于调整运算先后顺序，既括号内部分先计算；赋值运算（=）最后进行。本实验系统的语法规则是： program → compound compound → declaration assignstatement compound | ε declaration → var identifier_list ; | ε dentifier_list →id, dentifier_list | id assignstatement →id= expression ; | ε expression → expression addop expression | expression mulop expression | expression ^ expression | ( expression ) | id | num 3、语义分析及代码生成语义分析的主要任务是判断变量是否先定义后使用。代码生成的的主要任务是将赋值语句从中缀表达转换为后缀表达。

《编译原理》模拟期末试题汇总 6套,含答案

《编译原理》模拟试题一一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） 1．计算机高级语言翻译成低级语言只有解释一种方式。(×) 2．在编译中进行语法检查的目的是为了发现程序中所有错误。(×) 3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 (√ ) 4．正则文法其产生式为 A->a ， A->Bb, A,B∈VN ， a 、b∈VT 。 (×) 5．每个文法都能改写为 LL(1) 文法。 (√) 6．递归下降法允许任一非终极符是直接左递归的。 (√) 7．算符优先关系表不一定存在对应的优先函数。 (×) 8．自底而上语法分析方法的主要问题是候选式的选择。 (×) 9．LR 法是自顶向下语法分析方法。 (×) 10．简单优先文法允许任意两个产生式具有相同右部。 (×) 二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．一个编译程序中，不仅包含词法分析，_____，中间代码生成，代码优化，目标代码生成等五个部分。 A．( ) 语法分析B．( )文法分析C．( )语言分析D．( )解释分析 2．词法分析器用于识别_____。 A．( ) 字符串B．( )语句 C．( )单词 D．( )标识符 3．语法分析器则可以发现源程序中的_____。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正D．( ) 语法错误 4．下面关于解释程序的描述正确的是_____。

(1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1)C．( ) (1)(2)(3) D．( ) (2)(3) 5．解释程序处理语言时 , 大多数采用的是_____方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 6．编译过程中 , 语法分析器的任务就是_____。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4) C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 7．编译程序是一种_____。 A. ( ) 汇编程序B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 8．文法 G 所描述的语言是_____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 9．文法分为四种类型，即0型、1型、2型、3型。其中3型文法是_____。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法 10．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _____。 A．( ) 句子B．( ) 句型 C．( ) 单词 D．( ) 产生式三、填空题(每空1分，共10分)

编译原理期末论文

编译原理期末论文一、概述算符文法：即它的任一产生式的右部都不含两个相继的非终结符的文法。如果G是一个不含空字符的算法文法，那么只要它的任一对终结符都只满足>，=，<的关系的一种，则称G是一个算符优先文法。算符文法分类：对于一个算符优先文法，只要能构造出它的算符优先表，就可以利用算符优先分析方法，分析一个句子是否符合这个文法的定义。那么定义FirstVT(P)={a|P(+=>)a···或P(+=>)Qa···，a属于终结字符集，而Q属于非终结字符集}，其中···表示所有字符集 LastVT（P）={a|P(+=>)···a或P(+=>)···aQ，a属于终结字符集，而Q 属于非终结字符集} 由以下两条规则来构造FirstVT集： (1) 若有产生式P=>a···、或P=>Qa···，则a属于FirstVT（P）； (2) 若有a属于FirstVT（Q），且有产生式P=>Q···，则a属于FirstVT(P); 类似的有构造LastVT集的规则： (1) 若有产生式P=>···a或P=>···aQ，则a属于LastVT集。 (2) 若a属于LastVT（Q），且有产生式P=>···Q，则a属于LastVT集。构造FirstVT集的算法： Begin For 每个非终结符P和终结符a Do F[P，a]=FALSE； For 每个形如P=>a...或P=>Qa...的产生式 (1) DO insert（P，a） While Stack 非空 Do Begin 把Stack 的顶项，记为（Q，a），上托出去； For每条形如P=>Q...的产生式DO . (2) Insert（P，a） End of while； END 构造LastVT集的算法：将上述算法的对应的（1），（2）分别修改为 For 每个形如P-〉…a或P-〉…aQ的产生式, For每条形如P-〉…Q的产生式便可得。假定G是一个不含空字符产生式的算符文法。对于任何一对终结符a,b,

编译原理试题及答案(期末复习版).pdf

<编译原理>历年试题及答案一．（每项选择 2 分，共 20 分）选择题 1．将编译程序分成若干个“遍”是为了_b__。 a.提高程序的执行效率 b.使程序的结构更加清晰 c.利用有限的机器内存并提高机器的执行效率 d.利用有限的机器内存但降低了机器的执行效率 2．构造编译程序应掌握__d__。 a.源程序 b.目标语言 c.编译方法 d.以上三项都是 3．变量应当 c＿。 a.持有左值 b.持有右值 c.既持有左值又持有右值 d. 既不持有左值也不持有右值 4．编译程序绝大多数时间花在_d___上。 a.出错处理 b.词法分析 c.目标代码生成 d.管理表格 5．词法分析器的输出结果是_c___。 a.单词的种别编码 b.单词在符号表中的位置 c. 单词的种别编码和自身值 d.单词自身值 6．正规式 MI 和 M2 等价是指__c__。 a. MI 和 M2 的状态数相等 b.Ml 和 M2 的有向弧条数相等。 C.M1 和 M2 所识别的语言集相等d. Ml 和 M2 状态数和有向弧条数相等 7．中间代码生成时所依据的是—c。 a．语法规则 b．词法规则c．语义规则 d．等价变换规则8．后缀式 ab+cd+/可用表达式__b_来表示。 a． a+b/c+d b． (a+b)/(c+d) c． a+b/(c+d) d． a+b+c/d 9．程序所需的数据空间在程序运行前就可确定，称为____c_＿管理技术。 a.动态存储 b.栈式存储 c.静态存储 d.堆式存储 10. 堆式动态分配申请和释放存储空间遵守___d____＿原则。 a.先请先放 b.先请后放 c.后请先放 d.任意二（每小题 10 分，共 80 分）简答题 1.画出编译程序的总体结构图，简述各部分的主要功能。 2. 已知文法 G[E]: E→ET+|T T→TF* | F F→F^ | a 试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄. 3．为正规式(a|b) *a(a|b)构造一个确定的有限自动机。 4．设文法 G(S)：

编译原理测试及答案

编译原理期中测试答案三、单项选择题(每题3分，共15分) 1．设有文法G[S]: S→(AS)|(b) A→(SaA)|(a) 该文法的句型(((b)a(a))(b))有 C 个直接短语。 A.1 B. 2 C. 3 D. 4 2．如果一个文法满足 D ，则称该文法是二义性文法。 (1) 文法的某一个句子存在两个（包括两个）以上的语法树 (2) 文法的某一个句子存在两个（包括两个）以上的最左推导 (3) 文法的某一个句子存在两个（包括两个）以上的最右推导 (4) 在进行归约时，文法的某些规范句型的句柄不唯一上述描述中的所有正确描述有： A. (1) B. (1)(2) C. (1)(2)(3) D. (1)(2)(3)(4) 3．构造一个不带回溯的自顶向下语法分析器，要求文法满足 E 。 A.对每个形如A→x1|x2|…|xn的产生式，要求FIRST(xi)与FIRST(xj)的交集为空集(i≠j) B.对每个形如A→x1|x2|…|xn的产生式，若xi* ε，则要求FIRST(xj)与FOLLOW(A)的交集为空集(i≠j) C. 不含左递归 D. A和B同时满足 E. A、B和C同时满足

4、给定文法A→bA|cc，下列符号串中，是该文法的句子的是 C 。 ① cc ② bcbc ③ bcbcc ④ bccbcc ⑤ bbbcc A① B. ①③④⑤ C. ①⑤ D. ①④⑤ 5、若一个句型中出现了某一产生式的右部，则此右部 B 是该句型的句柄。 A.一定 B. 不一定 C. 一定不 D. 无法判断四、简述题(每题5分，共20分) 1、写一上下文无关文法,它能产生语言}0 n。 n a L m b , =m | {>= # S→A#B A→Aa|ε B→Bb|ε 2、将文法G[S] 改写为等价的G′[S]，使G′[S]不含左递归和左公共因子。G[S]：S→bSAe | bA A→Ab | d 答：文法G[S] 改写为等价的不含左递归和左公共因子的 G'[S]S→bB B→SAe | A A→d A' A' →bA' | ε 3、什么是文法的二义性？下面的文法是二义的吗？为什么？

编译原理实验题目及报告要求

编译原理上机实验试题一、实验目的通过本实验使学生进一步熟悉和掌握程序设计语言的词法分析程序的设计原理及相关的设计技术，如何针对确定的有限状态自动机进行编程序；熟悉和掌握程序设计语言的语法分析程序的设计原理、熟悉和掌握算符优先分析方法。二、实验要求本实验要求：①要求能熟练使用程序设计语言编程；②在上机之前要有详细的设计报告（预习报告）； ③要编写出完成相应任务的程序并在计算机上准确地运行；④实验结束后要写出上机实验报告。三、实验题目针对下面文法G(S)： S→v = E E→E+E│E-E│E*E│E/E│（E）│v │i 其中，v为标识符，i为整型或实型数。要求完成 ①使用自动机技术实现一个词法分析程序； ②使用算符优先分析方法实现其语法分析程序，在语法分析过程中同时完成常量表达式的计算。

1、题目（见“编译原理---实验题目.doc，“实验题目”中的第一项） 2、目的与要求（见“编译原理---实验题目.doc”） 3、设计原理： (1)单词分类：标识符，保留字，常数，运算符，分隔符等等 (2)单词类型编码 (3)自动机 4、程序流程框图 5、函数原型（参数，返回值） 6、关键代码（可打印，只打印关键代码） 7、调试：（1）调试过程中遇到的错误，如何改进的；（2）需要准备测试用例（至少3个，包含输入和输出）——（可打印） 8、思考： (1)你编写的程序有哪些要求是没有完成的，你觉得该采用什么方法去完成； (2)或者是你觉得程序有哪些地方可以进一步完善，简述你的完善方案。

1、题目（见“编译原理---实验题目.doc，“实验题目”中的第二项） 2、目的与要求（见“编译原理---实验题目.doc”） 3、设计原理：构造出算法优先关系表 4、程序流程框图 5、函数原型（参数，返回值） 6、关键代码（可打印，只打印关键代码） 7、调试：（1）调试过程中遇到的错误，如何改进的；（2）需要准备测试用例（至少3个，包含输入和输出）——（可打印） 8、思考： (1)你编写的程序有哪些要求是没有完成的，你觉得该采用什么方法去完成； (2)或者是你觉得程序有哪些地方可以进一步完善，简述你的完善方案。

编译原理课程设计报告_LL(1)分析过程模拟

课程设计(论文)任务书软件学院学院软件工程专业07-1班一、课程设计(论文)题目LL(1)分析过程模拟二、课程设计(论文)工作自 2010 年 6 月 22日起至 2010 年 6月 28 日止。三、课程设计(论文) 地点: 四、课程设计(论文)内容要求： 1．本课程设计的目的（1）使学生掌握LL（1）模块的基本工作原理；（2）培养学生基本掌握LL（1）分析的基本思路和方法；（3）使学生掌握LL（1）的调试；（4）培养学生分析、解决问题的能力；（5）提高学生的科技论文写作能力。 2．课程设计的任务及要求 1）基本要求：（1）分析LL（1）模块的工作原理；（2）提出程序的设计方案；（3）对所设计程序进行调试。 2）创新要求：在基本要求达到后，可进行创新设计，如改算法效率。 3）课程设计论文编写要求（1）要按照书稿的规格打印誊写课程设计论文（2）论文包括目录、绪论、正文、小结、参考文献、附录等（3）课程设计论文装订按学校的统一要求完成 4）答辩与评分标准：（1）完成原理分析：20分；（2）完成设计过程（含翻译）：40分；（3）完成调试：20分；

（4）回答问题：20分。 5）参考文献：（1）张素琴，吕映芝，蒋维杜，戴桂兰.编译原理（第2版）.清华大学出版社（2）丁振凡.《Java语言实用教程》北京邮电大学出版社 6）课程设计进度安排内容天数地点构思及收集资料2图书馆编程与调试4实验室撰写论文1图书馆、实验室学生签名： 2009 年6 月22 日课程设计(论文)评审意见（1）完成原理分析（20分）：优（）、良（）、中（）、一般（）、差（）；（2）设计分析（20分）：优（）、良（）、中（）、一般（）、差（）；（3）完成调试（20分）：优（）、良（）、中（）、一般（）、差（）；（4）翻译能力（20分）：优（）、良（）、中（）、一般（）、差（）；（5）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性及考勤是否降等级：是（）、否（）评阅人：职称：年月日

编译原理实验报告

编译原理实验报告班级姓名：学号：自我评定：

实验一词法分析程序实现一、实验目的与要求通过编写和调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将字符形式的源程序流转化为一个由各类单词符号组成的流的词法分析方法。二、实验内容根据教学要求并结合学生自己的兴趣和具体情况，从具有代表性的高级程序设计语言的各类典型单词中，选取一个适当大小的子集。例如，可以完成无符号常数这一类典型单词的识别后，再完成一个尽可能兼顾到各种常数、关键字、标识符和各种运算符的扫描器的设计和实现。输入：由符合或不符合所规定的单词类别结构的各类单词组成的源程序。输出：把单词的字符形式的表示翻译成编译器的内部表示，即确定单词串的输出形式。例如，所输出的每一单词均按形如（CLASS，VALUE）的二元式编码。对于变量和常数，CLASS字段为相应的类别码；VALUE字段则是该标识符、常数的具体值或在其符号表中登记项的序号（要求在变量名表登记项中存放该标识符的字符串；常数表登记项中则存放该常数的二进制形式）。对于关键字和运算符，采用一词一类的编码形式；由于采用一词一类的编码方式，所以仅需在二元式的CLASS字段上放置相应的单词的类别码，VALUE字段则为“空”。另外，为便于查看由词法分析程序所输出的单词串，要求在CLASS字段上放置单词类别的助记符。三、实现方法与环境词法分析是编译程序的第一个处理阶段，可以通过两种途径来构造词法分析程序。其一是根据对语言中各类单词的某种描述或定义（如BNF），用手工的方式（例如可用C语言）构造词法分析程序。一般地，可以根据文法或状态转换图构造相应的状态矩阵，该状态矩阵同控制程序便组成了编译器的词法分析程序；也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序的另外一种途径是所谓的词法分析程序的自动生成，即首先用正规式对语言中的各类单词符号进行词型描述，并分别指出在识别单词时，词法分析程序所应进行的语义处理工作，然后由一个所谓词法分析程序的构造程序对上述信息进行加工。如美国BELL实验室研制的LEX就是一个被广泛使用的词法分析程序的自动生成工具。总的来说，开发一种新语言时，由于它的单词符号在不停地修改，采用LEX等工具生成的词法分析程序比较易于修改和维护。一旦一种语言确定了，则采用手工编写词法分析程序效率更高。四、实验设计 1）题目1：试用手工编码方式构造识别以下给定单词的某一语言的词法分析程序。语言中具有的单词包括五个有代表性的关键字begin、end、if、then、else；标识符；整型常数；六种关系运算符；一个赋值符和四个算术运算符。参考实现方法简述如下。单词的分类：构造上述语言中的各类单词符号及其分类码表。表I 语言中的各类单词符号及其分类码表单词符号类别编码类别码的助记符单词值

编译原理试题(卷)汇总-编译原理期末试题(卷)(8套含答案解析-大题集)

编译原理结课论文

1.绪论概述 “编译原理”是一门研究设计和构造编译程序原理课程，是计算机各专业的一门重要的专业课。编译原理这门课程蕴含着计算机学科中解决问题的思路和解决问题的方法，对应用软件和系统软件的设计与开发有一定的启发和指导作用。“编译原理”是一门实践性很强的课程，要掌握这门课程中的思想，就必须要把所学到的知识应用于实践当中。而课程设计是将理论与实践相互联系的一种重要方式。设计目的课程设计是对学生的一种全面综合素质训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，设计题中的问题比平时的练习题要复杂很多，但也更接近实际。编译原理这门课程安排的课程设计的目的是旨在要求学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容，选择合适的数据逻辑结构解决问题，然后编制算法和程序完成设计要求，从而进一步培养学生独立思考问题、分析问题、解决实际问题的能力。设计题目及要求基于这个学期所学习的内容以及自己所掌握到的知识，本次我所要设计的题目是赋值语句的四元式生成。

要求：（1）设计语法制导生成赋值语句的四元式的算法；（2）编写代码并上机调试运行通过；（3）输入一赋值语句；（4）输出相应的表达式的四元式； 2.背景知识语法制导翻译方法语法制导翻译的方法就是为每个产生式配上一个翻译子程序（称语义动作或语义子程序），并在语法分析的同时执行这些子程序。语义动作是为产生式赋予具体意义的手段，它一方面指出了一个产生式所产生的符号串的意义，另一方面又按照这种意义规定了生成某种中间代码应做哪些基本动作。在语法分析的过程中，当一个产生式获得匹配（对于自顶向下分析）或用于规约（对于自底向上分析）时，此产生式相应的语义子程序就进入工作，完成既定的翻译任务。语法制导翻译分为自底向上语法制导翻译和自顶向下语法制导翻译。属性文法属性文法是编译技术中用来说明程序语言语义的工具，也是当前实际应用中比较流行的一种语义描述方法。属性是指与文法符号的类型和值等有关的一些信息，在编译中用属性描述处理对象的特征。属性文法是一种

期末考试编译原理试卷及答案

一．填空题（每空2分，共20分） 1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静态存储分配方案和动态存储分配方案，而后者又分为（1）和（2）。 2. 规范规约是最（3）规约。 3. 编译程序的工作过程一般划分为5个阶段：词法分析、（4）、语义分析与中间代码生成，代码优化及（5）。另外还有（6）和出错处理。 4．表达式x+y*z/(a+b)的后缀式为（7）。 5．文法符号的属性有综合属性和（8）。 6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..20]某个元素a[i ，j]的地址计算公式为（9）。 7．局部优化是局限于一个（10）范围内的一种优化。二．选择题（1-6为单选题，7-8为多选题，每问2分，共20分） 1. 一个上下文无关文法G 包括四个组成部分：一组终结符，一组非终结符，一个（），以及一组（）。 A ．字符串 B ．产生式 C ．开始符号 D ．文法 2.程序的基本块是指（）。 A ．一个子程序 B ．一个仅有一个入口和一个出口的语句 C ．一个没有嵌套的程序段 D ．一组顺序执行的程序段，仅有一个入口和一个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（）分析方法。 A ．自左向右 B ．自顶向下 C ．自底向上 D ．自右向左 4．在通常的语法分析方法中，（）特别适用于表达式的分析。 A ．算符优先分析法 B ． LR 分析法 C ．递归下降分析法 D ． LL （1）分析法 5．经过编译所得到的目标程序是（）。 A ．四元式序列 B ．间接三元式序列 C ．二元式序列 D ．机器语言程序或汇编语言程序 6．一个文法所描述的语言是（）；描述一个语言的文法是（）。 A ．唯一的 B ．不唯一的 C ．可能唯一，也可能不唯一 7．如果在文法G 中存在一个句子，当其满足下列条件（）之一时，则称该文法是二义文法。 A ．其最左推导和最右推导相同 B ．该句子有两个不同的最左推导 C ．该句子有两个不同的最右推导 D ．该句子有两棵不同的语法树

《编译原理》课程设计题目-2014

《编译原理》课程设计题目设计题一：正规式r与正规文法G相互转换的程序设计任意给定一个正规式，求出其对应的正规文法；任意给定一个正规文法，求出其对应的正规式。（参考教材P53～55）设计题二：布尔表达式的递归下降翻译器针对布尔表达式的文法：〈布尔表达式〉∷＝〈布尔项〉{〈与运算符〉〈布尔项〉} 〈与运算符〉∷＝and 〈布尔项〉∷＝〈布尔因子〉{〈或运算符〉〈布尔因子〉} 〈或运算符〉∷＝or 〈布尔因子〉∷＝〈非运算符〉〈布尔因子〉｜〈布尔量〉〈非运算符〉∷＝not 〈布尔量〉∷＝（〈布尔表达式〉）｜〈标识符〉〈关系运算符〉〈标识符〉｜ true｜false 〈关系运算符〉∷＝＞｜＜｜≥｜≤｜＝｜≠ 〈标识符〉∷＝〈字母〉{〈字母〉｜〈数字〉} 利用递归下降分析法编制、调试其语法及语义分析程序，生成的中间代码为逆波兰式。编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（参考教材P92～93）设计题三：正规式r与有穷自动机FA相互转换的程序设计任意给定一个正规式，求出其对应的有穷自动机；任意给定一个有穷自动机，求出其对应的正规式。（参考教材P61～64）设计题四：赋值语句的LR翻译程序对教材P180中的赋值语句文法，给出该文法的属性文法，同时实现赋值语句的翻译，生成的中间代码为逆波兰式。（参考教材P179～181）设计题五：正规文法G与有穷自动机FA相互转换的程序设计任意给定一个正规文法，求出其对应的有穷自动机；任意给定一个有穷自

动机，求出其对应的正规文法。（参考教材P65～66）设计题六：条件语句的LR翻译程序对教材P187中的条件语句文法，给出该文法的属性文法，同时实现条件语句的翻译，生成的中间代码为四元式。（参考教材P186～189）设计题七：NFA确定化为DFA及化简的程序设计任意给定一个NFA，将其确定化为DFA，然后化简为最小的DFA。（参考教材P57～61）设计题八：布尔表达式的LR翻译器针对布尔表达式的文法： B →B and T | T T→T or F | F F→not F|true｜false |（B）| i rop i 利用LR分析法编制、调试其语法及语义分析程序，生成的中间代码为四元式。编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（参考教材P181～182）设计题九：生成预测分析表的算法实现任意给定一个LL(1)文法，生成相应的LL(1)分析表。（参考教材P75第5章）设计题十：while循环语句的LR翻译程序对教材P187中的循环语句文法，给出该文法的属性文法，同时实现循环语句的翻译，生成的中间代码为四元式。（参考教材P186～189）设计题十一：利用LEX自动生成词法分析程序输入描述某种语言词法规则的正规式，利用LEX自动生成词法分析程序。（参考教材P66～68）设计题十二：生成LR分析表的算法实现任意给定一个LR文法，生成相应的LR分析表。（参考教材P123第7章）设计题十三：布尔表达式翻译为逆波兰式的算法实现针对布尔表达式的二义性文法： B → B and B | B or B | not B | ( B ) | true｜false| i rop i 将文法拓广为G’[B’]： (0) B’ → B