编译原理第2讲.

第1讲作业题1.解释下列术语：翻译程序、汇编程序、编译程序、解释程序、源程序、目标程序、编译程序的前端和后端和趟2.编译程序与解释程序的根本区别在于？3.一般来说，编译程序分为哪5个阶段，同这5个阶段都要打交道的是？4.错误处理的主要任务是什么？对下列错误信息，请指出可能是编译的哪个阶段报告的？•Else没有匹配if•数组下标越界•使用的函数没有定义•在数中出现非数字字符5.高级语言书写的源程序只有被或者后才能执行。6.语言处理程序分为、和。习题答案1、翻译程序即语言处理程序，是把以汇编语言或高级语言编写的源程序翻译成机器语言目标程序的工具。2、汇编程序是把汇编语言书写的程序翻译成与之等价的机器语言程序的翻译程序。3、编译程序是将高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言程序)的程序。4、解释程序是把源语言书写的源程序作为输入，对源程序逐条解释，解释一条就提交计算机执行一条，直至执行完整个程序。就像外语翻译中的“同声翻译”一样，说一句翻一句，不产生全文的翻译文本。5、源程序：未经语言处理程序处理的以汇编语言或高级语言编写的程序。6、目标程序：源程序经过语言处理程序处理后翻译成的另一种等价的程序。编译各阶段的分组前端和后端前端依赖于源程序并在很大程度上独立于目标机器。前端与源语言有关，包括词法分析、语法分析、语义分析与中间代码产生，以及相关的错误处理和符号表的建立。源语言中间语言目标语言前端后端后端主要包括代码优化、代码生成和相关错误处理，后端依赖于目标机器。后端处理对象是由前端产生的结果，即中间代码。所谓趟，是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。每趟扫视可完成编译过程中一个阶段或多个阶段的工作。编译程序与解释程序的根本区别在于是否生成目标代码。一般来说，编译程序分为词法分析，语法分析，语义分析和中间代码生成，代码优化，目标代码生成5个阶段，同这5个阶段都要打交道的是符号管理表程序和错误处理器。错误处理的主要任务是：把检测到的错误局部化，尽可能多地编译源程序代码，以便发现更多的错误，有可能的话进行适当的错误校正。对下列错误信息，请指出可能是编译的哪个阶段报告的？•Else没有匹配if（语法分析）•数组下标越界（语义分析）•使用的函数没有定义（语法分析）•在数中出现非数字字符（词法分析）高级语言书写的源程序只有被编译或者解释后才能执行。语言处理程序分为编译程序、汇编程序和解释程序。编译器各阶段源程序：高级程序设计语言词法分析器错误处理器符号管理表语法分析器语义分析器中间代码生成器代码优化器代码生成器词法单元语法分析树中间代码：三地址码或四元式中间代码目标代码：汇编语言或机器语言必要必要必要可选可选可选编译器是分阶段执行的。每个阶段将源程序从一种表示转换成另一种表示第二讲词法分析一、词法分析程序（词法分析器）的功能输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词（词素）符号并添加到符号表中,并用词法单元方式表示识别出的单词，生成并输出一个词法单元序列。同时还可检查出源程序中的词法错误，如拼写错误。源程序词法分析器词法单元序列符号管理表错误处理器输入输出报错一、词法分析程序（词法分析器）的功能=80;eniLLine=80;==;;输入25,Line36,27,8045,输出若标识符词类编码为25，等号词类编码为36，数字常量词类编码为27，分号词类编码为45概念1：单词（词素）•单词是一个程序设计语言的基本字符。保留字是程序语言定义的具有固定含义的英文单词，有时称为关键字或基本字。保留字不能作为变量名或过程名使用。例如：c语言的保留字包括：auto：声明自动变量double：声明双精度变量或函数int：声明整型变量或函数struct：声明结构体变量或函数break：跳出当前循环等•在现今多数程序设计语言中，单词符号一般分为：保留字、标识符、常量、运算符和分界符等概念1：单词（词素）标识符：在编程语言中，标识符是用户编程时用来表示各种名字的字符串例如：C语言标识符由字母（A-Z,a-z）、数字（0-9）、下划线“_”组成，并且首字符不能是数字，但可以是字母或者下划线。例如，正确的标识符：abc，a1，prog_to。概念1：单词（词素）常量：指在程序运行过程中,其值不可改变的量例如：在C语言中,常量分为如下类型整型常量：100、-200、32767字符常量：‘b’、'y'字符串常量：howdoyoudo.,CHINA,a,$123.45浮点型常量：+1.2E+5、1.5e-9、-5.0e10符号常量：在使用之前必须先定义，其一般形式为：#define标识符常量，如：#definePRICE30概念1：单词（词素）运算符：包括算术运算符、关系运算符、逻辑运算符、赋值号和等号等。例如：C语言把除了控制语句和输入输出以外的几乎所有的基本操作都作为运算符处理，包括：指针运算符：*和&求字节数运算符：sizeof强制类型转换运算符：(类型)分量运算符：.-下标运算符：[]其他：如函数调用运算符:()算术运算符：*-+/关系运算符：==!===逻辑运算符：!&&||位运算符：~|^&赋值运算符：=及扩展赋值运算符条件运算符：?:逗号运算符：,概念1：单词（词素）分界符:包括逗号，分号，括号，结束符等分界符请将以下C程序中的词素进行分类？floatmatch0(char*s{if(!strncmp(s,0.0,3))return0;}请将以下C程序中的词素进行分类？floatmatch0(char*s{if(!strncmp(s,0.0,3))return0;}保留字运算符分界符标识符常量floatmatch0(char*s{if!strncmp0.0,3)return0;}一旦语言确定，这三类符号就确定，与具体的程序无关。而且这些符号是有限的。这些符号是变化的。与具体的程序有关。词法分析器在读取源程序的时候，还有一个任务是过滤掉源程序中的注释和空白。–注释：/*tryagain*/–空格：blanks–Tab键：tabs–换行符号：newlines概念2：词法单元（token字）•词法单元：又称记号，由词法分析程序生成的逻辑单元。•词法单元格式：词类编码，词法单元属性值–词类编码：词法单元种别名称。–词法单元属性值:一个可选的属性值,用来区分该类单词中哪一个单词。25,Line词类编码原则:•关键字:所有的关键字分成一类（一类一码）也可以一个关键字分成一类（一字一码）•标识符：所有的标识符分为一类（一类一码）•运算符：一个符号分成一类（一符一码）也可按类型（关系运算、算术运算等），每个类型的运算划分成一类（一类型一码）•分界符:一个符号分成一类（一符一码）•常量：所有的统归为一类（一类一码）也可按类型（整型、实型、布尔型等），每个类型的常数划分成一类（一类型一码）词类编码原则:例：以a=b+c*d为例a、b、c、d都是标识符，统一归为一类可以将＝、＋、*运算符，统一归为一类，也可以赋值运算符=归为一类，算术运算符+、*归为一类一类对应一个编码值例如：某种语言词类编码编码如下表请书写出此段源程序中各单词的词类编码ifi＞jtheni＝0elsej=1ifi＞jtheni＝0elsej=1对应的词类编码如下：词法单元属性值关键字、界符、运算符：属性值通常为空对于关键字（一字一码）、界符和运算符（一符一码）来说，它们的词类编码就可以表示其完整的信息，故对于这类单词，其单词自身的属性值通常为空。标识符：属性常用其在符号表中的入口指针来表示对于标识符（一类一码），词类编码所反映的信息不够充分，标识符的具体特性还要通过单词自身的属性进行互相区分，标识符的单词自身的属性常用其在符号表中的入口指针来表示。常数：属性常用其在常数表中的入口指针来表示对于常数（一类型一码），其单词自身的属性常用其在常数表中的入口指针来表示ifi＞jtheni＝0elsej=1例如：写出下述语句中词法单元的属性值以语句子a=b+c*d为例，假设按表中的单词编码，词法分析后的结果（即：生成并输出一个词法单元序列）为：Token字符号表a=b+c*da2525,36,--------25,32,--------25,b2525,c25d2531,--------生成并输出一个词法单元序列：25,a,36,_,25,b,32,_,25,c,31,_,25,d解题思路提示：根据C++程序设计语言的五种分类对号入座词法分析器的设计思路•按照词法分析程序的任务和作为一个独立子程序的要求来考虑词法分析程序的设计。1、组织源程序的输入5、识别单词，转换成词法单元表示形式3、删除注释行、空格及无用符号2、查填符号表4、检查词法错误词法分析器的设计思路•词法分析的第一任务是输入源程序，过滤掉源程序中的注释和空白。•设计思路：可设计一个预处理子程序，用以完成此项任务。将源程序输入串放在输入缓冲区中，借助预处理子程序过滤掉源程序中的注释和空白，将处理后的源程序输入扫描缓冲区，词法分析器即可对此缓冲区中的字符串进行单词符号的识别。词法分析器的设计•第1步：将源程序语言词素模式用正则表达式描述•第2步：将正则表达式转换成等价的状态转换图（NFA图）•第3步：将NFA图用子集法转换成DFA图•第4步：将DFA图简化为最小化的DFA图•第5步：将最小化的DFA图作为词法分析程序的框图，借助词法分析程序的自动构造工具（如：LEX等）设计词法分析程序正则表达式NFADFAminDFA词法分析程序字母表的概念•程序是语句的集合，而程序语句也是由保留字、变量名、运算符、常量等单词组成，而这些单词又是由一些基本符号（如字母、数字、运算符和标点符号）按一定规则组成。•字母表（alphabet）包含了程序设计语言中所允许的所有符号，是一个有穷的非空符号集合。•例如：二进制语言的字母表是{0,1}英文的字母表是{a……z，A……Z}•字母表通常用希腊字母∑（Sigma）表示。C语言的字母表：最简单的方法：查询C语言用户手册笨办法：自己分析分析思路：从保留字、标识符、常量、运算符和分界符的构成分析C语言的保留字包括：auto，double，int，struct，break，else，long，switch等，都由英文字母构成，而且区分大小写。所以字母表中应该包括{A……Z，a……z}C语言的字母表：C语言的标识符C语言标识符由字母、数字、下划线组成。所以字母表中应该包括{A-Z，a-z}，{0-9}，{_}C语言的常量包括整型常量：100、-200；字符常量：‘b’、‘y’；字符串常量：howdoyoudo.,CHINA,$123.45浮点型常量：+1.2E+5、1.5e-9、-5.0e10所以字母表中应该包括{0-9}，{+，-}，{‘},{“},{A-Z，a-z}，{.},{$}C语言的字母表：C语言把除了控制语句和输入输出以外的几乎所有的基本操作都作为运算符处理，包括：指针运算符：*和&求字节数运算符：sizeof强制类型转换运算符：(类型)分量运算符：.-下标运算符：[]其他：如函数调用运算符:()算术运算符：*-+/关系运算符：==!===逻辑运算符：!&&||位运算符：~|^&赋值运算符：=及扩展赋值运算符条件运算符：?:逗号运算符：,所以字母表中应该包括{*,-,+,/,,,=,&,|,~,?,:,,,(,),.,-,[,,],a-z}C语言的字母表：C语言的分界符包括逗号，分号，括号，结束符等分界符所以字母表中应该包括{，,；,（,），[，]，{，}，#，＄}C语言的字母表是{A-Z，a-z}{0-9}，{+，-}，{‘},{“},{.},{$}{*,-,+,/,,,=,&,|,~,?,:,,,(,),.,-,[,,]}{A-Z，a-z}，{0-9}，{_}{，,；,（,），[，