编译原理复习陆筱霞.ppt

编译原理复习课,陆筱霞 公共邮箱：zzti_soft 密码：soft_zzti,第一章 引 论,一. 什么是编译程序,翻译程序 把某一种语言程序(称为源语言程序)等价地转换成另一种语言程序(称为目标语言程序)的程序,一. 什么是编译程序,编译程序(compiler) 把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言程序)的程序 诊断编译程序 优化编译程序 交叉编译程序 可变目标编译程序,一. 什么是编译程序,解释程序 把源语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身,二. 编译过程,编译程序的工作一般分为五个阶段: 词法分析 语法分析 中间代码产生 优化 目标代码产生,1. 词法分析,任务: 输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号。 依循的原则：构词规则 描述工具：有限自动机 FOR I := 1 TO 100 DO 保留字 标识符 等符 整常数 保留字 整常数 保留字,2. 语法分析,任务:在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。 依循的原则：语法规则 描述工具：上下文无关文法 Z := X + 0.618 * Y 算术表达式，赋值语句,3. 中间代码产生,任务:对各类不同语法范畴按语言的语义进行初步翻译。 依循的原则：语义规则 中间代码:三元式，四元式，树形结构等 Z:=X + 0.618 * Y 翻译成四元式为 (1) * 0.618 Y T1 (2) + X T1 T2 (3) := T2 _ Z,4. 优化,任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码。 依循的原则：程序的等价变换规则,5. 目标代码产生,任务: 把中间代码变换成特定机器上的目标代码。 依赖于硬件系统结构和机器指令的含义 目标代码三种形式: 绝对指令代码: 可直接运行 可重新定位指令代码: 需要连接装配 汇编指令代码: 需要进行汇编,三. 编译程序结构,编译程序总框,词法分析器,语法分析器,语义分析与中间代码生成器,优化段,表 格 管 理,出 错 处 理,目标代码生成器,2. 表格和表格管理,常见的表格:符号名表，常数表，标号表，入口名表，过程引用表。 格式:,名字,信息,3. 出错处理,出错处理程序：发现源程序中的错误，把有关错误信息报告给用户 语法错误 语义错误,4. 遍(pass),所谓“遍“， 就是对源程序或源程序的中间表示从头到尾扫描一次。 阶段与遍是不同的概念。一遍可以由若干段组成，一个阶段也可以分若干遍来完成。,5. 编译前端与后端,编译前端：与源语言有关，如词法分析，语法分析，语义分析与中间代码产生，与机器无关的优化 编译后端：与目标机有关，与目标机有关的优化，目标代码产生 优点：减少对内存容量的要求，程序逻辑结构清晰; 优化更充分，有利于移植。 不足: 编译程序运行的效率低,前端,后端,第二章 高级语言及其语法描述,一. 语法,程序本质上是一定字符集（称为字母表）上的字符串（有限序列）。 语法：一组规则，用它可以形成和产生一个合式(well-formed)的程序。 规则的一部分称为词法规则，另一部分称为语法规则（或产生式规则）。,语 法,词法规则：单词符号的形成规则。 单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界符等。 描述工具：有限自动机 语法规则：语法单位的形成规则。 语法单位通常包括：表达式、语句、分程序、过程、函数、程序等; 描述工具：上下文无关文法,语义,语义：一组规则，用它可以定义一个程序的意义。 描述方法： 自然语言描述：隐藏错误、二义性和不完整性 形式描述： 操作语义(PL/1) 指称语义(ADA) 代数语义(PASCAL),2.3 程序语言的语法描述,几个概念: 考虑一个有穷 字母表 字符集 其中每一个元素称为一个字符 上的字(也叫字符串) 是指由中的字符所构成的一个有穷序列 不包含任何字符的序列称为空字，记为 用*表示上的所有字的全体,包含空字 例如: 设 =a， b，则 *=,a,b,aa,ab,ba,bb,aaa,. 即 是空集，表示一个不含任何元素的集合。,*的子集U和V的连接（积）定义为 UV | U & V 设： U a, aa V b, bb 那么： UV= ab, abb, aab, aabb,V自身的 n次积记为 Vn=VVV 规定V0=，令 V*=V0V1V2V3 称V*是V的闭包; 记 VVV* ，称V+是V的正规闭包。 闭包V*中每个符号串都是由V中的符号串经有限次连接而成的。,2.3.1 上下文无关文法,文法： 描述语言的语法结构的形式规则,上下文无关文法的定义： 一个上下文无关文法G是一个四元式 G=(VT，VN，S，P)，其中 VT：终结符集合(非空) VN：非终结符集合(非空)，且VT VN= S：文法的开始符号，SVN P：产生式集合(有限)，每个产生式形式为 P， PVN， (VT VN)* 开始符S至少必须在某个产生式的左部出现一次。,定义：称A直接推出，即 A 仅当A 是一个产生式， 且， (VT VN)* 。 如果1 2 n，则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n 。 对文法G(E)： E i | E+E | E*E | (E) E (E) (E+E) (i+E) (i+i),通常，用 表示：从1出发，经过一步或若干步，可以推出n。,用 表示：从1出发，经过0步或若干步，可以推出n。,从一个句型到另一个句型的推导往往不唯一。 E+Ei+Ei+i E+EE+ii+i 最左推导：任何一步 都是对中的最左非终结符进行替换。 最右推导：任何一步 都是对中的最右非终结符进行替换。 规范推导、规范规约,定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。 G(E)： E i|E+E|E*E|(E) 是二义文法。 语言的二义性：一个语言是二义性的，如果对它不存在无二义性的文法。 可能存在G和G，一个为二义的，一个为无二义的。但L(G)=L(G) 二义性问题是不可判定问题，即不存在一个算法，它能在有限步骤内，确切地判定一个文法是否是二义的。 可以找到一组无二义文法的充分条件。,2.3.3 形式语言鸟瞰,Chomsky于1956年建立形式语言体系，他把文法分成四种类型：0，1，2，3型。,0型(短语文法，图灵机)： 产生式形如： 其中： (VT VN)*且至少含有一个非终结符； (VT VN)* 1型(上下文有关文法，线性界限自动机)： 产生式形如： 其中：| |，仅 S 例外。,2型(上下文无关文法，非确定下推自动机)： 产生式形如： A 其中：A VN； (VT VN)*。 3型(正规文法，有限自动机)： 产生式形如： A B 或 A 其中： VT*；A，BVN 产生式形如： A B 或 A 其中： VT*；A，BVN,右线性文法,左线性文法,第三章 词法分析,词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。 词法分析器(Lexical Analyzer) 又称扫描器(Scanner)：执行词法分析的程序,3.1 对于词法分析器的要求,一、词法分析器的功能和输出形式 功能:输入源程序、输出单词符号 单词符号的种类： 基本字(保留字)：如 begin，repeat， 标识符表示各种名字：如变量名、数组名和过程名 常数：各种类型的常数 运算符：+，-，*，/， 界符：逗号、分号、括号和空白,输出的单词符号的表示形式: (单词种别，单词自身的值) 单词种别通常用整数编码表示。 若一个种别只有一个单词符号，则种别编码就代表该单词符号。假定基本字、运算符和界符都是一符一种。 若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值(单词符号的属性信息)。 标识符单列一种；标识符自身的值表示成按机器字节划分的内部码。 常数按类型分种；常数的值则表示成标准的二进制形式。,三、状态转换图,1 概念 状态转换图是一张有限方向图。,结点代表状态，用圆圈表示。,状态之间用箭弧连结，箭弧上的标记(字符)代表射出结状态下可能出现的输入字符或字符类。,一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态。,识别标识符的状态转换图,1,2,3,字母,其他,字母或数字,*,识别整常数的状态转换图,一个状态转换图可用于识别(或接受)一定的字符串。,单词的描述工具,程序设计语言中的单词是基本语法成分。单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，实现词法分析程序的自动构造。,正规表达式是典型的词法规则描述工具。,3.3.1 正规式和正规集,正规集可以用正规表达式（简称正规式）表示。 正规表达式是表示正规集一种方法。一个字集合是正规集当且仅当它能用正规式表示。,正规式也称正则表达式（regular expression），是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的数学工具。我们用以描述单词符号。,正规式和正规集的递归定义： 对给定的字母表 1) 和都是上的正规式，它们所表示的正规集为和; 2) 任何a ，a是上的正规式，它所表示的正规集为a ;,3) 假定e1和e2都是上的正规式，它们所表示的正规集为L(e1)和L(e2)，则 i) (e1|e2)为正规式，它所表示的正规集为L(e1)L(e2)， ii) (e1.e2)为正规式，它所表示的正规集为L(e1)L(e2)， iii) (e1)*为正规式，它所表示的正规集为(L(e1)*， 仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式表示的字集才是上的正规集。,所有词法结构一般都可以用正规式描述。 若两个正规式所表示的正规集相同，则称这两个正规式等价。如 b(ab)*=(ba)*b (a*b*)*=(a|b)*,L( (ba)*b) = L(ba)*) L(b) = (L(ba)*L(b) = (L(b)L(a)* L(b) = ba* b = , ba, baba, bababa, b = b, bab, babab, bababab, ,L(b(ab)*) = L(b)L(ab)*) = L(b) (L(ab)* = L(b) (L(a)L(b)* =b ab* = b , ab, abab, ababab, = b, bab, babab, bababab, , L(b(ab)*)= L( (ba)*b) b(ab)*=(ba)*b,3.3.2 确定有限自动机(DFA),对状态图进行形式化，则可以下定义： 自动机M是一个五元式M=(S, , f, S0, F),其中： 1. S: 有穷状态集， 2. ：输入字母表(有穷)， 3. f: 状态转换函数，为SS的单值部分映射，f(s，a)=s表示：当现行状态为s，输入字符为a时，将状态转换到下一状态s。我们把s称为s的一个后继状态。 4. S0S是唯一的一个初态； 5 FS ：终态集(可空)。,DFA可以表示为状态转换图。假定DFA M含有m个状态和n个输入字符，那么，这个图含有m个状态结点，每个结点顶多含有n条箭弧射出，且每条箭弧用上的不同的输入字符来作标记。,对于*中的任何字，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于，则称为DFA M所识别(接收) DFA M所识别的字的全体记为L(M)。 可以证明：上的字集V*是正规集，当且仅当存在上的DFA M，使得VL(M)。,3.3.3 非确定有限自动机(NFA),定义：一个非确定有限自动机(NFA) M是一个五元式M=(S, , f, S0, F)，其中： 1 S: 有穷状态集； 2 ：输入字母表(有穷)； 3 f: 状态转换函数，为S*2S的部分映射(非单值)； 4 S0S是非空的初态集； 5 F S ：终态集(可空)。,从状态图中看NFA 和DFA的区别： 1 弧上的标记可以是*中的一个字，而不一定是单个字符； 2 同一个字可能出现在同状态射出的多条弧上。 DFA是NFA的特例。,1. 假定NFA M=，我们对M的状态转换图进行以下改造： 1) 引进新的初态结点X和终态结点Y，X,YS， 从X到S0中任意状态结点连一条箭弧， 从F中任意状态结点连一条箭弧到Y。 2) 对M的状态转换图进一步施行替换，其中k是新引入的状态。,证明:,加入新初态和新终态的目的是让转换图中初态和终态唯一。 任意表示状态集合中的所有节点都应该与新加入节点间有弧相连。,代之为,代之为,代之为,按下面的三条规则对V进行分裂:,逐步把这个图转变为每条弧只标记为上的一个字符或，最后得到一个NFA M，显然L(M)=L(M),2. 把上述NFA确定化采用子集法.,设I是的状态集的一个子集，定义I的-闭包-closure(I)为: i) 若sI，则s-closure(I)； ii) 若sI，则从s出发经过任意条弧而能到达的任何状态s都属于-closure(I) 即 -closure(I)=Is|从某个sI出发经过任意条弧能到达s,设a是中的一个字符，定义 Ia= -closure(J) 其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。,确定化的过程: 不失一般性，设字母表只包含两个a和b，我们构造一张表:,首先，置第1行第1列为-closure(X)求出这一列的Ia，Ib； 然后，检查这两个Ia，Ib，看它们是否已在表中的第一列中出现，把未曾出现的填入后面的空行的第1列上，求出每行第2，3列上的集合. 重复上述过程，知道所有第2，3列子集全部出现在第一列为止。,现在把这张表看成一个状态转换矩阵，把其中的每个子集看成一个状态。 这张表唯一刻划了一个确定的有限自动机M，它的初态是-closure(X) ，它的终态是含有原终态Y的子集。 不难看出，这个DFA M与M等价。,3.3.4 正规文法与有限自动机的等价性,定理： 1.对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机(FA) M，使得L(M)L(G)。 2.对每一个FA M，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)L(GR)L(GL)。,了解转换过程： 1. 对每一个右线性正规文法G或左线性正规文法G，都构造一个有限自动机（FA） M，使得L(M)L(G)。 (1) 设右线性正规文法G=。将VN中的每一非终结符号视为状态符号，并增加一个新的终结状态符号f，fVN。 令M=，其中状态转换函数由以下规则定义：,(a) 若对某个AVN及aVT，P中有产生式Aa，则令(A,a)=f (b) 对任意的AVN及aVT，设P中左端为A，右端第一符号为a的所有产生式为： AaA1|aAk （不包括Aa）， 则令(A,a)=A1,Ak。 显然，上述M是一个NFA。,对于右线性正规文法G，在S w的最左推导过程中: 利用AaB一次就相当于在M中从状态A经过标记为a的箭弧到达状态B（包括a=的情形）; 在推导的最后，利用Aa一次则相当于在M中从状态A经过标记为a的箭弧到达终结状态f（包括a=的情形）。 综上，在正规文法G中，S w的充要条件是：在M中，从状态S到状态f有一条通路，其上所有箭弧的标记符号依次连接起来恰好等于w，这就是说，wL(G)当且仅当wL(M)，故L(G)L(M)。,(2) 设左线性正规文法G=。将VN中的每一符号视为状态符号，并增加一个初始状态符号q0，q0VN。 令M=，其中状态转换函数由以下规则定义： (a) 若对某个AVN及aVT，若P中有产生式Aa，则令(q0,a)=A (b) 对任意的AVN及aVT，若P中所有右端第一符号为A，第二个符号为a的产生式为： A1Aa, , AkAa， 则令(A,a)=A1,Ak。 与(1)类似，可以证明L(G)L(M)。,3.3.5 正规式与有限自动机的等价性,定理： 1. 对任何FA M，都存在一个正规式r，使得L(r)=L(M)。 2. 对任何正规式r，都存在一个FA M，使得L(M)=L(r)。 对转换图概念拓广，令每条弧可用一个正规式作标记。(对一类输入符号),证明： 1 对上任一NFA M，构造一个上的正规式r，使得L(r)=L(M)。 首先，在M的转换图上加进两个状态X和Y，从X用弧连接到M的所有初态结点，从M的所有终态结点用弧连接到Y，从而形成一个新的NFA，记为M，它只有一个初态X和一个终态Y，显然L(M)=L(M)。 然后，反复使用下面的一条规则，逐步消去的所有结点，直到只剩下X和Y为止；,代之为,代之为,代之为,对一个DFA M最少化的基本思想: 把M的状态集划分为一些不相交的子集，使得任何两个不同子集的状态是可区别的，而同一子集的任何两个状态是等价的。最后，让每个子集选出一个代表，同时消去其他状态。,具体做法: 对M的状态集进行划分 首先，把S划分为终态和非终态两个子集，形成基本划分。 假定到某个时候，已含m个子集，记为=I(1)，I(2)，I(m)，检查中的每个子集看是否能进一步划分: 对某个I(i)，令I(i)=s1,s2, ,sk，若存在一个输入字符a使得Ia(i) 不会包含在现行的某个子集I(j)中，则至少应把I(i)分为两个部分。,自上而下分析,第四章 语法分析,4.1 语法分析器的功能,语法分析的任务是分析一个文法的句子结构。 语法分析器的功能：按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子(合式程序)。,4.2 自上而下分析面临的问题,自上而下就是从文法的开始符号出发，向下推导，推出句子。 带“回溯”的 不带回溯的递归子程序(递归下降)分析方法。 自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号(根结点)出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。,当某个非终结符有多个产生式候选时，可能带来如下问题: 1. 分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时，不得不“回溯”。 2. 文法左递归问题。一个文法是含有左递归的，如果存在非终结符P,含有左递归的文法将使自上而下的分析陷入无限循环。,结论 左递归和回溯问题的产生直接与描述语言的文法有关。 因此，要对文法进行确定的自顶向下分析应该改造文法，使其不含左递归和回溯。,4.3.1 左递归的消除,直接消除见诸于产生式中的左递归：假定关于非终结符P的规则为 PP | 其中不以P开头。 我们可以把P的规则等价地改写为如下的非直接左递归形式： PP PP|,左递归变右递归,一般而言，假定P关于的全部产生式是 PP1 | P2 | | Pm | 1 | 2|n 其中，每个都不等于，每个都不以P开头 那么，消除P的直接左递归性就是把这些规则改写成： P1P | 2P | | nP P1P | 2P | | mP | ,左递归变右递归,消除左递归的算法: 1. 把文法G的所有非终结符按任一种顺序排列成P1，P2，Pn；按此顺序执行； 2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如PiPj的规则改写成 Pi1|2|k ; (其中Pj1|2|k是关于Pj的所有规则) 消除关于Pi规则的直接左递归性 END 3. 化简由2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。,4.3.2 消除回溯、提左因子,为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。 A 1 | 2 | | n,令G是一个不含左递归的文法，对G的所有非终结符的每个候选定义它的终结首符集FIRST()为：,特别是，若 ，则规定FIRST()。,如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选 i和 j FIRST(i)FIRST( j) 当要求A匹配输入串时，A就能根据它所面临的第一个输入符号a，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含a的。,提取公共左因子: 假定关于A的规则是 A 1 | 2 | | n | 1 | 2 | | m (其中，每个 不以开头) 那么，可以把这些规则改写成 AA | 1 | 2 | | m A 1 | 2 | | n 经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。,当A面临输入符a时, 若aFIRST(A)且FIRST(A), 则考虑自动匹配问题。 对于上述算术表达式文法,若输入串为i/i, 即使让T自动匹配, “/”仍不能与后面符号匹配, 此时没必要让T自动匹配。,结论: 只有在当前输入符能与A后的第一个终结符匹配成功时,才让A自动得到匹配。这就要求分析前先求出紧跟在A后的终结符, 即FOLLOW(A)。,假定S是文法G的开始符号，对于G的任何非终结符A，我们定义,特别是，若 ，则规定 FOLLOW(A),4.3.3 LL(1)分析条件,即FOLLOW(A)是所有句型中紧跟在A之后的终结符 或 # 。,自动匹配条件 当A面临输入符a时,若aFIRST(A)且FIRST(A), 则只有当aFOLLOW(A)时,才使A自动得到匹配。缺少任一条件,均不自动匹配。,若输入符aFIRST(A)且aFOLLOW(A), 则当FIRST(A)时仍可能需进行试探(回溯)。因此,对于存在-生成式的非终结符A,若要进行不带回溯的自上而下分析,则FIRST(A)与FOLLOW(A)应互不相交。,构造不带回溯的自上而下分析的文法条件 1. 文法不含左递归， 2. 对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若 A 1| 2| n 则 FIRST( i)FIRST( j) (ij) 3. 对文法中的每个非终结符A，若它存在某个候选首符集包含，则 FIRST( i)FOLLOW(A)= i=1,2,.,n 如果一个文法G满足以上条件，则称该文法G为LL(1)文法。,对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假设要用非终结符A进行匹配，面临的输入符号为a，A的所有产生式为 A 1 | 2 | | n 1. 若aFIRST( i)，则指派 i执行匹配任务； 2. 若a不属于任何一个候选首符集，则： (1) 若属于某个FIRST(i )且 aFOLLOW(A)， 则让A与自动匹配。 (2) 否则，a的出现是一种语法错误。,对每一文法符号XVTVN构造FIRST(X) 连续使用下面的规则，直至每个集合FIRST不再增大为止： 1. 若XVT，则FIRST(X)X。 2. 若XVN，且有产生式Xa，则把a加入到FIRST(X)中；若X也是一条产生式，则把也加到FIRST(X)中。,3. 若XY是一个产生式且YVN，则把FIRST(Y)中的所有非-元素都加到FIRST(X)中； 若XY1Y2Yk是一个产生式，Y1，Yi-1都是非终结符，而且，对于任何j，1ji-1，FIRST(Yj)都含有(即Y1Yi-1)， 则把FIRST(Yi)中的所有非-元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有，j1，2，k，则把加到FIRST(X)中。,对于文法G的每个非终结符A构造FOLLOW(A)的办法是，连续使用下面的规则，直至每个FOLLOW不再增大为止： 1. 对于文法的开始符号S，置于FOLLOW(S)中； 2. 若AB是一个产生式，则把FIRST()加至FOLLOW(B)中；,3. 若AB是一个产生式，或AB是一个产生式而 (即FIRST()， 则把FOLLOW(A)加至FOLLOW(B)中。,4.4 递归下降分析程序构造,递归下降分析法也称递归子程序法，是一种直观易于构造的自顶向下分析方法。分析过程则通过自上而下一级一级地调用子程序来实现，所以称为递归下降分析法。 思想:对文法中的每个非终结符编写一个处理子程序，处理子程序的代码结构由相应的非终结符的规则右部来决定：规则右部的终结符号与输入符号相匹配，非终结符与相应的子程序调用相对应，非终结符对应的各个候选式与分支结构相对应。,构造不带回溯的自上而下分析器 分析程序由一组递归过程组成，文法中每个非终结符对应一个过程；所以这样的分析程序称为递归下降分析器。(因为文法的定义通常是递归的) 几个全局过程和变量： ADVANCE，把输入串指示器IP指向下一个输入符号，即读入一个单字符号 SYM，IP当前所指的输入符号 ERROR，出错处理子程序,每个非终结符有对应的子程序的定义，首先在分析过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。,4.5 预测分析程序,预测分析程序或LL(1)分析法： 总控程序 分析表 MA，a矩阵，A VN ，a VT 是终结符或， 分析栈 STACK 用于存放文法符号,二、分析表MA，a的构造,构造FIRST()和FOLLOW(A) 构造分析表MA，a,在对文法G的每个非终结符A及其任意候选都构造出FIRST()和FOLLOW(A)之后，现在可以用它们来构造G的分析表MA，a。 1. 对文法G的每个产生式A执行第2步和第3步； 2. 对每个终结符a FIRST()，把A加至MA，a中； 3. 若FIRST()，则对任何bFOLLOW(A)把A加至MA，b中。 4. 把所有无定义的MA，a标上“出错标志”。,第五章 语法分析,自下而上分析,语法分析的方法： 自下而上分析法(Bottom-up) 基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。 算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。 LR分析法：规范归约,5.1.2 规范归约,定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有 且,则称是句型相对于非终结符A的短语。 特别是，如果有A,则称是句型相对于规则A 的直接短语。一个句型的最左直接短语称为该句型的句柄。,把上例倒过来写，则得到： S aAcBe aAcde aAbcde abbcde 显然这是一个最右推导。 规范归约是一个最右推导的逆过程 最左归约 规范推导 由规范推导推出的句型称为规范句型。,首先必须定义任何两个可能相继出现的终结符a与b (可能中间有VN), 的优先关系 三种关系 ab a的优先级高于b 注意：与数学上的,=不同 a a,算符优先分析法,5.2.1 算符优先文法及优先表构造,一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部： QR 则我们称该文法为算符文法。 约定： a、b代表任意终结符； P、Q、R代表任意非终结符； 代表由终结符和非终结符组成的任意序列，包括空字。,假定G是一个不含-产生式的算符文法。对于任何一对终结符a、b，我们说： 1. a b 当且仅当文法G中含有形如Pab或PaQb的产生式；,3. a b 当且仅当G中含有形如PRb的产生式，而 R a或R aQ。,2. a b 当且仅当G中含有形如PaR的产生式， 而R b或R Qb；,如果一个算符文法G中的任何终结符对(a，b)至多只满足下述三关系之一： a b 则称G是一个算符优先文法。,从算符优先文法G构造优先关系表的算法。 通过检查G的每个产生式的每个候选式，可找出所有满足a b的终结符对。 确定满足关系 的所有终结符对： 首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：,从算符优先文法G构造优先关系表的算法。 通过检查G的每个产生式的每个候选式，可找出所有满足ab的终结符对。 确定满足关系 的所有终结符对： 首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：,从算符优先文法G构造优先关系表的算法。 通过检查G的每个产生式的每个候选式，可找出所有满足ab的终结符对。 确定满足关系 的所有终结符对： 首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：,比较,比较,有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系的所有终结符对。 假定有个产生式的一个候选形为 aP 那么，对任何bFIRSTVT(P)，有 a b。,数据结构： 布尔数组FP，a，使得FP，a为真的条件是，当且仅当aFIRSTVT(P)。开始时，按上述的规则(1)对每个数组元素FP，a赋初值。 栈STACK，把所有初值为真的数组元素FP，a的符号对(P，a)全都放在STACK之中。,运算： 如果栈STACK不空，就将顶项逐出，记此项为(Q，a)。对于每个形如 PQ 的产生式，若FP，a为假，则变其值为真且将(P，a)推进STACK栈。 上述过程必须一直重复，直至栈STACK拆空为止。,如果把这个算法稍为形式化一点，我们可得如下所示的一个程序(包括一个过程和主程序)： PROCEDURE INSERT(P，a)； IF NOT FP，a THEN BEGIN FP，a:=TRUE； 把(P，a)下推进STACK栈 END；,主程序： BEGIN FOR 每个非终结符P和终结符a DO FP，a:=FALSE； FOR 每个形如Pa或PQa的产生式 DO INSERT(P，a)； WHILE STACK 非空 DO BEGIN 把STACK的顶项，记为(Q，a)，上托出去； FOR 每条形如PQ的产生式 DO INSERT(P，a)； END OF WHILE； END,这个算法的工作结果得到一个二维数组F，从它可得任何非终结符P的FIRSTVT。 FIRSTVT(P)a | FP，a=TRUE 同理，可构造计算LASTVT的算法。,构造集合LASTVT(P)的算法。 按其定义，可用下面两条规则来构造集合LASTVT(P)： 1. 若有产生式P a或P aQ，则a LASTVT(P)； 2. 若a LASTVT(Q)，且有产生式P Q ，则a LASTVT(P)。,使用每个非终结符P的FI