一章：
1、编译程序各阶段都涉及。
A、词法分析
B、表格管理
C、语法分析
D、语义分析
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、过程
1、扫描器的任务是从源程序中识别出一个个单词符号。
2、高级语言源程序有两种执行方式，即解释和编译。
判断：
高级语言编写的源程序都必须通过编译，产生目标代码后才能运行。
多遍扫描的编译程序的多遍是指多次重复读源程序。
高级语言程序到低级语言程序的转换是基于语义的等价变换。
编译程序中错误处理的任务是对检查出的错误进行修改。
目标程序一定是机器语言程序。
连接装配程序可把经编译程序产生的目标程序变成可执行的机器语言程序。
简答题：
1、请指出下列错误信息可能是编译的哪个阶段报告的？
①else没有匹配的if；
②数组下标越界；
③使用的函数没有定义；
④在数中出现了非数字信息。
答：①语法分析阶段②语义分析与中间代码生成阶段③语义分析与中间代码生成阶段
④词法分析阶段
2、何谓源程序、中间代码和目标代码？它们三者之间有何种关系？
答：所谓源程序是指用某种高级语言编写的程序，它是编译程序的加工对象。目标程序是指低级语言（机器语言或汇编语言）编写的程序，它是编译程序的加工结果。中间代码是其结构介于源程序和目标程序之间的一种机内表示形式，它是编译程序产生的中间临时结果。它们三者之间的关系是等价关系，即结构不同，但语义相同。
二章：
1、文法G：S-→xSx|y所识别的语言是。
A、xyx B 、（xyx）* C、x n yx n(n≥0) D、x*yx*
2、设有文法G[S]=({S,B},{b},{S-→b|bB,B-→bS},S),该文法所描述的语言是。
A、L(G[S])={b i|i≥0}
B、L(G[S])={b2i|i≥0}
C、L(G[S])={b2i+1|i≥0}
D、L(G[S])={b2i|≥1}
3、给定文法A→bA|cc，下面的符号串中为该文法句子的是。
①cc ②bcbc ③bcbcc ④bccbcc ⑤bbbcc
可选项有：
A、①⑤
B、①③④⑤
C、①④
D、①④⑤
4、描述语言L={a m b n|n≥m≥1}的文法为。
A、Z--->Abb A-→aA|a B-→bB|b
B、A-→ABb A-→Aa|a B-→aBb|b
C、Z-→Ab A-→aAb|a
D、Z-→aAb A-→Ab|aAb|ε
1、假定G是一个文法，S是它的开始符号。如果S===〉α，则称α是一个句型，仅包含的句型称为句子。
2、设有文法G[S]:S-→bB B-→cC B→cCe C-→dS S-→aB，则V N={ },V T={ }。
判断
一个上下文无关文法的开始符号可以是终结符或非终结符。
1型文法对规则的限制比2型文法对规则的限制要多一些。
简答题：
1、令文法G为：
N→D|ND
D→0|1|2|3|4|5|6|7|8|9
(1)文法G定义语言是什么？
(2)给出句子0127的最左推导和最右推导。
答：(1)G的语言是任意的数字串：L(G)={a1a2..a n|a i∈[0,1,2,…,9]}。
(2) 最左推导：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127
最右推导：N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127
2、证明下述文法是一个二义性文法：
S→iSeS|iS|i
句子iiiei的语法树如下图所示。
S S
i S e S i S
i S i S e S
i i i 同一句子对应两棵不同的语法树，故该文法是二义的。
词法分析:
1、如果两个文法产生的语言相同，则称这两个文法是等价的。
2、确定的有限自动机DFA是不确定的有限自动机NFA的一个特例。
3、两个等价的正规式所表示的正规集相同，高级语言的词法结构一般可以用正规文法来实
现。
4、一张符号表的每一项（或称入口）包含两大栏，即名字栏和信息栏。
5、符号表的查找和整理技术通常有线性查找、二叉树和杂凑技术。
6、设∑={a,b}，试写一正规式，其表示的正规集为“不以a开头，但以aa结尾的字符串集合”。正规式为：b(a|b)*aa
1、词法分析器的输入是。
A、单词符号串
B、源程序
C、语法单位
D、目标程序
2、不是NFA的成分。
A、有穷字母表
B、唯一的初始状态
C、终止状态集合
D、有限状态集合
3、在词法分析阶段不能识别的是。
A、标识符
B、运算符
C、四元式
D、常数
4、对编译程序所用到的符号表，涉及的操作不包括。
A、填写或更新信息栏内容
B、填入新名
C、给定名字，访问它的有关信息
D、输出token字序列
判断：
1、有限自动机只有一个初态。
2、对任一个正规式r，都存在一个NFA M，使得L(M)=L(r)。
简答题：
1、设∑={0,1}，试写一正规式，其表示的正规集为：“含有子串010的所有串”。
答：正规式为：(0|1)*010(0|1)*
2、在实现编译程序时，常将词法分析程序从语法分析中独立出来，这样做有什么好处？
答：将词法分析程序从语法分析中独立出来，这样做有以下好处：
①建立高级语言时能独立地研究词法与语法两方面的特性。
②词法规则简单，因此可建立特别适用于这种文法的有效分析技术，也容易实现词法分
析程序生成自动化。
③可以就同一个语言为每种不同的机器编写一个词法分析程序，只编写一个共同的语法
分析程序，这时只要每一个词法分析程序产生相同的符号内部表示形式供该语法分析程序使用即可。
综合题：
1、设∑={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。
构造相应的正规式：(0|1)*1(0|1)
NFA:
确定化：
语法分析：
1、编译过程中，语法分析器的任务是。
①分析单词是怎样构成的②分析单词串是如何构成语句和说明的
③分析语句和说明是如何构成程序的④分析程序的结构
A、②③
B、②③④
C、①②③
D、①②③④
2、在通常的语法分析方法中，特别适用于表达式的分析。
A、算符优先分析法
B、LR分析法
C、递归下降分析法
D、LL（1）分析法
3、一个指明了在分析过程中的某时刻所能看到的产生是多大一部分。
A、活前缀
B、前缀
C、项目
D、项目集
判断
1、每个文法都能改写成LL（1）文法。
2、一个LL（1）文法一定是无二义的。
3、每一个算符优先文法，必定能找到一组优先函数与之对应。
4、欲构造行之有效的自上而下分析器，则只需消除左递归。
5、所有LR分析器的总控程序都是一样的，只是分析表各有不同。
6、若B为非终结符，则A α.Bβ为移进项目。
1、语法分析最常用的两类方法是自上而下和自下而上分析法。
2、语法分析器的输入是单词符号串，其输出是语法单位。
3、一个文法G，若它的预测分析表M不含多重定义入口，则G是LL（1）文法。
4、LL（1）文法中，第一个L表示从左到右扫描输入串，第二个L表示最左推导。
5、应用算符优先分析技术分析句型时，每步被直接规约的是最左素短语，而应用LR分析
技术时，每步被直接规约的是句柄。
6、活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。
简答题：
1、对于文法G（S）：S→（L）|as|a L→L,S|S S
(1)画出句型(S,(a))的语法树
(2)给出句型(S,(a))的短语、直接短语、句柄和素短语。( L )
L , S
S ( L )
S
A
短语：S、a、(a)、S,(a)、(S,(a))
直接短语：a,S 句柄：S 素短语：a
2、考虑以下文法G：S→a|∧|(T)
T→T,S|S
(1)消去G的左递归
(2)经改写后的文法是否是LL(1)的？
答：消左递归：S→ a|∧|(T) T→ST’ T’→,ST’|ε
fisrt(S)={a, ∧,(} first(T)={a, ∧,(} first(T’)={,,ε}
follow(S)={#,,,}} follow(T)={}} follow(T’)={}}
1.文法不含左递归
2.每个产生式的候选首符集两两不想交
3. first(T’)∩follow(T’)=φ
所以该文法是LL(1)文法。
综合题：
1、对下面的文法G：E→TE’ E’→+E|εT→FT’ T’→T|εF→PF’ F’→*F’|εP→(E)|a|b|∧
(1)计算这个文法的每个非终结符的FIRST和FOLLOW。
(2)证明这个文法是LL(1)的。
(3)构造它的预测分析表。
语义分析和中间代码生成：
1、语义分析和中间代码生成时所依据的是。
A、语法规则
B、词法规则
C、语义规则
D、等价变换规则
2、终结符具有属性。
A、传递
B、继承
C、抽象
D、综合
3、后缀式ab+cd+/可用表达式来表示。
A、a+b/c+d
B、(a+b)/(c+d)
C、a+b/(c+d)
D、a+b+c/d
4、语法制导的翻译程序能同时进行和语义分析。
A、词法分析
B、语法分析
C、优化
D、目标代码生成
5、四元式之间的联系是通过实现的。
A、指示器
B、临时变量
C、符号表
D、程序变量
1、语法制导的翻译是基于属性文法的，属性有两类，即综合属性和继承属性。
2、在语法树中，一个结点的综合属性的值由其子结点的属性确定，而继承属性则由该结点的父结点或兄弟结点的某些属性确定。
3、语义分析阶段所生成的与源程序等价的中间表示形式可以有逆波兰表示、三元式表示和四元式表示等。
4、生成中间代码主要是为了使目标代码的优化容易实现。
简答题：
1、给出下列表达式的逆波兰式：
(1)-a+b*(-c+d)
(2)a+b*(c-d)/e-f
答：(1)a-bc-d+*+
(2)abcd-*e/+f-
2、给出-(a+b)*(c+d)-(a+b+c)的三元式和四元式。(其中单目运算—用@表示)
1 (+,a,b) (+,a,b,T1)
2 (@,1,_) (@,T1,_,T2)
3 (+,c,d) (+,c,d,T3)
4 (*,2,3) (*,T2,T3,T4)
5 (+,a,b) (+,a,b,T5)
6 (+,c,5) (+,T5,c,T6)
7 (-,4,6) (-,T4,T6,T7)
优化：
1、下列优化方法不是针对循环优化进行的。
A、强度削弱
B、删除归纳变量
C、删除公共子表达式
D、代码外提
2、对于一个基本块来说，正确的说法是。
A、只有一个入口语句和一个出口语句
B、有一个入口语句和多个出口语句
C、有多个入口语句和一个出口语句
D、只有多个入口语句和多个出口语句
判断：
数组元素的地址计算与数组的存储方式有关。
循环中的不变运算都可以提到循环外。
根据优化设计到的程序范围，优化可分为局部优化、循环优化和全局优化三个不同的级别。局部优化是在基本块范围内进行的一种优化。
在优化中，可把循环中的不变运算提到循环外去，这种方法称为代码外提。
简答题
1、已知三地址代码序列为：
(1) i:=1
(2) i:=i+1
(3) j:=1
(4) j:=j+1 (5) k:=i mod j
(6) if k ≠0 goto (4)
(7) if i ≠j goto (10) (8)write I (9)writeln
(10) if i<10000 goto(2) (11)halt
划分基本块，并画出流图
2
read C A:=0 B:=1
L1:A:=A+1 iF B ≥C goto L2 B:=B+1 goto L1 L2:write A halt
2、 试构造以下基本块G 的DAG
(1)T0：=3.14
(2)T1：=2*T0
(3)T2：=R+r (4)A ：=T1*T2 (5) B ：=A (6) T3：=2*T0 (7)T4：=R+r (8T5：=T3+T4 (9)T6：=R-r (10) B ：=T5*T6
已知如下翻译模式，用回填法给出a>b or c>d and e>f 的四元式序列，要求给出简单过程。文法及其翻译模式如下：
(1)E→E1 and M E2 {backpatch(E1.truelist,M.quad);
E.truelist:= E2.truelist)
E.falselist:=merge(E1.falselist,E2.falselist )
(2) E→E1 or M E2 {backpatch(E1.falselist,M.quad);
E.truelist:=merge(E1.truelist,E2.truelist)
E.falselist:=E2.falselist}
(3)E1→id1 relop id2 {E.truelist:= makelist(nextquad);
E.falselist:=makelist(nextquad+1);
Emit(‘j’relop.op ‘,’id1.place ‘,’id2.place ‘,’ ‘0’ );
Emit(‘j,-,-,0’)}
(4)M→ε {M.quad:=nextquad}
E.t={100,104 }
E.f={103，105}
E.t={100 } E.f={101 }or M.q={102}
E.t={ 104}
E.f={103,105}
ε
a>b
E.t={102 }
E.f={103 }
and M.q={104}
E.t={ 104}
E.f={105}
ε
c>d
e>f
四元式序列为：
100 （j>，a，b，0）101 （j，--，--，102）102(j>，c，d，104) 103(j，--，--，0）104(j>，e，f，0) 105(j，--，--，0）
有文法G（S）：
S→A|B
A→aAb|c
B→aBb |d
试构造此方法的LR（0）项目集规范族。
1)将文法G拓广为文法G’
S’->S S->A
S->B
A->aAb A->c
B->aBb B->d
2)列出LR（0）的所有项目：
1．S’->?S 5. A->?aAb 9. A->?c 13. B->?aBb 17.B-> ?d S->S? 6. A->a?Ab 10. A->c? 14. B->a?Bb 18 B->d?
S->? A 7. A->aA?b 11. S->?B 15. B->aB?b
S->A? 8.A->aAb? 12. S->B? 16 B->aBb?
3)用ε-CLOSURE办法构造文法G’的LR（0）项目集规范族：
I0: S’->?S ,S->? A, A->?aAb, A->?c, S->?B, B->?aBb, B-> ?d I1: S’->S?
I2: S->A?
I3: S->B?
I4: A->a?Ab, A->?aAb, A->?c, B->a?Bb, B->?aBb, B-> ?d
I5: A->c?
I6: B->d?
I7: A->aA?b
I8: A->aAb?
I9: B->aB?b
I10: B->aBb?
已知现在寄存器R，其中A是活跃变量，试将以下三地址代码翻译成汇编代码的形式。
T1：=A+B
T2：=T1*C
A：=T2+D
目标代码序列为：
LD R,A
ADD R,B
MUL R,C
ADD R,D
ST R,A
编译原理实验指导 实验安排： 上机实践按小组完成实验任务。每小组三人，分别完成TEST语言的词法分析、语法分析、语义分析和中间代码生成三个题目,语法分析部分可任意选择一种语法分析方法。先各自调试运行，然后每小组将程序连接在一起调试，构成一个相对完整的编译器。 实验报告： 上机结束后提交实验报告，报告内容： 1．小组成员； 2．个人完成的任务； 3．分析及设计的过程； 4．程序的连接； 5．设计中遇到的问题及解决方案； 6．总结。
实验一词法分析 一、实验目的 通过设计编制调试TEST语言的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。 二、实验预习提示 1．词法分析器的功能和输出格式 词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示 成以下的二元式(单词种别码，单词符号的属性值)。 2．TEST语言的词法规则
编译原理综合实验指导书 一、实验任务 设计、编制并调试一个中缀表达转换为后缀表达的实验程序，加深对词法分析、语法分析、语义分析及代码生成的理解。 二、实验内容 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、语义分析及代码生成 语义分析的主要任务是判断变量是否先定义后使用。代码生成的的主要任务是将赋值语句从中缀表达转换为后缀表达。
南华大学 计算机科学与技术学院 实验报告 （ 2018~2019学年度第二学期） 课程名称编译原理 实验名称词法分析器的设计与 实现 姓名学号
专业班级 地点教师 1.实验目的及要求 实验目的 加深对词法分析器的工作过程的理解；加强对词法分析方法的掌握；能够采用一种编程语言实现简单的词法分析程序；能够使用自己编写的分析程序对简单的程序段进行词法分析。 实验要求 1.对单词的构词规则有明确的定义； 2.编写的分析程序能够正确识别源程序中的单词符号； 3.识别出的单词以 <种别码，值 >的形式保存在符号表中，正确设计和维护 符号表； 4.对于源程序中的词法错误，能够做出简单的错误处理，给出简单的错误 提示，保证顺利完成整个源程序的词法分析； 2.实验步骤 1.词法分析规则 <标识符 >::=< 字母 >|< 标识符 ><字母 >|< 标识符 ><数字 >
<常数 >::=< 数字 >|< 数字序列 ><数字 > <数字序列 >:: ＝<数字序列 ><数字 >|< 数字 >|<.> <字母 >::=a|b|c|??|x|y|z <数字 >::=0|1|2|3|4|5|6|7|8|9 <运算符 >::=< 关系运算符 >|< 算运算符 >|< 运算符 >|< 位运算符 >|< 运算符 > <算数运算符 >:: ＝+|-|*|／|...|-- <关系运算符 >:: ＝<|>|!=|>=|<=|== <运算符 >::=&&| || |！ <位运算符 >::=&| | |！ <运算符 >::==|+=|-=|/=|*= <分界符 >:: ＝ ,|;|(|)|{|}|：| // |/**/ <保留字 >:: ＝ main|if|else|while|do|for|...|void 2.符号的 符号种符号种 main0>26 if1>=27 else2<28 while3<=29 do4!30 for5!=31
第一章 1、将编译程序分成若干个“遍”就是为了。 a．提高程序得执行效率 b．使程序得结构更加清晰 c．利用有限得机器内存并提高机器得执行效率 d．利用有限得机器内存但降低了机器得执行效率 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、语法分析应遵循。 a．语义规则b．语法规则 c．构词规则d．等价变换规则 二、多项选择题 1、编译程序各阶段得工作都涉及到。 a．语法分析b．表格管理c．出错处理 d．语义分析e．词法分析 2、编译程序工作时，通常有阶段。 a．词法分析b．语法分析c．中间代码生成 d．语义检查e．目标代码生成 三、填空题 1、解释程序与编译程序得区别在于。 2、编译过程通常可分为5个阶段，分别就是、语法分析、代码优化与目标代码生成。 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)或者是你觉得程序有哪些地方可以进一步完善，简述你的完善方案。
、单项选择题（本大题共20小题，每小题 1 分，共20分） 在每小题列出的备选项中只有一个是符合题目要求的，多选或未选均无分。请将其代码填写在题后的括号内。错选、 1. 在软件生命周期的各个阶段中，工作量最大的阶段是 A ．需求分析B．总体设计 C．综合测试 D ．软件维护 2. 瀑布模型的特点不包括 A．前一阶段的任务没有完成，不能进入下一阶段工作 B．进入某个阶段工作后，不再回复到之前的阶段工作C．只有完成并评审了规定的文档，才标志着一个阶段的工作结束D．在软件产生之前，需求无法得到充分的测试 3. 螺旋模型强调的开发手段是 A．分阶段开发 C．风险驱动开发 4. 需求分析阶段的工作不包括 A．获得当前系统的物理模型 C．建立目标系统的逻辑模型 5. 总体设计阶段的工作不包括 A．确定程序的模块组成 C．确定实现各个模块功能的处理逻辑 6. 描绘系统物理模型的传统工具是 A ．系统流程图 C．实体-联系图 7. 符合信息隐藏原理的是 A ．将信息隐藏起来不被发现 C．将可能要修改的设计决策隐藏起来B．废弃式原型开发 D．增量式开发 B．抽象出当前系统的逻辑模 型 建立目标系统的物理模型 D． B．确定模块间的相互关 系 D．制定测试计划 B．数据流图 D．状态转换图 B．将信息隐藏起来确保安全 D．将不要修改的设计决策隐藏起 来 8. 模块的独立性原则是指软件设计时要尽量使模块具有 A ．低内聚、低耦合B．低内聚、高耦合C．高内聚、低耦合D．高内聚、高耦合
[ 9. 有利于提高模块独立性的做法是 A．尽量使模块具有逻辑型内聚 B．尽量使模块间具有内容型耦合 C．使判定作用范围内的模块尽量成为该判定所在模块的直属下级模块 D．尽量提高模块的扇入数和扇出数 [ 10. 有关结构化设计（SD ）方法的正确叙述是 ] A．只使用顺序、选择和循环 3 种控制结构 B．由数据结构映射出软件的结构 C．是一种面向对象的设计方法 D．是一种面向数据流的设计方法 [ 11. 有关总体设计阶段所使用的结构图的不正确叙述是 ] A．能够描述软件系统的模块组成 B．结构图中的模块是按照自上而下、自左向右的顺序执行的 C．能够描述模块间的调用关系以及模块间调用时所传递的信息 D．将模块间调用时所传递的信息分成两种：数据信息和控制信息 [ 12. 要求使用顺序、选择和循环控制结构的组合或嵌套来表达程序的过程设计工具是 A ．程序流程图B ． 盒图 C ．判定表D．PDL 13 . 关于好的编码风格的正确叙述是 A ．把多个语句写在同一行以节省空间B．要求用户指定输入数据的数目 C ．检查输入项重要组合的合法性D．表达式中不使用多余的括号，以简化表达式 14 . 能发现软件需求规格说明书中的错误的测试步骤是 A ．模块测试B．子系统测试 C ．系统测试D．验收测试 15 . 自顶向下集成测试和自底向上集成测试都具有的优点是 A ．较早发现主要设计错误B．可采用深度优先策略和宽度优先策略 C ．支持故障隔离D．可复用模块得到充分测试 19 . 不符合面向对象设计准则的是 A ．用对象的封装性来实现信息隐藏B．尽可能松散对象之间的交互耦合 C ．尽可能减小继承耦合度D．尽可能设计小而简单的类 20. 上海大学校内电话号码由 5 位数字组成，但第 1 位数字只能是 5 或6。该电话号码的
中南大学网络教育课程考试复习题及参考答案 编译原理 一、判断题： 1.一个上下文无关文法的开始符，可以是终结符或非终结符。 ( ) 2.一个句型的直接短语是唯一的。 ( ) 3.已经证明文法的二义性是可判定的。 ( ) 4.每个基本块可用一个DAG表示。 ( ) 5.每个过程的活动记录的体积在编译时可静态确定。 ( ) 6.2型文法一定是3 型文法。 ( ) 7.一个句型一定句子。 ( ) 8.算符优先分析法每次都是对句柄进行归约。 ( ) 9.采用三元式实现三地址代码时，不利于对中间代码进行优化。 ( ) 10.编译过程中，语法分析器的任务是分析单词是怎样构成的。 ( ) 11.一个优先表一定存在相应的优先函数。 ( ) 12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ) 13.递归下降分析法是一种自下而上分析法。 ( ) 14.并不是每个文法都能改写成 LL(1)文法。 ( ) 15.每个基本块只有一个入口和一个出口。 ( ) 16.一个 LL(1)文法一定是无二义的。 ( ) 17.逆波兰法表示的表达试亦称前缀式。 ( ) 18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ) 19.正规文法产生的语言都可以用上下文无关文法来描述。 ( ) 20.一个优先表一定存在相应的优先函数。 ( ) 21.3型文法一定是 2型文法。 ( ) 22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。 ( ) 二、填空题： 1.( )称为规范推导。 2.编译过程可分为（），（），（），（）和（）五个阶段。 3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（）。 4.从功能上说，程序语言的语句大体可分为（）语句和（）语句两大类。 5.语法分析器的输入是（），其输出是（）。 6.扫描器的任务是从（）中识别出一个个（）。 7.符号表中的信息栏中登记了每个名字的有关的性质，如（）等等。 8.一个过程相应的DISPLAY表的内容为（）。 9.一个句型的最左直接短语称为句型的（）。 10.常用的两种动态存贮分配办法是（）动态分配和（）动态分配。 11.一个名字的属性包括( )和( )。 12.常用的参数传递方式有（），（）和（）。 13.根据优化所涉及的程序范围，可将优化分成为（），（）和（）三个级别。 14.语法分析的方法大致可分为两类，一类是（）分析法，另一类是（）分析法。 15.预测分析程序是使用一张（）和一个（）进行联合控制的。 16.常用的参数传递方式有（），（）和（）。 17.一张转换图只包含有限个状态,其中有一个被认为是（）态;而且实际上至少要有一个（）态。 18.根据优化所涉及的程序范围，可将优化分成为（），（）和（）三个级别。 19.语法分析是依据语言的（）规则进行。中间代码产生是依据语言的（）规则进行的。 20.一个句型的最左直接短语称为句型的（）。 21.一个文法G，若它的预测分析表M不含多重定义，则该文法是（）文法。 22.对于数据空间的存贮分配， FORTRAN采用( )策略， PASCAL采用( )策略。
编译原理实验报告 班级 姓名： 学号： 自我评定：
实验一词法分析程序实现 一、实验目的与要求 通过编写和调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将字符形式的源程序流转化为一个由各类单词符号组成的流的词法分析方法。 二、实验内容 根据教学要求并结合学生自己的兴趣和具体情况，从具有代表性的高级程序设计语言的各类典型单词中，选取一个适当大小的子集。例如，可以完成无符号常数这一类典型单词的识别后，再完成一个尽可能兼顾到各种常数、关键字、标识符和各种运算符的扫描器的设计和实现。 输入：由符合或不符合所规定的单词类别结构的各类单词组成的源程序。 输出：把单词的字符形式的表示翻译成编译器的内部表示，即确定单词串的输出形式。例如，所输出的每一单词均按形如（CLASS，VALUE）的二元式编码。对于变量和常数，CLASS字段为相应的类别码；VALUE字段则是该标识符、常数的具体值或在其符号表中登记项的序号（要求在变量名表登记项中存放该标识符的字符串；常数表登记项中则存放该常数的二进制形式）。对于关键字和运算符，采用一词一类的编码形式；由于采用一词一类的编码方式，所以仅需在二元式的CLASS字段上放置相应的单词的类别码，VALUE字段则为“空”。另外，为便于查看由词法分析程序所输出的单词串，要求在CLASS字段上放置单词类别的助记符。 三、实现方法与环境 词法分析是编译程序的第一个处理阶段，可以通过两种途径来构造词法分析程序。其一是根据对语言中各类单词的某种描述或定义（如BNF），用手工的方式（例如可用C语言）构造词法分析程序。一般地，可以根据文法或状态转换图构造相应的状态矩阵，该状态矩阵同控制程序便组成了编译器的词法分析程序；也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序的另外一种途径是所谓的词法分析程序的自动生成，即首先用正规式对语言中的各类单词符号进行词型描述，并分别指出在识别单词时，词法分析程序所应进行的语义处理工作，然后由一个所谓词法分析程序的构造程序对上述信息进行加工。如美国BELL实验室研制的LEX就是一个被广泛使用的词法分析程序的自动生成工具。 总的来说，开发一种新语言时，由于它的单词符号在不停地修改，采用LEX等工具生成的词法分析程序比较易于修改和维护。一旦一种语言确定了，则采用手工编写词法分析程序效率更高。 四、实验设计 1）题目1：试用手工编码方式构造识别以下给定单词的某一语言的词法分析程序。 语言中具有的单词包括五个有代表性的关键字begin、end、if、then、else；标识符；整型常数；六种关系运算符；一个赋值符和四个算术运算符。参考实现方法简述如下。 单词的分类：构造上述语言中的各类单词符号及其分类码表。 表I 语言中的各类单词符号及其分类码表 单词符号类别编码类别码的助记符单词值
实验四中间代码生成 一．实验目的： 掌握中间代码的四种形式（逆波兰式、语法树、三元式、四元式）。 二．实验内容： 1、逆波兰式定义:将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表 达式也称做后缀式。 2、抽象（语法）树：运算对象作为叶子结点，运算符作为内部结点。 3、三元式：形式序号：（op,arg1,arg2） 4、四元式：形式（op,arg1,arg2,result） 三、以逆波兰式为例的实验设计思想及算法 (1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。 (2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。 (3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。 (4)如果不是数字，该字符则是运算符，此时需比较优先关系。 做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。 (5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。 四、程序代码： //这是一个由中缀式生成后缀式的程序 #include<> #include<> #include<> #include<> #define maxbuffer 64 void main() { char display_out(char out_ch[maxbuffer], char ch[32]); //int caculate_array(char out_ch[32]); static int i=0; static int j=0; char ch[maxbuffer],s[maxbuffer],out[maxbuffer]; cout<<"请输入中缀表达式: ";
一、填空题（每空2分，共20分） 1．编译程序首先要识别出源程序中每个单词，然后再分析每个句子并翻译其意义。 2．编译器常用的语法分析方法有自底向上和自顶向下两种。 3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合。 4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即静态存储分配方案和动态存储分配方案。 5．对编译程序而言，输入数据是源程序，输出结果是目标程序。 1．计算机执行用高级语言编写的程序主要有两种途径：解释和编译。 2．扫描器是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。 3．自下而上分析法采用移进、归约、错误处理、接受等四种操作。 4．一个LL（1）分析程序需要用到一张分析表和符号栈。 5．后缀式abc-/所代表的表达式是a/(b-c)。 二、单项选择题（每小题2分，共20分） 1．词法分析器的输出结果是__C。 A．单词的种别编码B．单词在符号表中的位置 C．单词的种别编码和自身值D．单词自身值 2．正规式 M 1 和 M 2 等价是指__C_。 A． M1和M2的状态数相等B． M1和M2的有向边条数相等 C． M1和M2所识别的语言集相等 D． M1和M2状态数和有向边条数相等 3．文法G：S→xSx|y所识别的语言是_C____。 A． xyx B． (xyx)* C．xnyxn(n≥0) D． x*yx* 4．如果文法G是无二义的，则它的任何句子α_A____。 A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握____D__。 A．源程序B．目标语言 C．编译方法 D．以上三项都是 6．四元式之间的联系是通过__B___实现的。 A．指示器B．临时变量C．符号表 D．程序变量 7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为__B___。 A．┐AB∨∧CD∨B．A┐B∨CD∨∧C． AB∨┐CD∨∧ D．A┐B∨∧CD∨8. 优化可生成__D___的目标代码。 A．运行时间较短B．占用存储空间较小 C．运行时间短但占用内存空间大 D．运行时间短且占用存储空间小 9．下列___C___优化方法不是针对循环优化进行的。 A. 强度削弱 B．删除归纳变量C．删除多余运算 D．代码外提 10．编译程序使用_B_区别标识符的作用域。 A. 说明标识符的过程或函数名B．说明标识符的过程或函数的静态层次 C．说明标识符的过程或函数的动态层次 D. 标识符的行号 三、判断题（对的打√，错的打×，每小题1分，共10分） 2．一个有限状态自动机中，有且仅有一个唯一的终态。x
《编译原理》课程设计题目 设计题一：正规式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
上海大学2013 ～2014学年秋季学期研究生试题A卷 课程名称：写作1 课程编号：001704G2学分：0.5 (请在答题纸上答题，否则无效) Part One: Diction （20%）（10—20%可以来自于课本） Directions: Choose the right one from the following two choices marked A or B. 1.The argument can only be settled by someone who is __________. A. disinterested B. uninterested 2.This is an interesting book with vivid account of __________ events and people. A. historic B. historical 3.The information was __________ as a result of various experiments. A. obtained B. acquired 4.If no one takes the __________ and plan for the trip, we will never leave home. A. initial B. initiative 5.From her conversation, I __________ that she had a happy family. A. induce B. deduce 6.I don’t know the results of the tests yet. __________, why are you so interested in them? A. Somehow B. Anyhow 7. He gave his clearest _____ yet that he will keep racing. A. indication B. prediction 8．He hoped the firm would _____ him to the Paris branch. A. transmit B. transfer 9. Jim Lovell talked about the current situation at NASA during an _____ to mark the fortieth anniversary of Apollo Thirteen. A. event B. incident 10. A good scientist is highly __________ since he often has to look for relations in data which are often complex and incomplete. A. imaginative B. imaginary 11. I seem to have _____ myself in something I don’t understand. A. evolved B. involved 12. I'm very sorry to have _____ you with so many questions on such an occasion. A. interfered B. bothered 13. When you have filled in the questionnaire, copy it and send the _____ to your employer. A. original B. initial 14. People don’t like to ask questions for fear of app earing _____. A. illiterate B. ignorant 15. From Mexico, President Obama traveled Friday to the Caribbean nation of Trinidad and Tobago for the Fifth _____ of the Americas. A. Conference B. Summit 16. She was a woman of _____ talent and determination. A. single B. unique 17. FM radio stations _____ in a range of frequencies between eighty-eight and one hundred eight megahertz.
编译原理实验指导书 主编：徐静李娜 信息与电气工程学院 2010年3月
概述 一、本课程实验的目的和任务 编译原理是一门实践性很强的课程，只有通过实践，才能真正掌握。实际的编译程序是十分复杂的，有时由多达十几万条指令组成。为此，编译原理的实践教学，采用简化编译过程的办法，选择最关键的3个环节──词法分析、语法分析（包括语义处理、产生无优化的目标指令）、连接调试，进行编程和调试训练。每个环节作为一个实践课题。先分别编程调试，再连接在一起总调。 二、实验方法 任何一个实用的高级语言，其语法都比较复杂，如选其作为源语言，很难实践全过程。故本实验将定义一个简化的语言── C语言的一个子集作为源语言，设计调试出它的编译程序。前后贯穿这一条主线进行实践。每次都可利用课余时间编程，利用上机时间进行输入和调试。 三、实验报告的规范和要求 每个实验完成后写出实验报告。实验报告的内容包括如下内容： 一、实验目的 二、程序设计时采用的算法和方法 三、输入的源程序 四、词法分析程序清单和输出结果。 五、心得体会
实验一词法分析 一、实验目的： （1）通过设计编制调试一个具体的词法分析程序，理解词法分析在编译程序中的作用。 （2）加深对有穷自动机模型的理解。 （3）掌握词法分析程序的实现方法和技术。 （4）用C语言对一个简单语言的子集编制一个一遍扫描的程序，以加深对编译原理的理解，掌握编译程序的实现方法和技术。 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）。 二、实验预习提示 1. 词法分析器的功能和输出格式 词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示成以下的二元式（单词种别码，单词符号的属性值）。本实验中，采用的是一类符号一种别码的方式。 2. 单词的BNF表示 <标识符>→ <字母><字母数字串> <字母数字串>→<字母><字母数字串>|<数字> <字母数字串>| <下划线><字母数字串>|ε <无符号整数>→<数字> <数字串> <数字串>→<数字><数字串>|ε <加法运算符>→+ <减法运算符>→- <大于关系运算符>→> <大于等于关系运算符>→>= 3. “超前搜索”方法
一、名词解释 1.正规文法 2. 编译程序 3. 文法的推导 4.子树 5. LL(1)文法 6. 文法的句子 7. LR （0）文法 8. 请写出四种参数传递的方式 二综合题 1. 请写出编译程序的五个步骤。 2. 给定文法G ：（0）S →aAcBe （1）A →b （2）A →Ab （3）B →d 若有句型 aAbcde ，试问b 是它的直接短语吗？它的短语是什么？句柄是什么？ 3. 设有文法:S->aSbS|bSaS|ε 通过为句子abab 建立两个最左推导来说明该文法是二义文法。 4. 写出下列语言的上下文无关文法：{}0,|)(≥=m n G L c b a m n n 5. 写出下列语言的上下文无关文法：L(G)={a n b n c m d m , n, m ≥0}。 6. 令文法G ：S → aS S →a | b 给出句子aaaab 的最左推导。 7. 证明下面的文法是有二义性的。 E →-EE E →-E E →a|b|c 8. 文法G 为： E→E+T|T T→T*F|F F→(E)|i （1）画出句型(E+F)*i 的语法树； （2）给出句型(E+F)*i 短语，简单(直接)短语,句柄。 9. 设字母表∑={a,b}，给出∑上的正则式R=（a | ba ）* （1）构造NFA M ，使得L （M ）=L （R ）。 （2）将NFA M 确定化、最小化，得到minDFA M 。 （3）求右线形文法G ，使得L （G ）=L （M ） 10. 设字母表∑={0,1}，给出∑上的正则式R=0（0 | 1）*1 （1）构造NFA M ，使得L （M ）=L （R ）。 （2）将NFA M 确定化，最小化，得到minDFA M 。 11. 设字母表∑={0,1}，给出∑上的正则式R=(a|b)*a (a|b) （1）构造NFA M ，使得L （M ）=L （R ）。
学生学号0120810680316 实验课成绩 武汉理工大学 学生实验报告书 实验课程名称《编译原理》 开课学院计算机科学与技术学院 指导老师姓名何九周 学生姓名刘洋 学生专业班级软件工程0803 2010 —2011 学年第二学期
实验课程名称：编译原理 实验项目名称单词的词法分析程序设计实验成绩实验者刘洋专业班级软件0803 组别 同组者实验日期 2011 年 5 月 17日 第一部分：实验分析与设计（可加页） 一、实验内容描述（问题域描述） 实验目的： 设计，编制并调试一个词法分析程序，加深对词法分析原理的理解。 实验要求： 在上机前应认真做好各种准备工作，熟悉机器的操作系统和语言的集成环境，独立完成算法编制和程序代码的编写；上机时应随带有关的高级语言教材或参考书；要学会程序调试与纠错；每次实验后要交实验报告。 实验题目： 对于给定的源程序（如C语言或Pascal等），要求从组成源程序的字符行中寻找出单词，并给出它们的种别和属性——输出二元组序列。以便提供给语法分析的时候使用。要求能识别所有的关键字，标志符等，并且能够对出先的一些词法规则的错误进行必要的处理。 二、实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或 者算法描述） 实验原理： 由于这是一个用高级语言编写一个词法分析器,使之能识别输入串,并把分析结果(单词符号,标识符,关键字等等)输出.输入源程序,输入单词符号,本词法分析器可以辨别关键字,标识符,常数,运算符号和某些界符,运用了文件读入来获取源程序代码,再对该源程序代码进行词法分析,这就是词法分析器的基本功能.当词法分析器调用预处理子程序处理出一串输入字符放进扫描缓冲区之后,分析器就从此缓冲区中逐一识别单词符号.当缓冲区里的字符串被处理完之后,它又调用预处理子程序来处理新串. 编写的时候，使用了文件的输入和输出，以便于词法分析的通用型，同时在文件输出时，并保存在输出文件output文件中。 从左到右扫描程序，通过初始化：1为关键字；2为标志符； 3为常数；4为运算符或界符。 三、主要仪器设备及耗材 计算机
《编译原理》实验报告软件131 陈万全132852
一、需求分析 通过对一个常用高级程序设计语言的简单语言子集编译系统中词法分析、语法分析、语义处理模块的设计、开发，掌握实际编译系统的核心结构、工作流程及其实现技术，获得分析、设计、实现编译程序等方面的实际操作能力，增强设计、编写和调试程序的能力。 通过开源编译器分析、编译过程可视化等扩展实验，促进学生增强复杂系统分析、设计和实现能力，鼓励学生创新意识和能力。 1、词法分析程序设计与实现 假定一种高级程序设计语言中的单词主要包括五个关键字begin、end、if、then、else；标识符；无符号常数；六种关系运算符；一个赋值符和四个算术运算符，试构造能识别这些单词的词法分析程序。 输入：由符合和不符合所规定的单词类别结构的各类单词组成的源程序文件。 输出：把所识别出的每一单词均按形如（CLASS，VALUE）的二元式形式输出，并将结果放到某个文件中。对于标识符和无符号常数，CLASS字段为相应的类别码的助记符；VALUE字段则是该标识符、常数的具体值；对于关键字和运算符，采用一词一类的编码形式，仅需在二元式的CLASS字段上放置相应单词的类别码的助记符，VALUE字段则为“空”。 2、语法分析程序设计与实现 选择对各种常见高级程序设计语言都较为通用的语法结构——算术表达式的
一个简化子集——作为分析对象，根据如下描述其语法结构的BNF定义G2[<算术表达式>]，任选一种学过的语法分析方法，针对运算对象为无符号常数和变量的四则运算，设计并实现一个语法分析程序。 G2[<算术表达式>]： <算术表达式>→<项> | <算术表达式>+<项> | <算术表达式>-<项> <项>→<因式>|<项>*<因式>|<项>/<因式> <因式>→<运算对象> | (<算术表达式>) 若将语法范畴<算术表达式>、<项>、<因式>和<运算对象>分别用E、T、F和i 代表，则G2可写成： G2[E]：E → T | E+T | E-T T → F | T*F | T/F F → i | (E) 输入：由实验一输出的单词串，例如：UCON，PL，UCON，MU，ID······输出：若输入源程序中的符号串是给定文法的句子，则输出“RIGHT”，并且给出每一步分析过程；若不是句子，即输入串有错误，则输出“ERROR”，并且显示分析至此所得的中间结果，如分析栈、符号栈中的信息等，以及必要的出错说明信息。 3、语义分析程序设计与实现 对文法G2[<算术表达式>]中的产生式添加语义处理子程序，完成运算对象是简单变量（标识符）和无符号数的四则运算的计值处理，将输入的四则运算转换为四元式形式的中间代码。 输入：包含测试用例（由标识符、无符号数和+、?、*、/、(、)构成的算术表达式）的源程序文件。 输出：将源程序转换为中间代码形式表示，并将中间代码序列输出到文件中。 若源程序中有错误，应指出错误信息 二、设计思路 1、词法分析程序设计与实现 1)单词分类 为了编程的实现。我们假定要编译的语言中，全部关键字都是保留字，程序员不得将它们作为源程序中的标识符；作了这些限制以后，就可以把关键字和标识符的识别统一进行处理。即每当开始识别一个单词时，若扫视到的第一个字符为字母，则把后续输入的字母或数字字符依次进行拼接，直至扫视到非字母、数字字符为止，以期获得一个尽可能长的字母数字字符串，然后以此字符串查所谓保留字表（此保留字表要事先造好），若查到此字符串，则取出相应的类别码；反之，则表明该字符串应为一标识符。
考试题型（供参考） 三.(5分) 写一个文法，使其语言是： L ＝ { ambn | m≥n≥1 } 答： G[S]: S → aSb | aAb A → aA |ε 四．（7分）给出接受字母表?={a，b}，语言为以b开头，以aa结尾的字符串集合的正规表 达式，并构造与之等价状态的NFA。（或求DFA!） 答： 依题意，以b开头，以aa结尾的字符串集合的正规表达式可写为： b(a|b)*aa（3分） 画NFA，如下图所示（4分） 五.（10分）已知文法：G[S]: S → aA | d A → bAS |ε （1）（4分）求出每条产生式的选择集 Select(S→aA) = Select(S→d) = Select(A→bAS) = Select(A→ε) = （2）（6分）判断该文法是否为LL（1）文法，若是，请给出理由并构造预测分析表。 七. （10分）设有拓广文法G为: S’? S S ? LaR | R L ? bR | c R ? L 其部分LR(1)项目集和转换函数如下图所示。 (1)写出状态I0，I12，I9的内容; (2)判断该文法是否为LR(1)文法。 答： （1）8分 I0： I12： I9： （2）因为状态图中没有冲突，所以是LR(1)文法。（2分） 八.（8分）试完成下列语句翻译的四元式序列。 while (A>B) do if(C>D) then X:=Y*Z else X:=Y+Z;
(1) if A>B goto (3) (2) goto (11) (3) _________ (4) goto (8) (5) _________ (6) X:=T1 (7) (8) T2:=Y+Z (9) X:=T2 (10) _________ (11) 答： (3) if C
相关主题
文本预览