1、第四章 语法分析赵建华南京大学计算机系2010.31fhfh程序设计语言构造的描述 程序设计语言构造的语法可使用上下文无关文法或BNF表示法来描述 文法可给出精确易懂的语法规则 可以自动构造出某些类型的文法的语法分析器 文法指出了语言的结构，有助于进一步的语义处理/代码生成。支持语言的演化和迭代。2fhfh语法分析器的作用 基本作用 从词法分析器获得词法单元的序列，确认该序列是否可以由语言的文法生成。对于语法错误的程序，报告错误信息 对于语法正确的程序，生成语法分析树。通常并不真的生产这棵语法分析树3fhfh语法分析器的分类 通用语法分析器 可以对任意文法进行语法分析 效率很低，不适合用于编译
2、器 自顶向下语法分析器 从语法分析树的根部开始构造语法分析树 自底向上语法分析器 从语法分析树的叶子开始构造语法分析树 后两种方法 总是从左到右、逐个扫描词法单元。只能处理特定类型的文法，但是这些文法足以用来描述程序设计语言。4fhfh上下文无关文法 定义：一个上下文无关文法包含四个部分 终结符号：组成串的基本符号（词法单元名字）非终结符号：表示串的集合的语法变量。给出了语言的层次结构。在程序设计语言中通常对应于某个程序构造，比如stmt（语句）开始符号：某个被指定的非终结符号。它对应的串的集合就是文法的语言 产生式集合：描述将终结符号和非终结符号组成串的方法 产生式的形式：头/左部 体/右部
3、 头部是一个非终结符号，右部是一个符号串；例子：expression expression+term5fhfh上下文无关文法的例子 简单算术表达式的文法：终结符号：id+-*/()非终结符号：expression,term,factor 开始符号：expression 产生式集合：expression expression+termexpression expression termexpression termterm term*factorterm term/factorterm factorfactor (expression)factor id6fhfh文法书写的约定 终结符号 靠前的
4、小写字母(a,b,c)；运算符号(+*)；标点符号；数位；黑体字符串(id,if,while)非终结符号 靠前的大小字母(A,B,C)；字母S（通常是开始符号）；小写斜体字母；表示程序构造的大写字母 X,Y,Z文法符号（终结符号或非终结符号）小写希腊字母表示文法符号串(,)靠后的小写字母表示终结符号串 具有相同头的产生式可以合并成A 1|2|n的形式 通常第一个产生式的左部就是开始符号。7fhfh文法简单形式的例子E E+T|E T|TT T*F|T/F|FF (E)|id 注意:|是元符号（即文法描述方式中的符号，而不是文法符号）这里(,)不是元符号；在有些地方会把()看作元符号8fhfh推
5、导（1）推导：将待处理的串中的某个非终结符号替换为这个非终结符号的某个产生式的体。从开始符号出发，不断进行上面的替换，就可以得到文法的不同句型 例子 文法:E -E|E+E|E*E|(E)|id 推导序列：E=-E=-(E)=-(id)9fhfh推导（2）推导的正式定义 如果A是一个产生式，那么A=最左(右)推导：()中不包含非终结符号 符号：经过零步或者多步推导出：对于任何串 如果 且=，那么 经过一步或者多步推导出：等价于 且不等于10fhfh句型/句子/语言 句型（sentential form）：如果S=*=，那么就是文法的句型 可能既包含非终结符号，又包含终结符号；可以是空串 句子（
6、sentence）文法的句子就是不包含非终结符号的句型 语言 文法G的语言就是G的句子的集合，记为L(G)w在L(G)中当且仅当w是G的句子，即S=*=w11fhfh语法分析树 推导的图形表示形式 根结点的标号时文法的开始符号 每个叶子结点的标号是非终结符号、终结符号或 每个内部节点的标号是非终结符号。每个内部结点表示某个产生式的一次应用 内部结点的标号为产生式头，结点的子结点从左到右是产生式的体 有时允许树的根不是开始符号（对应于某个短语）。树的叶子组成的序列是根的文法符号的句型 一棵分析树可对应多个推导序列，但是分析树和最左（右）推导序列之间具有一一对应关系12fhfh语法分析树的例子 文
7、法：E -E|E+E|E*E|(E)|id 句子：-(id+id)13fhfh从推导序列构造分析树 假设有推导序列：A=a1=a2=an 算法：初始化：a1的分析树是标号为A的单个结点 假设已经构造出ai-1=X1X2Xk的分析树，且ai-1到a1的推导是将Xj替换为，那么在当前分析树中找出第j个非结点，向这个结点增加构成的子结点。如果=，则增加一个标号为的子结点）14fhfh构造分析树的例子 推导序列：E=-E=-(E)=-(E+E)=-(id+E)=-(id+id)15fhfh二义性（1）二义性（ambiguous）：一个文法可以为某个句子生成多棵语法分析树，这个文法就是二义性的 例子：E
8、=E+E=id+E=id+E*E=id+id*E=id+id*id E=E*E=E+E*E=id+E*E=id+id*E=id+id*id16fhfh二义性（2）程序设计语言的文法通常都应该是无二义性的 否则就会导致一个程序有多种“正确”的解释。比如文法：E -E|E+E|E*E|(E)|id 的句子a+b*c 但有些二义性的情况可以方便文法或语法分析器的设计。但是需要消二义性规则来剔除不要的语法分析树 比如：先乘除后加减17fhfh证明文法生成的语言 证明文法G生成语言L可以帮助我们了解文法可以生成什么样的语言。基本步骤：首先证明L(G)L 然后证明LL(G)一般使用数学归纳法 证明L(G)
9、L的方法之一：构造L，使得LVt*=L；并证明SL，且对于L中的任意，=可推出也在L中。也可以按照推导序列长度进行数学归纳 证明LL(G)时，通常可按照符号串的长度来构造推导序列。18fhfh文法生成语言的例子（1）文法：S(S)S|语言：所有具有对称括号对的串 L(G)L的证明：令L=删除S后括号对称的串，显然有LVt*=L且S L 任意的删除S后括号对称的串，不管使用S还是(S)S 推导出串，删除中的S后得到的串仍然是括号对称的。有上面两点可知：G的所有句型都属于L，且L中的终结符号串就是L。可知L(G)L。19fhfh文法生成语言的例子（2）LL(G)的证明：注意：括号对称的串的长度必然
10、是偶数。归纳基础：如果括号对称的串的长度为0，显然它可以从S推导得到 归纳步骤：假设长度小于2n的括号对称的串都能够由S推导得到。假设w是括号对称且长度为2n的串 w必然以左括号开头，且w可以写成(x)y的形式，其中x也是括号对称的。因为x、y的长度都小于2n，根据归纳假设，x和y都可以从S推导得到。因此S=(S)S=*=(x)y。20fhfh上下文无关文法和正则表达式（1）上下文无关文法比正则表达式的能力更强。即：所有的正则语言都可以使用文法描述 但是一些用文法描述的语言不能用正则文法描述。证明：首先SaSb|ab 描述了语言anbn|n0，但是这个语言无法用DFA识别。假设有DFA识别此语
11、言，且这个文法有K个状态。那么在识别ak+1的输入串时，必然两次到达同一个状态。设自动机在第i个和第j个a时进入同一个状态，那么：因为DFA识别L，ajbj必然到达接受状态，因此aibj必然也到达接受状态。直观地讲：有穷自动机不能数（大）数。21fhfh上下文无关文法和正则表达式（2）证明（续）其次证明：任何正则语言都可以表示为上下文无关文法的语言。任何正则语言都必然有一个NFA。对于任意的NFA构造如下的上下文无关文法 对NFA的每个状态i，创建非终结符号Ai。如果有i在输入a上到达j的转换，增加产生式AiaAj。如果i在输入上到达j，那么增加产生式AiAj.如果i是一个接受状态，增加产生式
12、Ai 如果i是开始状态，令Ai为所得文法的开始符号。22fhfhNFA构造文法的例子 A0aA0|bA0|aA1 A1bA2 A2bA3 A3 考虑baabb的推导和接受过程可知：NFA接受一个句子的运行过程实际是文法推导出该句子的过程。23fhfh设计文法 文法能够描述程序设计语言的大部分语法 但不是全部，比如：标识符的先声明后使用无法用上下文无关文法描述。因此：语法分析器接受的语言是程序设计语言的超集。必须通过语义分析来剔除一些符合文法、但不合法的程序。24fhfh二义性的消除(1)一些二义性文法可以被改成等价的无二义性的文法 例子：stmt if expr then stmt|if ex
13、pr then stmt else stmt|other if E1 then if E2 then S1 else S2的两棵语法树25fhfh二义性的消除(2)为了保证“else和最近未匹配的then匹配”，我们要求在then分支的语句必须是匹配好的。引入matched_stmt表示匹配好的语句，有如下文法：stmt matched_stmt|open_stmtmatched_stmt if expr then matched_stmt else matched_stmt|otheropen_stmt if expr then stmt|if expr then matched_stmt
14、else open_stmt 二义性的消除方法没有规律可循。通常并不是通过改变文法来消除二义性。26fhfh左递归的消除 左递归的定义：如果一个文法中有非终结符号A使得A=*=A，那么这个文法就是左递归的。立即左递归（规则左递归）文法中存在一个形如AA的产生式。自顶向下的语法分析技术不能处理左递归的情况，因此需要消除左递归；但是自底向上的技术可以处理左递归。27fhfh立即左递归的消除 假设非终结符号A存在立即左递归的情形，假设以A为左部的规则有：A A1|A2|Am|1|2|n 可以替换为A1A|2A|n AA1A|2A|mA|由A生成的串总是以某个i开头，然后跟上零个或者多个i的重复。28
15、fhfh通用的左递归消除方法 输入：没有环和产生式的文法G 输出：等价的无左递归的文法 步骤：将文法的非终结符号任意排序为A1,A2,Anfor i=1 to n do for j=1 to i-1 do将形如Ai Aj的产生式替换为Ai1|2|n，其中Aj 1|2|m是以Aj为左部的所有产生式；消除Ai的立即左递归；1.内层循环的每一次迭代保证了Ai的产生式的右部首符号都比Aj更加靠后。2.当内层循环结束时，Ai的产生式的右部首符号不先于Ai。3.消除立即左递归就保证了Ai的产生式的右部首符号必然比Ai后。（不能有环和产生式）4.当外层循环结束时，所有的产生式都是如此。使用这些产生式当然不会
16、产生左递归的情形。29fhfh通用左递归消除的例子 S Aa|bAAc|Sd|步骤1：排列为S，A i=1时：内层循环不运行，S没有立即左递归；i=2时：j=1，处理规则ASd；替换得到 AAc|Aad|bd|消除A的立即左递归 SAa|b AbdA|A AcA|adA|通用左递归消除的问题在于很难找到新文法和旧文法的推导之间的对应关系，因此很难依据新文法进行语义处理。本例子中的产生式恰好没有影响算法的正确性30fhfh预测分析法简介 试图从开始符号推导出输入符号串；以开始符号作为初始的当前句型 每次为最左边的非终结符号选择适当的产生式；通过查看下一个输入符号来选择这个产生式。有多个可能的产生
17、式时预测分析法无能为力 比如文法：E+EE|-EE|id；输入为+id-id id 当两个产生式具有相同的前缀时无法预测 文法：stmt if expr then stmt else stmt|if expr then stmt 输入：if a then 新文法：stmt if expr then stmt elsePart elsePart else stmt|需要提取公因子31fhfh提取公因子的文法变换 算法：输入：文法G 输出：等价的提取了左公因子的文法 方法：对于每个非终结符号A，找出它的两个或者多个可选产生式体之间的最长公共前缀。A 1|2|n|AA|A1|2|n 其中是不以开头的
18、产生式体32fhfh提取公因子的例子 文法：S i E t S|i E t S e S|a E b 对于S而言，最长的前缀是i E t S，因此：S i E t S S|a Se S|E b33fhfh非上下文无关语言的构造 抽象语言 L1=wcw|w在(a|b)*中 这个语言不是上下文无关的语言 它抽象地表示了C或者Java中“标识符先声明后使用”的规则。说明了这些语言不是上下文无关语言，不能使用上下文无关文法描述。通常用上下文无关文法描述其基本结构，不能用文法描述的特性在语义分析阶段完成。原因是上下文文法具有高效的处理算法。34fhfh自顶向下的语法分析 为输入串构造语法分析树 从分析树的
19、根结点开始，按照先根次序，深度优先地创建各个结点 对应于最左推导。基本步骤 确定对句型中最左边的非终结符号应用哪个产生式 然后对句型中的非终结符号和输入符号进行匹配 关键问题是：确定对最左边的非终结符号应用哪个产生式35fhfh自顶向下分析的例子 文法：ETE E+TE|TFT T*FT|F(E)|id 输入id+id*id 分析树序列见右面（图4-12）36fhfh递归下降的语法分析 递归下降语法分析程序由一组过程组成 每个非终结符号对应于一个过程，该过程负责扫描非终结符号对应的结构 程序执行从开始符号对应的过程开始 当扫描整个输入串时宣布分析成功完成37fhfh递归下降分析技术的回溯 如果
20、没有足够的信息来唯一地确定可能的产生式，那么分析过程就产生回溯。前面的算法报告错误（第7行）并不意味着输入串不是句子，而可能是表示前面选错了产生式。第一行上保存当前的扫描指针 在第七行上应该改成 回退到保存的指针；GOTO (1)并选择下一个产生式；如果没有下一个产生式可选，报告错误。回溯需要来回扫描，低效 如果嵌入了语义处理，则需要撤销已经完成的语义处理动作。解决方法：设法通过一些信息确定唯一可能的产生式38fhfh递归下降分析中回溯的例子 文法：ScAdAab|a 输入串：cad 步骤：调用函数S；S选择唯一产生式ScAd 输入中的c和句型中的c匹配，继续调用A A首先选择产生式Aab，a
21、和输入的a匹配，b和输入的d不匹配；回溯并选择下一个产生式Aa；a和输入的a相匹配；对A的调用返回；到S的调用；ScAd中的d和下一个输入匹配；对S的调用返回，已经读入所有输入符号；因此扫描结束，cad是句子。39fhfhFIRST和FOLLOW（1）在自顶向下的分析技术中，通常使用向前看几个符号来唯一地确定产生式（这里假定只看一个符号）当前句型是xA，而输入是xa。那么选择产生式A的必要条件是下列之一：=*=，且以a开头；也就是说在某个句型中a跟在A之后；=*=a；如果按照这两个条件选择时能够保证唯一性，那么我们就可以避免回溯。因此，我们定义FIRST和FOLLOW40fhfhFIRST和F
22、OLLOW（2）FIRST()：可以从推导得到的串的首符号的集合；如果=*=，那么也在FIRST()中；FOLLOW(A)：可能在某些句型中紧跟在A右边的终结符号的集合。41fhfhFIRST的计算方法 计算FIRST(X)的方法 如果X是终结符号，那么FIRS(X)=X 如果X是非终结符号，且XY1Y2Yk是产生式，如果a在FIRST(Yi)中，且在FIRST(Y1),FIRST(Y2),FIRST(Yi-1)中，那么a也在FIRST(X)中。如果在FIRST(Y1),FIRST(Y2),FIRST(Yk)中，那么在FIRST(X)中。如果X是非终结符号，且X是一个产生式，那么在FIRST(
23、X)中 计算FIRST(X1X2Xn)的方法 向集合中加入FIRST(X1)中所有非的符号；如果在FIRST(X1)中，再加入FIRST(X2)中的所有非的符号；如果在所有的FIRST(X1)中，将加入FIRST(X1X2Xn)中。42fhfhFOLLOW的计算方法 算法 将右端结束标记$放到FOLLOW(S)中 按照下面的两个规则不断迭代，直到所有的FOLLOW集合都不再增长为止。如果存在产生式AB，那么FIRST()中所有非的符号都在FOLLOW(B)中。如果存在一个产生式AB，或者AB且FIRST()包含，那么FOLLOW(A)中的所有符号都加入到FOLLOW(B)中。请注意各个步骤中将
24、符号加入到FOLLOW集合中的理由。43fhfhFIRST/FOLLOW的例子（1）文法：ETEE+TE|T FTT*FT|F(E)|id FIRST集合 FIRST(F)=(,id；FIRST(E)=FIRST(T)=(,id FIRST(E)=+,;FIRST(T)=*,由此可以推出各个产生式右部的FIRST集合。44fhfhFIRST/FOLLOW的例子（2）FOLLOW集合的计算过程$在FOLLOW(E)中（E是开始符号）由规则F(E)可知，)也在FOLLOW(E)中 由规则ETE 可知FOLLOW(E)也包含了$和)。注意：因为E只出现在E和E的产生式的尾部，因此FOLLOW(E)必
25、然等于FOLLOW(E)。由规则E+TE，FIRST(E)中的+在FOLLOW(T)中；且FIRST(E)包含，因此FOLLOW(E)中的$和)也在FOLLOW(T)中。因为T只出现在T和T的产生式的末尾，可以FOLLOW(T)=FOLLOW(T)；由规则TFT且T可以推导出，因此可知FOLLOW(F)包含FOLLOW(T)；同时FIRST(T)也在FOLLOW(F)中。因此 E：$,)E：$,)T,T：+,),$F：+,*,),$45fhfhLL(1)文法（1）定义:对于文法的任意两个不同的产生式A|不存在终结符号a使得和都可以推导出以a开头的串 和最多只有一个可以推导出空串 如果可以推导出
26、空串，那么不能推导出以FOLLOW中任何终结符号开头的串；等价于：FIRST()FIRST()=;（条件一、二）如果FIRST()，那么FIRST()FOLLOW(A)=；反之亦然。（条件三）考虑：对于一个LL(1)文法，我们期望从A推导出以终结符号a开头的符号串，我们如何选择产生式？有多个选择吗？46fhfhLL(1)文法（2）对于LL(1)文法，可以在自顶向下分析过程中，根据当前输入符号来确定使用的产生式。例如：产生式：stmt if(exp)stmt else stmt|while(exp)stmt|a 输入：if(exp)while(exp)a else a 首先选择产生式stmt i
27、f(exp)stmt else stmt 得到句型if(exp)stmt else stmt 然后发现要把句型中的第一个stmt展开，选择产生式stmt while(exp)stmt，得到句型if(exp)while(exp)stmt else stmt。然后再展开第一个stmt，得到if(exp)while(exp)a else stmt 47fhfh预测分析表构造算法 输入：文法G 输出：预测分析表M 方法：对于文法G的每个产生式A 对于FIRST()中的每个终结符号a，将A加入到MA,a中；如果在FIRST()，那么对于FOLLOW(A)中的每个符号b，将将A加入到MA,b中。最后在所有
28、的空白条目中填入error。48fhfh预测分析表的例子文法：ETEE+TE|T FTT*FT|F(E)|idFIRST集：F：(,id；E,T：(,id；E：+,;T：*,FOLLOW集：E：$,)E：$,)T,T：+,),$F：+,*,),$这个例子恰巧使得每个产生式的右部的第一个符号的FIRST集合就等于产生式右部的FIRST集合。但是在一般情况下不总是这样的。49fhfh预测分析表冲突的例子 文法：SiEtSS|aSeS|Eb FIRST(eS)=e，使得SeS在MS,e中；FOLLOW(S)=$,e使得S 也在MS,e中 注意：LL(1)文法必然不是二义性的；而这个文法是二义性的50
29、fhfhLL(1)文法的递归下降分析 递归下降语法分析程序由一组过程组成 每个非终结符号对应于一个过程，该过程负责扫描非终结符号对应的结构 可以使用当前的输入符号来唯一地选择产生式如果当前输入符号为a，那么选择MA,a中的产生式51fhfh非递归的预测分析（1）在自顶向下分析的过程中，我们总是 匹配掉句型中左边的所有终结符号；对于最左边的非终结符号，我们选择适当的产生式展开。匹配成功的终结符号不会再被考虑，因此我们只需要记住句型的余下部分，以及尚未匹配的输入终结符号串。由于展开的动作总是发生在余下部分的左端，我们可以用栈来存放这些符号。52fhfh非递归的预测分析（2）分析时的处理过程：初始化
30、时，栈中仅包含开始符号；如果栈顶元素是终结符号，那么进行匹配 如果栈顶元素是非终结符号 使用预测分析表来选择适当的产生式；在栈顶用产生式右部替换产生式左部；因此对所有文法的预测分析都可以共用同样的驱动程序。53fhfh分析表驱动的预测分析器性质1：如果栈中的符号序列为，而w是已经被读入的部分输入，w是尚未处理的输入；那么 S推导出w 我们试图从推导出余下的输入终结符号串w预测分析程序使用MX,a来扩展X，将此产生式的右部按倒序压入栈中请注意：这样的操作使得分析过程中性质1得到保持。54fhfh预测分析算法 输入：串w，预测分析表M 输出：如果w是句子，输出w的最左推导；否则报错 方法：1.初始
31、化：输入缓冲区中为w$；栈中包含S$；ip指向w的第一个符号；2.令X=栈顶符号，ip指向符号aif(X=a)出栈，ip向前移动；/*和终结符号的匹配*/else if(X是终结符号)error()；/*失配*/else if(MX,a是报错条目)error();/*无适当的产生式*/else if(MX,a=XY1Y2Yk)输出产生式XY1Y2Yk；弹出栈顶符号X；将Yk,Yk-1,Y1压入栈中；3.不断执行第二步；直到要么报错，要么栈中为空55fhfh分析表驱动预测分析的例子 文法4.28，输入：id+id*id;注意：已经匹配部分加上栈中符号必然是一个最左句型56fhfh预测分析中的错误
32、恢复 错误恢复 当预测分析器报错时，表示输入的串不是句子。对于使用者而言，希望预测分析器能够进行恢复，并继续语法分析过程，以便在一次分析中找到更多的语法错误。有可能恢复得并不成功，之后找到的语法错误有可能是假的。进行错误恢复时可用的信息：栈里面的符号，待分析的符号 两类错误恢复方法：恐慌模式 短语层次的恢复57fhfh恐慌模式 基本思想 语法分析器忽略输入中的一些符号，直到出现由设计者选定的某个同步词法单元；解释：语法分析过程总是试图在输入的前缀中找到和某个非终结符号对应的串；出现错误表明现在已经不可能找到这个非终结符号（程序结构）的串。如果编程错误仅仅局限于这个程序结构，那么我们可以考虑跳过
33、这个程序结构，假装已经找到了这个结构；然后继续进行语法分析处理。同步词法单元就是这个程序结构结束的标志。58fhfh同步词法单元的确定 非终结符号A的同步集合的启发式规则 FOLLOW(A)的所有非终结符号A的同步集合中 这些符号的出现可能表示之前的那些符号是错误的A的串；将高层次的非终结符号对应串的开始符号加入到较低层次的非终结符号的同步集合 比如语句的开始符号，if，while等可以作为表达式的同步集合；FIRST(A)中的符号加入到非终结符号A的同步集合。碰到这些符号时，可能意味着前面的符号是多余的符号 如果A可以推导出空串，那么把此产生式当作默认值。在匹配时出现错误，可以直接弹出相应的
34、符号；哪些符号需要确定同步集合需要根据特定的应用而定。59fhfh恐慌模式的例子（1）对文法4.28的表达式进行语法分析时，可以直接使用FIRST、FOLLOW作为同步集合。我们为E、T和F设定同步集合；空条目表示忽略输入符号；synch条目表示忽略到同步集合，然后弹出非终结符号；终结符号不匹配时，弹出栈中终结符号；60fhfh恐慌模式的例子（2）错误输入：id*+id61fhfh短语层次的恢复 在预测语法分析表的空白条目中插入错误处理例程的函数指针；例程可以改变、插入或删除输入中的符号；发出适当的错误消息；62fhfh自底向上的语法分析 为一个输入串构造语法分析树的过程；从叶子（输入串中的终
35、结符号，将位于分析树的底端）开始，向上到达根结点；在实际的语法分析过程中并不会真的构造出相应的分析树，但是分析树概念可以方便理解；重要的自底向上语法分析的通用框架 移入-归约；LR：最大的可以构造出移入-归约语法分析器的语法类63fhfh分析过程示例64fhfh归约 自底向上语法分析过程看成从串w“归约”为文法开始符号的过程；归约步骤：一个与某产生式体相匹配的特定子串被替换为该产生式头部的非终结符号；问题：何时归约（归约哪些符号串）？归约到哪个非终结符号？65fhfh归约的例子 id*id的归约过程 id*id，F*id，F*id，T*F，T，E 对于句型T*id，有两个子串和某产生式右部匹配
36、 T是ET的右部；id是Fid的右部；为什么选择将id归约为F，而不是将T归约为E？原因：T归约为E之后，E*id不再是句型；问题：如何确定这一点？66fhfh句柄剪枝 对输入从左到右扫描，并进行自底向上语法分析，实际上可以反向构造出一个最右推导；句柄：最右句型中和某个产生式体匹配的子串，对它的归约代表了该最右句型的最右推导的最后一步；正式定义：如果S Aw w；那么紧跟之后的A的一个句柄；在一个最右句型中，句柄右边只有终结符号 如果文法是无二义性的，那么每个句型都有且只有一个句柄。67fhfh句柄的例子 输入：id*id68fhfh移入-归约分析技术 使用一个栈来保存归约/扫描移入的文法符号
37、；栈中符号（从底向上）和待扫描的符号组成了一个最右句型；开始时刻：栈中只包含$，而输入为w$；成功结束时刻：栈中$S，而输入$；在分析过程中，不断地移入符号，并在识别到句型时进行归约；句柄被识别时总是出现在栈的顶部；69fhfh主要分析动作 移入：将下一个输入符号移动到栈顶；归约：将句柄归约为相应的非终结符号;句柄总是在栈顶。具体操作时弹出句柄，压入被归约到的非终结符号。接受：宣布分析过程成功完成；报错：发现语法错误，调用错误恢复子程序；70fhfh归约分析过程的例子71fhfh为什么句柄总是在栈顶？（1）为什么每次归约得到的新句型的句柄仍不在栈顶？考虑最右推导的两个连续步骤的两种情况 A被替
38、换为By，然后产生式体中的最右非终结符号B被替换为。（归约之后句柄为By）A首先被展开，产生式体中只包含终结符号；下一个最右非终结符号B位于y左侧。y是终结符号串72fhfh移入-归约分析中的冲突 对于有些不能使用移入-归约分析的文法，不管用什么样的移入-归约分析器都会到达这样的格局 即使知道了栈中所有内容、以及下面k个输入符号，人们仍然无法知道是否该进行归约，或者不知道按照什么产生式进行归约；形式化地表达：设栈中符号串是，接下来的k个符号是x，产生移动/归约冲突的原因是存在y和y使得axy是最右句型且是句柄，而axy也是最右句型，但是句柄还在右边。73fhfh归约/归约冲突的例子 输入为id
39、(id,id)冲突时的格局：栈：id(id 输入：,id)某个语言中，多维数组的表示方法。74fhfhLR语法分析技术 LR(k)的语法分析概念 L表示最左扫描，R表示反向构造出最右推导；k表示最多向前看k个符号；当k的数量增大时，相应的语法分析器的规模急剧增大；K=2时，程序设计语言的语法分析器的规模通常非常庞大；当k=0、1时已经可以解决很多语法分析问题，因此具有实践意义。因此，我们只考虑k12w，那么我们说项A1.2么对1有效。102fhfhSLR的原理：可行前缀（2）如果我们知道A1.2对1有效，当2不等于空，表示句柄尚未出现在栈中，应该移入或者等待归约；如果2等于空，表示句柄出现在栈
40、中，应该归约。如果某个时刻存在两个有效项要求执行不同的动作，那么就应该设法解决冲突。冲突实际上表示可行前缀可能是两个最右句型的前缀，第一个包含了句柄，而另一个尚未包含句型 E+T+id E+T*id SLR解决冲突的思想：假如要按照A进行归约，那么得到的新句型中A后面跟随下一个输入符号。因此只有当下一个输入在FOLLOW(A)中时才可以归约。也可能都认为包含句柄，但是规则不一样103fhfhSLR的原理：可行前缀（3）如果在文法G的LR(0)自动机中，从初始状态出发，沿着标号为的路径到达一个状态，那么这个状态对应的项集就是的有效项集。回顾确定分析动作的方法，就可以知道我们实际上是按照有效项来确
41、定的。为了避免冲突，归约时要求下一个输入符号在FOLLOW(A)中。104fhfh活前缀/有效项的例子 可行前缀E+T*对应的LR(0)项 TT*.F F.(E)F.id 对应的最右推导 EEE+TE+T*F EEE+TE+T*FE+T*(E)EEE+TE+T*FE+T*id105fhfhSLR语法分析器的弱点（1）SLR技术解决冲突的方法：项集中包含A.时，按照A进行归约的条件是下一个输入符号a可以在某个句型中跟在A之后。如果对于a还有其它的移入/归约操作，则出现冲突。假设此时栈中的符号串为，如果Aa不可能是某个最右句型的前缀，那么即使a在某个句型中跟在A之后，仍然不应该按照A归约。进行归约
42、的条件更加严格可以降低冲突的可能性106fhfhSLR语法分析器的弱点（2）A.出现在项集中的条件：首先A.出现在某个项集中，然后逐步读入/归约到中的符号，点不断后移，到达末端。而A.出现的条件是B.A出现在项中 期望首先按照A归约，然后将B.A中的点后移到A之后。显然，在按照A归约时要求下一个输入符号是的第一个符号。但是从LR(0)项集中不能确定这个信息。107fhfh更强大的LR语法分析器 规范LR方法（或直接称LR方法）添加项A.时，把期望的向前看符号也加入项中。这个做法可以充分利用向前看符号，但是状态很多。向前看LR（LALR方法）基于LR(0)项集族。但是每个LR(0)项都带有向前看
43、符号。分析能力强于SLR方法，且分析表和SLR分析表一样大。LALR已经可以处理大部分的程序设计语言。108fhfhLR(1)项 LR(1)项中包含更多信息来消除一些归约动作。实际的做法相当于“分裂”一些LR(0)状态，精确地指明何时应该归约。LR(1)项的形式A.,a a称为向前看符号，可以是终结符号或者$a表示如果将来要按照A进行归约，归约时的下一个输入符号必须是a。当非空时，移入动作不考虑a，a传递到下一状态。109fhfhLR(1)项和可行前缀 A.,a对于一个可行前缀有效的条件是存在一个推导S Aw w，其中=，且 a是w的第一个符号，或者w为空且a=$。如果A.B,a对于可行前缀有
44、效，那么 B.,b对于有效的条件是什么？S Aw Bw Bxw xw 显然：b应该是xw的第一个符号，或xw为空且b=$。如果x为空，则b=a。如果A.X,a对于可行前缀有效，AX.,a对X有效。110fhfh可行前缀和LR(1)有效项的例子 文法：SBBBaB|b 最右推导：S aaBab aaaBab。对应于前面的定义：=aa，A=B w=ab，=a=B=aaa 因此：Ba.B,a对于aaa是有效的；111fhfh构造LR(1)项集 项集族的构造和LR(0)项集族的构造类似，但是CLOSURE和GOTO有所不同：在CLOSURE中，当由项A.B,a生成新项B.,b时，b必须在FIRST(a
45、)中。注意：对应LR(1)项集族中的任意项A.B,a，总是保证a在FOLLOW(A)中 初始项集满足这个条件 每次求CLOSURE项集时，新产生的项也满足这个条件。112fhfhLR(1)项集的CLOSURE算法 注意添加B.,b时，b的取值范围。即点后面跟着终结符号的项113fhfhLR(1)项集的GOTO算法 和LR(0)项集的GOTO算法基本相同即点后面跟文法符号X的项114fhfhLR(1)项集族的主构造算法 和LR(0)项集族的构造算法相同115fhfhLR(1)项集族的例子 增广文法 SSSCCCcC|d I0=CLOSURES.S,$S.S,$，S.CC,$，C.cC,c/d，C
46、.d,c/d GOTO(I0,S)=SS.,$GOTO(I0,C)=CLOSURESC.C,$=SC.C,$,C.cC,$，C.d,$GOTO(I0,c)=Cc.C,c/d,C.cC,c/d，C.d,c/d GOTO(I0,d)=Cd.,c/d 如果它是当前状态，下一个输入符号必须是c或者d才可以归约 116fhfhLR(1)项集的GOTO图不计向前看符号，I3，I6相同I8，I9相同I4，I7相同如果构造LR(0)项集族，只有6个项集。117fhfhLR语法分析表的构造 步骤：构造得到LR(1)项集族C=I0,I1,In。状态i对应于项集Ii。其分析动作如下：A.a,b在项集中，且GOTO(
47、Ii,a)=Ij，那么ACTIONi,a=“移入j”A.,a在项集中，ACTIONi,a=“按照A归约”SS.,$在项集中，ACTIONi,$=“接受”。GOTO表：GOTOi,A=j，如果GOTO(Ii,A)=Ij。没有填写的条目为报错。如果条目有冲突，则不是LR(1)的。初始状态对应于SS.,$所在的项集。移入时不考虑向前看符号118fhfhLR(1)语法分析表的例子(3,6)，(4,7)，(8,9)分别可以看作是由原来的一个LR(0)状态拆分而来的。文法：SSSCCCcC|d119fhfh构造LALR语法分析表 LR(1)语法分析表的状态数量很大 SLR(1)语法分析表的分析能力较弱 L
48、ALR(1)是实践中常用的方法 状态数量和SLR(1)的状态数量相同 能够方便地处理大部分常见的程序设计语言的构造120fhfhLR(1)语法分析表的合并 状态4和7仅在向前看符号上有所不同。Cd.c/d vs Cd.,$状态4：下一个符号如果为c或d则归约；为$在报错。状态7：分析动作正好反过来。如果我们将4和7中的项合并得47，那么在所有情况都归约 新的语法分析过程会在原来报错时进行归约；但是最终总会报错。对与这个文法，合并4和7不会引起任何冲突，但是有些文法会有冲突。对任意文法，如果SLR(1)分析表无冲突，合并后的分析表也无冲突。文法：SSSCCCcC|d121fhfhLALR分析技术
49、的基本思想 寻找具有相同核心的LR(1)项集，并把它们合并成为一个项集 项集的核心就是项的第一分量的集合；I4和I7的核心都是Cd.，I3和I6的核心Cc.C C.cC C.d 一个LR(1)项集的核心是一个LR(0)项集；GOTO(I,X)的核心只由I的核心决定，因此被合并项集的GOTO目标也可以合并。这表示合并之后，我们仍然可以建立GOTO关系。122fhfh合并引起的冲突 原来无冲突的LR(1)分析表在合并之后得到LALR(1)分析表；新的表中可能存在冲突。合并不会导致移入/归约冲突 假设合并之后在a上存在移入/归约冲突，即存在项B.a,?和A.,a。因为被合并的项集具有相同的核心，因此
50、被合并的所有项集中都包括B.a,?。而A.,a必然在某个项集中。这个项集必然已经存在冲突！合并会引起归约/归约冲突，即不能确定按照哪个产生式进行归约。123fhfh合并引起归约/归约冲突的例子 文法：SS SaAd|bBd|aBe|bAe Ac Bc 语言acd，ace，bcd，bce 可行前缀ac的有效项集Ac.,d,Bc.,e 可行前缀bc的有效项集Ac.,e,Bc.,d 合并之后的项集为Ac.,d/e,Bc.,d/e。这个项集包含了归约/归约冲突。应该把c归约成为A还是B？124fhfh基本的LALR分析表构造算法 步骤：构造得到LR(1)项集族C=I0,I1,In。对于LR(1)中的每
