编译原理总结

1、(1)程序设计语言 机器语言: 由0、1代码构成，不需翻译就可直接执行其程序。 汇编语言: 机器指令助记符（伪代码）形式，汇编后才可执行其程序。 高级程序设计语言: 类自然语言和数学公式形式(2) 基本术语 源程序(Source Program)：用源语言写的程序。源语言可以是汇编语言，也可以是高级程序设计语言。 目标程序(Target Program) ：也称为“结果程序”，是源程序经翻译程序加工以后所生成的程序。目标程序可以用机器语言表示，也可以用汇编语言或其它中间语言表示。 翻译程序(Translating Program)：是指把一个源程序翻译成逻辑上等价的目标程序的程序。源程序为其输

2、入，目标程序为其输出。 汇编程序(Assembler)：是指把一个汇编语言写的源程序转换成等价的机器语言表示的目标程序的翻译程序。 编译程序(Compiler)：若源程序是用高级程序设计语言所写，经翻译程序加工生成目标程序，则该翻译程序就称为“编译程序”，也可称为编译器。 解释程序：是高级语言翻译程序的一种，他将源语言书写的源程序作为输入，解释一句后就提交计算机执行一句，并不形成目标程序，就像外语翻译中的“口译”一样，不产生全文的翻译文本。 运行系统(Running System)：目标程序执行时，需要有一些子程序（如一些连接装配程序及一些连接库等）配合进行工作，由这些子程序组成的一个子程序库

3、称为运行系统。 编译系统(Compiling System)：编译程序和运行系统合称编译系统。(3) 程序的翻译 除机器语言程序外，用其它语言书写的程序都必须经过翻译才能被计算机识别。这一过程由翻译程序来完成。 编译方式是一种分阶段进行的方式，包括翻译和运行两部分。 前一阶段：翻译 后一阶段：运行，由运行系统配合完成。(4) 过程1、词法分析阶段 这个阶段的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词（也称单词符号或符号TOKEN）。 某源程序片断如下：begin var sum, first, count: real; sum:=fir

4、st+count*10 end.保留字begin var real end标识符sum first count sum first count 界符 .逗号， 逗号, 冒号： 分号； 加号+ 乘号* 赋值号：= 整数10102、语法分析阶段 是编译过程的第二个阶段。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等。一般这种语法短语，也称语法单位，或语法成分，或语法范畴。 语法分析所依据的是语言的语法规则，即描述程序结构的规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。 3、语义分析阶段 依据语言的语义规则，对语法分析得到的语法结

5、构分析其含义以及应进行的运算，审查源程序中有无语义错误，为代码生成阶段收集类型信息。4、中间代码生成 在进行了上述的语法分析和语义分析阶段的工作之后，有的编译程序将源程序转变成一种内部表示形式，这种内部表示形式叫做中间代码。所谓“中间代码”是一种结构简单，含义明确的记号系统，这种记号系统可以设计为多种多样的形式。重要的设计原则：一是容易生成；二是容易将它翻译成目标代码。5、代码优化 任务：对前阶段产生的中间代码系列进行变换或改造。目的是使生成的目标代码更高效，即省时间省空间。例如上例四个四元式可优化为下面两个四元式。6、目标代码生成 任务：将中间代码变换成特定机器上的绝对指令代码或可重定位的指

6、令代码或汇编指令代码。它的工作与硬件系统结构和指令含义有关。 7、表格管理编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作；8、出错处理如果编译过程中发现源程序有错误，编译程度应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。(5) 前端与后端参考上面的图，目的是为了在多种源语言和多种目标语言的开发过程中，可以灵活搭配组合，消除重复开发的工作量，提高编译系统的开发效率。(6) 遍所谓遍，是对源程

7、序或源程序的中间形式从头到尾扫视并完成规定任务的过程。 每一遍扫视可完成一个阶段或多个阶段的功能。一遍的编译程序：以语法分析程序为核心 。多遍扫描的优点：可以减少内存容量的需求，分遍后，以遍为单位分别调用编译的各个程序，各遍程序可以相互覆盖。可使各遍的编译程序相互独立，结构清晰。能够进行充分优化，产生高质量的目标程序。可将编译程序分为前端和后端，有利于编译程序的移植。多遍扫描的缺点每遍都要读符号、送符号，增加了许多重复性的工作，降低编译效率。(7) 程序设计语言范型（从支持的计算模式）1. 强制(命令)式语言:是面向动作的，即一个计算过程看做是一系列动作，其动作是命令驱动，以语言形式表示。也称

8、过程式语言，如C,FORTRAN等;2. 函数式语言：注重程序表示的功能也称应用式语言，如ML和LISP等；3. 基于规则的语言：检查一定的使能条件，满足时执行动作也称逻辑程序设计语言，如PROLOG。4. 面向对象语言：提供抽象数据类型，支持封装性、继承性和多态性。如C+和Java等。(1) 符号和符号串1、 字母表：元素的有穷非空集合。2、 符号串：由字母表中的符号组成的任何有穷序列。3、 符号串的头尾，固有头和固有尾：如果z=xy是一符号串，那么x是z的头，y是z的尾，如果x是非空的，那么y是固有尾；同样如果y非空，那么x是固有头。如:设z=abc，那么z的头是e，a, ab, abc,

9、 除abc外，其它都是固有头；z的尾是e, c, bc, abc, z的固有尾是e, c, bc。4、 符号串的运算（1）符号串的连接：设x和y是符号串，x和y的连接xy是把y的符号写在x的符号e后得的符号串。如：x=ST, y=abu, 则xy=STabu 显然有ex=xe=x。（2）符号串的方幂：设x是符号串，把x自身连接n次得x的几次方幂xn。 如：设x=ab则x0=e x1=ab x2=abab x3=ababab（3）符号串集合的乘积：设A和B为符号串集合，则A和B的乘积定义为AB=xy|xÎA且yÎB 如：a=a, b, B=00, 11 则AB=a00, a1

10、1, b00, b11 显然：eA=Ae=A（4）符号串集合的方幂：设A为符号串集，则A的n次方幂An定义为:An=AAA=AAn-1=An-1A（5）符号串集合的正闭包A+：A+=A1 U A2 U U An U （6）符号串集合的闭包A*：A*=A0 U A+ = e U A+如：设有正字母表å=0，1 则å*=å0 U å1 U å2 U U ån U =e, 0, 1, 00, 01, 10, 11, 000, 001,(2) 文法文法G定义为四元组（VN ，VT，P，S）其中:（1）VN 为非终结符号集非终结符号表示一个语言

11、短语（或语法成分、语法单位）。 如 程序、语句、表达式等。一般用大写字母或用 括起表示非终结符号。（2）VT 为终结符号集终结符号：组成语言的基本符号。是文法中不属于非终结符号集合的符号。一般用小写字母或不带 的符号表示。如程序设计语言的单词符号。设V=VN U VT，称V为文法G的字母表。（3）P 为产生式（也称规则）的集合。产生式的形式：ab或a=b，其中aV+，bV*（4）S 称作识别符号或开始符号，是一个非终结符号。一般表示此文法定义的最大语法短语，至少要在一条产生式 中作为左部出现。 句型、句子的定义设GS是一文法，如果符号串x是从识别符号推导出来的，即有SÞ*x， 则称x

12、是文法GS的句型。若x仅由终结符号组成，即SÞ*x, xÎV T ，则称x为GS的句子。句型：在一棵树生长过程的任何时刻，所有那些端末结点自左至右的排列，就是一个句型。语言的定义：文法G产生的语言记为L（G），它是文法G产生的全部句子的集合。文法等价定义：若L（G1）=L（G2）则称文法G1和G2是等价的。(3) 文法的类型 N.Chomsky0型文法：定义0型语言，对应Turing机；1型文法：定义1型语言，对应线性限界自动机；箭头后面的要比前面的长或相等2型文法：定义2型语言，对应非确定下推自动机；箭头前面的是非终结符，后面是串3型文法：定义3型语言，对应有限自动机。非

13、终结符可以推出一个终结符或一个终结符和一个非终结符最右推导也称为规范推导，所得句型称为规范句型。如果一个文法存在某个句型对应两棵不同的语法树，则说这个文法是二义的。或者说，若一个文法中存在某个句型，它有两个不同的最左（最右）推导，则这个文法是二义的。 上下文无关文法是否具有二义性是不可判定的。但有些特殊的2型文法例如LL（1）、LR（0）、LR（1）等文法是无二义性的。 一个文法兼有左递归和右递归是导致二义性的常见原因。排除文法二义性通常有两种方法:（1）在语义上加些限制（2）重新构造一个无二义性的文法 (4) 句型的分析句型的分析：就是识别一个符号串是否为某文法的句型。是某个推导的构造过程。

14、分析方法分两大类：自上而下分析法和自下而上分析法 推导与归约，最右推导是规范推导，逆过程为规范规约 若SÞ*aAdÞ+abd （由AÞ+b得）则称b是句型abd相对于非终结符A的短语。 若SÞ*aAdÞabd (由Ab得)则称b是句型abd相对于Ab的直接短语（也称简单短语）。 一个句型的最左直接短语称为该句型的句柄。一棵子树（至少要有父子两代）的所有端末结点自左至右排列起来形成相对于子树根的短语。若子树只有父子两代，则得到直接短语。 (5) 有关文法（1）有害规则 文法中含形如UU的产生式。它对描述语言没有必要，且会引起文法的二义性。（2）多

15、余规则 文法中任何一个句子的推导都用不到的规则。（3）无用规则 文法中含形如UV的产生式，即单产生式。为保证文法G的任一非终结符A在句子推导中出现，必须满足如下两个条件：（1）A必须在某句型中出现，aAd。（2） 必须能够从A推导出终结符号串t。有关文法的化简和改造，包括以下几项工作：（）无用符号和无用产生式的删除。（） e产生式的消除。（）单产生式的消除。（）左递归的消除。(1) 词法分析输出单词符号（TOKEN) 是一个程序设计语言的基本语法符号。程序设计语言的单词符号一般可分成下列5种：1基本字，也称关键字，如PASCAL语言中的begin，end，if，while和var等。2标识符，

16、用来表示各种名字，如常量名、变量名和过程名等。3常数，各种类型的常数，如25，3.1415，TRUE和"ABC"等。4运算符，如+，*，<= 等。5界符，如逗点，分号，括号等。词法分析程序所输出的单词符号常常采用下二元式表示：（单词种别，单词自身的值）可用整数码或助记符等表示。(2) 单词的描述工具程序设计语言中的单词(TOKEN)是基本语法符号。单词符号的语法可以用有效的工具加以描述。正规式和它所表示的正规集的递归定义如下。设字母表为，辅助字母表 = |, ·, *, (, ) 定义（正规式和它所表示的正规集）：设字母表为，辅助字母表=，|，·，

17、*，(， 。 和都是上的正规式，它们所表示的正规集分别为和 ； 任何a，a是上的一个正规式，它所表示的正规集为a； 假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1), e1|e2, e1·e2, e1*也都是正规式,它们所表示的正规集分别为L(e1), L(e1)L(e2), L(e1)L(e2)和(L(e1)*。 仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。(3) 有穷自动机有穷自动机（也称有限自动机）作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合

18、，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。确定的有穷自动机（DFA）：定义：一确定的有穷自动机（DFA）M是一个五元组： M=（K， ，f, S, Z）其中1K是一个有穷集，它的每个元素称为一个状态；2 是一个有穷字母表，它的每个元素称为一个输入字符，所以也称为输入符号字母表；3f是转换函数，是在K× K上的映像，即，如f(ki,a)= kj, 就意味着，当前状态为ki，输入字符为a时，将转换到下一状态kj，我们把kj称为ki的一个后继状态；4S 是唯一的一个初态；5Z是一个终态集，终态也称可接受状态或结束状态。DFA的作用：对于*中的任何字符串t，

19、若存在一条从初态到某一终态结的道路，且这条路上所有弧的标记符连接成的字符串等于t，则称t可为DFA M所接受，若M的初态结同时又是终态结，则空字可为M所识别。DFA M所能接受的字符串的全体记为L（M）。不确定的有穷自动机（NFA）定义：一个不确定的有穷自动机（NFA）M是一个五元组，M=（K，f, S, Z）。3.f是一个从K×*到K的幂集的映象4.S属于K，是一个非空初态集5.Z属于K，是一个终态集区别：DFA：只有唯一初态。NFA：有初态集。DFA是NFA的特例。对于每个NFA M，存在一个DFA M ，使得L（M）=L（M ）对于任何两个有穷自动机M和M ，如果L（M）=L（

20、M ），则称M与M 是等价的。(1) 自顶向下语法分析语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子。其中自顶向下分析，就是从文法的开始符号出发企图推导出与输入的单词串完全匹配的句子，若输入串是给定文法的句子，则必能推出，反之必然出错。FIRST（a）=a|a Þab, a ÎVT, a, b ÎV*（1）求FIRST（x）， xÎV （a）若xÎVT，则FIRST（x）=x （b）若x是e，则FIRST（x）=e （c）若xÎVN，且xy1y2ym|z1z2zn则FIRST（x）= FIRST(y1y2ym

21、) FIRST(z1z2zn) （2）求FIRST(y1y2ym), 其中 y1, y2, , ymÎV。 （a）若y1ÎVT, 则FIRST（y1y2ym）=y1 （b）若y1ÎVN, e Ï FIRST(y1)，则FIRST（y1y2ym）=FIRST(y1) 若e Î FIRST(y1)，则 FIRST(y1y2ym)=(FIRST(y1)e)FIRST(y2y3ym) 按上法求FIRST（y2y3ym），类推下去。对文法中每一A ÎVN，计算FOLLOW（A）（a） 设S为文法的开始符号，则#ÎFOLLOW（S）（b

22、） 若有AaBb，则将FIRST（b）e加入到FOLLOW（B）中，如果其中b Þe，则将FOLLOW（A）加入到FOLLOW（B）中。计算SELECT集定义：SELECT ( Aa ) =FIRST ( a ),其中a Þe。若a Þe，则SELECT ( Aa ) = (FIRST（a） e) FOLLOW(A)判定LL（1）文法对每个非终结符A的两个不同产生式，Aa，Ab，满足SELECTC（Aa）SELECT（A b ）=f 其中a、b不能同时 Þe (2) 非LL（1）文法到LL（1）文法的等价变换由LL（1）文法的定义可知,若文法中含有直接或

23、间接左递归，或含有左公共因子,则该文法肯定不是LL（1）文法。 参考：文法含左递归不便于使推导按从左往右的顺序匹配，甚至使分析发生死循环。（a）消除直接左递归一般情况下，直接左递归的形式为： AA a1|A a2|A am|b1|b2|bn消除左递归后改写为： Ab1A¢|b2A¢|bnA¢ A¢ a1 A¢| a2 A¢ | | am A¢ | e（b）消除间接左递归先通过产生式的替换，将间接左递归变为直接左递归，然后再消除直接左递归。(3) 确定的自顶向下分析方法1、基本思想 对每一非终结符构造一个过程，每个过程的功能是

24、识别由该非终结符推出的串。2、编写程序 IP：是输入串指示器，开始工作前IP指向串的第一个符号，每个程序工作完后，IP指向下一个未处理符号。 sym：表示IP所指符号。 ADVANCE：是过程，让IP指向下一个符号。 ERROR：是出错处理子程序。(4) 预测分析方法（1）预测分析表M 如下矩阵形式：矩阵M 行标题用文法的非终结符表示。 列标题用文法的终结符号和#表示。 矩阵元素MA, a的内容是产生式Aa（或a）表明当对A进行推导，面临输入符号a时，应采用候选a进行推导。 出错处理标志（即表中空白项）表明A不该面临输入符号a。（2）符号栈 用于存放文法符号，栈顶为推导过程中句型尚未匹配部分的

25、开头符号。 分析开始时，栈底先放一个#，然后放进文法开始符号，即S#（3）预测分析总控程序 总是按栈顶符号x和当前输入符号行事。 对于任何（x,a），总控程序每次都执行下述三种可能动作之一： （a）若x=a=#，则宣布分析成功。 （b）若x=a¹#，则把x从栈顶逐出，指针指向下一输入符号。 （c）若x是一个非终结符，则查看分析表M。 如果MA, a中存放关于X的一个产生式，那么，首先把X顶出栈，然后把产生式右部符号串按反序一一推进栈。 如果MA, a中存放“出错标志”，则调用出错处理程序ERROR。(1) 自底向上优先分析法 自底向上分析方法，也称移进归约分析法，粗略地说它的实现思想

26、是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，（该句柄对应某产生式的右部），就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一步归约。重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。可以看出，移进一归约过程是自顶向下最右推导的逆过程。最右推导称为规范推导。自左向右的归约过程称为规范归约。 如何知道何时在栈顶符号串中已形成某句型的句柄，这是自底向上分析的关键。在自底向上分析方法中，本章主要介绍常用的算符优先分析法和LR类分析法。(2) 算符优先分析法算符文法的定义：设有一文法

27、G，如果G中没有形如ABC的产生式，其中B和C为非终结符，则称G为算符文法（Operater Grammar）也称OG文法。（文法中没有两个非终结符相临的情况，则称是算符文法）性质1 在算符文法中任何句型都不包含两个相邻的非终结符。性质2 如果Ab或bA出现在算符文法的句型g中；其中AÎVN，bÎVT，则g中任何含b的短语必含有A。算符优先文法的定义：设有一不含e产生式的算符文法G，如果对任意两个终结符对a, b之间至多只有<、>和=三种关系的一种成立，则称G是一个算符优先文法。（Operator Precedence Grammar）即OPG文法。(3) 算符

28、优先关系表的构造FIRSTVT（B）=b|BÞb或BÞCb 构造规则： （1）若Bb或BQb，则bÎFIRSTVT(B) （2）若BQ，则FIRSTVT(Q)ÍFIRSTVT（B）LASTVT（B）=a|BÞa或BÞaC构造规则 （1）若Ba或BaQ，则aÎLASTVT(B) （2）若BQ，则LASTVT(Q)ÍLASTVT（B） 最左素短语：设有文法GS，其句型的素短语是一个短语，它至少包含一个终结符，并且除自身外不包含其它素短语，最左边的素短语称最左素短语。(4) 归约步骤初始时栈底存#，输入指针指向输入串的首

29、字符。控制程序根据栈顶终结符a（若栈顶是非终结符，则次栈顶的终结符称为栈顶终结符）和输入指针所指的输入符b，查优先关系表M，可能有四种情况： （1）Ma, b为<或=时移进b，即将b进栈，输入指针指向下一输入符。 （2）Ma, b为>时，则将栈顶含a的素短语按对应的产生式归约，素短语与产生式右部需终结符对应相同，非终结符位置应相同名称可不同。顶出栈中素短语，非终结符入栈。（3）Ma, b为空白，语法错，调用相应出错处理程序。（4）a=b=# 时分析结束。(5) 优先函数用关系法构造。 构造步骤：（a）对每一终结符a（包括#），用fa，ga为结点名。（b）若ai>aj或ai=a

30、j，则从fai到gaj画一条箭弧。若ai<aj或ai=aj，则从gaj到fai画一条箭弧。（c）给每个结点赋一个数，此数等于从该结点出发所能到达的结点（包括该结点自身在内）的个数。赋给结点f (ai)的数，就是函数f(ai)的值，赋给g (aj)的数，就是函数g(aj)的值。（d）对构造出的优先函数，按优先关系矩阵检查一遍是否满足优先关系的条件，若不满足时，则在关系图中有回路说明不存在优先函数。优先函数的优缺点优点：（1）节省存储空间；（2）执行整数比较运算比查优先关系表方便。缺点：（1）有些优先关系表不存在优先函数。（2）原先不存在优先关系的两个终结符变成可比较其函数值大小了，需加以克

31、服。(1) LR分析法LR分析法是一类对上下文无关文法进行“自左向右的扫描和最左归约（即最右推导的逆过程）”分析的方法，是一种规范归约过程。LR(k)分析方法是1965年Knuth提出的，其中k表示向右查看输入符号串的个数。（1）总控程序 所有LR分析器的总控程序都是相同的，共有四种动作：移进、归约、接受、出错。（2）分析表 常见的有四种:LR（0）分析表 适应文法范围小，是其它类型分析表构造的基础。SLR（1）分析表 是LR（0）分析表的改进，适应文法范围强于LR（0）。LR（1）分析表 分析能力强（指适应范围，查错速度），但状态太多。LALR（1）分析表 是LR（1）分析表的改进，分析能力

32、强于SLR而稍弱于LR（1），但状态少于LR（1）（3）分析栈 包括文法符号栈和相应的状态栈。(2) LR(0)分析可归前缀规范句型中，包括句柄及句柄以左的部分，称为可归前缀。有些可归前缀的前缀是相同的，不仅仅属于某一个规范句型。我们把可归前缀的前缀称为活前缀。 进行语法分析时，只要将待分析符号串的当前部分符号与aiPi进行比较，便可知是否归约，以及应按哪条产生式归约。 为了得到所有可归前缀，可以对文法G构造一个有穷自动机，该有穷自动机能识别文法G的所有可归前缀。构造识别可归前缀的有穷自动机项目：文法的识别可归前缀的有穷自动机以文法的“项目”作为它的状态，所谓文法的项目，是在文法的每一条规则的

33、右部添加一个圆点而形成。之所以这样构造项目，是受可归前缀的启发。圆点表示在识别可归前缀的过程中，对句柄（即某产生的右部）已识别过的部分。项目分四类 （a）圆点在最右端的项目，形如Aa·，表示已从输入串看到能由一条产生式右部推导出的符号串，即已达一可归前缀末端，已识别出句柄可以归约，这种项目称为归约项目，相应状态称为归约状态。即为可归前缀识别态 （b）对形如S¢S·的项目，其中S是文法开始符号，称为接受项目，相应状态称为接受状态，表明可由S推导的输入串已全部识别完，整个分析过程成功结束。 （c）对于形如Aa·ab的项目，表明尚未识别一可归前缀，需将a移进符

34、号栈，故称移进项目，相应状态为移进状态。 （d）对于形如Aa·Bb的项目，表明期待分析由B所推出的串归约到B，从而识别B。故称为待约项目，相应状态为待约状态。方法一：首先构造识别可归前缀的NFA，然后将NFA确定化，得DFA（部分）。方法二：根据文法直接构造识别文法可归前缀的DFA。拓广文法 对文法G加一条产生式 S¢S 得 G¢，目的是使开始状态唯一，接受状态易于识别。定义项目集I的闭包CLOSURE(I)a) I的项目均属于CLOSURE( I );b) 若AaBb属于CLOSURE（I）,则每一形如B 的项目也属于CLOSURE（I）;c) 重复b），直到C

35、LOSURE（I）不再增大为止。定义状态转换函数GO（I，X）其中I是项目集，X是文法符号。GO（I，X）=CLOSURE( J )，其中J=任何形如Aaxb的项目|AaxbI，以上可以避免出现 e 弧，避免从同状态射出相同标记弧。构造DFA a) DFA的初态集：CLOSURE(S¢S)b) 对初态集或其它所构造的项目集应用转换函数，GO (I, X) =CLOSURE（J）求出新的项目集。c) 重复b)直到不出现新的项目集为止。DFA中所有状态组成的集合也称为该文法的LR（0）项目集规范族。 构造算法a) 若项目Aa·ab属于Ik且转换函数GO（ Ik, a）=Ij，当

36、a为终结符时则置ACTIONk, a为Sj，其动作含意为将终结符a移进符号栈，状态j进 入状态栈，（即当状态k遇a时转向状态j）。b) 若项目Aa·属于Ik ，则对a为任何终结符或#号，置ACTIONk,a为“rj”，j为在文法G¢中某产生式Aa的序号。rj 动作的含义是把当前文法符号栈顶的符号串a归约为A，且将栈指针从栈顶向下移动|a|的长度（或符号栈中弹出|a|个符号），非终结符A变为当前面临的符号。c) 若GO（Ik, A）= Ij，则置GOTOk, A为 “j”，其中A为非终结符，表示当前状态为“k”时，遇文法符号A时状态应转向j，因此A 移入文法符号栈，j 移入状

37、态栈。d) 若项目S¢S·属于Ik，则置ACTIONk, #为“acc”，表示接受。e) 凡不能用上述方法填入的分析表的元素，均应填上“报错标志”。为了表的清晰我们令在表中用空白表示错误标志。LR（0）分析器的工作过程（1）若ACTION q i , a k = S j ，则将状态 S j , a k 进栈，三元式变化过程:（2）若ACTION q i, a k = r j ，且第 j 条产生式为 A b ，|b| = r ，则按 第 j 条产生式归约。（3）若ACTIONqi, ak=acc 则结束分析，输入串被接受。（4）若ACTIONqi, ak=ERROR 或表中为

38、空白，表示出错，进行相应出错处理。(2) 非LR（0）文法的判断判断方法一： 考察识别文法可归前缀的DFA，若某个状态（即项目集）中既含移进项目又含归约项目；或含不只一个归约项目， 则会发生分析动作的冲突，可知该文法不是LR（0）的。判断方法二： 若文法的LR（0）分析表中含多重定义，即表中某项动作不唯一，则该文法不是LR（0）文法。(3) SLR（1）分析用SLR（1）方法，对于当前状态中的归约项目，如Aa·，必须当前输入符号属于FOLLOW（A）时，才可做归约。有望解决LR（0）方法中的分析动作冲突问题。SLR（1）分析表的构造 将LR（0）分析表构造算法中的 b）改为： 若项目

39、Aa ·属于Ik，则对a为任何终结符或#号，且满足aÎFOLLOW(A)时，置ACTIONk, a为“rj”，j为在文法G¢中某产生式Aa的序号。(4) 非SLR文法的判断判断方法一：对识别文法可归前缀DFA中任一状态下，FOLLOW(B1)FOLLOW(Bn)，两两不相交，否则，文法不是SLR的。只求需要归约Follow集判断方法二：若构造的SLR分析表含多重定义，则文法不是SLR的。(5) LR（1）分析 对某些文法，用SLR（1）方法仍解决不了分析动作的冲突问题，可采取以下措施：若某归约项目Aa · Î I ，当 I 为当前状态，面临当前

40、输入符号a 时，只有a 是在 I 状态下A 的后继符号时 才用 A a 产生式归约，而不是对A的所有后继符号都可以归约。从而有望解决冲突。A a ·，Follow(A) 是向前搜索符，构造项目集是其他与LR(0)相似，只是加上向前搜索符 将LR（0）分析表构造算法中的 b) 中：若项目 A a · 属于Ik ，则对 a 为任何终结符或 # 号，置ACTIONk, a为 rj改为：若项目 Aa·, a 属于Ik ，则置 ACTION k,a = rjLR（k）分析表如果用 LR（1）方法仍不能解决冲突，则可再向前多搜索几个符号，这时的项目为 Aa·b ,

41、a1 a2 ak 称为 LR（k）项目，相应的分析表构造方法类似 LR（1）分析表的构造。(6) LALR（1）分析在LR（1）项目中，有很多状态中的项目除了向前搜索符号不同外，产生式部分是完全相同的，称这样的状态是同心的，为了克服LR（1）分析中状态太多的问题，可以将这些同心集合并。如果合并后得到的新状态没有冲突出现。则按新状态构造分析表。这就是LALR（1）分析法的基本思想。LR(0) LR(1) SLR(1) 这三种文法很重要。(1) 语义处理语义分析：主要检查各种语法成分的语义是否符合语义规定，例如参与运算的表达式类型是否一致，赋值语句的赋值左部和右部类型的一致性，数组元素的维数与数组

42、说明维数的一致性，每一维的下标是否越界，在相同作用域中名字是否被重复说明等。 目前尚无公认的、统一的形式化语义描述工具。但研究者已提出一些针对某些特殊语言的语义描述工具，例如：公理语义、指称语义、代数语义、操作语义等。中间代码生成：对说明语句，通常将其中定义的名字及其属性信息，在符号表中进行登记；对于执行语句，生成语义上等价的中间语言代码。属性文法：一个属性文法，包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每个产生式上。ET1+T2 T1·t=int AND T'2·t=int ET1 or T2 T1·t=bool AND T2

43、3;t=boolTnum T·t=int Ttrue T·t:=bool Tfalse T·t:=bool语法制导翻译：在语法分析过程中，随着分析的步步进展，根据每个产生式对应的语义子程序（或语义规则描述的语义动作）进行翻译的办法称作语法制导翻译。语法制导翻译的具体实现途径：假定有一个LR语法分析器，现在把它的分析栈扩充，使得每个文法符号都跟有语义值，即把栈的结构看成下图所示那样。同时把LR分析器能力扩大，使它不仅执行语法分析任务，且能在用某个产生式进行归约的同时调用相应的语义子程序，完成有关的语义动作。每步工作后的语义值保存在扩充的分析栈里“语义值”栏中。(2)

44、 中间代码形式常见的有逆波兰记号、三元式、四元式和树等。1.逆波兰表示（也称后缀表示）逆波兰表示的特点：（1）运算符紧跟在运算对象的后面出现，没有括号。（2）运算对象出现的顺序（从左到右）和原有顺序（中缀）相同。（3）运算符是按实际运算顺序（从左到右）出现的。逆波兰表示的最大优点是易于计算机处理表达式，使用栈进行运算很方便。可将逆波兰表示形式扩充，用来描述程序设计语言中的其它语法成分。2.三元式表示 三元式的形式为：（op，ARG1，ARG2）其中op为运算符，ARG1为运算对象1，ARG2为运算对象2。三元式出现的先后顺序与表达式的运算顺序一致。三元式的缺点是不便于优化，动一式，其它式子被牵

45、动，使用间接三元式，可以克服这个缺点。间接三元式：使用二个表（1）三元式：存放不相同的三元式（2）运算顺序表（也叫间接码表）：按运算的先后顺序列出有关三元式在三元式表中的位置。 3.树形表示 三元式表示也可用相应的树形表示。 简单变量或常量的树就是该变量或常量本身，如果表示表达式e1和e2的树为T1和T24.四元式：表示形式（op; ARG1, ARG2, RESULT）四元式表示较利于代码优化。(3) 简单赋值语句翻译（1） 语义变量，表示变量即标识符字符串。（2）E. place 语义变量，表示存放E值的变量名在符号表中的入口位置或一整数码（临时变量）。（3）Lookup(i

46、d. name)语义过程(函数），对查符号表，若找到，则返回其在符号表中的位置，否则返回nil，体现先定义后使用的原则。（4）GEN(op, ARG1, ARG2, RESULT)语义过程(函数）,生成四元式，填进四元式表。（5）newtemp 语义过程，生成一临时变量Ti。(4) 布尔表达式的翻译布尔表达式的翻译是指转换成最终能计算出该表达式的结果为真或假（1 或0）的四元式序列的过程。Eg. a or b and not c 的四元式序列为： (1) t1:=not c(2) t2 :=b and t1(3) t3 :=a or t2(1) 控制语句的代码结构 真出口E.tr

47、ue 假出口E.false(2) “回填”技术 控制语句中布尔表达式翻译成四元式序列时，有的转移地址不能在产生这些四元式的同时得知，需要在适当的时候回填这个地址。(3) “拉链”技术 为了记录需要回填地址的四元式，常采用“拉链”技术。把需回填E.true 的四元式拉成一条链，称为“真”链；把需回填E.false的四元式拉成一条链，称为“假”链。 (5) 控制结构的翻译for 循环语句的文法及其相应的语义动作第八章 错误的诊查与校正对于源程序，由于种种原因，往往含有或多或少的错误，因此，一个好的编译程序应具有较强的查错和改错能力。1、语法错误 指程序结构、单词和拼写不符合语法要求的规则。都是在词

48、法分析阶段和语法分析阶段发现的。 如 关键字拼写错误;某些语法成分未按语言的语法规则编写等。 2、语义错误 指程序不符合语义规则或超越具体计算机系统的限制。包括以下几种类型: 说明错：对变量未说明就引用，某些量被重复说明，或不符合有关作用域的规定。 类型不相容错：某些运算的操作数的类型不相容，形一实参在种属或类型上不相对应等。 对某些值超越限制错：如对各类变量数值范围的限制；对数组维数、形参个数、循环嵌套数的限制。 另外，我们将在编译阶段就能发现的错误，称为静态错;到目标代码运行时才能发现的错误称为动态错，如溢出，动态数组的下标越界。出错处理主要有两种处理方法：1、校正法 试图对错误进行校正。

49、 当编译程序发现错误时，给用户指出错误的性质、错误的位置，以及如何校正等方面的信息。2、局部化法 当发现错误时，跳过错误所在的语法单位，继续往下分析。以便把错误限制在尽可能小的局部范围内。只需给用户报告出错误位置，出错性质即可。一些语义错误的处理：1、遏止株连错误 株连错误：由于第一次错误，而派生出后面若干额外错误。只要消除第一个错误，后面若干错误也就自动消失。 遏止方法：第一次发现是标识符引起错误时，输出出错信息，并用一个“正确”的标识符代替它，并把此新的标识符填进符号表，尽可能正确地填入各种属性且加上标记。 以后发现一个引起错误的标识符时，查看符号表中相应登记项，如果它已被标记，则不再打印

50、出错信息。2、遏止重复错误 重复错误：一种错误，发现n次，报n次错。 如：x未被说明，程序中出现n次，则n次报x未被说明。 遏止方法： 设出错标识符为x 1、若x未经说明，则将x填入符号表，并填入鉴别出的属性。 2、若x已被说明，则查错误类表。 如果表中没有同类错误，则输出出错信息，并填进错误类表中。 如果表中有同类错误，则不输出错误信息。第九章 符号表符号表的作用 编译程序在词法分析到代码生成的各阶段，不断地积累和更新表中的信息，并按各自的需要从表中获取信息。符号表的功能归结为以下三个方面：1、收集符号属性 在分析语言程序中标识符说明部分时，编译程序根据说明信息收集有关标识符的属性，并在符号

51、表中建立符号的相应属性信息。如PL/0语言编译的符号表。2、上下文语义的合法性检查的依据 通过符号中属性记录可检查标识符属性在上下文中的一致性和合法性。如：是否未说明就引用，说明与引用，其属性、类型是否一致。是否有重复定义。运算量间运算类型是否一致等。3、作为目标代码生成阶段地址分配的依据 源程序中的变量在目标代码生成时需要确立其在存储分配的位置（主要是相对位置）。而地址分配主要根据变量的类型，在源程序中被说明的位置。 如在第几层分程序，是静态区还是动态区等，分配其在相应数据区中的相对地址，而这些地址分配的依据都是作为变量的语义信息被收集在该变量的符号表属性中。符号表的内容：1、符号名源程序中

52、一个标识符可以是一个变量名、常量名、函数名或过程名，登记在符号表中，通常把一个标识符在符号表中的位置（通常是一个整数）称之为该标识符的内部代码，从而取代该标识符。2、符号的类型信息符号的种类：如常量、变量、数组、标号、函数或过程等，符号的类型，如整型、实型、字符型、布尔型等。数组：应包括维数、上下界、计算下标地址时涉及的常量等，放在数组信息向量表即内情向量表中，用于确定存储分配时所占空间，确定数组元素的位置。过程或函数：应包括参数的个数、类型、排列次序等用来作调用过程的匹配处理和语义检查。记录结构：应包括其成员的类型、个数、排列次序等信息。以便确定结构型变量应分配的空间及结构成员的位置。3、符

53、号变量的存储分配信息存储类别：如全局量还是局部量，静态存储变量，还是动态存储变量等，作为存储分配的依据。地址表示：简单变量或常量，一般是该量在数据区所占单元的绝对或相对地址。数组，是该数组在数据区中的首地址，过程或函数，是该过程或函数的分程序入口地址。4、层次信息对于分程序嵌套或过程嵌套结构型程序设计语言，还应包括每个标识符所属分程序（过程）的层次。符号表的组织： 符号表的组织直接关系到语义功能的实现和语义处理的时空效率，关于符号表的组织可从符号表的总体组织和表项属性信息组织来分别讨论。1、符号表的总体组织第一种：按照属性完全相同的那些符号组织在一起。第二种：把语言中的所有符号都组织在一张符号

54、表中。 优点：总体管理集中单一。缺点：若各表项相等，则增加了无用的属性空间，从而增加了空间开销。 若各表项不等长，则增加 了对符号表管理的复杂度。第三种：折中方式 根据符号属性相似程度分类组织成若干张表，使管 理复杂性及时空效率方面都取得折中的效果。2、符号表项的排列：在编译程序的整个工作中，符号表被频繁地用来建立表项，找查表项，填充和引用表项的属性，因此表项的排列组织对该系统运行的效率起着十分重要的作用。传统上采用三种构造方法:（1）线性组织（按其出现顺序）表项按它的符号被扫描到的先后顺序建立。线性组织管理简单但运行效率低。适用于事先能确定符号个数且符号个数不大时。（2）排序组织及二分法（a

55、bcd排列）表项按其符号的字符代码串的值的大小排列。关于表项的建立和查找通常采用二分法。排序表的运行效率比线性表高，算法复杂性也高于线性表。（3）散列组织 表项位置是由对表项的符号值（即字符代码串）进行某种函数操作（通常称为“杂凑”）所得到的函数值来确定的，这种函数通常被称为杂凑函数。 符号表的散列组织具有较高的运行效率，因而绝大多数编译程序中的符号表采用散列组织。3、关键字域的组织： 在编译程序中，符号表的关键字域就是符号本身。也称名字域。（1）等长关键字段 可设置关键字段为标识符的最大长度。由于程序中的标识符不会总是使用很长的拼写字，关键字段的这种组织方式在实际使用中会有很多空间是冗余的。（2）关键字池的索引结构 符号表中关键字段是指针，指向该关键字在池中的位置，4、其它域的组织 符号表属性域的组织，根据属性性质大致分成两类：一类是符号表中符号的该属性值具有相同的类型且是等长的，则该属性域的类型结构就可用这个长度及类型来定义。 另一类属性值