东南大学编译原理试卷

99年编悔原理一.已知疋规文法中的左线件文法Gt: STSaLSbLc试枸诜无E产生式的等价佑纯性艾法・井构造相应的确定有限自动机dm 耐I］状态I 换图叩可.二、已知正规文法G2:X->0Y| IZ|OY->OX| IY|IZ-> IX⑴该文法产生的语宫恳什么•讷用正规式我示(2)枸造最简的确定有限自动机M比并画出状态转换图三、已知上下文无关文法G3: E9ET+ITTTT和」FFTE|i(1)消除文法左递归，并给;II改写后文法产生式(2)给出文法「鹤话的个非终结符的first TH follow集，并山此判師它見否1丄⑴文法四、已知表达式(已拓广)G4: ETEE->E i-E|i(!)试构进文法G4的LR(I)项『1集观范换(2)若忖咖从右结合率.WfftJh LR 5)折农五、已知文法G5:Z->bMbM-^(Ma) | a(1)试枸造算符优先分折我(2)若某相邻的终结符讣间廉亦a<=b曲伸关系，那么在进行外符优先分忻倣规约动作时，在寻找栈顶的素短语符号冷时翌杳吾它与哪个产生式右部符号小匹配.例如栈顶申・・.・aAba, (a b JffiT V T, A J®于(VN5)・ a<*b, aw V* )为已知可规约•而现右产生式X J aAba.M取素短语冰ba进行规约：苦只有产生武YT Aba.W么就取Aba进行规约.试按此规定的体法给：IH5^b((na)a)b//的％符优先分折过阳.沢、初译成中间代码I、将如下程作段酬邙成麻紛匕JiWL维数细po卯1屮・设讪血为1t:=!6;b:«20;while tob doelseb:«b -t;2、译布尔茨达式成四元式JT 列，并猜出待烦頁假傩序号.(a>b 卜 1) and not (c-»2<d) or f(x)注：f(x)为布尔函数七.有一个如下计算mF 的C 语宫程存,试给出运行时誥个栈式数据结构•数抵区的活 动记录结枸如右用.(数抿区从k 单元开始缩址•除返回他址不轨外.其余都耍橫.)八、乜知如下程序段a:«l;while a<=IO dobeginif aob then A(a, bJc^AJa, b] » 2;a:=a+1end; 1、 按语法和导生成四元式中间代码序列2、 将中何代码序迥划倔水块.画川程用流图，并J&tBM 环结点集3、 执行循环中代码外捉、啸度减弱优化和基木块内侧除公共了茨达武优化，泉后画;||包含 优化后的中何代码的稈序流图・注：数细按行疗放，侮个下标变駅占一字編址,甘地址为叙kkA int m;«n)int n;(int c;if(n= =0) c=m; elsec= f(n-l)*2; rettim(c))tnaii1()(int n°2;m=5;函妆返回值 局部变別区 主用用m 亦的数抿区函数数用区。

《编译原理》考试试题及答案（附录）一、判断题：1.一个上下文无关文法的开始符，可以是终结符或非终结符。

( X )2.一个句型的直接短语是唯一的。

( X )3.已经证明文法的二义性是可判定的。

（ X ）4.每个基本块可用一个DAG表示。

（√）5.每个过程的活动记录的体积在编译时可静态确定。

（√）6.2型文法一定是3型文法。

（ x ）7.一个句型一定句子。

( X )8.算符优先分析法每次都是对句柄进行归约。

(应是最左素短语) ( X )9.采用三元式实现三地址代码时，不利于对中间代码进行优化。

（√）10.编译过程中，语法分析器的任务是分析单词是怎样构成的。

( x )11.一个优先表一定存在相应的优先函数。

( x )12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。

( )13.递归下降分析法是一种自下而上分析法。

( )14.并不是每个文法都能改写成LL(1)文法。

( )15.每个基本块只有一个入口和一个出口。

( )16.一个LL(1)文法一定是无二义的。

( )17.逆波兰法表示的表达试亦称前缀式。

( )18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。

( )19.正规文法产生的语言都可以用上下文无关文法来描述。

( )20.一个优先表一定存在相应的优先函数。

( )21.3型文法一定是2型文法。

( )22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。

( )二、填空题：1.( 最右推导 )称为规范推导。

2.编译过程可分为（词法分析），（语法分析），（语义分析和中间代码生成），（代码优化）和（目标代码生成）五个阶段。

3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（）。

4.从功能上说，程序语言的语句大体可分为（）语句和（）语句两大类。

5.语法分析器的输入是（），其输出是（）。

6.扫描器的任务是从（）中识别出一个个（）。

( （ （ （ （ （ ( ( （ ( ( ( ( ( ( ( ( ( ( ( ( ( 10.× 22.√
) ） ） ） ） ） ) ) ） ) ) ) ) ) ) ) ) ) ) ) ) ) 11.
二、填空题： 2.编译过程可分为 （ 词法分析） ， （语法分析） ， （语义分析与中间代码生成 ） ， （优化）和（目标 代码生成 ）五个阶段。 3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（ 二义性的 4.从功能上说，程序语言的语句大体可分为（ 5.语法分析器的输入是（ 单词符号 6.扫描器的任务是从（ 源程序中 执行性 ）语句和（说明性 ） 。 ） 。 ） ，其输出是（ 语法单位 ）中识别出一个个（ 单词符号 ） 。 ）语句两大类。
因此，文法 G[为二义文法。
五.计算题（10 分） 已知文法 A->aAd|aAb| ε
判断该文法是否是 SLR(1) 文法，若是构造相应分析表，并对输入串 ab# 给出分析过程。 解：增加一个非终结符 S/后，产生原文法的增广文法有： S'->A A->aAd|aAb|ε 下 面 构 造 它 的 LR(0) 项 目 集 规 范 族 为 ：
对输入串 ab#给出分析过程为：
一、是非题：
1.一个上下文无关文法的开始符，可以是终结符或非终结符。 2.一个句型的直接短语是唯一的。 3.已经证明文法的二义性是可判定的。 4.每个基本块可用一个 DAG 表示。 5.每个过程的活动记录的体积在编译时可静态确定。 6.2 型文法一定是 3 型文法。 7.一个句型一定句子。 8.算符优先分析法每次都是对句柄进行归约。 X 9.采用三元式实现三地址代码时，不利于对中间代码进行优化。 10.编译过程中，语法分析器的任务是分析单词是怎样构成的。 11.一个优先表一定存在相应的优先函数。 13.递归下降分析法是一种自下而上分析法。 14.并不是每个文法都能改写成 LL(1)文法。 15.每个基本块只有一个入口和一个出口。 16.一个 LL(1)文法一定是无二义的。 17.逆波兰法表示的表达试亦称前缀式。 18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 19.正规文法产生的语言都可以用上下文无关文法来描述。 20.一个优先表一定存在相应的优先函数。 21.3 型文法一定是 2 型文法。 22.如果一个文法存在某个句子对应两棵不同的语法树， 则文法是二义性的。 答案：1.× 12.√ 13.× 2.× 14.√ 3.× 15.√ 4.√ 16.√ 5.√ 17.× 6.× × 18.√ 19.√ 20.× 21.√ 7.× 8.× 9.√ X 12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。

东 北 大 学秦 皇 岛 分 校课程名称： 编译原理 试卷： (B )答案 考试形式： 闭卷授课专业： 计算机科学与技术 考试日期： 年 月 日 试卷：共 2 页 题号 一 二 三 四 总分得分 阅卷人一、填空题（每空2分，共30分）1、编译程序的整个过程可以从逻辑上划分为词法分析、 语法分析 、语义分析、中间代码生成、 代码优化 和目标代码生成等几个阶段，另外还有两个重要的工 作是 理 和出错处理。

表格管2、规范规约中的可归约串是 句柄 ，算符优先分析中的可归约串是 最左素短语 。

3、语法分析方法主要可分为 自顶向下 和 自底向上 两大类。

4、LR （0）文法的项目集中不会出现 移进-归约 冲突和 归约-归约 冲突。

5、数据空间的动态存储分配方式可分为 栈式 和 堆式 两种。

6、编译程序是指能将 源语言 程序翻译成 目标语言 程序的程序。

7、确定有穷自动机DFA 是 NFA 的一个特例。

8、表达式 (a+b)*c 的逆波兰表示为 ab+c* 。

二、选择题（每题2分，共20分）1、LR 语法分析栈中存放的状态是识别 B 的DFA 状态。

A 、前缀B 、可归前缀C 、项目D 、句柄 2、 D 不可能是目标代码。

A 、汇编指令代码B 、可重定位指令代码C 、绝对机器指令代码D 、中间代码 3、一个控制流程图就是具有 C 的有向图A 、唯一入口结点B 、唯一出口结点C 、唯一首结点D 、唯一尾结点 4、设有文法G[S]：S →b|bBB →bS ，则该文法所描述的语言是C 。

A 、L （G ）={b i |i ≥0}B 、L （G ）={b 2i |i ≥0}C 、L （G ）={b 2i+1|i ≥0}D 、L （G ）={b 2i+1|i ≥1}5、把汇编语言程序翻译成机器可执行的目标程序的工作是由 B 完成的。

A 、编译器B 、汇编器C 、解释器D 、预处理器 6、在目标代码生成阶段，符号表用于 D 。

其SLR(1)分析表为：
对输入串ab#给出分析过程为：
一、是非题：
1.一个上下文无关文法的开始符，可以是终结符或非终结符。 ( )
2.一个句型的直接短语是唯一的。 （ ）
3.已经证明文法的二义性是可判定的。 （ ）
4.每个基本块可用一个DAG表示。 （ ）
5.每个过程的活动记录的体积在编译时可静态确定。 （ ）
1．编译程序是对高级语言程序的解释执行。(× )
2．一个有限状态自动机中，有且仅有一个唯一的终态。(×)
3．一个算符优先文法可能不存在算符优先函数与之对应。(√ )
4．语法分析时必须先消除文法中的左递归。(×)
5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。(√)
6．逆波兰表示法表示表达式时无须使用括号。(√ )
2.考虑文法G[S]:
S → (T) | a+S | a
T → T,S | S
消除文法的左递归及提取公共左因子。
解：消除文法G[S]的左递归：
S→(T) | a+S | a
T→ST′
T′→,ST′| ε
提取公共左因子：
S→(T) | aS′
S′→+S | ε
T→ST′
T′→,ST′| ε
3.试为表达式w+(a+b)*(c+d/(e-10)+8)写出相应的逆波兰表示。
8.一个过程相应的DISPLAY表的内容为(现行活动记录地址和所有外层最新活动记录的地址)
10.常用的两种动态存贮分配办法是（栈式）动态分配和（堆式）动态分配。
11.一个名字的属性包括( 类型)和(作用域 )。
12.常用的参数传递方式有(传地址），（传值），（传名）

编译原理考试试卷一、选择题（每题2分，共20分）1. 编译器的主要功能是将源代码转换成目标代码，以下哪个不是编译器的基本组成部分？A. 词法分析器B. 语法分析器C. 代码优化器D. 运行时环境2. 词法分析器通常不负责以下哪项任务？A. 识别关键字B. 识别标识符C. 进行语义分析D. 去除空白字符3. 语法分析中，递归下降分析是一种：A. 确定性分析方法B. 非确定性分析方法C. 基于语法制导的分析方法D. 基于语法树的分析方法4. LR分析器是用于处理：A. 上下文无关文法B. 上下文有关文法C. 正则文法D. 链式文法5. 语义分析的目的是：A. 检查源代码的语法是否正确B. 检查源代码的语义是否正确C. 将源代码转换为目标代码D. 优化源代码6. 代码生成阶段，编译器将抽象语法树转换成：A. 目标代码B. 源代码C. 汇编代码D. 机器代码7. 编译优化中，常量折叠是一种：A. 局部优化B. 全局优化C. 过程间优化D. 模块内优化8. 编译器的前端主要负责：A. 源代码的输入B. 目标代码的生成C. 源代码的解析和翻译D. 运行时错误检测9. 编译器的后端主要负责：A. 词法分析B. 语法分析C. 代码优化D. 目标代码的生成和链接10. 以下哪个是编译原理中常用的数据结构？A. 栈B. 队列C. 链表D. 所有选项都是二、简答题（每题10分，共30分）1. 简述编译原理中词法分析器的作用及其实现方式。

2. 描述语法分析中自顶向下分析和自底向上分析的区别。

3. 解释编译优化的重要性，并给出一个优化的例子。

三、计算题（每题25分，共50分）1. 给定一个简单的算术表达式 "3 + 4 * 2 - 1"，请说明如何使用递归下降分析器来解析这个表达式，并给出相应的语法树。

2. 假设你有一个简单的编译器后端，需要将四元式 "(a, b, +, c)" 转换成目标代码。

编译原理复习材料选择题1. 文法S→0S | S1 | 0的语言是( )。

A. { 0 m1m| m >=0 }B. { 0 m1m| m >=1 }C. { 0 m1n | m>=1,n>=0 }D. { 0 m1n | m>=0,n>=1 }2. 描述程序语言所采用的Ⅲ型文法是( )。

A. 短语文法B.正规文法C.上下文无关文法D.上下文有关文法3. 状态转换图实现的简单方法是使每个状态结对应( )。

A.一个终结符B.一个非终结符C.一段小程序D.一个函数4. 规范归约的关键问题是寻找( )。

A. 最左素短语B.句柄C.直接短语D.短语5. 一个算符文法的任何产生式的右部都不含有两个相继的( )。

A.终结符B.非终结符C.终结符和非终结符D.空字6. 算符优先分析法的关键在于规定( )。

A.算符优先顺序和结合性质B.算符优先顺序C.结合性质D.终结符和非终结符之间关系7. 优先函数的优点是( )。

A.形象直观B.便于进行比较运算C.语法分析速度快D.语法分析方法简单8. 文法符号的属性通常分为( )两类。

A. 共用属性和私有属性B.固有属性和可变属性C.语法属性和语义属性D.综合属性和继承属性9. 在程序流图中，组成循环的结点序列应满足( )A. 它们是强连通的B.它们中间有唯一的入口结点C.它们中间有一条回边D.它们是强连通的且有唯一的入口结点10. 在利用寄存器R生成T1:=C/B的目标代码同时,还应记录信息( )。

A. C/B在T1中B. T1在C/B中C. R含有T1, T1在R中D. R含有C/B, C/B在R中1.D2.B3.C4.B5.B6.A7.B8.D9.D 10.C1. 编译方式与解释方式的根本区别在于( )A.是否生成目标代码B.是否生成中间代码C.是否生成汇编代码D.是否生成优化代码2. 编译程序生成的目标程序( )A.一定是机器语言的程序B.不一定是机器语言的程序C.一定不是机器语言的程序D.一定是汇编语言的程序3. 设字母表∑={0,1,x,y}, 则∑上的正规式ε所对应的正规集为( )A.εB. {ε0,1,x,y }C. {ε}D.Φ4. *假设G是一个文法，S是文法的开始符号，如果S===> x,则称x是( )A.短语B.句柄C.句子D.句型5. 一个算符文法的任何产生式的右部都不含有两个相继的( )A.终结符B.非终结符C.终结符和非终结符D.ε字6. 设有文法G[A]：A →Ax|Ay|Aa|Ac|a|b|c，下列哪些是该文法的句子( )(1) aby (2) aycyx (3) aaa (4) bcxyA.(1) (2) (3)B. (1) (2) (4)C.(2) (3) (4)D.全部7. ＬＲ分析器的核心部分是( )A.带先进后出存贮器的DFAB.一张动作表C.一张GOTO表D.一张分析表8. 在程序流图中，组成循环的结点序列应满足( )A.它们是强连通的且有唯一的入B.它们中间有唯一的入口结点口结点C.它们中间有一条回边D.它们是强连通的9. 表达式a≤b＋c∧a＞d∨a＋b≠e的后缀式式为( )。

东南大学1997编译原理试题一:文法G1:E→ET+|TT→TF*|FF→FP↑|PP→E|i1.试证明符号串TET+*i↑是G1的一个句型(要求画出语法树).2.写出该句型的所有短语,简单短句和句柄.二:1.给出下图FA的正规式.a b──→ ──→ ②→○ ① a↑↓ε←── ←── ③ε b2.已知正规文法G2:S→aS|AA→bBB→aB|ε试构造一确定有限自动机DFA(要求化简),使得它接受的语言正是该文法产生的语言,要求画出状态图.三:1.试写出一个上下文无关文法G3,它能产生配对的圆括号串(例如,(),(()),()(())等,甚至包含0对括号).2.使用文法G3给出输入串(())()#的自上而下分析过程.四:已知文法G4:S→aAb|Sc|εA→aAb|ε1.给出G4文法的LR(0)项目集规范族;2.构造SLR分析表;3.G4文法所定义的语言;4.已知有如下文法及相应的LR分析表,试给出语句01001#的LR分析过程(填写下表).S→AAAA→1AA→0LR分析表:───┬──┬──┬──┰──┬──状态│ 1│ 0│ #┃ S│ A───┼──┼──┼──╂──┼──0 │ S3 │ S4 │ ┃ 1│ 21 │││acc ┃│───┼──┼──┼──╂──┼──2 │ S3 │ S4 │┃│ 5───┼──┼──┼──╂──┼──3 │ S3 │ S4 │┃│ 6───┼──┼──┼──╂──┼──4 │ r3 │ r3 │ r3 ┃│───┼──┼──┼──╂──┼──5 │ S3 │ S4 │┃│ 7───┼──┼──┼──╂──┼──6 │ r2 │ r2 │ r2 ┃│───┼──┼──┼──╂──┼──7 │││ r1 ┃│───┴──┴──┴──┸──┴──分析过程:──────┬──────┬──────状态栈│符号栈│ 输入串──────┼──────┼──────││││││││││││││──────┴──────┴──────五: 1.翻译下面语句成四元式中间代码序列和后缀式(逆波兰式);while x+y>a doif a<10 then a:=a+1 else x:=x-1;2.翻译布尔表达式(a>b) or (c=d) and not (e成转移四元式序列(即四元式中仅包含(zθ,-,-,-)和(j,-,-,-)两类语句,其中θ为关系运算符.)六: 1.有如下Fortran说明语句,试借助符号表登记等价环链EQ和相对数OFFSET,即填写下表的EQ栏和OFFSET栏.设每个整型量占1子编址.integer a,b,c(10,10),d(10)equivalence (a,d(8),c(5,5))equivalence (b,c(5,8))符号表┌───┬─────┬───┬───┐│ name │ ... │ EQ │OFFSET│1│ a │ ... │ ││├───┼─────┼───┼───┤2│ b │ ... │ │ │├───┼─────┼───┼───┤3│ c │ ... │ │ │├───┼─────┼───┼───┤4│ d │ ... │ │ │└───┴─────┴───┴───┘2.有如下pascal语言的程序轮廓,当运行该程序且第一次递归调用Q过程(即在过程Q中又调用了Q)时,数据区建立情况.假定各数据区首址用SP(i)(i=0,1,……)表示,试给出P,Q数据区的display表.┌ main│┌ P││┌ Q│││ Call Q││└││ Call Q│└│┌ R││ Call P│└│┌ S││ Call R│└│ Call S└七:已知如下流图,试给出回边与循环.↓┌─→①←┐│/ \ /│ ↓↓/\ ②③\ \ /↑\↓↓/┌→④──┐│ │ ↓│ │┌→⑤│ ↓/ │└─⑥←─┘东南大学1998编译原理试题一:已知文法G1:S→aB|εB→b C|bDC→cB|cD→d1.试构造一个最小DFA,画出状态转换图.2.由该DFA给出它所识别的语言(用正规式表示).二:已知正规式α=ab*c*d,1.试构造一个DFAM,其接受的语言为此α(画出图);2.由该DFAM写出对应的正规文法(古线性).三:文法G3:S→A[B]A→[B]|AaB→a1.求出各非终结符N的Firstvt(N)和Lastvt(N),构造包括语句括号'#'在内的算符优先表;2.给出语句#[a][a]#的算符优先分析过程,即填写如下格式的表:步骤│ 栈内│ 输入串│ 动作────┼───┼────┼─────0 │# │[a][a]# │... │││四:已知文法G4:T→T*F|FF→(T)|i1.试给出语句(i*i)#的自上而下分析过程(填下表);2.画出对应的语法树,指出每一步归纳的句柄.步骤│ 栈内│ 输入│ 动作────┼───┼────┼─────0 │#T │ (i*i)# │... │││五:已知文法G5:0. E'→E1. E→E+T2. E→T3. T→i列出LR(0)项目集规范族,求出各非终结符N的Follow集合,构造SLR分析表.六:翻译如下语句成四元式序列(由语法制导生成).while a>b and aif a=5 then b:=b+1 elserepeata:=a+1until a>=d;七:按语法制导翻译下段程序成四元式序列(不要优化),设数组A:array[1..10,1..10] of int;每个下标变量占1字编址,数组按行存放,Z为函数名.beginA[i,j]:=A[i,j]+2;B:=Z(A[i,j])*5end八:将如下一段四元式序列进行块内优化和循环优化(强度减弱及删除基本归纳变量),写出优化后的四元式序列.(要求先划分基本块)(1) i:=1(2) if i>100 goto (10)(3) T1:=20*i(4) M:=J+T1(5) T2:=20*i(6) N:=K+T2(7) O:=M+N(8) i:=i+1(9) goto (2)(10) ...九:已知如下一段程序,试给出运行时整个数据区结构.假定num初值为2,每个数据区的活动记录包含内容如下图所示,数据区从k单元开始编址.┌─────┐ progr am factoral;│函数返回值│ var num,fact:int;├─────┤ function f(n:int):int│ 变量单元│ if n>0 then f:=n*f(n-1)├─────┤ else f:=1;│display 表│ begin├─────┤ read(num);│ 形参单元│ fact:=f(num)├─────┤ end│ 返回地址│├─────┤│基SP │└─────┘东南大学1999编译原理试题一:已知正规文法中的左线性文法G1:S→Sa|Sb|c试构造无ε产生式的等价右线性文法,并构造相应的确定有限自动机DFA,画出状态转换图即可.二:已知正规文法(X为开始符号)G2: X→0Y|1Z|0Y→0X|1Y|1Z→1X1.该文法产生语言是什么?请用正规式表示.2.构造最简的确定有限自动机DFA,并画出状态转换图.三:已知上下文无关文法(E为开始符号)G3: E→ET+|TT→TF*|FF→E|i1.消除文法左递归,并给出改写后的文法产生式;2.给出文法改写以后的各非终结符X的First(X)与Follow(X)集合,并由此判定它是否是LL(1)文法(按下表填).V(N) │ First(X) │ Follow(X)───┼─────┼───────X ││───┼─────┼───────...││───┼─────┼───────││四:已知表达式文法(已拓广)G4: E'→EE→E+E|i1.试构造文法G4的LR(0)项目集规范族;2.若'+'服从右结合率,请给出LR分析表.五:已知文法(Z为开始符号)G5: Z→bMbM→(Ma)|a1.试构造算符优先分析表(即填下表);│ a │ b │( │ ) │# │──┼──┼──┼──┼──┼──┼a ││││││──┼──┼──┼──┼──┼──┼b ││││││──┼──┼──┼──┼──┼──┼( ││││││──┼──┼──┼──┼──┼──┼) ││││││──┼──┼──┼──┼──┼──┼# ││││││──┼──┼──┼──┼──┼──┼2.若某相邻的终结符a,b间存在a<=b两种关系,那么在进行算符优先分析做归约动作时,在寻找栈顶的素短语符号串时要察看它与哪个产生式右部的符号串匹配. 例如栈顶串...aAbα(a,b↔VT,A↔(VA∪ε),a<=b,α↔V*)为已知可归约,而现有产生式X→aAbα,则取素短语aAbα,若只有产生式Y→Abα,那么就取Abα进行归约.试按此规定的算法给出语句b((aa)a)b的算符优先分析过程.六:翻译成中间代码.1.将如下程序段翻译成后缀式(逆波兰式),填在一维数组POST[i]中,设i初值=1. t:=15;b:=20;while t<>b doif t>b then t:=t-belse b:=b-t;2.翻译布尔表达式成转移四元式序列,并指出待填真假链序号.(a>b+1) and not (c+2注:f(x)为布尔函数.七:有如下一个计算m*2^n的C语言程序,试给出运行时整个栈或数据区的结构.数据区的活动记录结构如图所示.┌──────┐┌─────┐│ 函数f返回值││返回结果值│├──────┤├─────┤│ 局部变量区││局部变量区│├──────┤├─────┤│ 全程变量区││形参单元区│├──────┤├─────┤│ 主程序main ││ 返回地址││ 数据区│├─────┤└──────┘│ 基SP │├─────┤│函数数据区│└─────┘int m;f(n)int n;{ int c;if (n==0) c=m;else c=f(n-1)*2;return (c);}main(){ int n=2;m=5;printf("%d\n",f(n));}八:已知如下程序段a:=1;while a<=10 dobeginif a<>b thenA[a,b]:=A[a,b]+2;a:=a+1;end;1.按语法制导生成四元式中间代码序列;2.将中间代码序列划分成基本块,画出程序流图,并指出循环结点集;3.执行循环中代码外提,强度减弱优化和基本块内删除公共子表达式优化,最后画出包含优化后的中间代码的程序流图.注:数组A: array[1..10,1..10] of int;按行存放,每个下标变量占1字编址,首地址为addrA上海交通大学1998年编译原理试题一、生成语言l={albmclanbn l>=0,m>=1,n>=2 }的文法是什么？它是chomsky那一型文法？二、文法G1：P aPQR abRRQ QRBQ bbbR bccR cc它是chomsky哪一型文法？请证aaabbbccc是G1的一个句子。

东南大学编译原理试卷S o ut he a s t Uni v e r si ty E xa mi na ti o n P a per (i n-t e r m) Course Name Principles of Compiling Examination Term Score Related Major Computer &SoftwareExamination Form Close test Test Duration120 MinsThere are 5 problems in this paper. Y ou can write the answers inEnglish or Chinese on the attached paper sheets.1.Please construct context-free grammars with ε-free productionsfor the following languages (20%).(1){i|i∈N(Natural number), and i is a palindrome, and (i mod 5)=0}(2){ω| ω∈(a,b,c,d)* and the numbers of a’s ,b’s and c’s occurred inω are even, and ωstarts with a or c , ends with d }2.Please construct a DFA with minimum states for the followingregular expression. (20%)(((a|b)*a)*(a|b))*(a|b)3.Please eliminate the left recursions (if there are)and extractmaximum common left factors (if there are) from the followingcontext free grammar, and then decide the resulted grammar iswhether a LL(1) grammar by constructing the related LL(1) parsing table.(20%) Please obey the rules of examination. If you violate the rules, your answer sheets will be invalid共 2 页第 1 页S→iEtS|iEtSeS|aE→E and F|FF→ F or G|GG→b4.Please construct a LR(1) parsing table for the followingambiguous grammar with the additional conditions that all θi (i=1,2) has the properties of right associative law, andθ2has lower precedence than θ1.(20%)E→E θ1 E| E θ2 E |(E)|i5.Please show that if a grammar G is a LL(1) grammar, then Gmust be a LR(1) grammar (20%):共 2 页第 2 页。

南工大编译原理期末试卷2019篇一：一、简答题1.什么就是编译程序？答：编译程序是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序。

将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。

2.请写出文法的形式定义？请问：一个文法g抽象地则表示为四元组 g=（vn,vt,p,s）–其中vn表示非终结符号– vt则表示破灭符号，vn∪vt=ｖ(字母表)，vn∩vt=φ– s是开始符号，– p就是产生式，形例如：α→β(α∈v+且至少所含一个非破灭符号，β∈v*)3.语法分析阶段的功能是什么？请问：在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(基准：程序、语句、表达式)。

确定整个输入串是否构成语法上正确的程序。

4.局部优化存有哪些常用的技术？答：优化技术1—删除公共子表达式优化技术2—撷取传播优化技术3—删除无用代码优化技术4—对程序展开代数并集转换（减少运算强度）优化技术5—代码外提优化技术6—强度削弱优化技术7—删除归纳变量优化技术概述——对程序展开代数并集转换（代数精简）优化技术简介——对程序进行代数恒等变换（合并已知量）5．编程过程分后哪几个阶段？答：逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成。

每个阶段把源程序从一种则表示转换变成另一种则表示。

6. 什么是文法？请问：文法就是描述语言的语法结构的形式规则。

就是一种工具，它可以用作严苛定义句子的结构；用有穷的规则刻划无穷的集合；文法是被用来精确而无歧义地描述语言的句子的构成方式；文法描述语言的时候不考虑语言的含义。

7. 语义分析阶段的功能就是什么？答：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译(翻译成中间代码)；并对静态语义展开审查。

8.代码优化须遵循哪些原则？请问：等价原则：不发生改变运转结果有效原则：优化后时间更短，占用空间更少不划算原则：应用领域较低的代价获得较好的优化效果9.词法分析阶段的功能是什么？请问：逐个读入源程序字符并按照构词规则切分成一系列单词任务：初始化源程序，输入单词符号—滤掉空格，跳过注释、换行符—跟踪下划线标志，表示源程序失效的行列边线—宏展开，……10.什么就是符号表？答：符号表在编译程序工作的过程中需要不断收集、记录和使用源程序中一些语法符号的类型和特征等有关信息。

《编译原理》考试试题及答案（汇总）一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）1．编译程序是对高级语言程序的解释执行。

(× )2．一个有限状态自动机中，有且仅有一个唯一的终态。

(×)3．一个算符优先文法可能不存在算符优先函数与之对应。

(√ )4．语法分析时必须先消除文法中的左递归。

(×)5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。

(√)6．逆波兰表示法表示表达式时无须使用括号。

(√ )7．静态数组的存储空间可以在编译时确定。

(×)8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。

(×) 9．两个正规集相等的必要条件是他们对应的正规式等价。

(× )10．一个语义子程序描述了一个文法所对应的翻译工作。

(×)二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．词法分析器的输出结果是_____。

A．( ) 单词的种别编码B．( ) 单词在符号表中的位置C．( ) 单词的种别编码和自身值D．( ) 单词自身值2．正规式M 1 和M 2 等价是指_____。

A．( ) M1和M2的状态数相等B．( ) M1和M2的有向边条数相等C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等3．文法G：S→xSx|y所识别的语言是_____。

A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx*4．如果文法G是无二义的，则它的任何句子α_____。

A．( )最左推导和最右推导对应的语法树必定相同B．( ) 最左推导和最右推导对应的语法树可能不同C．( ) 最左推导和最右推导必定相同D．( )可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握______。

Please construct a DFA with minimum states for the following regular expression. ((ab*)(a|b)*)*(a|b)(a|b)*
Review 6.Important knowledge points • Chapter 4 – Top-down Parsing • Recursive descent parsing • Predictive parsing
Review 6.Important knowledge points • Chapter 4 – Ambiguous Grammar parsing • Additional conditions
– Associated law and precedence – Dangle rules – Parsing an ambiguous grammar in LR parsing method with additional conditions
Review 6.Important knowledge points • Chapter 6 – Type – Type expression • Construct a type expression for a declaration
Review 6.Important knowledge points • Chapter 7 – Stack-based storage allocation • Activation Record Form • C language program
Please construct a LR(1) parsing table for the following ambiguous grammar with your own defined additional conditions (You determine the required additional conditions by yourself).

编译原理试题及答案一、选择题1. 编译器的主要功能是什么？A. 将高级语言代码翻译成机器语言代码B. 进行程序调试C. 进行代码优化D. 管理程序运行时的内存分配答案：A2. 词法分析器的主要任务是什么？A. 将源代码分解成多个语句B. 将源代码分解成多个词素C. 检查源代码的语法正确性D. 将词素转换为相应的语法单位答案：B3. 下列哪个是自顶向下的语法分析方法？A. LL(1)分析法B. LR(1)分析法C. LALR(1)分析法D. GLR分析法答案：A4. 语义分析的主要任务是什么？A. 检查程序的语法正确性B. 检查程序的类型正确性C. 将源代码转换为目标代码D. 进行程序的优化答案：B5. 代码生成阶段的主要任务是什么？A. 将语法树转换为目标代码B. 进行程序的优化C. 检查程序的类型正确性D. 将源代码分解成多个词素答案：A二、简答题1. 简述编译过程的主要阶段。

答案：编译过程主要分为四个阶段：词法分析、语法分析、语义分析和代码生成。

词法分析将源代码分解成词素，语法分析检查源代码的语法结构，语义分析检查源代码的语义正确性，代码生成将源代码转换为目标代码。

2. 什么是中间代码？它在编译过程中起到什么作用？答案：中间代码是一种介于源代码和目标代码之间的代码形式，它通常具有更接近于机器语言的特性，但仍然保持一定的抽象级别。

中间代码在编译过程中起到桥梁的作用，它使得代码优化和目标代码生成更加方便和高效。

三、论述题1. 论述编译器优化的几种常见方法。

答案：编译器优化主要包括以下几种方法：常量折叠、死代码消除、公共子表达式消除、循环优化、代码内联、寄存器分配等。

这些优化方法可以提高程序的执行效率，减少资源消耗，提高程序的运行速度。

结束语：本试题涵盖了编译原理的基本知识点，包括编译器的功能、编译过程的主要阶段、中间代码的作用以及编译器优化的方法。

希望考生能够通过本试题加深对编译原理的理解和掌握。

//东南大学一、文法G1： E→ET+|T T→TF*|F F→FP↑|P P→E|i 1、试证明符号串TET+*i↑是G1的一个句型（要求画出语法树）。

2、写出该句型的所有短语，简单短句和句柄。

三、 1、试写出一个上下文无关文法G3，它能产生配对的圆括号串（例如，（），（（）），（）（（））等，甚至包含0对括号）。

2、使用文法G3给出输入串（（））（）#的自上而下分析过程。

四、已知文法G4： S→aAb|Sc|ε A→aAb|ε 1、给出G4文法的LR（0）项目集规范族； 2、构造SLR分析表； 3、G4文法所定义的语言； 4、已知有如下文法及相应的LR分析表，试给出语句01001#的LR分析过程（填写下表）。

S→AAA A→1A A→０五、 1、翻译下面语句成四元式中间代码序列和后缀式（逆波兰式）； while x+y>a do if a<10 then a：=a+1 else x：=x-1； 2、翻译布尔表达式 （a>b） or （c=d） and not （e<f） 成转移四元式序列（即四元式中仅包含（zθ，-，-，-）和（j，-，-，-）两类语句，其中θ为关系运算符。

）一、判断下列命题的真假，并简述理由：（20分） 1、文法G的一个句子对应于多个推导，则G是二义的。

2、LL（1）分析必须对原有文法提取左因子和消除左递归。

3、算符优先分析法采用“移近-归约”技术，其归约过程是规范的。

4、文法S→aA；A→Ab；A→ｂ是LR（0）文法（S为文法的开始符号）。

5、一个BASIC解释程序和编译程序的不同在于，解释程序由语法制导翻译成目标代码并立即执行之，而编译程序需产生中间代码及优化。

二、设计一个最小状态有穷自动机，识别由下列子串组成的任意字符串。

（20分） GO，GOTO，TOO，ON是合法字符串。

例如：GOTOONGOTOOGOON 三、构造一个LL（1）文法G，识别语言L：（20分） L={ω|ω为{0，1}上不包括两个相邻的1的非空串} 并证明你的结论。

<编译原理>历年试题及答案一．（每项选择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/d9．程序所需的数据空间在程序运行前就可确定，称为____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)：S→(L)|a S|aL→L，S|S(1)消除左递归和回溯；(2)计算每个非终结符的FIRST和FOLLOW；(3)构造预测分析表。

东南大学编译原理试题东南大学一九九三年攻读硕士学位研究生入学考试试题试题编号:553试题名称:编译原理一:(15分)判断下列命题的真假,并简述理由:1.文法G的一个句子对应于多个推导,则G是二义的.2.LL(1)分析必须对原有文法提取左因子和消除左递归.3.算符优先分析法采用"移近-归约"技术,其归约过程是规范的.4.文法S→aA;A→Ab;A→b是LR(0)文法(S为文法的开始符号).5.一个BASIC解释程序和编译程序的不同在于,解释程序由语法制导翻译成目标代码并立即执行之,而编译程序需产生中间代码及优化.二:(15分)设计一个最小状态有穷自动机,识别由下列子串组成的任意字符串. GO,GOTO,TOO,ON例如:GOTOONGOTOOGOON是合法字符串.三:(15分)构造一个LL(1)文法G,识别语言L:L={ω|ω为{0,1}上不包括两个相邻的1的非空串}并证明你的结论.四:(20分)设有一台单累加器计算机,并汇编语言含有通常的汇编指令LOAD,STORE,ADD和MUL.1.写一个递归下降分析程序,将如下文法所定义的赋值语句翻译成汇编语言:A→i:=EE→E+E|E*E|(E)|i2.利用加,乘法满足交换率这一性质,改进你的分析程序,以期产生比较高效的目标代码.五:(15分)C为大家熟知的程序语言.1.C的参数传递采用传值的方式,而且允许函数定义和调用时的参数个数不一致(如printf).请指出其函数调用语句:f(arg1,arg2,...,argn)翻译成的中间代码序列,并简述其含义.2.C语言中的变量具有不同的作用范围,试述C应采用的存储分配策略.六:(20分)设有一个子程序的四元式序列为:(1) I:=1(2) if I>20 GOTO (16)(3) T1:=2*J(4) T2:=20*I(5) T3:=T1+T2(6) T4:=addr(A)-22(7) T5:=2*I(8) T6:=T5*20(9) T7:=2*J(10) T8:=T6+T7(11) T9:=addr(A)-22(12) T10:=T9[T8](13) T4[T3]:=T10+J(14) I:=I+1(15) goto (2)(16) ret1.分划基本块.2.对代码施行各种可能的优化,并写出优化过程中采用了何种优化策略.________________________________________________________________ _______________ 东南大学一九九四年攻读硕士学位研究生入学考试试题试题编号:553试题名称:编译原理一:由文法G1构造LR(1)部分分析表:1.列出4个项目集I0,I1,I2,I3;(如下图)2.填写LR(1)分析表的状态0,1,2的action和goto表的内容.(如下图)G1: (0) S→T(1) T→T(T)(2) T→ε┌──────┐┌──┐┌──┐┌──┐│I0:S→·T,# │T │I1: │ (│I2: │ T│I3: │││ -→││-→ ││-→ ││└──────┘└──┘└──┘└──┘┌──┬────────┬───┐││action │ goto ││状态├──┬──┬──┼───┤││ (│ )│ #│ T │├──┼──┼──┼──┼───┤│ 0│││││├──┼──┼──┼──┼───┤│ 1│││││├──┼──┼──┼──┼───┤│ 2│││││├──┼──┴──┴──┼───┤│││││... │ ... │ ...│││││└──┴────────┴───┘二:已知文法G2,请用类pascal语言写出它的递归下降分析程序.G2: A→[BB→X]|BAX→Xa|Xb|a|b三:已知文法G3,要求:1.写出各非终极符的首终极符集合和尾终极符集合;2.填写opt表:│+ │* │@ │ ↑ │i │# │──┼──┼──┼──┼──┼──┼──┤+ │││││││──┼──┼──┼──┼──┼──┼──┤* │││││││──┼──┼──┼──┼──┼──┼──┤@ │││││││──┼──┼──┼──┼──┼──┼──┤↑│││││││──┼──┼──┼──┼──┼──┼──┤i │││││││──┼──┼──┼──┼──┼──┼──┤# │││││││──┼──┼──┼──┼──┼──┼──┤│││││││G3: E→E+T|T|@TT→T*F|FF→p↑F|Pp→i四:请写出产生下列语言的文法.1. L1={a^ib^j|i>j>=1}2. L2={ω1|ω1?{0,1}*&ω1中包含0,1个数相等的任意串}3. L3={ω2|ω2?{a,b}*&ω2中a之后必定跟b}4. L4={ω3+ω3|ω3?{0,1}*}五:简要回答问题.1.对编译程序而言,模块,遍,子程序这三个概念的主要区别?2.静态存储分配与动态存储分配的主要区别?3.何谓自适应线性表?六:翻译如下布尔表达式成四元式序列,结果留待填的真假链的四元式序号.A∧B-C<d+e∨┐f< p="">________________________________________________________________ _____东南大学一九九五年攻读硕士学位研究生入学考试试题试题编号:553试题名称:编译原理一:按算法构造文法G1:S→#M#M→(L|aL→M,a)的算符优先矩阵.(即填写下列矩阵)│ a │, │( │) │# │──┼──┼──┼──┼──┼──┼a ││││││──┼──┼──┼──┼──┼──┼, ││││││──┼──┼──┼──┼──┼──┼( ││││││──┼──┼──┼──┼──┼──┼) ││││││──┼──┼──┼──┼──┼──┼# ││││││──┼──┼──┼──┼──┼──┼二:将下列cfg文法修改成正规文法.S→ABA→M|N|PB→aB|aM→bM|bN→cN|cP→αP|ε三:已知文法G2:(1) S'→S(2) S→AAA(3) S→1A(4) S→01.列出LR(0)项目集族;2.构造SLR分析表;3.试给处语句01100#的LR分析过程.四:1.构造由下列三型文法G3所对应的FA.2.将构造的FA确定化和最小化.3.写出该DFA所识别的语言.G3: S→aA|bS|dCA→dEC→aD|bC|bD→bE|bE→aD|bE|b五:设有源语句A[I+1,J+2]:=A[B[K+2],5]1.列出计算两个数组的下标地址(按行存放)A[I+1,J+2]的地址D1=?B[K+2]的地址D2=?2.按语法制导翻译该语句成四元式序列.(设数组首地址分别为a,b;数组按行存放,每个元素占一字编址.数组说明:A:array[1..10,-5..5],B:array[-5..5]) 六:求文法G4:A→BCc|gDBB→bcDE|εC→Dab|caD→dD|εE→gAf|c的各非终结符的随符集.七:1.简述由基本块寻找循环结点的算法.2.对于如下一段程序,若参数传递分别采用:(a)传名 (b)传结果 (c)传地址试问程序执行结果,Y值是什么?proc Q(B,C)beginB:=B+2;B:=B*Cend;beginY:=2;Q(Y,2*Y);print(Y)end;3.文法G5:E→P↑E|PP→P*Q|QQ→Q+R|RR→(E)|aa→整常数试给出下列表达式计值结果(语法制导).3+2*5↑2*2+32+(2↑2↑3)*2+3________________________________________________________________ _____ 东南大学一九九六年攻读硕士学位研究生入学考试试题试题编号:553试题名称:编译原理一:1.试写一正规文法,使其定义的语言是不以0打头的偶整数集合.其中数字可以用简名表示,比如α1→0|2|4|6|8,并把α1看作是终结符.2.试写一上下文无关文法,它能产生下列语言:L={ω|ω?{a,b}*,且ω中a的个数是b的两倍,例如aab等}二:请写出由下列文法所确定的语言.1. G1: S→10S01S→aAA→bAA→a2. G2: S→aSSS→a三:已知NFA的状态转换图如下,试对它确定化并化简,并写出该FA 接受的语言.∩b a→S──────→Ad││c↓ a b ↓b＜C──→D──→E＞b│b│←──│b│↓ a │b└─→T ←──┘四:已知文法G4:S'→SS→ASS→bA→SAA→a1.试求closure({(S'→·S,#)})和GO(closure({(S'→·S,#)}),S)2.文法是LR(1)吗?为什么?五:试将下面语句按语法制导翻译成四元式序列.while (a<="" p="">if a=1 then c:=c+1else while a<=d do a:=a+2;六:1.试对如下四元式序列划分成基本块,并化出程序流图;2.写出源语句.(1) I:=1(2) if I>M goto (19)(3) J:=1(4) if J>N goto (17)(5) T1:=I*N(6) T2:=T1+J(7) T3:=addr(A)-C(8) T4:=I*2(9) T5:=J+2(10) T6:=T4*N(11) T7:=T6+T5(12) T8:=addr(A)-C(13) T9:=T8[T7](14) T3[T2]:=T9(15) J:=J+1(16) goto (4)(17) I:=I+1(18) goto (2)(19) ...七:1.求文法G7的各非终结符的终结首符集First和随符集Follow.2.判定该文法是LL(1)吗?G7: A→BCc|gDBB→bCDE|εC→DaB|caD→dD|εE→gAf|c________________________________________________________________ _____东南大学一九九七年攻读硕士学位研究生入学考试试题试题编号:553试题名称:编译原理一:文法G1:E→ET+|TT→TF*|FF→FP↑|PP→E|i1.试证明符号串TET+*i↑是G1的一个句型(要求画出语法树).2.写出该句型的所有短语,简单短句和句柄.二:1.给出下图FA的正规式.a b──→──→ ②→◎①a↑↓ε←──←── ③ε b2.已知正规文法G2:S→aS|AA→bBB→aB|ε试构造一确定有限自动机DFA(要求化简),使得它接受的语言正是该文法产生的语言,要求画出状态图.三:1.试写出一个上下文无关文法G3,它能产生配对的圆括号串(例如,(),(()),()(())等,甚至包含0对括号).2.使用文法G3给出输入串(())()#的自上而下分析过程.四:已知文法G4:S→aAb|Sc|εA→aAb|ε1.给出G4文法的LR(0)项目集规范族;2.构造SLR分析表;3.G4文法所定义的语言;4.已知有如下文法及相应的LR分析表,试给出语句01001#的LR 分析过程(填写下表).S→AAAA→1AA→0LR分析表:───┬──┬──┬──┰──┬──状态│ 1│ 0│ #┃ S│ A───┼──┼──┼──╂──┼──0 │ S3 │ S4 │┃ 1│ 2───┼──┼──┼──╂──┼──1 │││acc ┃│───┼──┼──┼──╂──┼──2 │ S3 │ S4 │┃│ 5───┼──┼──┼──╂──┼──3 │ S3 │ S4 │┃│ 6───┼──┼──┼──╂──┼──4 │ r3 │ r3 │ r3 ┃│───┼──┼──┼──╂──┼──5 │ S3 │ S4 │┃│ 7───┼──┼──┼──╂──┼──6 │ r2 │ r2 │ r2 ┃│───┼──┼──┼──╂──┼──7 │││ r1 ┃│───┴──┴──┴──┸──┴──分析过程:──────┬──────┬──────状态栈│符号栈│输入串──────┼──────┼──────││││││││││││││──────┴──────┴──────五:1.翻译下面语句成四元式中间代码序列和后缀式(逆波兰式);while x+y>a doif a<10 then a:=a+1 else x:=x-1;2.翻译布尔表达式(a>b) or (c=d) and not (e<f)< p="">成转移四元式序列(即四元式中仅包含(zθ,-,-,-)和(j,-,-,-)两类语句,其中θ为关系运算符.)六:1.有如下Fortran说明语句,试借助符号表登记等价环链EQ和相对数OFFSET,即填写下表的EQ栏和OFFSET栏.设每个整型量占1子编址.integer a,b,c(10,10),d(10)equivalence (a,d(8),c(5,5))equivalence (b,c(5,8))符号表┌───┬──────┬───┬───┐│ name │ ... │ EQ │OFFSET│├───┼──────┼───┼───┤1│ a │ ... │││├───┼──────┼───┼───┤2│ b │ ... │││├───┼──────┼───┼───┤3│ c │ ... │││├───┼──────┼───┼───┤4│ d │ ... │││└───┴──────┴───┴───┘2.有如下pascal语言的程序轮廓,当运行该程序且第一次递归调用Q过程(即在过程Q中又调用了Q)时,数据区建立情况.假定各数据区首址用SP(i)(i=0,1,……)表示,试给出P,Q数据区的display表.┌ main│┌ P││┌ Q│││ Call Q││└││ Call Q│└│┌ R││ Call P│└│┌ S││ Call R│└│ Call S└七:已知如下流图,试给出回边与循环.↓┌─→①←┐│/ \ /│ ↓↓/\ ②③\ \ /↑\↓↓/┌→④──┐││↓││┌→⑤│↓/ │└─⑥←─┘________________________________________________________________ _____ 东南大学一九九八年攻读硕士学位研究生入学考试试题试题编号:553试题名称:编译原理一:已知文法G1:S→aB|εB→bC|bDC→cB|cD→d1.试构造一个最小DFA,画出状态转换图.2.由该DFA给出它所识别的语言(用正规式表示).二:已知正规式α=ab*c*d,1.试构造一个DFAM,其接受的语言为此α(画出图);2.由该DFAM写出对应的正规文法(古线性).三:文法G3:S→A[B]A→[B]|AaB→a1.求出各非终结符N的Firstvt(N)和Lastvt(N),构造包括语句括号'#'在内的算符优先表;2.给出语句#[a][a]#的算符优先分析过程,即填写如下格式的表:步骤│栈内│ 输入串│动作────┼────┼────┼─────0 │#│[a][a]# │... │││四:已知文法G4:T→T*F|FF→(T)|i1.试给出语句(i*i)#的自上而下分析过程(填下表);2.画出对应的语法树,指出每一步归纳的句柄.步骤│栈内│输入│动作────┼────┼────┼─────0 │#T│ (i*i)# │... │││五:已知文法G5:0. E'→E1. E→E+T2. E→T3. T→i列出LR(0)项目集规范族,求出各非终结符N的Follow集合,构造SLR分析表. 六:翻译如下语句成四元式序列(由语法制导生成).while a>b and a<="" p="">if a=5 then b:=b+1 elserepeata:=a+1until a>=d;七:按语法制导翻译下段程序成四元式序列(不要优化),设数组A:array[1..10,1..10] of int;每个下标变量占1字编址,数组按行存放,Z 为函数名.beginA[i,j]:=A[i,j]+2;B:=Z(A[i,j])*5end八:将如下一段四元式序列进行块内优化和循环优化(强度减弱及删除基本归纳变量),写出优化后的四元式序列.(要求先划分基本块)(1) i:=1(2) if i>100 goto (10)(3) T1:=20*i(4) M:=J+T1(5) T2:=20*i(6) N:=K+T2(7) O:=M+N(8) i:=i+1(9) goto (2)(10) ...九:已知如下一段程序,试给出运行时整个数据区结构.假定num初值为2,每个数据区的活动记录包含内容如下图所示,数据区从k单元开始编址.┌─────┐ program factoral;│函数返回值│ var num,fact:int;├─────┤ function f(n:int):int│ 变量单元│ if n>0 then f:=n*f(n-1)├─────┤ else f:=1;│display 表│ begin├─────┤ read(num);│ 形参单元│ fact:=f(num)├─────┤ end│ 返回地址│├─────┤│基SP │└─────┘________________________________________________________________ _____东南大学一九九九年攻读硕士学位研究生入学考试试题试题编号:553试题名称:编译原理一:已知正规文法中的左线性文法G1:S→Sa|Sb|c试构造无ε产生式的等价右线性文法,并构造相应的确定有限自动机DFA,画出状态转换图即可.二:已知正规文法(X为开始符号)G2: X→0Y|1Z|0Y→0X|1Y|1Z→1X1.该文法产生语言是什么?请用正规式表示.2.构造最简的确定有限自动机DFA,并画出状态转换图.三:已知上下文无关文法(E为开始符号)G3: E→ET+|TT→TF*|FF→E|i1.消除文法左递归,并给出改写后的文法产生式;2.给出文法改写以后的各非终结符X的First(X)与Follow(X)集合,并由此判定它是否是LL(1)文法(按下表填).V(N) │ First(X) │ Follow(X)────┼──────┼───────X ││... ││││四:已知表达式文法(已拓广)G4: E'→EE→E+E|i1.试构造文法G4的LR(0)项目集规范族;2.若'+'服从右结合率,请给出LR分析表.五:已知文法(Z为开始符号)G5: Z→bMbM→(Ma)|a1.试构造算符优先分析表(即填下表);│ a │ b │( │) │# │──┼──┼──┼──┼──┼──┼a ││││││──┼──┼──┼──┼──┼──┼b ││││││──┼──┼──┼──┼──┼──┼( ││││││──┼──┼──┼──┼──┼──┼) ││││││──┼──┼──┼──┼──┼──┼# ││││││──┼──┼──┼──┼──┼──┼2.若某相邻的终结符a,b间存在a<=b两种关系,那么在进行算符优先分析做归约动作时,在寻找栈顶的素短语符号串时要察看它与哪个产生式右部的符号串匹配. 例如栈顶串...aAbα(a,b?VT,A?(VA∪ε),a<=b,α?V*)为已知可归约,而现有产生式X→aAbα,则取素短语aAbα,若只有产生式Y→Abα,那么就取Abα进行归约.试按此规定的算法给出语句b((aa)a)b的算符优先分析过程.六:翻译成中间代码.1.将如下程序段翻译成后缀式(逆波兰式),填在一维数组POST[i]中,设i初值=1. t:=15;b:=20;while t<>b doif t>b then t:=t-belse b:=b-t;2.翻译布尔表达式成转移四元式序列,并指出待填真假链序号.(a>b+1) and not (c+2<="" or="" p="">注:f(x)为布尔函数.七:有如下一个计算m*2^n的C语言程序,试给出运行时整个栈或数据区的结构.数据区的活动记录结构如图所示.┌──────┐┌─────┐│函数f返回值││返回结果值│├──────┤├─────┤│ 局部变量区││局部变量区│├──────┤├─────┤│ 全程变量区││形参单元区│├──────┤├─────┤│主程序m ain ││ 返回地址││ 数据区│├─────┤└──────┘│基SP │├─────┤│函数数据区│└─────┘int m;f(n)int n;{ int c;if (n==0) c=m;else c=f(n-1)*2;return (c);}main(){ int n=2;m=5;printf("%d\n",f(n));}八:已知如下程序段a:=1;while a<=10 dobeginif a<>b thenA[a,b]:=A[a,b]+2;a:=a+1;end;1.按语法制导生成四元式中间代码序列;2.将中间代码序列划分成基本块,画出程序流图,并指出循环结点集;3.执行循环中代码外提,强度减弱优化和基本块内删除公共子表达式优化,最后画出包含优化后的中间代码的程序流图.注:数组A: array[1..10,1..10] of int;按行存放,每个下标变量占1字编址,首地址为addrA.友情赠送--东南大学计算机系编译原理期末考试试题两套!________________________________________________________________ _____东南大学试题纸课程: 编译原理 1997-1998学年第一学期一:1.试给出产生L1语言的相应预测分析文法.L1={a^ib^j|j>i>0}2.设文法G1: S→aA A→bA|a试给出文法G1所定义的语言,并用正规式表示.二:1.设文法G2如下,试给出G2文法中各非终结符的First与Follow,即填写下表. G2: A→BCc|gDBB→bCDE|εC→DaB|caD→dD|εE→gAF|c│ First │ Follow────┼──────┼───────A ││B ││C ││D ││E ││────┴──────┴───────2.构造G2文法的预测分析表.│ a│ b│ c│ d│ f│ g│ #────┼──┼──┼──┼──┼──┼──┼───A │││││││B │││││││C │││││││D │││││││E │││││││────┴──┴──┴──┴──┴──┴──┴───三:设正规文法如下,1.构造相应的NFA,画出状态转换图.2.将NFA确定化与最小化,画出最小DFA状态转换图.S→aA|bS|dCA→dEC→aD|bC|bD→bE|bE→aD|bE|b四:构造文法G4:S→#M#M→(M,a)|a的算符优先分析表(按a，,，(，)，#顺序列出);并给出语句((a,a),a)#的算符优先分析过程.五:1.构造已拓广文法G5的LR(0)项目集规范族;G50) S'→S(1) S→BB(2) B→a B(3) B→b2.构造G5文法的SLR分析表;3.该文法是LR(0)吗?为什么?六:1.令F(x,y)为一函数过程,试写出过程调用语句:F(F(A+B,C)+D,E)的四元式中间代码序列.2.设数组A:array[1..10,-5..5],B:array[-5..5],数组按行存放,每个元素占1字编址,其首地址分别为1000和2000.试翻译赋值语句A[I+1,J+2]:=A[B[K+2],5]成四元式序列.3.计算A[5,2]和B的内存地址.七:设有如下pascal程序,在运行时数据区随调用语句而建立,当过程(程序)结束时撤销数据区.试写出最后一次调用fib时刻的整个数据区结构.假定在活动记录中不设全局display与形参个数这二项,其它按书上规定.整个数据区从k单元开始分配.所谓最后一次调用fib试制从那时刻之后只有撤销数据区动作.program fibonacci;var m:integer;function fib(n:int):int;if n=0 then fib:=0else if n=1 then fib:=1else fib:=fib(n-2)+fib(n-1);beginm:=3;write (fib(m))end八:试对如下四元式序列进行强度减弱优化.要求先画出程序流图,对循环体作强度减弱优化.I:=1read J,KL:A:=K*IB:=J*IC:=A*Bwrite CI:=I+1if I<100 goto Lhalt________________________________________________________________ _____东南大学试题纸课程: 编译原理 1998-1999学年第一学期一:构造正规式 (-|ε)(a|b)*ab 相应的DFA.先构造NFA,确定化,最小化,最后画出最小DFA状态转换图.二:已知状态转换图如下,试给出相应的右线性文法和相应正规表达式Re.b ∩a c┌────→A←────┐→S b└────→B←┐a└────────────┘三:设文法G3A'→AA→a|aAc|bBcB→aA|bB1.消除左递归和/或提取左因子,写出改写后的文法G3';2.给出改写后的文法G3'的First(x)与Follow(x),x为非终结符;3.构造G3'的LL(1)分析表.四:已知文法G4S→a|(T)T→T,S|S1.给出文法G4的算符优先表.2.将该优先表用逐次加1法转换成优先函数.│ a │( │) │, │# │──┼──┼──┼──┼──┼──┼a ││││││──┼──┼──┼──┼──┼──┼( ││││││──┼──┼──┼──┼──┼──┼) ││││││──┼──┼──┼──┼──┼──┼, ││││││──┼──┼──┼──┼──┼──┼# ││││││──┼──┼──┼──┼──┼──┼│ a │( │) │, │# │──┼──┼──┼──┼──┼──┼f ││││││──┼──┼──┼──┼──┼──┼g ││││││──┼──┼──┼──┼──┼──┼五:已知文法G5T→T(T)T→ε1.构造G5文法的LR(0)项目集规范族(要求先拓广);2.构造G5文法的SLR分析表;3.给出句子(())#的LR分析过程.六:将布尔表达式A>B+1∧┐(D∨E)1.按逻辑演算中求布尔值译成四元式序列;2.翻译成转移四元式序列;七:1.将如下程序段译成四元式中间代码序列,设每个下表变量占4字编址,数组首地址为a.i:=0;repeatif i>2 then A[i]:=A[i]*2;i:=i+1until i>10;2.将译成的中间代码划分成基本块,画出程序流图,并指出循环结点.八:对如下pascal程序试给出运行时整个数据区,并标出各数据区建立的先后顺序.设m=3,每个数据区的活动记录包含:Top→┌─────┐│函数返回值│├─────┤│ 变量单元│├─────┤│disp lay 表│├─────┤│ 形参单元│├─────┤│ 返回地址│├─────┤│基SP │Sp→ └─────┘program fibonacci; var m:int;function fib(n:int):int; </f)<></d+e∨┐f<>。

《编译原理》考试试题及答案（汇总）一、是非题（请在括号，正确的划√，错误的划×）（每个2分，共20分）1．编译程序是对高级语言程序的解释执行。

(× )2．一个有限状态自动机中，有且仅有一个唯一的终态。

(×)3．一个算符优先文法可能不存在算符优先函数与之对应。

(√ )4．语法分析时必须先消除文法中的左递归。

(×)5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。

(√)6．逆波兰表示法表示表达式时无须使用括号。

(√ )7．静态数组的存储空间可以在编译时确定。

(×)8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。

(×) 9．两个正规集相等的必要条件是他们对应的正规式等价。

(× )10．一个语义子程序描述了一个文法所对应的翻译工作。

(×)二、选择题(请在前括号选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．词法分析器的输出结果是_____。

A．( ) 单词的种别编码B．( ) 单词在符号表中的位置C．( ) 单词的种别编码和自身值D．( ) 单词自身值2．正规式 M 1 和 M 2 等价是指_____。

A．( ) M1和M2的状态数相等 B．( ) M1和M2的有向边条数相等C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等3．文法G：S→xSx|y所识别的语言是_____。

A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx*4．如果文法G是无二义的，则它的任何句子α_____。

A．( )最左推导和最右推导对应的语法树必定相同B．( ) 最左推导和最右推导对应的语法树可能不同C．( ) 最左推导和最右推导必定相同D．( )可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握______。