《编译原理》教案
授课类型（请打√）：理论课讨论课□实验课□练习课□其他□
教学方式（请打√）：讲授讨论□示教□指导其他□
教学资源（请打√）：多媒体模型□实物□挂图□音像□其他□教学内容
0 课程学习的要求及任务，学习方法介绍，成绩考核标准。
第一章引论
1.1 什么叫编译程序？
通常所说的翻译程序是指这样的一个程序，它能够把某一种语言程序(称为源语言程序)转换成另一种语言程序(称为目标语言程序)，而后者与前者在逻辑上是等价的。如果源语言是诸如FORTRAN、Pascal、C、Ada、Smalltalk或Java这
样的“高级语言”，而目标语言是诸如汇编语言或机器语言之类的“低级语言”，这样的一个翻译程序就称为编译程序。
高级语言程序除了像上面所说的先编译后执行外，有时也可“解释”执行。一个源语言的解释程序是这样的程序，它以该语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。本书将不对解释程序作专门的讨论。实际上，许多编译程序的构造与实现技术同样适用于解释程序。
根据不同的用途和侧重，编译程序还可进一步分类。专门用于帮助程序开发和调试的编译程序称为诊断编译程序(Diagnostic Compiler)，着重于提高目标代码效率的编译程序叫优化编译程序(Optimizing Compiler)。现在很多编译程序同时提供了调试、优化等多种功能，用户可以通过“开关”进行选择。运行编译程序的计算机称宿主机，运行编译程序所产生目标代码的计算机称目标机。
如果一个编译程序产生不同于其宿主机的机器代码，则称它为交叉编译程序(CrOSS Compiler)。如果不需重写编译程序中与机器无关的部分就能改变目标机，则称该编译程序为可变目标编译程序(Retargetable Compiler)。
1.2 编译过程概述
编译程序过程: 从输入源程序开始到输出目标程序为止的整个编译过程可分为以下五个阶段：词法分析,语法分析,语义分析,中间代码产生,优化和目标代码生成.
1.3 编译程序的结构
编译程序的结构可以按照从输入源程序开始到输出目标程序为止的整个编译过程可分为以下五个阶段：词法分析,语法分析,语义分析,中间代码产生,优化和目标代码生成。
1.3.1 编译程序总框
编译程序的结构可以按照这五个阶段的任务分模块进行设计。下图给出了编译程序的总框。
1.3.2 表格与表格管理
编译程序在工作过程中需要保持一系列的表格，以登记源程序的各类信息和编译各阶段的进展状况。在编译程序使用的表格中，最合理的是符号表。编译程序在工作过程中需要保持一系列的表格，以登记源程序的各类信息和编译各阶段的进展状况。合理地设计和使用表格是编译程序构造的一个重要问题。在编译程序使用的表格中，最重要的是符号表。它用来登记源程序中出现的每个名字以及名字的各种属性。例如，一个名字是常量名、变量名，还是过程名等等；如果是变量名，它的类型是什么、所占内存是多大、地址是什么等等。通常，编译程序在处理到名字的定义性出现时，要把名字的各种属性填人到符号表中；当处理到名字的使用性出现时，要对名字的属性进行查证。
当扫描器识别出一个名字(标识符)后，它把该名字填人到符号表中。但这时不能
完全确定名字的属性，它的各种属性要在后续的各阶段才能填人。例如，名字的类型等要在语义分析时才能确定，而名字的地址可能要到目标代码生成才能确定。
由此可见，编译各阶段都涉及到构造、查找或更新有关的表格。
1.3.3 出错处理
遍:是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生产新的中间结果或目标程序。一个编译程序不仅应能对书写正确的程序进行翻译，而且应能对出现在源程序中的错误进行处理。如果源程序有错误，编译程序应设法发现错误，把有关错误信息报告给用户。这部分工作是由专门的一组程序(叫做出错处理程序)完成的。一个好的编译程序应能最大限度地发现源程序中的各种错误，准确地指出错误的性质和发生错误的地点，并且能将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，以便进一步发现其它可能的错误。如果不仅能够发现错误，而且还能自动校正错、误，那当然就更好了。但是，自动校正错误的代价是非常高的。
编译过程的每一阶段都可能检测出错误，其中，绝大多数错误可以在编译的前三阶段检测出来。源程序中的错误通常分为语法错误和语义错误两大类。语法错误是指源程序中不符合语法(或词法)规则的错误，它们可在词法分析或语法分析时检测出来。例如，词法分析阶段能够检测出“非法字符”之类的错误；语法分析阶段能够检测出诸如“括号不匹配”、“缺少；”之类的错误。语义错误是指源程序中不符合语义规则的错误，这些错误一般在语义分析时检测出来，有的语义错误要在运行时才能检测出来。语义错误通常包括：说明错误、作用域错误、类型不一致等等。
1.3.4 遍
遍:是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生产新的中间结果或目标程序。通常，每遍的工作由从外存上获得的前一遍的中间结果开始(对于第一遍而言，从外存上获得源程序)，完成它所含的有关工作之后，再把结果记录于外存。既可以将几个不同阶段合为一遍，也可以把一个阶段的工作分为若干遍。例如，词法分析这一阶段可以单独作为一遍，但更多的时候是把它与语法分析合并为一遍；为了便于处理，语法分析和语义分析与中间代码产生又常常合为一遍。在优化要求很高时，往往还可把优化阶段分为若干遍来实现。
当一遍中包含若干阶段时，各阶段的工作是穿插进行的。例如，我们可以把词法分析、语法分析及语义分析与中间代码产生这三阶段安排成一遍。这时，语法分析器处于核心位置，当它在识别语法结构而需要下一单词符号时，它就调用词法分析器，一旦识别出一个语法单位时，它就调用中间代码产生器，完成相应的语义分析并产生相应的中间代码。
一个编译程序究竟应分成几遍，如何划分，是与源语言、设计要求、硬件设备等诸因素有关的，因此难于统一划定。遍数多一点有个好处，即整个编译程序的逻辑结构可能清晰一点。但遍数多势必增加输入／输出所消耗的时间。因此，在主存可能的前提下，一般还是遍数尽可能少一点为好。应当注意的是，并不是每种语言都可以用单遍编译程序实现。
1.3.5 编译前端与后端
概念上，我们有时把编译程序划分为编译前端和编译后端。前端主要由与源语言有关但与目标机无关的那些部分组成。这些部分通常包括词法分析、语法分析、语义分析与中间代码产生，有的代码优化工作也可包括在前端。后端包括编译程
序中与目标机有关的那些部分，如与目标机有关的代码优化和目标代码生成等。
通常，后端不依赖于源语言而仅仅依赖于中间语言。
可以取编译程序的前端，改写其后端以生成不同目标机上的相同语言的编译程序。如果后端的设计是经过精心考虑的，那么后端的改写将用不了太大工作量，这样就可实现编译程序的目标机改变。也可以设想将几种源语言编译成相同的中间语言，然后为不同的前端配上相同的后端，这样就可为同一台机器生成不同语言的编译程序。然而，由于不同语言存在某些微妙的区别，因此在这方面所取得的成果还非常有限。
为了实现编译程序可改变目标机，通常需要有一种定义良好的中间语言支持。例如．在著名的Ada程序设计环境APSE中，使用的是一种称为Diana的树形结构的中间语言一个Ada源程序通过前编译转换为Diana中间代码，由编译后端把Diana中间代码转换为目标代码。编译前端与不同的编译后端以Diana为界面，实现编译程序的目标机改变。
又如，在Java语言环境中，为了使编译后的程序从一个平台移到另一个平台，Java定义一种虚拟机代码--Bytecode。只要实际使用的操作平台上实现了的Java解释器，这个操作平台就可以执行各种Java程序。这就是所谓Java语言操作平台无关性。
1.4 编译程序与程序设计环境
开发通常还需要一些其它的工具；如编辑程序、连接程序，调试工具等等。编译程序与这些程序设计工具一起构成所谓的程序设计环境。
在高级语言发展的早期，这些程序设计工具往往是独立的，缺乏整体性，而且也缺乏对软件开发全生命周期的支持。随着软件技术的不断发展，现在人们越来越
倾向于构造集成化的程序设计环境。一个集成化的程序设计环境的特点是，它将相互独立的程序设计工具集成起来，以便为程序员提供完整的、一体化的支持，从而进一步提高程序开发效率，改善程序质量。在一个好的集成化程序设计环境中，不仅包含丰富的程序设计工具，而且还支持程序设计方法学，支持程序开发的全生命周期。有代表性的集成化程序设计环境有Ada语言程序设计环境APSE、LISP语言程序设计环境INTERLISP等。广大读者所熟悉的Pascal、TurboC、VisualC++等语言环境也都可认为是集成化的程序设计环境。
1.5 编译程序的生成
以前人们构造编译程序大多是用机器语言或汇编语言做工具的。为了发挥各种不同硬件系统的效率，为了满足各种不同的具体要求，现在许多人仍然采用这种工具来构造编译程序。但是，越来越多的人倾向于使用高级语言作为工具来构造编译程序。因为，这样可以节省大量的程序设计时间，而且所构造出来的编译程序也易于阅读、修改和移植。
人们已经建立了多种编制部分编译程序或整个编译程序的有效工具。有些能用于自动产生扫描器，有些可用于自动产生语法分析器，有些甚至可用来自动产生整个的编译程序。如：编译程序-编译程序、编译程序产生器、翻译程序书写系统等，它们是按照对源语言和目标语言（或机器）的形式描述（作为输入数据）而自动产生编译程序的。本课程将把自动产生器作为一个重要课题来讨论。近些年来，有些人主张采用“自编译方式”产生编译程序。意思是，先对语言的核心部分构造一个小小的编译程序（可用手编实现），再以它为工具构造一个能够编译更多语言成分的较大编译程序。如此扩展下去，就象滚雪球一样，越滚越大，最后形成人们所期望的整个编译程序。这种通过一系列自展途径而形成编译程序的
过程叫作自编译过程。
现在，有些编译程序是通过“移植”得到的。即把某一机器上的编译程序移植到另一机器上。着需要寻求某种适当的“中间语言”。但是，由于建立通用中间语言实际上办不到，因此，移植也只能在几种语言和几种机器之间进行。
授课类型（请打√）：理论课讨论课□实验课练习课其他□
教学方式（请打√）：讲授讨论□示教□指导其他□
教学资源（请打√）：多媒体模型□实物□挂图□音像□其他□
教学内容
第二章词法分析
2.1 对于词法分析器的要求
首先讨论词法分析器输出的单词符号的一般形式，然后研究词法分析器应如何和语法分析器相衔接。
2.1.1 词法分析器的功能和输出形式
词法分析器的功能是输入源程序，输出单词符号。单词符号是一个程序语言的基本语法符号，程序语言的单词符号一般可分为下列五种：
1 基本字如FORTRAN中的DIMENSION、IF和DO 等等；
2 标识符用来表示各种名字，如变量名、数组名和过程名等等；
3 常数各种类型的常数，如125，0.718、TRUE等等；
4 运算符如+、-、*、/等等；
5 界符如逗号、括号、分号等等。
标识符一般统归为一种。常数则宜按类型（整、实、复或布尔）分种。基本字可将其全体视为一种，也可以一字一种。运算符可采用一符一种的分法，但也可以把具有一定共性的算符（如所有关系符）视为一种。界符一般用一符一种的分法。
如果一个种别只含一个单词符号，那么，对于这个单词符号，种别编码就完全代表它自身了。若一个种别含有许多个单词符号，那么对于它的每个单词符号，除了给出种别编码之外，还应给出自身的值。
2.1.2 词法分析器作为一个独立子程序
可以使整个编译程序的结构更简洁、清晰和条例化。
2.2 词法分析器的设计
我们将按照词法分析的任务和作为一个独立子程序的要求来考虑词法分析器的设计。
2.2.1 输入、预处理
词法分析器工作的第一步是输入源程序文本。输入串一般是放在一个缓冲区中，这个缓冲区称为输入缓冲区。词法分析的工作（单词符号的识别）可以直接在这个缓冲区中进行。但在许多情况下，把输入串预处理一下，对单词符号的识别工作将是比较方便的。
预处理的工作包括：剔除无用的空白、跳格、回车和换行符等编辑性字符；预处理工作还可以包括源程序和出错信息的列表打印。
2.2.2 单词符号的识别：超前搜索
词法分析器的结构如下图所示：当词法分析器调用预处理子程序处理出一串输入
字符放进扫描缓冲区之后，扫描器就从此缓冲区中逐一识别单词符号。当缓冲区里的字符串被处理完之后，它又调用预处理程序装入新串。
图3.1 词法分析器
下面我们来介绍一下单词符号识别的一个简单方法——超前搜索。
基本字的识别有些语言的基本字的输入表示有特殊标志，如加双引号（如“BEGIN”），在这种情况下，基本字的识别是很直接的，不存在什么困难。象FORTRAN这样的语言，基本字不加特殊保护，基本字和用户自定义的标识符或
标号之间没有特殊的界符作间隔，这就使得基本字的识别甚为麻烦。这里就需要用到超前搜索。
2.2.3 状态转换图
使用状态转换图是设计词法分析程序(扫描器)的一种好途径。转换图是一张有限方向图。在状态转换图中，结点代表状态，用圆圈表示。状态之间用箭弧连结。
箭弧上的标记（字符）代表在射出结(即箭弧始节)状态下可能出现的输入字符或字符类。如下图3.2（a）所示。
在状态1下，若输入字符X，则读进X，并转换到状态2。若输入字符Y，则读进Y，并转换到状态3。一张转换图只包含有限个状态（即有限个结点），其中有一个被认为是初态，而且实际上至少要有一个终态（用双圈表示）。
图3.2（a）状态转换图示例
2.2.4 状态转换图的实现
一个状态转换图可用于识别（或接受）一定的字符。大多数程序语言的单词符号都可以用转换图予以识别。转换图非常易于用程序实现，最简单的办法是让每个状态结点对应一小段程序。下面我们将引进一组全局变量和过程，把它们作为实现转换图的基本成分。这些变量和过程是：
1. CHAR 字符变量，存放最新读进的源程序字符。
2. TOKEN 字符数组，存放构成单词符号的字符串。
3. GETCHAR 子程序过程，把下一个输入字符读到CHAR中，把搜索指示器前
移一字节位置。
4. GETBC 子程序过程，检查CHAR中的字符是否为空白.若是，则GETCHAR
直到CHAR中进入一个非空白符。
5. CONCAT 子程序过程，把CHAR中的字符连接TOKEN之后。例如，TOKEN
原来的值为‘AB'，而CHAR中存放着'C'，经调用CONCAT后，TOKEN的值就变为'ABC'。
6. LETTER和DIGIT布尔函数过程，它们分别CHAR中的字符是否为字母和数
字，从尔给出真值TRUE或假值FALSE。
7. RESERVE 整型函数过程，对TOKEN中的字符串查找保留字表，若它是一个
保留字则返回它的编码，否则返回0值(假定0不是保留字的编码)。
8. RETRACT 子程序过程，把搜索指示器回调一个字节位置，把CHAR中的字符
置为空白。
2.3 正规表达式与有限自动机
2.3.1 正规式与正规集
设Σ是一个有穷字母表，它的每个元素称为一个字符。Σ上的一个字（也叫字符串）是指由Σ中的字符所构成的一个有穷序列。不包含任何字符的序列称为空字，记为ε。用Σ* 表示Σ上的所有字的全体，空字ε也包括在其中。例如，若Σ={a，b}，则Σ*={ε,a,b,aa,ab,ba,bb,aaa}下面是正规式和正规集的递归定义：
1.和Φ都是上的正规式，它们所表示的正规集分别为{ε} 和Φ；
2.任何α∈Σ，是Σ上的一个正规式，它所表示的正规集为{α};
3.假定U和V都是上的正规式，它们所表示的正规集分别记为L（U）和L（V），
那么，（U V）、（U|V）和（U）*也都是正规式，它们所表示的正规集分别为L（U）L（V）、L（U）.L（V）（连接积）和（L（U））*（闭包）。
仅由有限次使用上述三步骤而定义的表达式才是Σ上的正规式，仅由这些正规式所表示的字集才是Σ上的正规集。算符的优先顺序为：先"*"，次"."，最后"|"。
例如，令Σ={a，b} ，下面是Σ上的正规式和相应的正规集：
ba*：Σ上所有以b为首后跟任意多个a的字
a(a| b)* ：Σ上所有以a为首的字
(a| b)* (aa| bb)(a|b)*：Σ上所有含有两个相继的a或两个相继的b的字
又例如，令Σ={A，B，0，1} ，则
(A|B)(A|B|0|1)* ：Σ上的"标识符"的全体
(0|1)(0|1)* ：Σ上的"数"的全体
若两个正规式所表示的正规集相同，则认为二者等价。两个等价的正规式U和V 记为U=V。令U、V和W 均为正规式，显而易见，下列关系普遍成立
1. V=V|U （交换律）
2. U|(V|W)=(u|v)|w（结合律）
3. U|(V|W)=(U|V)|W（结合律）
4. U|(VW)=UV|UW（分配律）(V|W)U=VU|WU
5.εU=Uε=U
2.3.2 确定有限自动机（DFA）
设一个确定的有限自动机（DFA）M是一个五元式M=(S, Σ,f,S0, Z)其中
1. S是一个有限集，它的每个元素称为一个状态；
2. 是一个有穷字母表Σ，它的每个元素称为一个输入字符；
3. f是一个从S×Σ至S的（单值）部分映照。f（s，a）=s'意味着：当现行状态为
s，输入字符a时，将转换到下一状态s'。我们把s'称为s的一个后继状态；
4. S0S，是唯一的一个初态；
5. Z S，是一个终态集（可空）。
一个DFA可用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示f（s，a）的值，这个矩阵称为状态转换矩阵。
例如，有DFA M=({0,1,2,3 ,{a,b ,f,0,{3 }其中f为：
f(0,a)=1 f(0,b)=2
f(1,a)=3 f(4,b)=2
f(2,a)=1 f(2,b)=3
f(3,a)=3 f(3,b)=3
则对应的状态转换矩阵如下表3.2所示：
表3.2 状态转换矩阵
一个DFA也可以表示成一张（确定的）状态转换图。
对于Σ*中的任何字，若存在一条从初态结到某一条终态结的道路，且这条路上所有弧的标记符连接成的字等于，则称可为DFA M 所识别（读出或接受）。
若M的初态结同时又是终态结，则空字ε可为M所识别（或接受）。
上例所定义的DFA M相应的状态转换图如下所示：它能识别Σ上所有含有相继两个a或相继两个b的字。
图3.5 状态转换图
2.3.3 非确定有限自动机(NFA)
设一个确定的有限自动机（DFA）M是一个五元式M=(S,Σ,f,S0, Z)其中
1. S是一个有限集，它的每个元素称为一个状态；
2.Σ是一个有穷字母表，它的每个元素称为一个输入字符；
3. f是一个从S×Σ*到S的子集的映照，即f：S×Σ*2S
4. S0S，是非空初态集；
5. Z S，是一个终态集（可空）。
2.3.4 正规文法与有限自动机的等价性
对于正规文法G和有限自动机M，如果L（G）＝L（M），则称G和M是等价的。关于正规文法和有限自动机的等价性，有以下结论：
（1）对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机（FA）M，使得L（M）＝L（G）。
（2）对每一个FA M，都存在一个右线性正规文法G R或左线性正规文法G L，
使得L（M）＝L（G R）＝L（G L）
2.3.5 正规式与有限自动机的等价性
我们可以证明：
（1）对任何FA M，都存在一个正规式r，使得L（r）＝L（M）。
（2）对任何的正规式r，都存在一个FA M，使得L（M）＝L（r）。
上述结论加上前面章节所证明的结论，说明正规文法、正规式、确定有限自动机和非确定有限自动机在接收语言的能力上是互相等价的。
2.3.6 确定有限自动机的化简
等价状态；最少化。
2.4 词法分析器的自动产生
教学目的：使用状态转换图构造词法分析程序；上机实践LEX的实现。
2.4.1 语言LEX的一般描述
一个LEX源程序主要包括两部分。一部分是正规定义式，另一个是识别规则。产生式(也称产生规则或简称规则)是定义语法范畴的一种书写规则。一个产生式的形式是A a 其中，箭头(有时也用：：＝)左边的A是一个非终结符，称为产生式的左部符号；箭头右边的a是由终结符号或非终结符号组成的符号串，称为产生式的右部。我们有时也说，产生式A a是关于A的一条产生规则。产生式是用来定义语法范畴的。
例如，令i 代表已定义的范畴“变量”，那么，产生式算术表达式i 意味着把“算术表达式”这个范畴定义为“变量”。在有的书上，“”也用“：：＝”表示：这种表示方法也称巴科斯范式。
2.4.2 超前搜索
在某些语言中，要识别一个单词符号必须超前看若干字符。
2.4.3 LEX的实现
LEX的编译程序旨在将一个LEX源程序改造为一个词法分析器L，这个词法分析器L将像有限自动机那样工作。
相关介绍：人们已建立了多种编制部分编译程序或整个编译程序的有效工具。有些能用于自动产生扫描器(如LEX)，有些可用于自动产生语法分析器(如YACC)，有些甚至可用来自动产生整个的编译程序。这些构造编译程序的工具称为编译程序——编译程序、编译程序产生器或翻译程序书写系统，它们是按对源程序和目标语言(或机器)的形式描述(作为输入数据)而自动产生编译程序的。
授课类型（请打√）：理论课讨论课□实验课□练习课其他□
教学方式（请打√）：讲授讨论□示教□指导其他□
教学资源（请打√）：多媒体模型□实物□挂图□音像□其他□
教学内容
3.1.1 上下文无关文法
箭头‘-->’读为“定义为”，直竖‘|’读为“或”，它们是元语言符号。在后面的讨论中，根据不同情况，我们将用大写字母A、B、C…或汉语词组(如，算术表达式)代表非终结符号，特别是用小写字母a、b、c…代表终结符，用α、β、γ等代表由终结符和非终结符组成的符号串。为简便起见，当引用具体的文法例子时，仅列出产生式和指出开始符号。
例如，下面是一个上下文无关文法：
E-->i|EAE
A-->+|*
其中，E、A是非终结符，E是开始符号，而i、+和*是终结符。
一个上下文无关文法如何定义一个语言呢?其中心思想是，从文法的开始符号出发，反复连续使用产生式，对非终结符施行替换和展开。例如，我们考虑下面的文法G:
E-->E十E | E*E | (E) |i
其中，唯一的非终结符E可以看成是代表一类算术表达式。我们可以从E出发，进行一系列的推导，推出种种不同的算术表达式来。例如，根据规则E一>(E)我们可以说：从‘E’可直接(一步地)推出‘(E)’。与前面一样，我们用‘’表示“直接推出”，这样，这句话就可表示为:E(E)。若对‘(E)’中的E使用规则E-->E+E，就有
(E)(E+E)。即，从‘(E)’可直接推出‘(E+E)’。把上述这两步合并起来，就有
E(E)(E+E)。再对‘(E+E)’中的E相继两次使用规则E-->i之后，我们就有(E) (E+E)(i+E)(i+i)。
我们称这样的一串替换序列是从E推出(i+i)的一个推导。这个推导提供了一个证明，证明(i+i)是文法(2.1)所定义的一个算术表达式。注意，推导每前进一步总是引用一条规则(产生式),而符号‘’指仅推导一步的意思。
我们可以用一种图示化的方法来表示这种推导，如下图2.1，说明He gave me a book是一个语法正确的句子。这种图形表示称为语法分析树。
定义“he gave me a book”这个英文句子的规则可以说就是一个上下文无关文法。其中，He，me，book，gave，a等，称为终结符号；<句子>、<主语>、<谓语>、<动词>、<代词>等，称为非终结符号；这个文法最终是要定义<句子>
的语法结构，所以<句子>在这里称为开始符号；<间接宾语>--><冠词><名词>这种书写形式称为产生式。
归纳起来，一个上下文无关文法C包括四个组成部分：一组终结符号，一组非终结符号，一个开始符号，以及一组产生式。
所谓终结符号乃是组成语言的基本符号，在程序语言中就是以前屡次提到的单词符号，如基本字、标识符、常数、算符和界符等。从语法分析的角度来看，终结符号是一个语言的不可再分的基本符号。
<句子>
<主语> <谓语>
<形容词> <名词> <动词> <宾语>
<形容词> <名he gave me a boo
图2.1语法树
非终结符号(也称语法变量)用来代表语法范畴。例如，“算术表达式”、“布尔表达式”、
编译原理与技术模拟试题一 一、填空题（20分） 1.1编译程序的工作过程可划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等 阶段，一般在语义分析阶段对表达式中运算对象的类型进行检查。 1.2 递归下降法和预测分析法是自上而下的语法分析方法。 1.3常用日的存储分配策略有静态存储分配和动态存储分配，其中，动态存储分配策略包括栈分配和堆分配。 1.4移进、归约是自下而上或LR 分析中的典型操作。 1.5对于数组M[1..6, 1..8]，如果每个元素占k个存储单元，且起始地址为a，则以行为主序存放时元素M[4,4]的地址是__ a+27*k __，以列为主序存放时元素M[4,4]的地址是__ a+21k __。 二、单选题（20分） 2.1词法分析器不能 D 。 A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 2.2给定文法A→bA|ca， C 是该文法的句子。 A. bba B. cab C. bca D. cba 2.3一个句型中的最左 B 称为该句型的句柄。 A. 短语 B. 直接短语 C. 非终结符号 D. 终结符号 2.4已知文法G[S]:S→A1A→A1|S0|0。与G等价的正规式是 C 。 A. 0(0|1)* B. 1*|0*1 C. 0(1|10)*1 D. 1(10|01)*0 2.5源程序是句子的集合， B 可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 2.6与逆波兰式ab+c*d+对应的中缀表达式是 B 。 A. a+b+c*d B. (a+b)* c+d C. (a+b)* (c+d) D. a+b*c+d 2.7识别上下文无关语言的自动机是 A 。 A. 下推自动机 B. NFA C. DFA D. 图灵机 2.8 B 是与规范归约（最左归约）互逆的一个过程。 A. 最左推导 B. 最右推导 C. 词法分析 D. 语义分析 2.9文法G产生的 A 的全体是该文法描述的语言， A. 句子 B. 短语 C. 终结符 D. 非终结符 2.10在表达式x:=y+1中， A 作为左值出现(其中，“:=”表示赋值)。 A. x B. y C. 1 D. y+1 三、简答题（30分） 3.1 （5分）请分别写出传值调用、引用调用方式下，下面代码的输出结果。 program main(input,output) procedure f(a,b) begin a := b - a; b := a * b + 1; end; begin x := 5; y := 10; f(y,x); print(x,y); end.
南华大学 计算机科学与技术学院 实验报告 （ 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
实验一词法分析程序实现 一、实验目得与要求 通过编写与调试一个词法分析程序,掌握在对程序设计语言得源程序进行扫描得过程中,将字符流形式得源程序转化为一个由各类单词符号组成得流得词法分析方法 二、实验内容 基本实验题目：若某一程序设计语言中得单词包括五个关键字begｉｎ、end、if、then、elsｅ；标识符；无符号常数；六种关系运算符；一个赋值符与四个算术运算符，试构造能识别这些单词得词法分析程序（各类单词得分类码参见表Ｉ）。 表Ｉ语言中得各类单词符号及其分类码表 输入:由符合与不符合所规定得单词类别结构得各类单词组成得源程序文件。 输出：把所识别出得每一单词均按形如(CLASS，VＡLUE）得二元式形式输出,并将结果放到某个文件中。对于标识符与无符号常数，CＬASS字段为相应得类别码得助记符;V AL ＵＥ字段则就是该标识符、常数得具体值；对于关键字与运算符,采用一词一类得编码形式，仅需在二元式得CLASS字段上放置相应单词得类别码得助记符，V ALUE字段则为“空". 三、实现方法与环境 词法分析就是编译程序得第一个处理阶段，可以通过两种途径来构造词法分析程序.其一就是根据对语言中各类单词得某种描述或定义(如BＮF)，用手工得方式（例如可用Ｃ语言)构造词法分析程序。一般地,可以根据文法或状态转换图构造相应得状态矩阵,该状态矩阵连同控制程序一起便组成了编译器得词法分析程序;也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序得另外一种途径就是所谓得词法分析程序得自动生成，即首先用正规式对语言中得各类单词符号进行词型描述,并分别指出在识别单词时,词法分析程
编译原理上机实验试题 一、实验目的 通过本实验使学生进一步熟悉和掌握程序设计语言的词法分析程序的设计原理及相关的设计技术， 如何针对确定的有限状态自动机进行编程序；熟悉和 掌握程序设计语言的语法分析程序的设计原理、熟悉 和掌握算符优先分析方法。 二、实验要求 本实验要求：①要求能熟练使用程序设计语言编程；②在上机之前要有详细的设计报告（预习报告）； ③要编写出完成相应任务的程序并在计算机上准确 地运行；④实验结束后要写出上机实验报告。 三、实验题目 针对下面文法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)或者是你觉得程序有哪些地方可以进一步完善，简述你的完善方案。
编译原理实验教案 计算机专业教研室 季玉茹
实验一：词法分析程序设计 实验目的 1．巩固对词法分析的基本功能和原理的认识。 2．能够应用自动机的知识进行词法分析。 3．理解并处理词法分析中的异常和错误。 实验要求 1．掌握词法分析的基本功能，并将其实现。 2．词法分析程序应具有较好的可扩展性，应清晰明确。 3．除对相关问题的全面考虑外，还需对局部作一些优化考虑（如符号表）。 3．明确词法分析的基本功能和原理。 4．在词法分析中哪些地方体现自动机意识。 5．词法分析的异常和错误处理。 6．编写并运行该题目程序代码，具有该题目的参考答案。 7．深刻理解题目内涵，能够清晰描述问题，掌握该题目涉及的知识点，指导学生实验时需要注意的问题。 实验原理 参考教材第2章2.3节和下图算法，可以做Pascal语言的词法分析程序； 单词的种类分为五种： 1．Pascal常用保留字： AND,ARRAY,BEGIN,CASE,CONST,DIV,DO,DOWNTO,ELSE,END,FILE, FOR,GOTO,FUNCTION,IF,IN,LABEL,MOD,NOT,OF,OR,PACKEN,PROCEDURE,PROG RAM,RECORD,REPEAR,SET,THEN,TO,TYPE,UNTIL,V AR,WHILE,WITH 2.标识符：[字母]{字母|数字} 另外标识符里包括：标准常量：false,ture 标准类型：integer,boolen,real,char,text 标准文件：input,output 标准过程：read,readln,write,writeln 3.运算符：+，-，*，/，DIV，MOD，OR，AND，NOT，<,<=,=,>=,>,<>,:= 4.界符：“，”，“.”,“、”，“（”，“）”，“：”，“；” 5.常数：如10，25，100，14.25 实验内容 对一段类高级语言代码进行词法分析，并输出词法分析的结果。
编译原理的复习提纲 1.编译原理=形式语言+编译技术 2.汇编程序： 把汇编语言程序翻译成等价的机器语言程序 3.编译程序： 把高级语言程序翻译成等价的低级语言程序 4.解释执行方式： 解释程序，逐个语句地模拟执行 翻译执行方式： 翻译程序，把程序设计语言程序翻译成等价的目标程序 5.计算机程序的编译过程类似，一般分为五个阶段： 词法分析、语法分析、语义分析及中间代码生成、代码优化、目标代码生成 词法分析的任务： 扫描源程序的字符串，识别出的最小的语法单位（标识符或无正负号数等） 语法分析是： 在词法分析的基础上的，语法分析不考虑语义。语法分析读入词法分析程序识别出的符号，根据给定的语法规则，识别出各个语法结构。 语义分析的任务是检查程序语义的正确性，解释程序结构的含义，语义分析包括检查变量是否有定义，变量在使用前是否具有值，数值是否溢出等。
语法分析完成之后，编译程序通常就依据语言的语义规则，利用语法制导技术把源程序翻译成某种中间代码。所谓中间代码是一种定义明确、便于处理、独立于计算机硬件的记号系统，可以认为是一种抽象机的程序 代码优化的主要任务是对前一阶段产生的中间代码进行等价变换，以便产生速度快、空间小的目标代码 编译的最后一个阶段是目标代码生成，其主要任务是把中间代码翻译成特定的机器指令或汇编程序 编译程序结构包括五个基本功能模块和两个辅助模块 6.编译划分成前端和后端。 编译前端的工作包括词法分析、语法分析、语义分析。编译前端只依赖于源程序，独立于目标计算机。前端进行分析 编译后端的工作主要是目标代码的生成和优化后端进行综合。独立于源程序，完全依赖于目标机器和中间代码。 把编译程序分为前端和后端的优点是： 可以优化配置不同的编译程序组合，实现编译重用，保持语言与机器的独立性。 7.汇编器把汇编语言代码翻译成一个特定的机器指令序列 第二章 1.符号，字母表，符号串，符号串的长度计算P18，子符号串的含义，符号串的简单运算XY，Xn， 2.符号串集合的概念，符号串集合的乘积运算，方幂运算，闭包与正闭包的概念P19，P20A0 ={ε} 3.重写规则，简称规则。非xx（V
编译原理实验指导 书
《编译原理》实验指导书 太原科技大学计算机学院 -3-1
序 《编译原理》是国内外各高等院校计算机科学技术类专业，特别是计算机软件专业的一门重要专业课程。该课程系统地向学生介绍编译程序的结构、工作流程及编译程序各组成部分的设计原理和实现技术。由于该课程理论性和实践性都比较强，内容较为抽象复杂，涉及到大量的软件设计和算法，因此，一直是一门比较难学的课程。为了使学生更好地理解和掌握编译原理和技术的基本概念、基本原理和实现方法，实践环节非常重要，只有经过上机进行程序设计，才能使学生对比较抽象的教学内容产生具体的感性认识，增强学生综合分析问题、解决问题的能力，并对提高学生软件设计水平大有益处。 为了配合《编译原理》课程的教学，考虑到本课程的内容和特点，本指导书设置了七个综合性实验，分别侧重于词法分析、NFA的确定化、非递归预测分析、算符优先分析器的构造、LR分析、语义分析和中间代码的生成、基于DAG的基本块优化，以支持编译程序的各个阶段，基本涵盖了《编译原理》课程的主要内容。 本指导书可作为《编译原理》课程的实验或课程设计内容，在课程教学的同时，安排学生进行相关的实验。实验平台可选择在MS-DOS或Windows操作系统环境，使用C/C++的任何版本作为开发工具。学生在做完试验后，应认真撰写实验报告，内容应
包括实验名称、实验目的、实验要求、实验内容、测试或运行结果等。
目录 实验一词法分析 ........................................................... 错误!未定义书签。实验二 NFA的确定化.................................................... 错误!未定义书签。实验三非递归预测分析 ............................................... 错误!未定义书签。实验四算符优先分析器的构造................................... 错误!未定义书签。实验五 LR分析 .............................................................. 错误!未定义书签。实验六语义分析和中间代码生成................................ 错误!未定义书签。实验七基于DAG的基本块优化................................... 错误!未定义书签。
实验四中间代码生成 一．实验目的： 掌握中间代码的四种形式（逆波兰式、语法树、三元式、四元式）。 二．实验内容： 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<<"请输入中缀表达式: ";
学生学号实验课成绩 武汉理工大学 学生实验报告书 实验课程名称编译原理 开课学院计算机科学与技术学院 指导老师姓名饶文碧 学生姓名 学生专业班级
—学年第学期 实验课程名称：编译原理 实验项目名称单词的词法分析实验成绩 实验者专业班级组别 同组者实验日期 第一部分：实验分析与设计（可加页） 一、实验内容描述（问题域描述） 完成对某一种常用高级语言（如Pascal、C语言、PL/0语言）的各类单词进行词法分析，即对源程序从左到右进行扫描，对组成源程序的字符串拼接成为单词；并把其转换成属性字输出。 实验要求： （1）选择常用高级程序设计语言（如 Pascal、C语言、PL/0语言）的源程序作为词法分析对象。 （2）根据教学要求和学生具体情况，从上列语言之一中选取它的一个适当大小的子集，可以选取一类典型单词，也可以尽可能使各种类型的单词都能兼顾到。其基本要求是：对源程序从左到右进行扫描，对组成源程序的字符串拼接成为单词，并把其转换成属性字输出。
二、实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或者算法描述） #include
( 编译原理实验报告 , 实验名称：实验一编写词法分析程序 实验类型：验证型实验 指导教师：何中胜 专业班级：（ 13软件四 姓名：丁越 学号： 实验地点：) 秋白楼B720
实验成绩： 日期：2016年 3 月 18 日
一、实验目的 通过设计、调试词法分析程序，实现从源程序中分出各种单词的方法；熟悉词法分析程序所用的工具自动机，进一步理解自动机理论。掌握文法转换成自动机的技术及有穷自动机实现的方法。确定词法分析器的输出形式及标识符与关键字的区分方法。加深对课堂教学的理解；提高词法分析方法的实践能力。通过本实验，应达到以下目标：[ 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。 二、实验过程 以编写PASCAL子集的词法分析程序为例 1.理论部分 > （1）主程序设计考虑 主程序的说明部分为各种表格和变量安排空间。 数组 k为关键字表，每个数组元素存放一个关键字。采用定长的方式，较短的关键字后面补空格。 P数组存放分界符。为了简单起见，分界符、算术运算符和关系运算符都放在 p表中（编程时，还应建立算术运算符表和关系运算符表，并且各有类号），合并成一类。 id和ci数组分别存放标识符和常数。 instring数组为输入源程序的单词缓存。 ￥ outtoken记录为输出内部表示缓存。 还有一些为造表填表设置的变量。 主程序开始后，先以人工方式输入关键字，造 k表；再输入分界符等造p表。 主程序的工作部分设计成便于调试的循环结构。每个循环处理一个单词；接收键盘上送来的一个单词；调用词法分析过程；输出每个单词的内部码。 ⑵词法分析过程考虑 将词法分析程序设计成独立一遍扫描源程序的结构。其流程图见图 1-1。 …
编译原理实验指导书 主编：徐静李娜 信息与电气工程学院 2010年3月
概述 一、本课程实验的目的和任务 编译原理是一门实践性很强的课程，只有通过实践，才能真正掌握。实际的编译程序是十分复杂的，有时由多达十几万条指令组成。为此，编译原理的实践教学，采用简化编译过程的办法，选择最关键的3个环节──词法分析、语法分析（包括语义处理、产生无优化的目标指令）、连接调试，进行编程和调试训练。每个环节作为一个实践课题。先分别编程调试，再连接在一起总调。 二、实验方法 任何一个实用的高级语言，其语法都比较复杂，如选其作为源语言，很难实践全过程。故本实验将定义一个简化的语言── C语言的一个子集作为源语言，设计调试出它的编译程序。前后贯穿这一条主线进行实践。每次都可利用课余时间编程，利用上机时间进行输入和调试。 三、实验报告的规范和要求 每个实验完成后写出实验报告。实验报告的内容包括如下内容： 一、实验目的 二、程序设计时采用的算法和方法 三、输入的源程序 四、词法分析程序清单和输出结果。 五、心得体会
实验一词法分析 一、实验目的： （1）通过设计编制调试一个具体的词法分析程序，理解词法分析在编译程序中的作用。 （2）加深对有穷自动机模型的理解。 （3）掌握词法分析程序的实现方法和技术。 （4）用C语言对一个简单语言的子集编制一个一遍扫描的程序，以加深对编译原理的理解，掌握编译程序的实现方法和技术。 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）。 二、实验预习提示 1. 词法分析器的功能和输出格式 词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示成以下的二元式（单词种别码，单词符号的属性值）。本实验中，采用的是一类符号一种别码的方式。 2. 单词的BNF表示 <标识符>→ <字母><字母数字串> <字母数字串>→<字母><字母数字串>|<数字> <字母数字串>| <下划线><字母数字串>|ε <无符号整数>→<数字> <数字串> <数字串>→<数字><数字串>|ε <加法运算符>→+ <减法运算符>→- <大于关系运算符>→> <大于等于关系运算符>→>= 3. “超前搜索”方法
2.1 考虑文法G[S],其产生式如下: S→(L)|a L→L，S|S (1)试指出此文法的终结符号、非终结符号。 终结符号为：{(,),a,,,} 非终结符号为：{S,L} 开始符号为：S (2)给出下列各句子的分析树： ① ②(a,(a,a))③ (a,((a,a),(a,a))) (a,a) (3)构造下列各句子的一个最左推导： ① (a,a) S (L) (L,S) (S,S) (a,S) (a,a) ② (a,(a,a)) S (L) (L,S) (S,S) (a,S) (a,(L) (a,(L,S)) (a,(S,S)) (a,(a,S)) (a,(a,a)) ③ (a,((a,a),(a,a))) S (L) (L,S) (S,S) (a,S) (a,(L)) (a,(L,S)) (a,(S,S)) (a,((L),S)) (a,((L,S),S)) (a,((S,S),S)) (a,((a,S),S)) (a,((a,a),S)) (a,((a,a),(L))) (a,((a,a),(L,S))) (a,((a,a),(S,S))) (a,((a,a),(a,S))) (a,((a,a),(a,a))) (4)构造下列各句子的一个最右推导： ①(a,a) S (L) (L,S) (L,a) (S,a) (a,a) ②(a,(a，a)) S (L) (L,S) (L,(L)) (L,(L,S)) (L,(L,a)) (L,(S,a)) (L,(a,a)) (S,(a,a)) (a,(a,a) ③(a，((a，a)，(a，a)) S (L) (L,S) (L,(L)) (L,(L,S)) (L,(L,(L))) (L,(L,(L,S))) (L,(L,(L,a))) (L,(L,(S,a))) (L,(L,(a,a))) (L,(S,(a,a))) (L,((L),(a,a))) (L,((L,S),(a,a))) (L,((L,a),(a,a))) (L,((S,a),(a,a))) (L,((a,a),(a,a))) (S,((a,a),(a,a))) (a,((a,a),(a,a))) (5)这个文法生成的语言是什么？ L(G[S]) = (α1,α2,...,αn)或a 其中αi(1≤i≤n)，即L(G[S])是一个以a为原子的纯表，但不包括空表。 2.2 考虑文法G[S] S→aSbS|bSaS|ε (1)试说明此文法是二义性的。可以从对于句子abab有两个不同的最左推导来说明。 S aSbS abS abaSbS ababS abab S aSbS abSaSbS abaSbS ababS abab 所以此文法是二义性的。 (2)对于句子abab构造两个不同的最右推导。 S aSbS aSbaSbS aSbaSb aSbab abab S aSbS aSb abSaSb abSab abab (3)对于句子abab构造两棵不同的分析树。
《编译原理》实验报告软件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)单词分类 为了编程的实现。我们假定要编译的语言中，全部关键字都是保留字，程序员不得将它们作为源程序中的标识符；作了这些限制以后，就可以把关键字和标识符的识别统一进行处理。即每当开始识别一个单词时，若扫视到的第一个字符为字母，则把后续输入的字母或数字字符依次进行拼接，直至扫视到非字母、数字字符为止，以期获得一个尽可能长的字母数字字符串，然后以此字符串查所谓保留字表（此保留字表要事先造好），若查到此字符串，则取出相应的类别码；反之，则表明该字符串应为一标识符。
实验一词法分析程序实现 一、实验目的与要求 通过编写和调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将字符流形式的源程序转化为一个由各类单词符号组成的流的词法分析方法 二、实验内容 基本实验题目：若某一程序设计语言中的单词包括五个关键字begin、end、if、then、else；标识符；无符号常数；六种关系运算符；一个赋值符和四个算术运算符，试构造能识别这些单词的词法分析程序（各类单词的分类码参见表I）。 表I 语言中的各类单词符号及其分类码表
输入：由符合和不符合所规定的单词类别结构的各类单词组成的源程序文件。 输出：把所识别出的每一单词均按形如（CLASS，VALUE）的二元式形式输出，并将结果放到某个文件中。对于标识符和无符号常数，CLASS字段为相应的类别码的助记符；VALUE 字段则是该标识符、常数的具体值；对于关键字和运算符，采用一词一类的编码形式，仅需在二元式的CLASS字段上放置相应单词的类别码的助记符，VALUE字段则为“空”。 三、实现方法与环境 词法分析是编译程序的第一个处理阶段，可以通过两种途径来构造词法分析程序。其一是根据对语言中各类单词的某种描述或定义（如BNF），用手工的方式（例如可用C语言）构造词法分析程序。一般地，可以根据文法或状态转换图构造相应的状态矩阵，该状态矩阵连同控制程序一起便组成了编译器的词法分析程序；也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序的另外一种途径是所谓的词法分析程序的自动生成，即首先用正规式对语言中的各类单词符号进行词型描述，并分别指出在识别单词时，词法分析程序所应进行的语义处理工作，然后由一个所谓词法分析程序的构造程序对上述信息进行加工。如美国BELL实验室研制的LEX就是一个被广泛使用的词法分析程序的自动生成工具。 处理过程简述：在一个程序设计语言中，一般都含有若干类单词符号，为此可首先为每类单词建立一张状态转换图，然后将这些状态转换图合并成一张统一的状态图，即得到了一个有限自动机，再进行必要的确定化和状态数最小化处理，最后添加当进行状态转移时所需执行的语义动作，就可以据此构造词法分析程序了。 为了使词法分析程序结构比较清晰，且尽量避免某些枝节问题的纠缠，我们假定要编译的语言中，全部关键字都是保留字，程序员不得将它们作为源程序中的标识符；在源程序的输入文本中，关键字、标识符、无符号常数之间，若未出现关系和算术运算符以及赋值符，则至少须用一个空白字符加以分隔。作了这些限制以后，就可以把关键字和标识符的识别统一进行处理。即每当开始识别一个单词时，若扫视到的第一个字符为字母，则把后续输入的字母或数字字符依次进行拼接，直至扫视到非字母、数字字符为止，以期获得一个尽可能长的字母数字字符串，然后以此字符串查所谓保留字表（此保留字表要事先造好），若查到此字符串，则取出相应的类别码；反之，则表明该字符串应为一标识符。
《编译原理》教案 授课类型（请打√）：理论课讨论课□实验课□练习课□其他□ 教学方式（请打√）：讲授讨论□示教□指导其他□ 教学资源（请打√）：多媒体模型□实物□挂图□音像□其他□教学内容 0 课程学习的要求及任务，学习方法介绍，成绩考核标准。 第一章引论 1.1 什么叫编译程序？ 通常所说的翻译程序是指这样的一个程序，它能够把某一种语言程序(称为源语言程序)转换成另一种语言程序(称为目标语言程序)，而后者与前者在逻辑上是等价的。如果源语言是诸如FORTRAN、Pascal、C、Ada、Smalltalk或Java这
样的“高级语言”，而目标语言是诸如汇编语言或机器语言之类的“低级语言”，这样的一个翻译程序就称为编译程序。 高级语言程序除了像上面所说的先编译后执行外，有时也可“解释”执行。一个源语言的解释程序是这样的程序，它以该语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。本书将不对解释程序作专门的讨论。实际上，许多编译程序的构造与实现技术同样适用于解释程序。 根据不同的用途和侧重，编译程序还可进一步分类。专门用于帮助程序开发和调试的编译程序称为诊断编译程序(Diagnostic Compiler)，着重于提高目标代码效率的编译程序叫优化编译程序(Optimizing Compiler)。现在很多编译程序同时提供了调试、优化等多种功能，用户可以通过“开关”进行选择。运行编译程序的计算机称宿主机，运行编译程序所产生目标代码的计算机称目标机。 如果一个编译程序产生不同于其宿主机的机器代码，则称它为交叉编译程序(CrOSS Compiler)。如果不需重写编译程序中与机器无关的部分就能改变目标机，则称该编译程序为可变目标编译程序(Retargetable Compiler)。 1.2 编译过程概述 编译程序过程: 从输入源程序开始到输出目标程序为止的整个编译过程可分为以下五个阶段：词法分析,语法分析,语义分析,中间代码产生,优化和目标代码生成. 1.3 编译程序的结构 编译程序的结构可以按照从输入源程序开始到输出目标程序为止的整个编译过程可分为以下五个阶段：词法分析,语法分析,语义分析,中间代码产生,优化和目标代码生成。 1.3.1 编译程序总框
参考答案及评分标准 一、填空（15分，每空1分） 1．高级，低级 2．源程序，单词 3．自顶向下 4．综合，继承 5．结构，名称 6．非局部名字访问，参数传递 7．上下文有关，上下文无关，正规 8．abcd+*+ 二、（15分） 答：正规表达式（4）代表了这个程序段所有可能走过的全部步序列（5分）把A,T,B,I分别代表相应的基本块，E表示程序段的出口，则程序段可以表示为如下的流（程）图：（5分） 转换为等价的确定状态自动机如下： 由上述确定状态自动机可以得到等价的正规表达式为：AT(BIT)*（5分） 如果没有画流程图而直接给出自动机可以给分。既没有画流程图，也没有画自动机，可以根据描述的理由是否能说明清楚酌情给分。 三、（20分） 答：1．FIRST(S)={a,b} FOLLOW(S)={$} FIRST(A)={a,b} FOLLOW(A)={b,$} FIRST(B)={b,ε} FOLLOW(B)={c,$} (6分，每个1分)。 2
3．分析符号串baabbb是否为该文法的句子的过程如下表所示：（7分）步骤栈输入串输出 1 $S baabbb$ 2 $BAb baabbb$ S →bAB 3 $BA aabbb$ 4 $BbAa aabbb$ A →aAb 5 $BbA abbb$ 6 $BbbAa abbb$ A →aAb 7 $BbbA bbb$ 8 $Bbbb bbb$ A →b 9 $Bbb bb$ 10 $Bb b$ 11 $B $ 12 $ $ B →ε 四、（25分） 答：1．文法G的拓广文法G`如下：（10分） S`→S S →Aa∣dAb∣Bb∣dBa A →c B→c 构造识别所有活前缀的确定有限状态自动机（DFA）如下：
作业题: 2.1(a,c,d), 2.8(a,c,d), 2.12, 3.3, 3.4, 4.8, 4.12 5.8(a,b,c), 5.12, 6.7, 6.8, 6.13 7.4, 7.15 第二章作业： 2．1(a) a | a[a-z]*a (c)[1-9][0-9]* (d)[0-9]*[02468] 2.8（a） 正则表达式中丢了单独a的情况的比较多，另外有些同学在有NFA到DFA的转化过程中，不能够正确的确定最终的状态，造成有两个终结状态的情况。 （c） （d） 问题比较多，建议同学画出DFA图生成的全部过程。
2.12 3．4 （c ）.rewrite this grammar to establish the correct precedences for the operator. rexp -> rexp “|” rexp1 | rexp1 rexp1 -> rexp1 rexp2 | rexp2 rexp2 -> rexp3 * | rexp3 rexp3 -> (rexp) | letter 左结合 4．8 （a ） 消除左递归 lexp -> atom | list atom -> number | identifier list -> (lexp-seq) lexp-seq -> lexp lexp-seq’ lexp-seq’ -> lexp lexp-seq’ | ε first (lexp)= { number ,identifier,( } first (atom)= { number, identifier } first (list) = { ( } first (lexp-seq)= { number ,identifier,( } first (lexp-seq’)= { number ,identifier,( , ε}
编译原理实验报告 实验名称NFA转换为DFA 实验时间2014-5-18 院系计算机科学与技术学院 班级 学号 姓名
1.试验目的 不确定有限状态自动机的确定化（Affirmation of the indefinitely finite automata） 2.实验原理 一个确定的有限自动机（DFA）M可以定义为一个五元组，M＝（K，∑，F，S，Z），其中： （1）K是一个有穷非空集，集合中的每个元素称为一个状态； （2）∑是一个有穷字母表，∑中的每个元素称为一个输入符号； （3）F是一个从K×∑→K的单值转换函数，即F（R，a）＝Q，（R，Q∈K）表示当前状态为R，如果输入字符a，则转到状态Q，状态Q称为状态R的后继状态； （4）S∈K，是惟一的初态； （5）Z?K，是一个终态集。 由定义可见，确定有限自动机只有惟一的一个初态，但可以有多个终态，每个状态对字母表中的任一输入符号，最多只有一个后继状态。 对于DFA M，若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记符连接形成的字符串可为DFA M所接受。若M的初态结点同时又是终态结点，则称ε可为M所接受（或识别），DFA M所能接受的全部字符串（字）组成的集合记作L（M）。 一个不确定有限自动机（NFA）M可以定义为一个五元组，M＝（K，∑，F，S，Z），其中： （1）k是一个有穷非空集，集合中的每个元素称为一个状态； （2）∑是一个有穷字母表，∑中的每个元素称为一个输入符号； （3）F是一个从K×∑→K的子集的转换函数； （4）S?K，是一个非空的初态集； （5）Z?K，是一个终态集。 由定义可见，不确定有限自动机NFA与确定有限自动机DFA的主要区别是： （1）NFA的初始状态S为一个状态集，即允许有多个初始状态； （2）NFA中允许状态在某输出边上有相同的符号，即对同一个输入符号可以有多个后继状态。即DFA中的F是单值函数，而NFA中的F是多值函数。 因此，可以将确定有限自动机DFA看作是不确定有限自动机NFA的特例。和DFA一样，NFA也可以用矩阵和状态转换图来表示。 对于NFA M，若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记（ε除外）连接形成的字符串可为M所接受。NFA M所能接受的全部字符串（字）组成的集合记作L（M）。 由于DFA是NFA的特例，所以能被DFA所接受的符号串必能被NFA所接受。 设M 1和M 2 是同一个字母集∑上的有限自动机，若L（M 1 ）＝L（M 2 ），则称有 限自动机M 1和M 2 等价。 由以上定义可知，若两个自动机能够接受相同的语言，则称这两个自动机等 价。DFA是NFA的特例，因此对于每一个NFA M 1总存在一个DFA M 2 ，使得L（M 1 ） ＝L（M 2 ）。即一个不确定有限自动机能接受的语言总可以找到一个等价的确定有限自动机来接受该语言。
编译原理实验教案 The Standardization Office was revised on the afternoon of December 13, 2020
实验教学进度表
实验一 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, }) （三）词法分析程序主要算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 注： ①关键字表初值 关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表可处理为一个字符串数组（实际为指向字符数组的指针数组），其描述如下： char *KEY_WORDS[8]= {“main”,”int”,”char”,”if”,”else”,”for”,”while”}; 为分析方便,这里把main作关键字处理。 ②程序中需要用到的主要变量：syn,token和sum。 2．扫描子程序（scaner）的算法思想