机密★启用前
大连理工大学网络教育学院
2019年秋《编译原理基础》
期末考试复习题
☆注意事项：本复习题满分共：200分。
一、单项选择题
1、以010结尾的二进制串的正规式为（）。
A．(1|0)*01 B．0*01*
C．(1|0)*010 D．0(1|0)*01
2、与(s|t)* (s|t)等价的正规式是（）。
A．s*| t* B．(st)*(s|t)
C．(s|t)(s|t)* D．(s|t)*
3、对正规式(a*|b*)+所描述的语言，下列说法准确的是（）。
A．连续个a再加连续个b所组成的串的集合
B．a和b个数相等的串的集合
C．a和b组成的所有串（不含空串）的集合
D．a和b组成的所有串（包含空串）的集合
4、对于DFA模型，说法错误的是（）。
A．DFA从任何状态出发，对于任何输入符号，可有多个转换
B．任何状态都没有ε转换
C．DFA有唯一的开始状态
D．DFA可以有多个接受状态
5、以下说法错误的是（）。
A. NFA的状态集合是无限的
B. NFA的输入符号可能有多个
C. DFA的状态集合是有限的
D. DFA的输入符号可能有多个
6、符号串ab1b2是文法G[A]：A→aB B→bB|b的句子，该句子的句柄是（）。
A．b1B．b2
C．a D．b1b2
7、移进-归约分析为输入串构造分析树是从（）开始的。
A．根结点B．叶结点
C．中间结点D．任一结点
8、下列叙述正确的是（）。
A．任何LL(1)文法都是LR(1)文法
B．任何LL(1)文法都是SLR(1)文法
C．任何SLR(1)文法肯定是LR(1)文法
D．任何LR(1)文法肯定是LALR(1)文法
9、下列叙述正确的是（）。
A．S属性定义属于L属性定义
B．变量类型声明的语法制导定义不是一个L属性定义
C．L属性定义只包含综合属性
D．L属性定义只包含继承属性
10、中间代码生成时所依据的为（）。
A．语法规则B．语法规则
C．语义规则D．等价变换规则
单选题答案
1． A 2． B 3． D 4． A 5． A
6． B 7． B 8． C 9． A 10．C
二、填空题
1、对编译程序而言，输入数据是，输出结果是。
答案：源程序目标程序
2、对于一个文法G而言，如果L(G)中存在某个句子对应两棵不同的那么该文法就称为是二义的。
答案：语法树
3、编译器常用的语法分析方法有和两种。
答案：自底向上、自顶向下
4、程序设计语言的发展带来日渐多变的运行时存储管理方案，主要分为两大类
即分配方案和分配方案。
答案：静态存储、动态存储
5、最右推导称为，由规范推导产生的句型称为规范句型。
答案：规范推导
三、判断题
1、L*表示零个或多个L连接的并集。（）
2、闭包运算有最高的优先级并且是右结合的运算。（）
3、不确定的有限自动机是指对于某个输入符号，它存在不止一种转换。（）
4、每一个正规集都可以由一个状态数最少的DFA识别，这个DFA是可以不唯一的。（）
5、对于S属性定义，分析树各结点属性的计算可以自下而上地完成。（）
6、编程语言的一些构造的属性依赖于它们所在的上下文，此时使用继承属性是方便的。（）
7、中间表示设计的选择随编译器不同而不同。（）
8、三地址代码每条指令通常包含三个地址，即两个运算对象的地址和一个结果的地址。（）
9、静态单赋值形式是一种便于某些代码优化的中间表示。（）
10、流图的结点是基本块。（）
11、解释器可以通过翻译来生成目标程序。（）
12、如果X和Y都是串，那么X和Y的连接是把Y加到X的后面形成的串。（）
13、LM表示L和M的并。（）
14、正规式a*表示由字母a构成的所有串的集合其中不包括空串。（）
15、有限自动机分成确定的和不确定的两种情况。（）
16、由上下文无关文法产生的语言叫做上下文无关语言。（）
17、分析树子结点由非终结符本次推导所用产生式的右部的各符号从右到左依次来标记。（）
18、在语法制导定义中，其中的文法被称为基础文法。（）
19、后缀表示的最大优点是便于计算机处理表达式。（）
20、三地址语句序列的一种图形表示叫做流图。（）
答案：
1．√ 2．× 3．√ 4．× 5．√
6．√ 7．√ 8．√ 9．√ 10．√
11．× 12．√ 13．× 14．× 15．√
16．√ 17．× 18．√ 19．√ 20．√
四、名词解释
1、基本块
连续的语句序列，控制流从它的开始进入，并从它的末尾离开
2、词法单元
又称单元，是源程序中匹配一个记号模式的字符序列,它由词法分析器识别该记号的一个实例。
3、翻译器
把一种语言变换到另外一种语言的软件。这两种语言分别称为源语言和目标语言。
4、编译器
是一种翻译器，它的目标语言比源语言低级。
五、简答题
1、给出下列语言的正规表达式。
在{0,1}上不以0开头的，以11结尾的字符串集合。
最多只含2个a的{a,b}上的语言。
答：(1) 11 | 1(1|0)* 11
(2) b*(a| ε)b *(a| ε)b* 或者b*|b*ab*|b*ab*ab*
2、简述用综合属性代替继承属性的方法。
答：
（1）删除翻译方案中嵌入的动作；
（2）分析栈上的继承属性，使用栈上的综合属性代替继承属性；
（3）模拟继承属性的计算
3、分析器的基本动作分类
答：
移进动作
归约动作
接受动作
报错动作
4、简述确定的有限自动机和不确定的有限自动机的区别。
答：确定和不确定的有限自动机都正好能识别正规集，它们之间存在着时空权衡问题:从确定的有限自动机得到识别器，比从等价的不确定的有限自动机得到识别器要快得多，但是，确定的有限自动机可能比等价的不确定有限自动机占用更多的空间，把正规式变成不确定的自动机更直接一些。
5、设∑={0, 1}，写出∑上所有以1开头，101结束的字符串的正规式，并构造其对应的NFA。
答：构造该正规式相应的不确定有限自动机NFA: 1(0|1)*101。
评分标准：画出DFA视为等同画出NFA。
6、简述编译器常用的语法分析方法
答：编译器常用的语法分析方法有自上而下和自下而上两种。自上而下分析器按从根结点到叶结点的次序来建立分析树，而自下而上分析器恰好相反，它们的共同点是从左向右地扫描输入，每次一个符号。
7、从软件工程的角度看，词法分析和语法分析的分离有什么好处？
答：
编译器的效率会改进。
编译器的可移植性加强。
把语言的语法结构分成词法和非词法两部分，为编译器前端的模块划分提供了方便的途径。
8、简述编程通常会出现的错误。
答：
词法错误
语法错误
语义错误
逻辑错误
9、试述为什么用正规式定义语言的词法？
答：
语言的词法规则非常简单，不必用功能更强的上下文无关文法描述它。
对于词法记号，正规式给出的描述比上下文无关文法给出的更简洁且易于理解。
从正规式自动构造出的词法分析器比从上下文无关文法构造出的更有效。
10、写出X:=(B-5)*A+(C+D)*T的三地址代码。
答：
t1=B-5
t2= t1*A
t3=C+D
t4=t3*T
X=t2+t4
11、简述分析器错误处理的基本目标。
答：
清楚而准确地报告错误的出现；
迅速地从每个错误中恢复过来，以便诊断剩余程序的错误；
它不应该使处理正确程序的速度降低太多。
六、分析题
1、设文法G[E]：
E→T | E + T | E - T
T→F | T * F | T / F
F→( E ) | i
1）给出该文法的终结符集合。
2）给出该文法的非终结符集合。
3）画出句子i*( i + i )的自上而下分析树。
4）该文法是LL(1)文法吗？请解释。
答：
1）给出该文法的终结符集合。
+ - * / ( ) i
2）给出该文法的非终结符集合。
E, T, F
3）画出句子i*( i + i )的的自上而下分析树。
最左推导
E?T?T*F?F*F ?i*F?i*(E) ? i*(E+T) ? i*(T+T) ? i*(F+T) ? i*(i+T) ? i*(i+F) ? i*( i + i )
F E F T E ()E T T F i
F T *
4）该文法是LL(1)文法吗？请解释。 不是。
因为存在左递归，因此不是LL(1)文法。 2、考虑如下的上下文无关文法G[L]：
（1）针对表达式id + id ; id ( id ( ) )给出最左推导。 （2）给出表达式id + id ; id ( id ( ) )的语法树。
L → E ; L | E E → E + T | T T → id | id ( ) | id ( L ) 答： （1）
L ? E ; L
? E+ T ; L ? T+ T ; L ? id + T ; L ? id + id ; L ? id + id ; E ? id + id ; T
? id + id ; id ( L ) ? id + id ; id ( E ) ? id + id ; id ( T ) ? id + id ; id ( id ( ) )
（2）
L ；L E E T L T T +
id E id
id (
)
T E id （）
(判断题)1: 试探与回溯是一种穷尽一切可能的办法,效率低、代价高,它只有理论意义,在实践中价值不大。 A: 对 B: 错 正确答案: (判断题)2: 预测分析的关键问题是在扩展一个非终结符时怎样为它选择合适的产生式。A: 对 B: 错 正确答案: (判断题)3: 移进-归约分析为输入串构造分析树是从根结点开始的,朝着叶结点方向前进。A: 对 B: 错 正确答案: (判断题)4: 句型的句柄是该句型中和一个产生式左部匹配的子串。 A: 对 B: 错 正确答案: (判断题)5: 一个文法,如果能为它构造出所有条目都唯一的LR分析表,就说它是LR文法。A: 对 B: 错 正确答案: (判断题)6: 语法制导的产生式有多组语义规则。 A: 对 B: 错 正确答案: (判断题)7: 属性文法是指语义规则函数无副作用的语法制导定义。 A: 对 B: 错 正确答案: (判断题)8: 仅仅使用综合属性的语法制导定义称为S属性定义。 A: 对 B: 错 正确答案: (判断题)9: 每个结点的属性值都标注出来的分析树叫做注释分析树。 A: 对 B: 错
(判断题)10: 过程定义是一个声明,它的最简单形式是将一个名字和一个语句联系起来,该名字是过程名,而这个语句是过程体。 A: 对 B: 错 正确答案: (判断题)11: 过程名出现在调用语句中则称这个过程在该点被调用。 A: 对 B: 错 正确答案: (判断题)12: 出现在过程定义中的某些名字是特殊的,它们被称为该过程的形式参数,简称形参。 A: 对 B: 错 正确答案: (判断题)13: 一个声明起作用的程序部分称为该声明的作用域。 A: 对 B: 错 正确答案: (判断题)14: 引用某个已被回收的存储单元就称为悬空引用。 A: 对 B: 错 正确答案: (判断题)15: 后缀表示是语法树的一种线性表示。 A: 对 B: 错 正确答案: (单选题)16: 对于LR(0)分析法,语法分析栈中存放的状态是识别规范句型()的DFA状态。A: 前缀 B: 活前缀 C: LR(0)项目 D: 句柄 正确答案: (单选题)17: 同心集合并可能会产生的冲突为()。 A: 二义 B: 移进-移进
编译原理实验指导 实验安排： 上机实践按小组完成实验任务。每小组三人，分别完成TEST语言的词法分析、语法分析、语义分析和中间代码生成三个题目,语法分析部分可任意选择一种语法分析方法。先各自调试运行，然后每小组将程序连接在一起调试，构成一个相对完整的编译器。 实验报告： 上机结束后提交实验报告，报告内容： 1．小组成员； 2．个人完成的任务； 3．分析及设计的过程； 4．程序的连接； 5．设计中遇到的问题及解决方案； 6．总结。
实验一词法分析 一、实验目的 通过设计编制调试TEST语言的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。 二、实验预习提示 1．词法分析器的功能和输出格式 词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示 成以下的二元式(单词种别码，单词符号的属性值)。 2．TEST语言的词法规则
编译原理语法分析实验报告 - 班级:XXX 学号:XXX 姓名:XXX 年月日 1、摘要: 用递归子程序法实现对pascal的子集程序设计语言的分析程序 2、实验目的: 通过完成语法分析程序，了解语法分析的过程和作用 3、任务概述 实验要求:对源程序的内码流进行分析，如为文法定义的句子输出”是”否则输出”否”,根据需要处理说明语句填写写相应的符号表供以后代码生成时使用 4、实验依据的原理 递归子程序法是一种自顶向下的语法分析方法，它要求文法是LL(1)文法。通过对文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式时，程序能够按LL(1)形式唯一地确定选择某个候选式进行推导，最终识别输入串是否与文法匹配。 递归子程序法的缺点是:对文法要求高，必须满足LL(1)文法，当然在某些语言中个别产生式的推导当不满足LL(1)而满足LL(2)时，也可以采用多向前扫描一个符号的办法;它的另一个缺点是由于递归调用多，所以速度慢占用空间多，尽管这样，它还是许多高级语言，例如PASCAL，C等编译系统常常采用的语法分析方法。
为适合递归子程序法，对实验一词法分析中的文法改写成无左递归和无左共因子的,,,如下: <程序>?<程序首部><分程序>。 <程序首部>?PROGRAM标识符; <分程序>?<常量说明部分><变量说明部分><过程说明部分> <复合语句> <常量说明部分>?CONST<常量定义><常量定义后缀>;|ε <常量定义>?标识符=无符号整数 <常量定义后缀>?，<常量定义><常量定义后缀> |ε <变量说明部分>?VAR<变量定义><变量定义后缀> |ε <变量定义>?标识符<标识符后缀>:<类型>; <标识符后缀>?，标识符<标识符后缀> |ε <变量定义后缀>?<变量定义><变量定义后缀> |ε <类型>?INTEGER | LONG <过程说明部分>?<过程首部><分程序>;<过程说明部分后缀>|ε <过程首部>?PROCEDURE标识符<参数部分>; <参数部分>?(标识符: <类型>)|ε <过程说明部分后缀>?<过程首部><分程序>;<过程说明部分后缀>|ε <语句>?<赋值或调用语句>|<条件语句>|<当型循环语句>|<读语句> |<写语句>|<复合语句>|ε <赋值或调用语句>?标识符<后缀> <后缀>?:=<表达式>|(<表达式>)|ε <条件语句>?IF<条件>THEN<语句> <当型循环语句>?WHILE<条件>DO <语句> <读语句>?READ(标识符<标识符后缀>)
(判断题)1: 编译器是一种翻译器,它的特点是目标语言比源语言低级。 A: 对 B: 错 正确答案: (判断题)2: 语法树的子结点代表该运算的运算对象。 A: 对 B: 错 正确答案: (判断题)3: 语义分析的一个重要部分是类型检查,编译器检查每个算符的运算对象,看它们的类型是否适当。 A: 对 B: 错 正确答案: (判断题)4: 语言定义不允许运算对象的类型作隐式转换。 A: 对 B: 错 正确答案: (判断题)5: 代码生成是指取源程序的一种中间表示作为输入并把它映射到一种目标语言。A: 对 B: 错 正确答案: (判断题)6: 符号表是为每个变量名字保存一个记录的数据结构,记录的域是该名字的属性。A: 对 B: 错 正确答案: (判断题)7: 解释器可以通过翻译来生成目标程序。 A: 对 B: 错 正确答案: (判断题)8: 解释执行的效率比编译器生成的机器代码的执行效率高。 A: 对 B: 错 正确答案: (判断题)9: 类型检查是一种捕捉程序中不一致性的成熟并且有效的技术。 A: 对 B: 错
(判断题)10: 类型检查技术不能用于捕捉多种安全漏洞。 A: 对 B: 错 正确答案: (判断题)11: 词法分析器的任务是把构成源程序的字符流翻译成词法记号流。 A: 对 B: 错 正确答案: (判断题)12: 词法分析难以发现源程序的错误,因为词法分析器对源程序采取非常局部的观点。 A: 对 B: 错 正确答案: (判断题)13: 字母表上的串是该字母表符号的有穷序列。 A: 对 B: 错 正确答案: (判断题)14: 术语语言表示字母表上的一个串集,属于该语言的串称为该语言的句子或字。A: 对 B: 错 正确答案: (判断题)15: 对于连接运算而言,空串是一个恒等元素。 A: 对 B: 错 正确答案: (单选题)16: ( )不是编译程序的组成部分。 A: 词法分析程序 B: 代码生成程序 C: 设备管理程序 D: 语法分析程序 正确答案: (单选题)17: 编译的各阶段工作都涉及( )。 A: 符号表管理 B: 词法分析 C: 语法分析
编译原理实验报告实验名称：实验一编写词法分析程序 实验类型：验证型实验 指导教师：何中胜 专业班级：13软件四 姓名：丁越 学号： 电子邮箱： 实验地点：秋白楼B720 实验成绩： 日期：2016年3 月18 日
一、实验目的 通过设计、调试词法分析程序，实现从源程序中分出各种单词的方法；熟悉词法分析 程序所用的工具自动机，进一步理解自动机理论。掌握文法转换成自动机的技术及有穷自动机实现的方法。确定词法分析器的输出形式及标识符与关键字的区分方法。加深对课堂教学的理解；提高词法分析方法的实践能力。通过本实验，应达到以下目标： 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。 二、实验过程 以编写PASCAL子集的词法分析程序为例 1.理论部分 （1）主程序设计考虑 主程序的说明部分为各种表格和变量安排空间。 数组 k为关键字表，每个数组元素存放一个关键字。采用定长的方式，较短的关键字 后面补空格。 P数组存放分界符。为了简单起见，分界符、算术运算符和关系运算符都放在 p表中 （编程时，还应建立算术运算符表和关系运算符表，并且各有类号），合并成一类。 id和ci数组分别存放标识符和常数。 instring数组为输入源程序的单词缓存。 outtoken记录为输出内部表示缓存。 还有一些为造表填表设置的变量。 主程序开始后，先以人工方式输入关键字，造 k表；再输入分界符等造p表。 主程序的工作部分设计成便于调试的循环结构。每个循环处理一个单词；接收键盘上 送来的一个单词；调用词法分析过程；输出每个单词的内部码。 ⑵词法分析过程考虑 将词法分析程序设计成独立一遍扫描源程序的结构。其流程图见图1-1。 图1-1 该过程取名为 lexical，它根据输入单词的第一个字符（有时还需读第二个字符），判断单词类，产生类号：以字符 k表示关键字；i表示标识符；c表示常数；p表示分界符；s表示运算符（编程时类号分别为 1，2，3，4，5）。 对于标识符和常数，需分别与标识符表和常数表中已登记的元素相比较，如表中已有 该元素，则记录其在表中的位置，如未出现过，将标识符按顺序填入数组id中，将常数 变为二进制形式存入数组中 ci中，并记录其在表中的位置。 lexical过程中嵌有两个小过程：一个名为getchar，其功能为从instring中按顺序取出一个字符，并将其指针pint加1；另一个名为error，当出现错误时，调用这个过程， 输出错误编号。 2.实践部分
学号107 成绩 编译原理上机报告 名称：编写递归下降语法分析器 学院：信息与控制工程学院 专业：计算机科学与技术 班级：计算机1401班 姓名：叶达成 2016年10月31日
一、上机目的 通过设计、编制、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握常用的语法分析方法。通过本实验，应达到以下目标： 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。 二、基本原理和上机步骤 递归下降分析程序实现思想简单易懂。程序结构和语法产生式有直接的对应关系。因为每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。 递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。 每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。 自上向下分析过程中，如果带回溯，则分析过程是穷举所有可能的推导，看是否能推导出待检查的符号串。分析速度慢。而无回溯的自上向下分析技术，当选择某非终结符的产生时，可根据输入串的当前符号以及各产生式右部首符号而进行，效率高，且不易出错。 无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。 无左递归：既没有直接左递归，也没有间接左递归。 无回溯：对于任一非终结符号U的产生式右部x1|x2|…|x n，其对应的字的首终结符号两两不相交。 如果一个文法不含回路（形如P?+ P的推导），也不含以ε为右部的产生式，那么可以通过执行消除文法左递归的算法消除文法的一切左递归（改写后的文法可能含有以ε为右部的产生式）。 三、上机结果 测试数据： (1)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# (2)输出结果：i+i*i#为合法符号串 (3)输入一符号串如i+i*#,要求输出为“非法的符号串”。 程序清单： #include
《编译原理》课程实验指导书 计算机学院编 ２００７年９月
实验一 C语言子集编译程序 一、实验目的 用C语言对一个C语言的子集编制一个一遍扫描的编译程序，以加深对编译原理的理解，掌握编译程序的实现方法和技术。 1．设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 2．编制一个递归下降分析程序，并对C语言的简单子集进行分析。 3．通过上机实习，加深对语法制导翻译原理的理解，掌握将语法分析所识别的语法成分变换中间代码的语义翻译方法。 二、实验要求、内容及学时 词法分析部分：2学时 （一）待分析的C语言子集的词法： 1．关键字 main if else int return void while 所有关键字都是小写。 2．专用符号 = + - * / < <= > >= == != ; : , { } [ ] ( ) 3.其他标记ID和NUM 通过以下正规式定义其他标记： ID→letter(letter|digit)*NUM→digit(digit)* letter→a|…|z|A|…|Z digit→0|…|9 4.空格由空白、制表符和换行符组成 空格一般用来分隔ID、NUM、专用符号和关键字，词法分析阶段空格通常被忽略。各种
（二）词法分析程序的功能： 输入：所给文法的源程序字符串。 输出：二元组（syn,token或sum）构成的序列。其中， syn 为单词类别码。 token 为存放的单词自身字符串。 sum 为整型常量。 具体实现时，可以将单词的二元组用结构进行处理。 例如：对源程序 main() { int i=10; while(i) i=i-1; } 的源文件，经词法分析后输出如下序列： (1,main) (26,() (27,)) (30,{) (2,int) (10,i) (21,=) (20,10) (34,;) (7,while) (26,() (10,i) (27,)) (10,i) (21,=) (10,i) (23,-) (20,1) (34,;) (31, }) （三）词法分析程序主要算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 1．主程序示意结构图（如下）： 注：
1．编译程序 编译程序是一种翻译程序，它将高级语言所写的源程序翻译成等价的机器语言或汇编语言的目标程序。 2．词法分析（Lexical analysis或Scanning）和词法分析程序（Lexical analyzer 或Scanner） 词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。词法分析程序实现这个任务。词法分析程序可以使用lex等工具自动生成。 3．语法分析（Syntax analysis或Parsing）和语法分析程序（Parser） 语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述. 4．语义分析（Syntax analysis）及中间代码生成 语义分析是编译过程的一个逻辑阶段. 语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查, 进行类型审查.例如一个C程序片断: int arr[2],b; b = arr * 10; 源程序的结构是正确的. 语义分析将审查类型并报告错误:不能在表达式中使用一个数组变量,赋值语句的右端和左端的类型不匹配.语义分析时，根据语句的含义，可对它进行翻译，用另一种语言形式（比源语言更接近于目标语言的一种中间代码或直接用目标语言）来描述这种语义。 5．代码优化 代码优化的任务是对前阶段产生的中间代码进行等价变换或改造，以期获得更为高效的，即省时间和空间的代码。 6．目标代码生成 目标代码的生成的任务是将中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。 7．遍 8．前端（Front－end）和后端（Back end） 有时，常常把编译的过程分为前端(front end)和后端(back end)，前端由那样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常这些阶段包括词法分析、语法分析、语义分析和中间代码生成，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理工作。后端工作指那
《编译原理》实验指导书 实验目的和内容 编译原理实验的目的是使学生将编译理论运用到实际当中，实现一个简单语言集的词法、语法和语义分析程序，验证实际编译系统的实现方法，并加深对编译技术的认识。 实验内容共需实现编译器的词法、语法和语义分析程序三个组成部分。要求学生必须完成每个实验的基本题目要求，有余力的同学可尝试实验的扩展要求部分。 实验报告 要求每人针对所完成的实验内容上交一份实验报告，其中主要包括三方面内容：1、实验设计：实验采用的实现方法和依据（如描述语言的文法及其机内表示，词分析 的单词分类码表、状态转换图或状态矩阵等，语法分析中用到的分析表或优先矩阵等，语法制导翻译中文法的拆分和语义动作的设计编写等）；具体的设计结果（应包括整体设计思想和实现算法，程序结构的描述，各部分主要功能的说明，法以及所用数据结构的介绍等）。 2、程序代码：实验实现的源程序清单，要求符合一般的程序书写风格，有详细的注释。 3、实验结果分析：自行编写若干源程序作为测试用例，对所生成的编译程序进行测试 （编译程序的输入与输出以文件的形式给出）；运行结果分析（至少包括一个正确和一个错误单词或语句的运行结果）；以及改进设想等。 注意事项 1、电子版实验报告和源程序在最后一次机时后的一周内上交。（每个同学上交一个压 缩文件，其命名格式为“学号_姓名.rar”，内含实验报告和一个命名为“源程序” 的文件夹。注意提交的源程序应是经过调试、测试成功的较为通用的程序，并应有相应的注释、运行环境和使用方法简介。） 2、不接受不完整的实验报告和没有说明注释的源程序，或者说明与程序、运行结果不 符合的作业。 特别鼓励：扩展题目 1、为亲身经历一个小型编译器的开发全过程，触摸一下与实际编译器开发相关的工作， 大家可以自由组成3人左右的小组，推举组长，模拟一个团队分工协作开发大型软件的实战环境，融入软件工程的思想规范和一般理论方法，初步体验从系统分析设计、编码测试到交付维护的一个完整编译器软件的开发过程。要求组长为每个小组成员分配主要负责的任务，完成相应的分析设计员、程序员和测试员等角色的工作，并以小组为单位提交一份实验报告和源程序，在报告封面上写明每个同学主要完成和负责的部分。 2、以组为单位完成的实验内容至少必须整合词法、语法和语义三个部分的实验，对于 选定的适当规模的文法（如C语言的一个大小适宜的子集），进行系统的总体设计、功能分析、编码测试等工作。完成一个从对源程序的词法分析开始，到中间代码生成的完整的编译器前端的开发，使所涉及到的编译系统的各个组成模块有机地衔接在一起，提交一份完整的实验报告和源程序，并将以下几个方面描述清楚：
词法分析 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 3.1 主程序示意图： 扫描子程序主要部分流程图 其他
词法分析程序的C语言程序源代码： // 词法分析函数: void scan() // 数据传递: 形参fp接收指向文本文件头的文件指针； // 全局变量buffer与line对应保存源文件字符及其行号，char_num保存字符总数。 void scan() { char ch; int flag,j=0,i=-1; while(!feof(fp1)) { ch=fgetc(fp1); flag=judge(ch); printf("%c",ch);//显示打开的文件 if(flag==1||flag==2||flag==3) {i++;buffer[i]=ch;line[i]=row;} else if(flag==4) {i++;buffer[i]='?';line[i]=row;} else if(flag==5) {i++;buffer[i]='~';row++;} else if(flag==7) continue; else cout<<"\n请注意，第"< 实验二语法分析 一、实验目的： 设计MiniC的上下文无关文法，利用JavaCC生成调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、语法分析器: 按照MiniC语言的语法规则检查词法分析输出的记号流是否符合这些规则，并根据这些规则所体现出的语言中的各种语法结构的层次性。把规则写入到JavaCC的.jjt文件中，可以生成树状的层次结构。 三、JavaCC: 在JavaCC的文法规范文件中，不仅可以描述语言的语法规范，而且可以描述词法规范，本次实习中，利用JavaCC以MiniC语言构造一个不含语义分析的编译器前端，包括词法分析、语法分析，并要考虑语法分析中的错误恢复问题。通过使用JavaCC, 可以体会LL(k)文法的编写特点，掌握编写JavaCC文法规范文件的方法。 内容：利用JavaCC生成一个MiniC的语法分析器； 要求： 1.用流的形式读入要分析的C语言程序，或者通过命令行输入源程序。 2.具有错误检查的能力，如果有能力可以输出错误所在的行号，并简单提示 3.如果输入的源程序符合MiniC的语法规范，输出该程序的层次结构的语法树本次实习仅完成以下语法范畴的语法分析： 1. 写出一个源程序中仅包含if…else, else语句的语法分析。要求能分析其自身 嵌套. 其他语句可简化处理 2. 写出一个源程序中仅包含for语句的语法分析。要求能分析其自身嵌套， 其他语句可简化处理 3. 写出一个源程序中仅包含while语句的语法分析。要求能分析其自身嵌套。 其他语句可简化处理 4. 写出一个源程序中包含上面的12或者13或者23或者123语句的语法分析。 要求能分析除其自身嵌套外，还包括相互嵌套。其他语句可简化处理 具体实施步骤如下： 1.把MiniC转换为文法如下 <程序〉→ main()〈语句块〉 〈语句块〉→{〈语句串〉} 编译原理： 编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。编译原理是计算机专业设置的一门重要的专业课程。编译原理课程是计算机相关专业学生的必修课程和高等学校培养计算机专业人才的基础及核心课程，同时也是计算机专业课程中最难及最挑战学习能力的课程之一。编译原理课程内容主要是原理性质，高度抽象。 基本概念： 编译原理即是对高级程序语言进行翻译的一门科学技术, 我们都知道计算机程序由程序语言编写而成, 在早期计算机程序语言发展较为缓慢, 因为计算机存储的数据和执行的程序都是由0、1代码组合而成的, 那么在早期程序员编写计算机程序时必须十分了解计算机的底层指令代码通过将这些微程序指令组合排列从而完成一个特定功能的程序, 这就对程序员的要求非常高了。人们一直在研究如何如何高效的开发计算机程序, 使编程的门槛降低。 编译器： C语言编译器是一种现代化的设备, 其需要借助计算机编译程序, C语言编译器的设计是一项专业性比较强的工作, 设计人员需要考虑计算机程序繁琐的设计流程, 还要考虑计算机用户的需求。计算机的种类在不断增加, 所以, 在对C语言编译器进行设计时, 一定要增加其适用性。C语言具有较强的处理能力, 其属于结构化语言, 而且在 计算机系统维护中应用比较多, C语言具有高效率的优点, 在其不同类型的计算机中应用比较多。 C语言编译器前端设计 编译过程一般是在计算机系统中实现的, 是将源代码转化为计算机通用语言的过程。编译器中包含入口点的地址、名称以及机器代码。编译器是计算机程序中应用比较多的工具, 在对编译器进行前端设计时, 一定要充分考虑影响因素, 还要对词法、语法、语义进行分析。 1 词法分析 词法分析是编译器前端设计的基础阶段, 在这一阶段, 编译器会根据设定的语法规则, 对源程序进行标记, 在标记的过程中, 每一处记号都代表着一类单词, 在做记号的过程中, 主要有标识符、关键字、特殊符号等类型, 编译器中包含词法分析器、输入源程序、输出识别记号符, 利用这些功能可以将字号转化为熟悉的单词。 2 语法分析 语法分析是指利用设定的语法规则, 对记号中的结构进行标识, 这包括句子、短语等方式, 在标识的过程中, 可以形成特殊的结构语法树。语法分析对编译器功能的发挥有着重要影响, 在设计的过程中, 一定要保证标识的准确性。 3 语义分析 语义分析也需要借助语法规则, 在对语法单元的静态语义进行检查时, 要保证语法规则设定的准确性。在对词法或者语法进行转化 《编译原理》课程实验指导书 课程编号： 课程名称：编译原理/Compiler Principles 实验总学时数： 8 适用专业：计算机科学与技术、软件工程 承担实验室：计算机学院计算机科学系中心实验室、计算机技术系中心实验室 一、实验教学的目的与要求 上机实习是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实习题中的问题比平时的练习题要复杂，也更接近实际。编译原理这门课程安排的2次上机实验都属于一种设计类型的实验，每个实验的训练重点在于基本的编译技术和方法，而不强调面面俱到；实验的目的是旨在使学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容；培养学生编制算法的能力和编程解决实际问题的动手能力。 要求学生在上机前应认真做好各种准备工作，熟悉机器的操作系统和语言的集成环境，独立完成算法设计和程序代码的编写；上机时应随带有关的编译原理教材或参考书；要学会程序调试与纠错。 每次实验后要交实验报告，实验报告的内容应包括： （1）实验题目、班级、学号、姓名、完成日期； （2）简要的需求分析与概要设计； （3）详细的算法描述； （4）源程序清单； （5）给出软件的测试方法和测试结果； （6）实验的评价、收获与体会。 开发工具： （1）DOS环境下使用Turbo C； （2）Windows环境下使用Visual C++ 。 考核： 实验成绩占编译原理课程结业成绩的10%。 三、单项实验的内容和要求： 要求每个实验保证每个学生一台微机。 实验一（4学时）：单词的词法分析程序设计。 （一）目的与要求 1．目的 通过设计、编制、调试一个具体的词法分析程序，加深对词法分析原理的理解，并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 编译原理实验报告 实验名称：编写语法分析分析器实验类型： 指导教师： 专业班级： 学号： 电子邮件： 实验地点： 实验成绩： 一、实验目的 通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。 1、选择最有代表性的语法分析方法，如LL(1) 语法分析程序、算符优先分析程序和LR分析分析程序，至少选一题。 2、选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。 二、实验过程 编写算符优先分析器。要求： （a）根据算符优先分析算法，编写一个分析对象的语法分析程序。读者可根据自己的能力选择以下三项(由易到难)之一作为分析算法中的输入： Ⅰ：通过构造算符优先关系表，设计编制并调试一个算法优先分析程序Ⅱ：输入FIRSTVT，LASTVT集合，由程序自动生成该文法的算符优先关系矩阵。 Ⅲ：输入已知文法，由程序自动生成该文法的算符优先关系矩阵。（b）程序具有通用性，即所编制的语法分析程序能够使用于不同文法以及各种输入单词串，并能判断该文法是否为算符文法和算符优先文法。 （c）有运行实例。对于输入的一个文法和一个单词串，所编制的语法分析程序应能正确地判断，此单词串是否为该文法的句子，并要求输出分析过程。 三、实验结果 算符优先分析器： 测试数据：E->E+T|T T->T*F|F F->(E)|i 实验结果：(输入串为i+i*i+i) 四、讨论与分析 自下而上分析技术－算符优先分析法： 算符文法：一个上下无关文法G，如果没有且没有P→..QR...(P ,Q ,R属于非终结符)，则G是一个算符文法。 FIRSTVT集构造 1、若有产生式P →a...或P →Qa...，则a∈FIRSTVT(P)。 2、若有产生式P→...，则FIRSTVT(R)包含在FIRSTVT(P)中。由优先性低于的定义和firstVT集合的定义可以得出：若存在某个产生式：…P…，则对所有：b∈firstVT(P)都有：a≦b。 构造优先关系表： 1、如果每个非终结符的FIRSTVT和LASTVT集均已知,则可构造优先关系表。 2、若产生式右部有...aP...的形式，则对于每个b∈FIRSTVT(P)都有 编译原理 实 验 指 导 书 前言 编译原理是计算机科学与技术、软件工程等专业的主干课和必修课，由于这门课程相对抽象且内容较复杂，一直是比较难学的一门课程。在编译原理的学习过程中，实验非常重要，只有通过上机实验，才能使学生对比较抽象的课程内容产生一个具体的感性认识。 本书实验环境主要为C环境及一个词法分析器自动生成工具FLEX和一个语法分析器自动生成工具BISON。书中给出的参考源程序也是C源程序，但由于实验者熟悉精通的语言工具不尽相同，因而强求采用统一的编程语言编程是不现实的。实验者在掌握了编译程序各个阶段的功能和原理之后，不难借助使用其他自己熟悉的语言实现相关功能。 实验者在实验过程中应该侧重写出自己在算法分析、设计思路、实现功能或程序代码等方面的特色，写出设计和实现过程中遭遇到的难点和解决办法，可以不拘泥于实验指导给出的参考性设计思路，尽可能在深度和广度上加以拓展。只有这种各具特色的实验报告，才将更有利于体现实验者在创新思维和动手能力上的差异。 通过这些实验，能使学生对这些部份的工作机理有一个详细的了解，达到“知其然，且知其所以然”的目的。并可在C环境下对自动生成工具生成的词法、语法分析器进行编译调试。 由于手工生成词法和语法分析器的工作量太大，在实际中常用自动生成工具来完成之。这些工具中最著名的当属贝尔实验室的词法分析器生成工具LEX和语法分析器生成工具YACC。它们现已成为UNIX的标准应用程序同UNIX一起发行。与此同时GNU推出与LEX完全兼容的FLEX，与YACC完全兼容的BISON。这两个程序都在Internet上以源代码的形式免费发行，所以很容易在其它操作系统下重新编译安装。我们实验采用的就是for dos的FLEX和BISON。本书有关的编译工具及其源程序例子，可到BISON的网站上下载。关于FLEX和BISON的用法简介，参见附录，如需更详细的介绍，请参阅编译工具中帮助文件。 集美大学计算机工程学院实验报告 课程名称：编译原理班级： 指导教师：： 实验项目编号：实验一学号： 实验项目名称：词法分析器的设计实验成绩： 一、实验目的 通过设计编制调试一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 二、实验容 编写一个词法分析器，从输入的源程序（编写的语言为C语言的一个子集）中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示） 三、实验要求 1、词法分析器的功能和输出格式 词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符 2 别单词的类型，将标识符和常量分别插入到相应的符号表中，增加错误处理等。 3、编程语言不限。 四、实验设计方案 1、数据字典 本实验用到的数据字典如下表所示： 3、实验程序 #include 5. 目标代码生成 本章实验为实验四，是最后一次实验，其任务是在词法分析、语法分析、语义分析和中间代码生成程序的基础上，将C 源代码翻译为MIPS32指令序列（可以包含伪指令），并在SPIM Simulator上运行。当你完成实验四之后，你就拥有了一个自己独立编写、可以实际运行的编译器。 选择MIPS作为目标体系结构是因为它属于RISC范畴，与x86等体系结构相比形式简单便于我们处理。如果你对于MIPS体系结构或汇编语言不熟悉并不要紧，我们会提供详细的参考资料。 需要注意的是，由于本次实验的代码会与之前实验中你已经写好的代码进行对接，因此保持一个良好的代码风格、系统地设计代码结构和各模块之间的接口对于整个实验来讲相当重要。 5.1 实验内容 5.1.1 实验要求 为了完成实验四，我们建议你首先下载并安装SPIM Simulator用于对生成的目标代码进行检查和调试，SPIM Simulator的官方下载地址为：https://www.doczj.com/doc/3d12621655.html,/~larus/spim.html。这是由原Wisconsin-Madison的Jame Larus教授（现在在微软）领导编写的一个功能强大的MIPS32汇编语言的汇编器和模拟器，其最新的图形界面版本QtSPIM由于使用了Qt组件因而可以在各大操作系统平台如Windows、Linux、Mac等上运行，推荐安装。我们会在后面介绍有关SPIM Simulator的使用方法。 你需要做的就是将实验三中得到的中间代码经过与具体体系结构相关的指令选择、寄存器选择以及栈管理之后，转换为MIPS32汇编代码。我们要求你的程序能输出正确的汇编代码。“正确”是指该汇编代码在SPIM Simulator（命令行或Qt版本均可）上运行结果正确。因此，以下几个方面不属于检查范围： 1)寄存器的使用与指派可以不必遵循MIPS32的约定。只要不影响在SPIM Simulator中的 正常运行，你可以随意分配MIPS体系结构中的32个通用寄存器，而不必在意哪些寄存器应该存放参数、哪些存放返回值、哪些由调用者负责保存、哪些由被调用者负责保存，等等。 2)栈的管理（包括栈帧中的内容及存放顺序）也不必遵循MIPS32的约定。你甚至可以使 用栈以外的方式对过程调用间各种数据的传递进行管理，前提是你输出的目标代码（即MIPS32汇编代码）能运行正确。 实验二语法分析器 一、实验目的 通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培养适应社会多方面需要的能力。 二、实验内容 ◆根据某一文法编制调试LL （1 ）分析程序，以便对任意输入的符号串 进行分析。 ◆构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分 析程序。 ◆分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号 以及LL（1）分析表，对输入符号串自上而下的分析过程。 三、LL（1）分析法实验设计思想及算法 ◆模块结构： （1）定义部分：定义常量、变量、数据结构。 （2）初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）； （3）控制部分：从键盘输入一个表达式符号串； （4）利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。 四、实验要求 1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。 2、如果遇到错误的表达式，应输出错误提示信息。 3、对下列文法，用LL（1）分析法对任意输入的符号串进行分析：（1）E->TG （2）G->+TG|—TG （3）G->ε （4）T->FS （5）S->*FS|/FS （6）S->ε （7）F->(E) （8）F->i 输出的格式如下： 五、实验源程序 LL1.java import java.awt.*; import java.awt.event.*; import javax.swing.*; import javax.swing.table.DefaultTableModel; import java.sql.*; import java.util.Vector; public class LL1 extends JFrame implements ActionListener { /** * */ private static final long serialVersionUID = 1L; JTextField tf1; JTextField tf2; JLabel l; JButton b0; JPanel p1,p2,p3; JTextArea t1,t2,t3; JButton b1,b2,b3; 实验时间：200 年月日实验小组：第组 组长：组员： 组员： 指导教师签名：实验情况评定： 实验二编写一个简单的FLEX脚本并编译运行 实验目的: 通过实验掌握下列知识: 1、进一步熟悉Visual C++的基本操作； 2、进一步熟悉Visual C++ 6.0里Win32 Console Application工程的建立和相应的编程知识； 3、了解如何建立和编译Flex脚本文件； 5、了解如何通过Visual C++ 6.0编译Flex程序； 内容及步骤: 一、输入一个Flex脚本，编译并运行: 1、按实验一介绍的方法，建立一个Win32 Console Application并选择“An empty project”； 2、从选课系统里下载“Flex源代码及编译系统”； 3、将下载的RAR文件解压到D盘的某个文件夹，然后将解压的所有文件复制到D盘的文件夹“D:\Flex”里； 4、打开“附件->记事本”，输入以下代码，并以文件名“DEMO1.L”保存到文件夹“D:\Flex”里： %{ #include return 0; } 5、点击桌面左下角并运行“开始->程序->附件->命令提示符”； 6、在DOS窗口中输入命令(1)D: (2)cd \Flex(与你存储Flex文件的文件夹名有关) (3)flex DEMO1.L； 7、将D:Flex文件夹下的文件“emalloc.c”、“hash.c”、“LEXYY.C”、“libyywra.c”、“hash.h”、“types.h”和“DEMO1.L”全部复制到你的工程文件夹下； 8、运行VC并调入你建立的工程文件，然后点击左边的FileView，分别用鼠标右键点击Source Files和Header Files，并选择“Add Files to Folder”添加7步复制的c文件和h文件： 图1 9、在第8步添加的文件如下： 图2 10、点击“编译”菜单里的“重建全部”,或者点工具栏上的“!”运行； 注：Flex程序在DOS窗口里运行，词法分析程序是通过键盘输入文本信息，文本信息输入结束时，先按回车，再按Ctrl+Z即可结束文本输入； 实验报告要求: 1、记录错误信息、错误数量和警告数量，以及运行结果； 2、记录Flex脚本文件；编译原理实验二
编译原理知识点
编译原理实验指导书2010
编译原理-语法分析-算符优先文法分析器
编译原理实验指导书(图)
编译原理实验-词法分析器的设计说明
编译原理实验：目标代码的生成
编译原理 语法分析器 (java完美运行版)
编译原理实验2-编写一个简单的FLEX脚本并编译运行
相关主题
文本预览