◇第二章PL/0编译程序的实现
【课前思考】
复习第1章介绍的一个高级程序设计语言编译程序的功能和实现的步骤。编译程序就是一个语言的翻译程序，通常是把一种高级程序设计语言（称源语言）书写的程序翻译成另一种等价功能语言（称目标语言）的程序。换句话说，编译是指把一种用源语言表示的算法转换到另一种等价的用目标语言表示的算法。编译程序实现的必要步骤有词法、语法、语义分析和代码生成。此外必需有符号表管理程序和出错处理程序。本章介绍的PL/0编译程序的实现是用PASCAL语言书写的。
【学习目标】
本章目的：以PL/0语言编译程序为实例,学习编译程序实现的基本步骤和相关技术，对编译程序的构造和实现得到一些感性认识和建立起整体概念，为后面的原理学习打下基础。
◇了解并掌握用语法图和扩充的巴科斯-瑙尔范式(EBNF)对PL/0语言的形式描述。
◇了解并掌握PL/0语言编译程序构造和实现的基本技术和步骤。
◇了解并掌握PL/0语言编译程序的目标程序在运行时数据空间的组织管理。
【学习指南】
◇要求读者阅读PL/0语言编译程序文本，了解一个编译程序构造的必要步骤和实现技术。一个编译程序的实现比较复杂，读懂一个典型的程序从设计思想到实现技术也有一定难度，特别是入门开始需要耐心。一但读懂，不仅了解编译程序的实现方法和技术，还可学到许多编程技巧和好的编程风格。
◇阅读PL/0语言编译程序文本时，应从整体结构开始逐步细化，弄清楚每个过程的功能和实现方法及过程之间的相互关系。
◇建议用一个PL/0源程序的例子为导引作为阅读PL/0语言编译程序文本的入门，然后再逐步全面读懂。
◇通过对PL/0语言编译程序某些指定功能的扩充，加深对编译程序构造步骤和实现技术的理解，并能在实践中应用。
【难重点】
重点：
◇弄清源语言(PL/0)目标语言(类pcode)实现语言（pascal) 这3个语言之间的关系和作用。
◇掌握用语法图和扩充的巴科斯-瑙尔范式(EBNF)对一个高级程序设计语言的形式描述。
◇了解PL/0语言编译程序的语法分析技术采用的是自顶向下递归子程序法。
◇掌握PL/0语言编译程序的整体结构和实现步骤，并弄清词法分析、语法分析、语义分析、代码生成及符号表管理每个过程的功能和相互联系。
◇掌握PL/0语言编译程序的目标程序在运行时采用栈式动态存储管理的实现技术。
难点：
◇符号表管理起着编译期间和目标程序运行时信息联系的纽带，符号表的建立并不困难，但信息之间的关系往往需要反复学习才能理解。
【知识结构】
为了使读者在系统地学习本教材以下各章节之前，对编译程序的构造得到一些感性认识和初步了解，本章推荐了世界著名计算机科学家N.Wirth编写的"PL/0语言的编译程序"，并对其实现过程作了概括的分析说明，作为读者阅读PL/0语言编译程序文本的提示。对PL/0语言文法的表示只给出语法图和扩充的巴科斯-瑙尔范式(EBNF)的描述形式，不作文法理论上的讨论。由于PL/0语言功能简单、结构清晰、可读性强，而又具备了一般高级语言的必须部分，因而PL/0语言的编译程序能充分体现一个高级语言编译程序实现的基本技术和步骤。因此，"PL/0语言编译程序"是一个非常合适的小型编译程序的教学模型。所以，阅读"PL/0语言编译程序"文本后，可帮助读者对编译程序的实现建立起整体概念。
2.1 PL/0语言和类pcode的描述
在上一章中已介绍过，编译程序的功能是把一种高级程序设计语言的程序翻译成某种等价功能的低级语言的程序。PL/0语言的编译程序就是要把PL/0语言程序翻译成为一种称为类pcode的假想的栈式计算机汇编语言程序。这种汇编语言与机器无关，若需要在某一机器上实现PL/0语言程序，只需用机器上配置的任何语言对类pcode语言程序进行解释执行。那么PL/0语言是什么样的语言？类pcode语言又是什么样的结构？它们之间是如何映射的？只有在明确了这些问题之后，才能确定如何构造这个翻译程序。
就像一个翻译要把汉语翻译成英语，必须对汉语和英语的单词、语法结构都很精通，才有可能翻译得准确无误。另外，编译程序既然是为了完成这种功能的一个程序，就存在用什么语言来编写这个程序的问题。这些问题在本节将逐步介绍。
现对PL/0语言编译程序的功能用“T”型图（“T”型图将在第13章详细介绍）表示，并用图形概括描述PL/0编译程序的结构框架。
PL/0编译程序的功能
本节将用语法图和扩充的巴科斯-瑙尔范式（BACKUS-NAUR FORM）(EBNF)两种形式给出PL/0语言的语法描述。对类pcode代码给出指令的结构形式和含义。
巴科斯-瑙尔范式（BACKUS-NAUR FORM）是根据美国的John W.Backus与丹麦的Peter Naur命名的。
2.1.1 PL/0语言的语法描述图
用语法图描述语法规则的优点是直观、易读。在图2.1的语法图中用椭圆和圆圈中的英文字表示终结符，用长方形内的中文字表示非终结符。所谓终结符，是构成语言文法的单词，是语法成分的最小单位，而每个非终结符也是一个语法成分。
但非终结符可由其它文法符号定义，终结符不能由其它文法符号定义。例如，程序是由非终结符'分程序'和终结符"."组成的串定义的。由于对某些非终结符可以递归定义，如图2.1(b)、2.1 (c)、2.1 (e)中：分程序、表达式和语句。第一个非终结符'程序'为文法的开始符号。
注意在书写语言程序时非终结符并不出现，程序是由终结符串构成。
图 2.1(a) 程序语法描述图
图 2.1(b) 分程序语法描述图
图2.1(c) 语句语法描述图
图 2.1(d) 条件语法描述图
图 2.1(e) 表达式语法描述图
图 2.1(f) 项语法描述图
图 2.1(g) 因子语法描述图
画语法图时要注意箭头方向和弧度，语法图中应该无直角，如图 2.1给出的PL/0语法描述图。沿语法图分析时不能走尖狐线。
2.1.2 PL/0语言文法的EBNF表示
EBNF表示的符号说明。
〈〉：用左右尖括号括起来的中文字表示语法构造成分，或称语法单位，为非终结符。
∷= ：该符号的左部由右部定义，可读作'定义为'。
| ：表示'或'，为左部可由多个右部定义。
{ } ：花括号表示其内的语法成分可以重复。在不加上下界时可重复0到任意次数，有上下界时为可重复次数的限制。
如：{*}表示*重复任意次，{*}38表示*重复3-8次。
[ ] ：方括号表示其内的成分为任选项。
( ) ：表示圆括号内的成分优先。
例：用EBNF描述<整数>文法的定义：
<整数>∷=[+|-]<数字>{<数字>}
<数字>∷=0|1|2|3|4|5|6|7|8|9
或更好的写法
<整数>∷=[+|-]<非零数字>{<数字>}|0
<非零数字>∷=1|2|3|4|5|6|7|8|9
<数字>∷=0|<非零数字>
PL/0语言文法的EBNF表示为：
〈程序〉∷=〈分程序〉．
〈分程序〉∷=[〈常量说明部分〉][〈变量说明部分〉][〈过程说明部分〉]〈语句〉〈常量说明部分〉∷=CONST〈常量定义〉{，〈常量定义〉}；
〈常量定义〉∷=〈标识符〉=〈无符号整数〉
〈无符号整数〉∷=〈数字〉{〈数字〉}
〈变量说明部分〉∷=V AR〈标识符〉{，〈标识符〉}；
〈标识符〉∷=〈字母〉{〈字母〉|〈数字〉}
〈过程说明部分〉∷=〈过程首部〉〈分程序〉{；〈过程说明部分〉}；
〈过程首部〉∷=PROCEDURE〈标识符〉；
〈语句〉∷=〈赋值语句〉|〈条件语句〉|〈当型循环语句〉|
〈过程调用语句〉|〈读语句〉|〈写语句〉|〈复合语句〉|〈空〉
〈赋值语句〉∷=〈标识符〉∶=〈表达式〉
〈复合语句〉∷=BEGIN〈语句〉{；〈语句〉}END
〈条件〉∷=〈表达式〉〈关系运算符〉〈表达式〉|ODD〈表达式〉
〈表达式〉∷=[+|-]〈项〉{〈加法运算符〉〈项〉}
〈项〉∷=〈因子〉{〈乘法运算符〉〈因子〉}
〈因子〉∷=〈标识符〉|〈无符号整数〉|'('〈表达式〉')'
〈加法运算符〉∷=+|-
〈乘法运算符〉∷=*|/
〈关系运算符〉∷=#|=|＜|＜=|＞|＞=
〈条件语句〉∷=IF〈条件〉THEN〈语句〉
〈过程调用语句〉∷=CALL〈标识符〉
〈当型循环语句〉∷=WHILE〈条件〉DO〈语句〉
〈读语句〉∷=READ'('〈标识符〉{，〈标识符〉}')'
〈写语句〉∷=WRITE'('〈表达式〉{，〈表达式〉}')'
〈字母〉∷=a|b|…|X|Y|Z
〈数字〉∷=0|1|2|…|8|9
用语法图描述语言的语法与EBNF描述相比较：
语法图描述：直观，易读，易写。
EBNF表示：形式化强，易机器识别。
无论用语法图或EBNF作为描述程序设计语言语法的工具，对描述的语法可以检查哪些符号序列是所给语言的合法程序，一个程序设计语言如C或JA VA，用户可用它写出成千上万个不同的程序，但C或JA VA 它们各自的语法只有一个，这就使得无穷的句子集可用有穷的文法（语法）描述。
练习：下面给出一个PL/0语言的程序，请学员对应PL/0语言的语法描述图与EBNF ，检查该程序的语法是否正确。
CONST A=10;
VAR B,C;
PROCEDURE P;
VAR D;
PROCEDURE Q;
VAR X;
BEGIN
READ(X);
D:=D* C +X; WRITE(D);
WHILE X#0 DO CALL P;
END;
BEGIN
READ(D, C);
CALL Q;
END;
BEGIN
CALL P;
END.
PL/0编译程序的使用限制
◇标识符的有效长度是10
◇数字最多为14位
◇过程最多可嵌套三层，可递归调用
◇标识符的作用域同PASCAL，内层可引用包围它的外层定义的标识符（如：变量名，过程名，常量名）
2.1.3 类pcode代码指令的结构
PL/0编译程序所产生的目标代码是一个假想栈式计算机的汇编语言，可称为类PCODE指令代码，它
其中f代表功能码，l表示层次差，也就是变量或过程被引用的分程序与说明该变量或过程的分程序之间的层次差。a的含意对不同的指令有所区别，对存取指令表示位移量，而对其它的指令则分别有不同的含义，见下面对每条指令的解释说明。
目标指令有8条：
①LIT：将常量值取到运行栈顶。a域为常数值。
②LOD：将变量放到栈顶。a域为变量在所说明层中的相对位置,l为调用层
与说明层的层差值。
③STO：将栈顶的内容送入某变量单元中。a,l域的含意同LOD指令。
④CAL：调用过程的指令。a为被调用过程的目标程序入口地址，l为层差。
⑤INT：为被调用的过程(或主程序)在运行栈中开辟数据区。a域为开辟的单元个数。
⑥JMP：无条件转移指令，a为转向地址。
⑦JPC：条件转移指令，当栈顶的布尔值为非真时，转向a域的地址，否则顺序执行。
⑧OPR：关系运算和算术运算指令。将栈顶和次栈顶的内容进行运算，结果存放在次栈顶，此外还可以是读写等特殊功能的指令，具体操作由a域值给出。（详见解释执行程序）。
类pcode代码指令的详细解释（指令功能表）
认识目标代码类pcode
目标代码类pcode是一种假想栈式计算机的汇编语言。
f 功能码
l 层次差（标识符引用层减去定义层）
一个PL/0程序与目标代码类pcode指令的映射例子
武汉科技大学计算机科学与技术学院 编译原理实验指导书
实验一词法分析器设计 【实验目的】 1．熟悉词法分析的基本原理，词法分析的过程以及词法分析中要注意的问题。 2．复习高级语言，进一步加强用高级语言来解决实际问题的能力。 3．通过完成词法分析程序，了解词法分析的过程。 【实验内容】 用C语言编写一个PL/0词法分析器，为语法语义分析提供单词，使之能把输入的字符串形式的源程序分割成一个个单词符号传递给语法语义分析，并把分析结果（基本字，运算符，标识符，常数以及界符）输出。 【实验要求】 1．要求绘出词法分析过程的流程图。 2．根据词法分析的目的以及内容，确定完成分析过程所需模块。 3．写出每个模块的源代码，并给出注释。 4．整理程序清单及所得结果。 【说明】 运行成功以后，检查程序，并将运行结果截图打印粘贴到实验报告上。 辅助库函数scanerLib设计以及使用说明： 下面内容给出了一个辅助库函数的接口说明以及具体实现。 接口设计 //字符类 class Token { TokenType type; String str; Int line; } //词法分析结果输出操作类 class TokenWriter { ArrayList tokens; //用来记录所识别出来的token TokenWriter(); //构造函数指定输入文件名，创建文件输出流 V oid Add(Token); //将词法分析器中分析得到的Token添加到tokens中 WriteXML(); //将tokens写出到目标文件.xml中 } //词法分析操作词法分析生成文件接口<暂时不需要对该类的操作；下一步做语法分析的时候使用> class TokenReader
/*PL/0编译程序（C语言版） *编译和运行环境： *Visual C++6.0 *WinXP/7 *使用方法： *运行后输入PL/0源程序文件名 *回答是否将虚拟机代码写入文件 *回答是否将符号表写入文件 *执行成功会产生四个文件（词法分析结果.txt符号表.txt虚拟代码.txt源程序和地址.txt） */ #include
编译原理实验报告实验名称：实验一编写词法分析程序 实验类型：验证型实验 指导教师：何中胜 专业班级：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.实践部分
编译过程的六个阶段：词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成 解释程序：把某种语言的源程序转换成等价的另一种语言程序——目标语言程序，然后再执行目标程序。 解释方式是接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执 行结果，然后再接受下一句。 编译程序：就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序)。 解释程序和编译程序的根本区别：是否生成目标代码 句子的二义性（这里的二义性是指语法结构上的。）:文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。 文法的二义性:一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。 LL(1)的含义：(LL(1)文法是无二义的； LL(1)文法不含左递归) 第1个L：从左到右扫描输入串第2个L：生成的是最左推导 1：向右看1个输入符号便可决定选择哪个产生式 某些非LL(1)文法到LL(1)文法的等价变换: 1. 提取公因子 2. 消除左递归 文法符号的属性:单词的含义，即与文法符号相关的一些信息。如，类型、值、存储地址等。 一个属性文法(attribute grammar)是一个三元组A=(G, V, F) G：上下文无关文法。 V：属性的有穷集。每个属性与文法的一个终结符或非终结符相连。属性与变量一样，可以进行计算和传递。 F：关于属性的断言或谓词(一组属性的计算规则)的有穷集。断言或语义规则与一个产生式相联，只引用该产生式左端或右端的终结符或非终结符相联的属性。 综合属性:若产生式左部的单非终结符A的属性值由右部各非终结符的属性值决定,则A的属性称为综合属继承属性:若产生式右部符号B的属性值是根据左部非终结符的属性值或者右部其它符号的属性值决定的,则B的属性为继承属性。 (1)非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性。 (2) 终结符只有综合属性，没有继承属性，它们由词法程序提供。 在计算时：综合属性沿属性语法树向上传递；继承属性沿属性语法树向下传递。 语法制导翻译：是指在语法分析过程中，完成附加在所使用的产生式上的语义规则描述的动作。 语法制导翻译实现：对单词符号串进行语法分析，构造语法分析树，然后根据需要构造属性依赖图，遍历语法树并在语法树的各结点处按语义规则进行计算。 中间代码（中间语言） 1、是复杂性介于源程序语言和机器语言的一种表示形式。 2、一般，快速编译程序直接生成目标代码。 3、为了使编译程序结构在逻辑上更为简单明确，常采用中间代码，这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理，并且可以在中间代码一级进行优化工作，使得代码优化比较容易实现。 何谓中间代码：源程序的一种内部表示，不依赖目标机的结构，易于代码的机械生成。 为何要转换成中间代码:(1)逻辑结构清楚；利于不同目标机上实现同一种语言。 (2)便于移植，便于修改，便于进行与机器无关的优化。 中间代码的几种形式：逆波兰记号，三元式和树形表示，四元式 符号表的一般形式：一张符号表的的组成包括两项，即名字栏和信息栏。 信息栏包含许多子栏和标志位，用来记录相应名字和种种不同属性，名字栏也称主栏。主栏的内容称为关键字（key word）。 符号表的功能：（1）收集符号属性(2) 上下文语义的合法性检查的依据：检查标识符属性在上下文中的一致性和合法性。(3)作为目标代码生成阶段地址分配的依据
《编译原理》 实验指导书 太原理工大学计算机与软件学院 2017 年 3 月
《编译原理》实验 适用专业：计算机实验类别：专业实验 实验时数：8学时 一、实验课程的性质、目的和任务 1．培养学生初步掌握编译原理实验的技能。 2．验证所学理论、巩固所学知识并加深理解。 3．对学生进行实验研究的基本训练。 二、实验课程的内容、要求及学时分配 实验一、无符号数的词法分析程序（4学时） 内容：掌握词法分析的基本思想，并用高级语言编写无符号数的词法分析程序。 要求：从键盘上输入一串字符（包括字母、数字等），最后以“；”结束，编写程序识别出其中的无符号数。 无符号数文法规则可定义如下： <无符号数>→<无符号实数>│<无符号整数> <无符号实数>→<无符号整数>.<数字串>[E<比例因子>]│ <无符号整数>E<比例因子> <比例因子>→<有符号整数> <有符号整数>→[+│-]<无符号整数> <无符号整数>→<数字串> <数字串>→<数字>{<数字>} <数字>→0 1 2 3 (9) 读无符号数的程序流程图见下图
实验二、逆波兰式生成程序（4学时） 内容：掌握语法分析的基本思想，并用高级语言编写逆波兰式生成程序； 要求：利用逆波兰式生成算法编写程序，将从键盘上输入的算术表达式（中缀表达式）转化成逆波兰式。 逆波兰表达式的生成过程涉及到运算符的优先级，下表中列出几个常用运算 符的优先关系。 常用运算符优先关系矩阵 如上表所示的优先关系矩阵表示了+，-，*，/，↑，（，）等七种运算符之间的相互优先关系。“＞、＜、＝”三种符号分别代表“大于”、“小于”、“相等”三种优先关系。左边的“＝”与右边的“（”之间没有优先关系存在，所以表中为空白。 逆波兰表达式生成算法的关键在于比较当前运算符与栈顶运算符的优先关系，若当前运算符的优先级高于栈顶运算符，则当前运算符入栈，若当前运算符的优先级低于栈顶运算符，则栈顶运算符退栈。 下面给出了逆波兰表达式生成算法的流程图。（为了便于比较相邻运算符的优先级，需要设立一个工作栈，用来存放暂时不能处理的运算符，所以又称运算符栈）。
SAMPLE语言定义 一、字符集定义 1．<字符集> →<字母>│<数字>│<单界符> 2．<字母> →A│B│…│Z│a│b│…│z 3．<数字> →0│1│2│…│9 4．<单界符> →+│-│*│/│=│<│>│(│)│[│]│:│. │; │, │' 二、单词集定义 5．<单词集> →<保留字>│<双界符>│<标识符>│<常数>│<单界符> 6．<保留字> →and│array│begin│bool│call│case│char│constant│dim│do│else│end│false│for│if│input│integer│not│of│or│output│procedure│ program│read│real│repeat│set│stop│then│to│true│until│var│while│ write 7．<双界符> →<>│<=│>=│:= │/*│*/│.. 8．<标识符> →<字母>│<标识符> <数字>│<标识符> <字母> 9．<常数> →<整数>│<布尔常数>│<字符常数> 10．<整数> →<数字>│<整数> <数字> 11．<布尔常数> →true│false 12．<字符常数> →' 除{'} 外的任意字符串' 三、数据类型定义 13．<类型> →integer│bool│char 四、表达式定义 14．<表达式> →<算术表达式>│<布尔表达式>│<字符表达式> 15．<算术表达式> →<算术表达式> + <项>│<算术表达式> - <项>│<项> 16．<项> →<项> * <因子>│<项> / <因子>│<因子> 17．<因子> →<算术量>│- <因子> 18．<算术量> →<整数>│<标识符>│（<算术表达式> ） 19．<布尔表达式> →<布尔表达式> or <布尔项>│<布尔项> 20．<布尔项> →<布尔项> and <布因子>│<布因子> 21．<布因子> →<布尔量>│not <布因子> 22．<布尔量> →<布尔常量>│<标识符>│（<布尔表达式> ）│ <标识符> <关系符> <标识符>│<算术表达式> <关系符> <算术表达式> 23．<关系符> →<│<>│<=│>=│>│= 24．<字符表达式> →<字符常数>│<标识符> 五、语句定义 25．<语句> →<赋值句>│
编译程序实验指导书解讲． 编译程序实验指导书 实验目的：用C语言对一个C语言的子集编制一个一遍扫描的编译程序，以加深对编译原理的理解，掌握编译程序的实现方法和技术。 1．词法分析 1.1 实验目的 设计、编制并测试一个词法分析程序，加深对词法分析原理的理解。 1.2 实验要求 1.2.1 待分析的C语言子集的词法 1. 关键字
main if else int char for while 所有的关键字都是小写。 2．专用符号 = + - * / < <= > >= == != ; : , { } [ ] ( ) 3．其他标记ID和NUM 通过以下正规式定义其他标记： →letter(letter|digit) *ID →digit digit *NUM letter→a|…|z|A|…|Z digit→0|…|9… 4．空格由空白、制表符和换行符组成 空格一般用来分隔ID、NUM、专用符号和关键字，词法分析阶段通常被忽略。 1.2.2 各种单词符号对应的种别码 表1 各种单词符号的种别码 单词符号种别码单词符号种别码单词符号种别码 main 1 = 21 , 32 int 2 + 22 : 33 char 3 - 23 ; 34 if 4 * 24 > 35 else 5 / 25 < 36 for 6 ( 26 >= 37 while 7 ) 27 <= 38 ID 10 [ 28 == 39 MUN 20 ] 29 != 40 { 30 ‘\0' 1000 } 31 ERROR -1 1.2.3 词法分析程序的功能 输入：所给文法的源程序字符串。 输出：二元组（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,))
课程设计报告 ( 2013-- 2014年度第1学期) 名称：编译技术课程设计B 题目：简单编译程序的设计与实现院系：计算机系 班级：XXX 学号：XXX 学生姓名：XXX 指导教师：XXX 设计周数：XXX 成绩： 日期：XX 年XX 月
实验一．词法分析器的设计与实现 一、课程设计(综合实验)的目的与要求 1.1 词法分析器设计的实验目的 本实验是为计算机科学与技术专业的学生在学习《编译技术》课程后，为加深对课堂教学内容的理解，培养解决实际问题能力而设置的实践环节。通过这个实验，使学生应用编译程序设计的原理和技术设计出词法分析器，了解扫描器的组成结构，不同种类单词的识别方法。能使得学生在设计和调试编译程序的能力方面有所提高。为将来设计、分析编译程序打下良好的基础。 1.2 词法分析器设计的实验要求 设计一个扫描器，该扫描器是一个子程序，其输入是源程序字符串，每调用一次识别并输出一个单词符号。为了避免超前搜索，提高运行效率，简化扫描器的设计，假设该程序设计语言中，基本字（也称关键词）不能做一般标识符用，如果基本字、标识符和常数之间没有确定的运算符或界符作间隔，则用空白作间隔。 单词符号及其内部表示如表1-1所示，单词符号中标识符由一个字母后跟多个字母、数字组成，常数由多个十进制数字组成。单词符号的内部表示，即单词的输出形式为二元式：（种别编码,单词的属性值）。 表1-1 单词符号及其内部表示
二、设计（实验）正文 1.词法分析器流程图 2.词法分析器设计程序代码 // first.cpp : 定义控制台应用程序的入口点。// #include"stdafx.h" #include
一填空题 1．编译程序首先要识别出源程序中每个，然后再分析每个并翻译 其意义。 单词，句子 2．编译器常用的语法分析方法有和两种。 自底向上，自顶向下 2．通常把编译过程分为分析与综合两大阶段。词法、语法和语义 分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程 序的综合。 前端，后端 4．程序设计语言的发展带来了日渐多变的
运行时存储管理方案，主要分为两大 类，即方案和分配方案。 静态存储分配，动态存储 5．对编译程序而言，输入数据是，输出结果是。 源程序，目标程序 6．文法G包括四个组成部分：一组终结符号，一组非终结符号，一组，以 及一个开始符号。 产生式 7．文法按产生式的形式分为四种类型，它们是：0型文法，又称短语文法；1型 文法，又称上下文有关文法；2型文法， 又称；3型文法，又称。上下文无关文法，正规文法
8．最右推导称为，由规范推导产生的句型称为规范句型。 规范推导 9．设G是一个文法，S是它的开始符号，如果S=>*α，则称α是一个。 仅由终结符号组成的句型是一 个。 句型，句子 10 对于一个文法G而言，如果L(G)中存在 某个句子对应两棵不同，那么该 文法就称为是二义的。 语法树 11．通常程序设计语言的单词符号分为五种：基本字、、常数、算符、界 限符。
标识符 12．在自底向上分析法中，LR分析法把“可归约串”定义为。 句柄 13．编译中常用的中间代码形式有逆波兰式、三元式、和四元式等。 树代码 14．对中间代码优化按涉及的范围分 为，和全局优化。 局部优化，循环优化 15．局部优化主要包括、利用公共子表达式和删除无用赋值等内容。 合并已知量 16．为了构造不带回溯的递归下降分析程
编译原理 实 验 指 导 书
前言 编译原理是计算机科学与技术、软件工程等专业的主干课和必修课，由于这门课程相对抽象且内容较复杂，一直是比较难学的一门课程。在编译原理的学习过程中，实验非常重要，只有通过上机实验，才能使学生对比较抽象的课程内容产生一个具体的感性认识。 本书实验环境主要为C环境及一个词法分析器自动生成工具FLEX和一个语法分析器自动生成工具BISON。书中给出的参考源程序也是C源程序，但由于实验者熟悉精通的语言工具不尽相同，因而强求采用统一的编程语言编程是不现实的。实验者在掌握了编译程序各个阶段的功能和原理之后，不难借助使用其他自己熟悉的语言实现相关功能。 实验者在实验过程中应该侧重写出自己在算法分析、设计思路、实现功能或程序代码等方面的特色，写出设计和实现过程中遭遇到的难点和解决办法，可以不拘泥于实验指导给出的参考性设计思路，尽可能在深度和广度上加以拓展。只有这种各具特色的实验报告，才将更有利于体现实验者在创新思维和动手能力上的差异。 通过这些实验，能使学生对这些部份的工作机理有一个详细的了解，达到“知其然，且知其所以然”的目的。并可在C环境下对自动生成工具生成的词法、语法分析器进行编译调试。 由于手工生成词法和语法分析器的工作量太大，在实际中常用自动生成工具来完成之。这些工具中最著名的当属贝尔实验室的词法分析器生成工具LEX和语法分析器生成工具YACC。它们现已成为UNIX的标准应用程序同UNIX一起发行。与此同时GNU推出与LEX完全兼容的FLEX，与YACC完全兼容的BISON。这两个程序都在Internet上以源代码的形式免费发行，所以很容易在其它操作系统下重新编译安装。我们实验采用的就是for dos的FLEX和BISON。本书有关的编译工具及其源程序例子，可到BISON的网站上下载。关于FLEX和BISON的用法简介，参见附录，如需更详细的介绍，请参阅编译工具中帮助文件。
《编译原理》期末考试复习题 一、是非题（请在括号内，正确的划√，错误的划×）（每个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．简单优先文法允许任意两个产生式具有相同右部。 () 三、填空题(每空1分，共10分) 1．编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有__ ___和 ___ _。 表格管理出错处理_ 2．若源程序是用高级语言编写的,__ __是机器语言程序或汇编程序,则其翻译程序称为 __ __ 。 _目标程序_编译程序 3．编译方式与解释方式的根本区别在于__ __。 是否生成目标代码_ 4．对编译程序而言,输入数据是__ __, 输出结果是__ ___。 _源程序目标程序
5．产生式是用于定义__ __的一种书写规则。 _语法成分 6．语法分析最常用的两类方法是___ __和__ __分析法。 自上而下_自下而上 四、简答题（20分） 1. 什么是句子？什么是语言 ? 答：(1)设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈VT*),则称x是文法的一个句子。 (2)设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│S x,x∈VT*} 。 一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） ×1．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。() ×2．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。() √3．递归下降分析法是自顶向上分析方法。() ×4．产生式是用于定义词法成分的一种书写规则。() √5．LR 法是自顶向下语法分析方法。() √6．在SLR （1 ）分析法的名称中，S的含义是简单的。() ×7．综合属性是用于“ 自上而下” 传递信息。() ×8．符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。() ×9．程序语言的语言处理程序是一种应用软件。() ×10．解释程序适用于COBOL 和FORTRAN 语言。() 三、填空题(每空1分，共10分) 1．一个句型中的最左简单短语称为该句型的___句柄__。
编译程序实验指导书 讲解
编译程序实验指导书 实验目的：用C语言对一个C语言的子集编制一个一遍扫描的编译程序，以加深对编译原理的理解，掌握编译程序的实现方法和技术。 1．词法分析 1.1 实验目的 设计、编制并测试一个词法分析程序，加深对词法分析原理的理解。 1.2 实验要求 1.2.1 待分析的C语言子集的词法 1. 关键字 main if else int char for while 所有的关键字都是小写。 2．专用符号 = + - * / < <= > >= == != ; : , { } [ ] ( ) 3．其他标记ID和NUM 通过以下正规式定义其他标记： ID→letter(letter|digit)* NUM→digit digit* letter→a|…|z|A|…|Z digit→0|…|9… 4．空格由空白、制表符和换行符组成 空格一般用来分隔ID、NUM、专用符号和关键字，词法分析阶段通常被忽略。 1.2.2 各种单词符号对应的种别码 表1 各种单词符号的种别码 单词符号种别码单词符号种别码单词符号种别码 main 1 = 21 , 32 int 2 + 22 : 33 char 3 - 23 ; 34 if 4 * 24 > 35 else 5 / 25 < 36 for 6 ( 26 >= 37 while 7 ) 27 <= 38 ID 10 [ 28 == 39 MUN 20 ] 29 != 40 { 30 ‘\0’ 1000 } 31 ERROR -1
1.2.3 词法分析程序的功能 输入：所给文法的源程序字符串。 输出：二元组（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.3 词法分析程序的主要算法思想 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想 是根据扫描到的单词符号的第一个字符的种类，拼出相应的单词符号。 1. 主程序示意图 主程序示意图如图1所示。 图1 词法分析主程序示意图 其中初值包括如下两方面： (1)关键字表初值 关键字作为特殊标识符处理,把它们预先安排在一张表格中(称为关键字表),当扫描程序识 别出标识符时,查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下：
《编译原理》（实验部分） 实验1_程序预处理 一、实验目的 明确预处理子程序的任务，构造一个简单的预处理子程序，对源程序进行相应的预处理。 二、实验设备 1、PC 兼容机一台；操作系统为WindowsWindowsXP。 2、Visual C++ 6.0 或以上版本， Windows 2000 或以上版本，汇编工具（在Software 子目录下）。 三、实验原理 定义模拟的简单语言的词法构成，编制读入源程序和进行预处理的程序，要求将源程序读入到文件或存入数组中，再从文件或数组中逐个读取字符进行预处理，包括去掉注释、Tab、Enter和续行符等操作，并显示预处理后的程序。 四、实验步骤 1、从键盘读入源程序存放到输入缓冲区中。 2、对源程序进行预处理，预处理后的程序存放到扫描缓冲区中。 3、显示预处理后的程序。 参考源程序（C++语言编写） //源程序的输入及预处理 #include
{ //定义扫描缓冲区 char buf[4048]={'\0'}; //缓冲区清0 //调用预处理程序 pro_process(buf); //在屏幕上显示扫描缓冲区的内容cout<
1. 源语言：书写源程序所使用的语言 2. 源程序：用程序设计语言书写的程序 3. 目标语言：计算机的机器指令。目标语言可以是机器语言，也可以是汇编语言， 或者是其他中间语言，但最终结果必是机器语言。 4. 目标程序：由机器指令构成的程序。目标程序是经过翻译程序加工后用目标语言 表示的程序。 5. 翻译程序：能够把某一种语言程序(源程序)改造成另一种语言程序(目标程序)将 源程序译成逻辑上等价的目标程序的程序。翻译程序有两种工作方式：编译和解释。 6. 编译程序：也称翻译程序 7. 解释程序：有些翻译程序在翻译过程中并不产生完整的目标程序，而是翻译一句， 解释执行一句，这样的称为解释程序。 8. 汇编程序：由汇编语言写成的程序 9. 词法分析：执行词法分析的程序成为词法分析器，词法分析依据的是语言构词规 则。词法分析器从文件读入源程序，由字符拼接单词。每当识别出一个单词，词法分析器就输出这个单词的内部码。 10. 语法分析：执行语法分析的程序叫做语法分析器。语法分析的任务就是根据语言 的规则，将词法分析器所提供的单词种别分成各类语法范畴。 11. 中间代码生成：中间代码产生有时称为语义分析，执行中间代码产生的程序称为 中间代码生成器。他的任务时按照语法分析器所识别出的语法范畴产生相应的中间代码，并建立符号表、常数表，等各种表格。 12. 目标代码生成：执行目标代码生成的程序称为目标代码生成器。他的任务是根据 中间代码和表格信息，确定各类数据在内存中的位置，选择合适的指令代码，将中间代码翻译成汇编语言或机器指令，这部分工作与计算机硬件有关。 13. 符号表：用于记录源程序中出现的标识符，一个标识符往往具有一系列的语义 值，她包括标识符的名称、种属、类型、值存放的地址等等。 14. 常数表：用于记录在源程序中出现的常数。 15. 编译程序前端：是由词法分析器、语法分析器和中间代码产生器组成的。她的特 点是依赖于被编译的源程序，输出结果用中间代码描述，和目标机器无关。16. 编译程序后端：是由目标代码生成器组成，他的特点是和源程序无关，以中间代 码形式的源程序为输入进行处理，输出结果依赖于目标机器。 17. 文本文件：文本文件的内容由94个图形字符‘！‘-' ~ '(33-126)和4个 控制字符换行(10)、回车(13)、空格(32)、TAB( 9)构成，文本文件又称为 ASCII码文件，扩展名通常为TXT,文件尾用控制字符EOF( 26)指示。 18. 二进制文件：由机器指令即二进制数构成，因二进制数可能是26 (文件结束控制 符)，故文件尾用文件长度(文件的字节数)指示，扩展名通常为EX E。 19. 源代码(source code)—预处理器(preprocessor) —编译器(compiler) —汇编程序 (assembler)—目标代码(object code)—链接器(Linker) —可执行程序 (executables) 20. 编译程序的流程是： 源程序―》词法分析―》语法分析―》语义分析(中间代码产生)―》目标 代码生成-》目标程序
C 语言程序设计 实 验 指 导 书 电子工程学院 2012-2
实验一 C程序的运行环境和编辑、调试、运行简单C程序 一、实验目的 1.了解 Turbo C 的基本操作方法，学会独立使用该系统。 2.掌握在该系统上如何编辑、编译、运行一个C程序。 二、实验内容及步骤 1.进入C的工作环境 1）在Windouws环境下：“开始”→“程序”→“MS-DOS” 屏幕上进入 MS-DOS窗口 2）在Dos环境下：键入命令c:\> cd c:\tc↙ c:\tc> tc↙ 屏幕上出现Turbo C的工作环境 2.熟悉Turbo C的工作环境 了解Edit窗口与Message窗口 了解主菜单的8个菜单项 File Edit Compile Project Option Debug break/watch 3.输入并运行一个简单的程序 File→New 输入源程序：
main() { printf("This is a C program.\n"); printf("OK\n"); } 按F9进行编译和连接，观察屏幕上显示的编译信息。如果出现出错信息，则应找出原因并改正。 按Run→Run(或按Ctrl+F9) 编译、连接、运行一起完成。 按Run→User screen(或按Alt+F5) 察看运行结果。 按任一键从用户屏切换回TC窗口。 4.输入并编辑第二个C程序 File→New 输入源程序： main ( ) { int a，b，sum; a=123; b=456; sum=a+b; printf("sum is %d\n"， sum); }
编辑、运行、调试该程序。 5.编辑、运行、调试自己编写的程序（至少一个程序） 如：输入上底、下底和高，计算梯形面积。 观察屏幕上显示的编译信息。如果出现出错信息，则应找出原因并改正。 用File→Save （或F2）保存程序（程序名为a1.c） 三、实验报告要求 写明： 1.实验目的 2.实验内容与步骤 3.编写的程序（题目，经调试、运行后正确的程序） 4.编译过程中出现的错误信息。 5.总结讨论本次实验的结果和收获。
/*PL/0 编译系统C版本头文件pl0.h*/ # define norw 13 //a number of reserved word /*关键字个数*/ # define txmax 100 //length of identifier table /*名字表容量*/ # define nmax 14 //max number of digits in numbers /*number的最大位数*/ # define al 10 //length of identifier /*符号的最大长度*/ # define amax 2047 //maximum address /*地址上界*/ # define levmax 3 //max depth of block nesting /*最大允许过程嵌套声明层数[0，lexmax]*/ # define cxmax 200 //size of code array /*最多的虚拟机代码数*/ /*符号*/ enum symbol{ nul, ident, number, plus, minus, times, slash, oddsym, eql, neq, //slash斜线 lss, leq, gtr, geq, lparen, //leq :less than or equal to; gtr: great than;lparen:left parenthesis rparen, comma, semicolon,period, becomes,//comma逗号semicolon分号period句号becomes赋值号 beginsym, endsym, ifsym, thensym, whilesym, writesym, readsym, dosym, callsym, constsym, varsym, procsym, }; #define symnum 32 /*-------------*/ enum object{ //object为三种标识符的类型 constant, variable, procedur, }; /*--------------*/ enum fct{ //fct类型分别标识类PCODE的各条指令 lit, opr, lod, sto, cal, inte, jmp, jpc, //书本P23 }; #define fctnum 8 /*--------------*/ struct instruction //指令 { enum fct f; //功能码 int l; //层次差 int a; //P23 }; FILE * fas; //输出名字表
一、填空题: 1-01.编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析，之间代码生成,代码优化等几个基本阶段,同时还会伴有表格处理和出错处理. 1-02.若源程序是用高级语言编写的,目标程序是机器语言程序或汇编程序,则其翻译程序称为编译程序. 1-03.编译方式与解释方式的根本区别在于是否生成目标代码. 1-04.翻译程序是这样一种程序,它能够将用甲语言书写的程序转换成与其等价的用乙语言书写的程序. 1-05.对编译程序而言,输入数据是源程序,输出结果是目标程序. 1-06.如果编译程序生成的目标程序是机器代码程序,则源程序的执行分为两大阶段:编译阶段和运行阶段.如果编译程序生成的目标程序是汇编语言程序,则源程序的执行分为三个阶段:编译阶段,汇编阶段和运行阶段. 1-07.若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序。 1-08.一个典型的编译程序中，不仅包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。其中，词法分析器用于识别单词。 1-09.编译方式与解释方式的根本区别为是否生成目标代码。 2-01.所谓最右推导是指：任何一步αβ都是对α中最右非终结符进行替换的。 2-02.一个上下文无关文法所含四个组成部分是一组终结符号、一组非终结符号、一个开始符号、一组产生式。 2-03.产生式是用于定义语法成分的一种书写规则。 2-04.设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│S x,x∈V T*}。 2-05.设G是一个给定的文法，S是文法的开始符号，如果S x（其中x∈V*），则称x是文法的一个句型。 2-06.设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈V T*),则称x是文法的一个句子。3-01.扫描器的任务是从源程序中识别出一个个单词符号。 4-01.语法分析最常用的两类方法是自上而下和自下而上分析法。 4-02.语法分析的任务是识别给定的终极符串是否为给定文法的句子。 4-03.递归下降法不允许任一非终极符是直接左递归的。 4-04.自顶向下的语法分析方法的关键是如何选择候选式的问题。 4-05.递归下降分析法是自顶向上分析方法。 4-06.自顶向下的语法分析方法的基本思想是：从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。 5-01.自底向上的语法分析方法的基本思想是：从给定的终极符串开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。 5-02.自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行直接归约，力求归约到文法的开始符号。