编译原理语法分析3－金锄头文库

资源描述

《编译原理语法分析3》由会员分享，可在线阅读，更多相关《编译原理语法分析3（283页珍藏版）》请在金锄头文库上搜索。

1、第三章第三章语法分析语法分析词词法法分析器分析器记记号号取下一个取下一个记号记号源程序源程序分析分析树树前端的前端的其余部分其余部分分析器分析器中间中间表示表示符号表符号表本章内容本章内容上下文无关文法上下文无关文法自上而下自上而下分析和自下而上分析分析和自下而上分析围绕分析器的自动生成展开围绕分析器的自动生成展开3.1上下文无关文法上下文无关文法3.1.1上下文无关文法的定义上下文无关文法的定义正规式能定义一些简单的语言正规式能定义一些简单的语言，能表示给定结构能表示给定结构的固定次数的重复或者没有指定次数的重复的固定次数的重复或者没有指定次数的重复例：例：a(ba)5,a(ba)*正规式不

2、能用于描述配对或嵌套的结构正规式不能用于描述配对或嵌套的结构例例1：配对括号串的集合配对括号串的集合例例2：wcw | w是是a和和b的串的串 3.1上下文无关文法上下文无关文法上下文无关文法上下文无关文法是四元组（是四元组（VT ,VN ,S,P）VT : : 终结符终结符集合集合VN: : 非非终结符终结符集合集合S : : 开始符号开始符号P : :产生式产生式集合，集合，产生式形式产生式形式 : : A 例例 (id,+, , ,(,),expr,op,expr,P )exprexpropexpr expr (expr)expr expr expridop +op 3.1上下文无关文

3、法上下文无关文法简化表示简化表示exprexpropexpr | (expr)| expr | idop +| 简化表示简化表示E E A E | (E ) | E | idA +| 3.1上下文无关文法上下文无关文法3.1.2 推导推导把产生式看成重写规则，把符号串中的非终结符把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替用其产生式右部的串来代替例例 E E + E |E E|(E)| E|id E E (E) (E +E) (id+E) (id+id)概念概念上下文无关语言上下文无关语言、等价的等价的文法、文法、句型句型记号记号S * 、S +w 3.1上下文无关文法

4、上下文无关文法例例E E + E |E E|(E)| E|id 最左最左推导推导E lm E lm (E)lm (E +E)lm (id+E)lm (id+id)最右最右推导（规范推导）推导（规范推导）E rm E rm (E)rm (E +E)rm (E+id)rm (id+id)3.1上下文无关文法上下文无关文法3.1.3分析树分析树例例E E + E |E E|(E)| E|idEE ()EEE+idid3.1上下文无关文法上下文无关文法3.1.4二义性二义性EE EEE+Eid EE E+Eid E+Eid E+Eid id+Eid id+Eid id+idid id+idEEE*+E

5、EidididEEidE*+EEidid3.2 语言和文法语言和文法文法的优点文法的优点文法给出了精确的，易于理解的语法说明文法给出了精确的，易于理解的语法说明自动产生高效的分析器自动产生高效的分析器可以给语言定义出层次结构可以给语言定义出层次结构以文法为基础的语言的实现以文法为基础的语言的实现便于语言的修改便于语言的修改文法的问题文法的问题文法只能描述编程语言的大部分语法文法只能描述编程语言的大部分语法3.2 语言和文法语言和文法 3.2.1 正规式和上下文无关文法的比较正规式和上下文无关文法的比较正规式正规式(a|b)*ab文法文法A0aA0|b A0|aA1A1bA2A2 12开始开始

6、a0abb3.2 语言和文法语言和文法 3.2.2分离词法分析器理由分离词法分析器理由为什么要用正规式定义词法为什么要用正规式定义词法词法规则非常简单，不必用上下文无关文法词法规则非常简单，不必用上下文无关文法对于词法记号，正规式描述简洁且易于理解对于词法记号，正规式描述简洁且易于理解从正规式构造出的词法分析器效率高从正规式构造出的词法分析器效率高3.2 语言和文法语言和文法从软件工程角度看，词法分析和语法分析的从软件工程角度看，词法分析和语法分析的分离有如下好处分离有如下好处简化设计简化设计编译器的效率会改进编译器的效率会改进编译器的可移植性加强编译器的可移植性加强便于编译器前端的模块划分

7、便于编译器前端的模块划分 3.2 语言和文法语言和文法能否把词法分析并入到语法分析中，直接从能否把词法分析并入到语法分析中，直接从字符流进行语法分析字符流进行语法分析若把词法分析和语法分析合在一起，则必须将语若把词法分析和语法分析合在一起，则必须将语言的注解和空白的规则反映在文法中，文法将大言的注解和空白的规则反映在文法中，文法将大大复杂大复杂注解和空白由自己来处理的分析器，比注解和空注解和空白由自己来处理的分析器，比注解和空格已由词法分析器删除的分析器要复杂得多格已由词法分析器删除的分析器要复杂得多3.2 语言和文法语言和文法 3.2.3 验证文法产生的语言验证文法产生的语言G : S(S

8、)S| L(G)=配对的括号串的集合配对的括号串的集合3.2 语言和文法语言和文法 3.2.3 验证文法产生的语言验证文法产生的语言G : S(S)S| L(G)=配对的括号串的集合配对的括号串的集合按推导步数进行归纳按推导步数进行归纳：推出的是：推出的是配对括号串配对括号串归纳基归纳基础：础：S 归纳假设：归纳假设：少于少于n步的推导都产生配对的括号串步的推导都产生配对的括号串归纳步骤：归纳步骤：n步的最左推导步的最左推导如下：如下：S(S)S*(x)S*(x)y3.2 语言和文法语言和文法 3.2.3 验证文法产生的语言验证文法产生的语言G : S(S)S| L(G)=配对的括号串的集合配

9、对的括号串的集合按串长进行归纳按串长进行归纳：配对括号串可由配对括号串可由S推出推出归纳基归纳基础：础：S 归纳假设：归纳假设：长度小于长度小于2n的都可以从的都可以从S推导出来推导出来归纳步骤：归纳步骤：考虑长度为考虑长度为2n(n 1)的的w =(x)yS(S)S*(x)S*(x)y3.2 语言和文法语言和文法 3.2.4适当的表达式文法适当的表达式文法用一种层次观点看待表达式用一种层次观点看待表达式id id (id+id)+id id+idid id (id+id)文法文法exprexpr+term|termterm term factor|factorfactorid|(expr)3

10、.2 语言和文法语言和文法 exprexpr+term|termtermterm factor|factorfactorid|(expr)expridtermfactorididterm*termfactorfactor*exprexpr+idfactortermididterm*termfactorfactorid+id id分析树分析树 id id id分析树分析树 3.2 语言和文法语言和文法 3.2.5消除二义性消除二义性stmtifexprthenstmt|ifexprthenstmtelsestmt|other句型句型：ifexprthenifexprthenstmtelsestm

11、t两个最左推导：两个最左推导：stmt ifexprthenstmt ifexprthenifexprthenstmtelsestmtstmt ifexprthenstmtelsestmt ifexprthenifexprthenstmtelsestmt3.2 语言和文法语言和文法无二义的文法无二义的文法stmtmatched_stmt|unmatched_stmtmatched_stmtifexprthenmatched_stmtelsematched_stmt|otherunmatched_stmtif exprthenstmt|ifexprthenmatched_stmtelseunm

15、文法语言和文法 L3 =anbn|n 1S aSb | abL3 是不能用正规式描述的语言的一个范例是不能用正规式描述的语言的一个范例若存在接受若存在接受L3 的的DFAD，状态数为状态数为k个个设设D读完读完 , a, aa, ,ak 分别到达状态分别到达状态s0,s1, ,sk至少有两个状态相同，例如是至少有两个状态相同，例如是si和和sj，则则ajbi属于属于L3 sifs0标记为标记为ai的路径的路径标记为标记为bi的路径的路径标记为标记为aj i的路径的路径3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G =(VT , VN, S,P)0型文法：型文法：

16、， , (VN VT)*,| | 13.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G =(VT , VN, S,P)0型文法：型文法：， , (VN VT)*,| | 1短语文法短语文法3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G =(VT , VN, S,P)0型文法：型文法：， , (VN VT)*,| | 11型文法：型文法：| | | |，但但S 可以例外可以例外短语文法短语文法3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G =(VT , VN, S,P)0型文法：型文法：， , (VN

17、VT)*,| | 11型文法：型文法：| | | |，但但S 可以例外可以例外短语文法、上下文有关文法短语文法、上下文有关文法3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G =(VT , VN, S,P)0型文法：型文法：， , (VN VT)*,| | 11型文法：型文法：| | | |，但但S 可以例外可以例外2型文法：型文法：A ，A VN , (VN VT)*短语文法、上下文有关文法短语文法、上下文有关文法3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G =(VT , VN, S,P)0型文法：型文法：， , (VN VT)

18、*,| | 11型文法：型文法：| | | |，但但S 可以例外可以例外2型文法：型文法：A ，A VN , (VN VT)*短语文法、上下文有关文法、上下文无关文短语文法、上下文有关文法、上下文无关文法法3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G =(VT , VN, S,P)0型文法：型文法：， , (VN VT)*,| | 11型文法：型文法：| | | |，但但S 可以例外可以例外2型文法：型文法：A ，A VN , (VN VT)*3型文法：型文法：A aB或或A a，A, B VN ,a VT短语文法、上下文有关文法、上下文无关文短语文法、上下文

19、有关文法、上下文无关文法法3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G =(VT , VN, S,P)0型文法：型文法：， , (VN VT)*,| | 11型文法：型文法：| | | |，但但S 可以例外可以例外2型文法：型文法：A ，A VN , (VN VT)*3型文法：型文法：A aB或或A a，A, B VN ,a VT短语文法、上下文有关文法、上下文无关文短语文法、上下文有关文法、上下文无关文法、正规文法法、正规文法3.2 语言和文法语言和文法例例 L3anbncn|n 1的上下文有关文法的上下文有关文法S aSBC S aBCCBBCaB ab

20、bB bbbC bccC ccanbncn的推导过程如下：的推导过程如下：S *an-1S(BC)n 1用用S aSBC n-1次次S +an(BC)n用用S aBC 1次次S +anBnCn用用CBBC交换相邻的交换相邻的CBS +anbBn 1Cn用用aBab1次次S +anbnCn用用bB bb n-1次次S +anbncCn-1用用bC bc 1次次S +anbncn用用cCcc n-1次次3.3 自上而下分析自上而下分析 3.3.1自上而下分析的一般方法自上而下分析的一般方法例例文法文法 S aCb C cd | c为输入串为输入串w=acb建立分析树建立分析树SaCbSaCbcd

21、SaCbc不能处理不能处理左递归左递归3.3 自上而下分析自上而下分析不能处理左递归的例子不能处理左递归的例子算术表达文法算术表达文法EE+T|TTT F |FF(E)|idEE+TE+TE+T 3.3 自上而下分析自上而下分析 3.3.1自上而下分析的一般方法自上而下分析的一般方法例例文法文法 S aCb C cd | c为输入串为输入串w=acb建立分析树建立分析树SSSaCbaaCCbbcdc不能处理不能处理左递归左递归、复杂的回溯技术复杂的回溯技术3.3 自上而下分析自上而下分析 3.3.1自上而下分析的一般方法自上而下分析的一般方法例例文法文法 S aCb C cd | c为输入

22、串为输入串w=acb建立分析树建立分析树SSSaCbaaCCbbcdc不能处理不能处理左递归左递归、复杂的回溯技术复杂的回溯技术、回溯导回溯导致语义工作推倒重来致语义工作推倒重来3.3 自上而下分析自上而下分析 3.3.1自上而下分析的一般方法自上而下分析的一般方法例例文法文法 S aCb C cd | c为输入串为输入串w=acb建立分析树建立分析树SSSaCbaaCCbbcdc不能处理不能处理左递归左递归、复杂的回溯技术复杂的回溯技术、回溯导回溯导致语义工作推倒重来致语义工作推倒重来、难以报告出错的确切难以报告出错的确切位置位置3.3 自上而下分析自上而下分析 3.3.1自上而下分析的一

23、般方法自上而下分析的一般方法例例文法文法 S aCb C cd | c为输入串为输入串w=acb建立分析树建立分析树SSSaCbaaCCbbcdc不能处理不能处理左递归左递归、复杂的回溯技术复杂的回溯技术、回溯导回溯导致语义工作推倒重来致语义工作推倒重来、难以报告出错的确切难以报告出错的确切位置位置、效率低效率低3.3 自上而下分析自上而下分析 3.3.2LL(1)文法文法对文法加什么样的限制可以保证没有对文法加什么样的限制可以保证没有回溯回溯？先定义两个和文法有关的函数先定义两个和文法有关的函数FIRST( )=a | *a, a VT特别是，特别是， * 时，规定时，规定 FIRST(

24、)对对A的任何两个不同选择的任何两个不同选择 i和和 j，希望有希望有FIRST( i ) FIRST( j )=若若FIRST( i )或或FIRST( j )含含，还需增加条件，还需增加条件3.3 自上而下分析自上而下分析 3.3.2LL(1)文法文法对文法加什么样的限制可以保证没有对文法加什么样的限制可以保证没有回溯回溯？先定义两个和文法有关的函数先定义两个和文法有关的函数FIRST( )=a | *a, a VT特别是，特别是， * 时，规定时，规定 FIRST( )FOLLOW(A)=a|S*Aa，a VT如如果果A是是某某个个句句型型的的最最右右符符号号，那那么么$属属于于FOL

25、LOW(A)3.3 自上而下分析自上而下分析 LL(1)文法文法任何两个产生式任何两个产生式A | 都满足下列条件：都满足下列条件：FIRST( ) FIRST( )=若若 * ，那么，那么FIRST( ) FOLLOW(A)=例如例如,对于下面文法，面临对于下面文法，面临a时不知用什么规则时不知用什么规则S ABAa b | a FIRST(ab) FOLLOW(A)Ba CC 3.3 自上而下分析自上而下分析 LL(1)文法文法任何两个产生式任何两个产生式A | 都满足下列条件：都满足下列条件：FIRST( ) FIRST( )=若若 * ，那么，那么FIRST( ) FOLLOW(A)=

26、LL(1)文法有一些明显的性质文法有一些明显的性质没有公共左因子没有公共左因子不是二义的不是二义的不含左递归不含左递归3.3 自上而下分析自上而下分析例例 ETE E +TE | TFT T FT | F(E)|idFIRST(E)=FIRST(T)=FIRST(F)=(,idFIRST(E )=+, FRIST(T )= , FOLLOW(E)=FOLLOW(E )=),$FOLLOW(T)=FOLLOW(T )=+,),$FOLLOW(F)=+, ,),$3.3 自上而下分析自上而下分析 3.3.3递归下降的预测分析递归下降的预测分析为每一个非终结符写一个分析过程为每一个非终结符写一个分

27、析过程这些过程可能是递归的这些过程可能是递归的例例type simple| id |arraysimpleoftypesimple integer|char|numdotdotnum3.3 自上而下分析自上而下分析一个辅助过程一个辅助过程voidmatch(terminalt)if(lookahead=t)lookahead=nextToken();elseerror();3.3 自上而下分析自上而下分析 voidtype()if(lookahead=integer)|(lookahead=char)|(lookahead=num)simple();else if ( lookahead =

28、 ) match();match(id);elseif(lookahead=array)match(array);match( );simple();match( );match(of);type();elseerror(); type simple| id|arraysimpleoftype3.3 自上而下分析自上而下分析 voidsimple()if(lookahead=integer)match(integer);elseif(lookahead=char)match(char);elseif(lookahead=num)match(num);match(dotdot);match(nu

29、m);elseerror(); simple integer|char|numdotdotnum3.3 自上而下分析自上而下分析3.3.4非递归的预测分析非递归的预测分析a + b $输入输入预测分析程序预测分析程序分析表分析表M输出输出 XYZ$栈栈3.3 自上而下分析自上而下分析非终非终结符结符输输入入符符号号 id + .E ETE E E +TE TTFT T T T FT FFid分析表的一部分分析表的一部分3.3 自上而下分析自上而下分析栈栈输输入入输输出出$E id id+id$ 预测预测分析器接受输入分析器接受输入id * id + id的前一部分动作的前一部分动作 3.3

30、自上而下分析自上而下分析栈栈输输入入输输出出$E id id+id$ $E T id id+id$ ETE 预测预测分析器接受输入分析器接受输入id * id + id的的前一部分前一部分动作动作 3.3 自上而下分析自上而下分析栈栈输输入入输输出出$E id id+id$ $E T id id+id$ ETE $E T F id id+id$ TFT 预测预测分析器接受输入分析器接受输入id * id + id的的前一部分前一部分动作动作 3.3 自上而下分析自上而下分析栈栈输输入入输输出出$E id id+id$ $E T id id+id$ ETE $E T F id id+id$

31、 TFT $E T id id id+id$ Fid 预测预测分析器接受输入分析器接受输入id * id + id的的前一部分前一部分动作动作 3.3 自上而下分析自上而下分析栈栈输输入入输输出出$E id id+id$ $E T id id+id$ ETE $E T F id id+id$ TFT $E T id id id+id$ Fid $E T id+id$ 预测预测分析器接受输入分析器接受输入id * id + id的的前一部分前一部分动作动作 3.3 自上而下分析自上而下分析栈栈输输入入输输出出$E id id+id$ $E T id id+id$ ETE $E T F id

32、id+id$ TFT $E T id id id+id$ Fid $E T id+id$ $E T F id+id$ T FT 预测预测分析器接受输入分析器接受输入id * id + id的的前一部分前一部分动作动作 3.3 自上而下分析自上而下分析栈栈输输入入输输出出$E id id+id$ $E T id id+id$ ETE $E T F id id+id$ TFT $E T id id id+id$ Fid $E T id+id$ $E T F id+id$ T FT $E T F id+id$ 预测预测分析器接受输入分析器接受输入id * id + id的的前一部分前一部分动作动作

33、 3.3 自上而下分析自上而下分析栈栈输输入入输输出出$E id id+id$ $E T id id+id$ ETE $E T F id id+id$ TFT $E T id id id+id$ Fid $E T id+id$ $E T F id+id$ T FT $E T F id+id$ $E T id id+id$ Fid 预测预测分析器接受输入分析器接受输入id * id + id的的前一部分前一部分动作动作 3.3 自上而下分析自上而下分析3.3.5构造预测分析表构造预测分析表（1）对文法的每个产生式对文法的每个产生式A ，执行执行(2)和和(3)（2）对）对FIRST( )的每个

34、终结符的每个终结符a，把把A 加入加入MA,a（3）如如果果在在FIRST( )中中，对对FOLLOW(A)的的每每个个终终结符结符b（包括包括$）,把把A 加入加入MA,b（4）M中中其它没有定义的条目都是其它没有定义的条目都是error3.3 自上而下分析自上而下分析非终非终结符结符输输入入符符号号 other b else .stmt stmt other e_part e_partelsestmte_part expr expr b 多重定义的条目多重定义的条目3.3 自上而下分析自上而下分析非终非终结符结符输输入入符符号号 other b else .stmt stmt oth

35、er e_part e_partelsestmtexpr expr b 消去多重定义消去多重定义3.3 自上而下分析自上而下分析3.3.6 预测分析的错误恢复预测分析的错误恢复1、先对编译器的错误处理做一个概述先对编译器的错误处理做一个概述词词法法错错误误，如如标标识识符符、关关键键字字或或算算符符的的拼拼写写错错语法错误，如算术表达式的括号不配对语法错误，如算术表达式的括号不配对语义错误，如算符作用于不相容的运算对象语义错误，如算符作用于不相容的运算对象逻辑错误，如无穷的递归调用逻辑错误，如无穷的递归调用3.3 自上而下分析自上而下分析2、分析器对错误处理的基本目标、分析器对错误处理的基本目

36、标清清楚楚而而准准确确地地报报告告错错误误的的出出现现，并并尽尽量量少少出出现现伪错误伪错误迅迅速速地地从从每每个个错错误误中中恢恢复复过过来来，以以便便诊诊断断后后面的错误面的错误它不应该使正确程序的处理速度降低太多它不应该使正确程序的处理速度降低太多 3.3 自上而下分析自上而下分析3、非递归预测分析在什么场合下发现错误、非递归预测分析在什么场合下发现错误栈顶的终结符和下一个输入符号不匹配栈顶的终结符和下一个输入符号不匹配a + b $输入输入预测分析程序预测分析程序分析表分析表M输出输出 XYZ$栈栈3.3 自上而下分析自上而下分析3、非递归预测分析在什么场合下发现错误、非递归预测分析在

37、什么场合下发现错误栈顶是非终结符栈顶是非终结符A，输入符号是输入符号是a，而而MA, a是是空白空白a + b $输入输入预测分析程序预测分析程序分析表分析表M输出输出 XYZ$栈栈3.3 自上而下分析自上而下分析4、非递归预测分析：采用、非递归预测分析：采用紧急方式的错误恢复紧急方式的错误恢复发现错误时，分析器每次抛弃一个输入记发现错误时，分析器每次抛弃一个输入记号，直到输入记号属于某个指定的同步记号号，直到输入记号属于某个指定的同步记号集合为止集合为止5、同步、同步词法分析器当前提供的记号流能构成的语词法分析器当前提供的记号流能构成的语法构造，正是语法分析器所期望的法构造，正是语法分析器所

38、期望的3.3 自上而下分析自上而下分析6、同步记号集合的选择、同步记号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有终结符放入非终结符A的的同步记号集合同步记号集合3.3 自上而下分析自上而下分析6、同步记号集合的选择、同步记号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有终结符放入非终结符A的的同步记号集合同步记号集合ifexpr thenstmt（then是是expr的一个同步记号）的一个同步记号）3.3 自上而下分析自上而下分析6、同步记号集合的选择、同步记号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有终结符放入非终结符A的的同步记号集合

39、同步记号集合把高层构造的开始符号加到低层构造的同步记号把高层构造的开始符号加到低层构造的同步记号集合中集合中3.3 自上而下分析自上而下分析6、同步记号集合的选择、同步记号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有终结符放入非终结符A的的同步记号集合同步记号集合把高层构造的开始符号加到低层构造的同步记号把高层构造的开始符号加到低层构造的同步记号集合中集合中a=expr;if(语句的开始符号作为表达式的同步记号，以免表语句的开始符号作为表达式的同步记号，以免表达式出错又遗漏分号时忽略达式出错又遗漏分号时忽略if语句等一大段程序语句等一大段程序)3.3 自上而下分析自上而下分析

40、6、同步记号集合的选择、同步记号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有终结符放入非终结符A的的同步记号集合同步记号集合把高层构造的开始符号加到低层构造的同步记号把高层构造的开始符号加到低层构造的同步记号集合中集合中把把FIRST(A)的终结符加入的终结符加入A的同步记号集合的同步记号集合a=expr;,if（语句的开始符号作为语句的同步符号，以免多出语句的开始符号作为语句的同步符号，以免多出一个逗号时会把一个逗号时会把if语句忽略了）语句忽略了）3.3 自上而下分析自上而下分析6、同步记号集合的选择、同步记号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有

41、终结符放入非终结符A的的同步记号集合同步记号集合把高层构造的开始符号加到低层构造的同步记号把高层构造的开始符号加到低层构造的同步记号集合中集合中把把FIRST(A)的终结符加入的终结符加入A的同步记号集合的同步记号集合如果非终结符可以产生空串，若出错时栈顶是这如果非终结符可以产生空串，若出错时栈顶是这样的非终结符，则可以使用推出空串的产生式样的非终结符，则可以使用推出空串的产生式3.3 自上而下分析自上而下分析非终非终结符结符输输入入符符号号 id+ .EETE E E+TE TTFT T 出错出错T T FT . 例例栈顶为栈顶为T ，面临，面临id时出错时出错3.3 自上而下分析自上而

42、下分析非终非终结符结符输输入入符符号号 id+ .EETE E E+TE TTFT T 出错，出错，用用T T T FT . T 可以产生空串，报错并用可以产生空串，报错并用T 3.3 自上而下分析自上而下分析同步记号集合的选择同步记号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有终结符放入非终结符A的的同步记号集合同步记号集合把高层结构的开始符号加到低层结构的同步记号把高层结构的开始符号加到低层结构的同步记号集合中集合中把把FIRST(A)的终结符加入的终结符加入A的同步记号集合的同步记号集合如果非终结符可以产生空串，若出错时栈顶是这如果非终结符可以产生空串，若出错时栈顶是

43、这样的非终结符，则可以使用推出空串的产生式样的非终结符，则可以使用推出空串的产生式如果终结符在栈顶而不能匹配，弹出此终结符如果终结符在栈顶而不能匹配，弹出此终结符 3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc | bB d 3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc | bB dabbcde（读入（读入ab） ab3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc | bB dabbcdeaAbcde（归约）（归约） abA3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S

44、 aABeA Abc | bB dabbcdeaAbcde（再读入（再读入bc） abAbc3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc | bB dabbcdeaAbcdeaAde（归约）（归约） abAbAc3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc | bB dabbcdeaAbcdeaAde（再读入（再读入d） abAbdAc3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc | bB dabbcdeaAbcdeaAdeaABe（归约）（归约） abAbdAcB3.4 自下而上

45、分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc | bB dabbcdeaAbcdeaAdeaABe(再读入再读入e) eabAbdAcB3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc | bB dabbcdeaAbcdeaAdeaABeS（归约）（归约）SeabAbdAcB3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc | bB dabbcdeaAbcdeaAdeaABeS S rm aABe rm aAde rm aAbcde rm abbcdeSeabAbdAcB3.4 自下而上分析自下而上分析

46、3.4.2 句柄句柄句型的句型的句柄句柄是和某产生式右部匹配的子串，是和某产生式右部匹配的子串，并且，把它归约成该产生式左部的非终结符并且，把它归约成该产生式左部的非终结符代表了最右推导过程的逆过程的一步代表了最右推导过程的逆过程的一步S aABeA Abc | bB dS rm aABe rm aAde rm aAbcde rm abbcde句柄的右边仅含终结符句柄的右边仅含终结符如果文法二义，那么句柄可能不唯一如果文法二义，那么句柄可能不唯一3.4 自下而上分析自下而上分析例例句柄不唯一句柄不唯一E E + E | E E | (E ) | id3.4 自下而上分析自下而上分析例例

47、句柄不唯一句柄不唯一E E + E | E E | (E ) | idE rm E Erm E E + Erm E E +id3rm E id2+id3 rm id1 id2+id3 3.4 自下而上分析自下而上分析例例句柄不唯一句柄不唯一E E + E | E E | (E ) | idE rm E E E rm E + Erm E E + Erm E +id3rm E E +id3rm E E +id3rm E id2+id3 rm E id2+id3 rm id1 id2+id3 rm id1 id2+id3 在句型在句型E E +id3中，句柄不唯一中，句柄不唯一3.4 自下而上分

48、析自下而上分析 3.4.3用栈实现移进用栈实现移进归约分析归约分析先通过先通过移进移进归约分析器在分析输入串归约分析器在分析输入串id1 id2+id3时时的动作序列的动作序列来了解移进来了解移进归约分析的工作方式归约分析的工作方式3.4 自下而上分析自下而上分析栈栈输输入入动动作作$id1 id2+id3$ 3.4 自下而上分析自下而上分析栈栈输输入入动动作作$id1 id2+id3$移进移进 3.4 自下而上分析自下而上分析栈栈输输入入动动作作$id1 id2+id3$移进移进$id1 id2+id3$ 3.4 自下而上分析自下而上分析栈栈输输入入动动作作$id1 i

49、d2+id3$移进移进$id1 id2+id3$按按Eid归约归约 3.4 自下而上分析自下而上分析栈栈输输入入动动作作$id1 id2+id3$移进移进$id1 id2+id3$按按Eid归约归约$E id2+id3$3.4 自下而上分析自下而上分析栈栈输输入入动动作作$id1 id2+id3$移进移进$id1 id2+id3$按按Eid归约归约$E id2+id3$移进移进3.4 自下而上分析自下而上分析栈栈输输入入动动作作$id1 id2+id3$移进移进$id1 id2+id3$按按Eid归约归约$E id2+id3$移进移进$E id2+id3$3.4 自下而上分析自下而

50、上分析栈栈输输入入动动作作$id1 id2+id3$移进移进$id1 id2+id3$按按Eid归约归约$E id2+id3$移进移进$E id2+id3$移进移进3.4 自下而上分析自下而上分析栈栈输输入入动动作作$id1 id2+id3$移进移进$id1 id2+id3$按按Eid归约归约$E id2+id3$移进移进$E id2+id3$移进移进$E id2+id3$3.4 自下而上分析自下而上分析栈栈输输入入动动作作$id1 id2+id3$移进移进$id1 id2+id3$按按Eid归约归约$E id2+id3$移进移进$E id2+id3$移进移进$E id2+id3$

51、按按Eid归约归约3.4 自下而上分析自下而上分析栈栈输输入入动动作作$id1 id2+id3$移进移进$id1 id2+id3$按按Eid归约归约$E id2+id3$移进移进$E id2+id3$移进移进$E id2+id3$按按Eid归约归约$E E+id3$3.4 自下而上分析自下而上分析栈栈输输入入动动作作$id1 id2+id3$移进移进$id1 id2+id3$按按Eid归约归约$E id2+id3$移进移进$E id2+id3$移进移进$E id2+id3$按按Eid归约归约$E E+id3$移进移进3.4 自下而上分析自下而上分析栈栈输输入入动动作作$id1 id

52、2+id3$移进移进$id1 id2+id3$按按Eid归约归约$E id2+id3$移进移进$E id2+id3$移进移进$E id2+id3$按按Eid归约归约$E E+id3$移进移进$E E+id3$3.4 自下而上分析自下而上分析栈栈输输入入动动作作$id1 id2+id3$移进移进$id1 id2+id3$按按Eid归约归约$E id2+id3$移进移进$E id2+id3$移进移进$E id2+id3$按按Eid归约归约$E E+id3$移进移进$E E+id3$移进移进3.4 自下而上分析自下而上分析栈栈输输入入动动作作$id1 id2+id3$移进移进$id1 id2

53、+id3$按按Eid归约归约$E id2+id3$移进移进$E id2+id3$移进移进$E id2+id3$按按Eid归约归约$E E+id3$移进移进$E E+id3$移进移进$E E+id3$3.4 自下而上分析自下而上分析栈栈输输入入动动作作$id1 id2+id3$移进移进$id1 id2+id3$按按Eid归约归约$E id2+id3$移进移进$E id2+id3$移进移进$E id2+id3$按按Eid归约归约$E E+id3$移进移进$E E+id3$移进移进$E E+id3$按按Eid归约归约3.4 自下而上分析自下而上分析栈栈输输入入动动作作$id1 id2+id3

54、$移进移进$id1 id2+id3$按按Eid归约归约$E id2+id3$移进移进$E id2+id3$移进移进$E id2+id3$按按Eid归约归约$E E+id3$移进移进$E E+id3$移进移进$E E+id3$按按Eid归约归约$E E+E$3.4 自下而上分析自下而上分析栈栈输输入入动动作作$id1 id2+id3$移进移进$id1 id2+id3$按按Eid归约归约$E id2+id3$移进移进$E id2+id3$移进移进$E id2+id3$按按Eid归约归约$E E+id3$移进移进$E E+id3$移进移进$E E+id3$按按Eid归约归约$E E+E$按按EE

55、+E归约归约3.4 自下而上分析自下而上分析栈栈输输入入动动作作$id1 id2+id3$移进移进$id1 id2+id3$按按Eid归约归约$E id2+id3$移进移进$E id2+id3$移进移进$E id2+id3$按按Eid归约归约$E E+id3$移进移进$E E+id3$移进移进$E E+id3$按按Eid归约归约$E E+E$按按EE+E归约归约$E E$3.4 自下而上分析自下而上分析栈栈输输入入动动作作$id1 id2+id3$移进移进$id1 id2+id3$按按Eid归约归约$E id2+id3$移进移进$E id2+id3$移进移进$E id2+id3$按按E

56、id归约归约$E E+id3$移进移进$E E+id3$移进移进$E E+id3$按按Eid归约归约$E E+E$按按EE+E归约归约$E E$按按EE E归归约约3.4 自下而上分析自下而上分析栈栈输输入入动动作作$id1 id2+id3$移进移进$id1 id2+id3$按按Eid归约归约$E id2+id3$移进移进$E id2+id3$移进移进$E id2+id3$按按Eid归约归约$E E+id3$移进移进$E E+id3$移进移进$E E+id3$按按Eid归约归约$E E+E$按按EE+E归约归约$E E$按按EE E归归约约$E$3.4 自下而上分析自下而上分析栈栈输输入

57、入动动作作$id1 id2+id3$移进移进$id1 id2+id3$按按Eid归约归约$E id2+id3$移进移进$E id2+id3$移进移进$E id2+id3$按按Eid归约归约$E E+id3$移进移进$E E+id3$移进移进$E E+id3$按按Eid归约归约$E E+E$按按EE+E归约归约$E E$按按EE E归归约约$E$接受接受3.4 自下而上分析自下而上分析要想很好地使用移进要想很好地使用移进归约方式，尚需解决一归约方式，尚需解决一些问题些问题如何决策选择移进如何决策选择移进还是还是归约归约进行归约时，确定右句型中将要归约的子串进行归约时，确定右句型中将要归约的

58、子串进行归约时，如何确定选择哪一个产生式进行归约时，如何确定选择哪一个产生式3.4 自下而上分析自下而上分析 3.4.4 移进移进归约分析的冲突归约分析的冲突 1、移进、移进归约冲突归约冲突例例stmtifexprthenstmt|ifexprthenstmtelsestmt|other如果移进如果移进归约分析器处于格局归约分析器处于格局栈栈输入输入ifexprthenstmtelse$ 3.4 自下而上分析自下而上分析 2、归约、归约归约冲突归约冲突stmt id(parameter_list)|expr=exprparameter_listparameter_list,parame

59、ter | parameterparameteridexprid(expr_list)|idexpr_listexpr_list,expr | expr由由A(I,J)开始的语句开始的语句栈栈输入输入id(id,id)归约成归约成expr还还是是parameter ?3.4 自下而上分析自下而上分析 2、归约、归约归约冲突归约冲突stmt id(parameter_list)|expr=exprparameter_listparameter_list,parameter | parameterparameteridexprid(expr_list)|idexpr_listexpr_list,

60、expr | expr由由A(I,J)开始的语句开始的语句( (词法分析查符号表词法分析查符号表, ,区分第一个区分第一个id) )栈栈输入输入procid(id,id)需要修改上面的文法需要修改上面的文法3.5 LR分析器分析器本节介绍本节介绍LR(k)分析技术分析技术特点特点适用于一大类上下文无关文法适用于一大类上下文无关文法效率高效率高主要介绍构造主要介绍构造LR分析表的三种技术分析表的三种技术简单的简单的LR方法（简称方法（简称SLR）规范的规范的LR方法方法向前看的向前看的LR方法（简称方法（简称LALR） 3.5 LR分析器分析器 3.5.1 LR分析算法分析算法输入输入LR分析

61、程序分析程序输出输出栈栈LR分析器的模型分析器的模型actiongotosmXmsm-1Xm-1s0a1aian$3.5 LR分析器分析器例例 E E + T | E T T T F |T E F (E )|F id状态状态动动作作转转移移 id + ()$ ET F 0 s5s41231 s6acc2r2s7r2r23 r4r4r4r44 s5 s4 8233.5 LR分析器分析器栈栈输输入入动动作作0id id+id$ 3.5 LR分析器分析器栈栈输输入入动动作作0id id+id$ 移进移进 3.5 LR分析器分析器栈栈输输入入动动作作0id id+id$ 移进移进0id5 i

62、d+id$ 3.5 LR分析器分析器栈栈输输入入动动作作0id id+id$ 移进移进0id5 id+id$ 按按Fid归约归约 3.5 LR分析器分析器栈栈输输入入动动作作0id id+id$ 移进移进0id5 id+id$ 按按Fid归约归约0F3 id+id$ 3.5 LR分析器分析器栈栈输输入入动动作作0id id+id$ 移进移进0id5 id+id$ 按按Fid归约归约0F3 id+id$ 按按TF归约归约 3.5 LR分析器分析器栈栈输输入入动动作作0id id+id$ 移进移进0id5 id+id$ 按按Fid归约归约0F3 id+id$ 按按TF归约归约0T2 id+

63、id$3.5 LR分析器分析器栈栈输输入入动动作作0id id+id$ 移进移进0id5 id+id$ 按按Fid归约归约0F3 id+id$ 按按TF归约归约0T2 id+id$ 移进移进3.5 LR分析器分析器栈栈输输入入动动作作0id id+id$ 移进移进0id5 id+id$ 按按Fid归约归约0F3 id+id$ 按按TF归约归约0T2 id+id$ 移进移进0T2 7id+id$3.5 LR分析器分析器栈栈输输入入动动作作0id id+id$ 移进移进0id5 id+id$ 按按Fid归约归约0F3 id+id$ 按按TF归约归约0T2 id+id$ 移进移进0T2 7id

64、+id$ 移进移进3.5 LR分析器分析器栈栈输输入入动动作作0id id+id$ 移进移进0id5 id+id$ 按按Fid归约归约0F3 id+id$ 按按TF归约归约0T2 id+id$ 移进移进0T2 7id+id$ 移进移进0T2 7id5+id$3.5 LR分析器分析器栈栈输输入入动动作作0id id+id$ 移进移进0id5 id+id$ 按按Fid归约归约0F3 id+id$ 按按TF归约归约0T2 id+id$ 移进移进0T2 7id+id$ 移进移进0T2 7id5+id$ 按按Fid归约归约3.5 LR分析器分析器栈栈输输入入动动作作0id id+id$ 移进移进0

65、id5 id+id$ 按按Fid归约归约0F3 id+id$ 按按TF归约归约0T2 id+id$ 移进移进0T2 7id+id$ 移进移进0T2 7id5+id$ 按按Fid归约归约0T2 7F10+id$3.5 LR分析器分析器栈栈输输入入动动作作0id id+id$ 移进移进0id5 id+id$ 按按Fid归约归约0F3 id+id$ 按按TF归约归约0T2 id+id$ 移进移进0T2 7id+id$ 移进移进0T2 7id5+id$ 按按Fid归约归约0T2 7F10+id$ 按按TT F归归约约3.5 LR分析器分析器栈栈输输入入动动作作0id id+id$ 移进移进0id5

66、 id+id$ 按按Fid归约归约0F3 id+id$ 按按TF归约归约0T2 id+id$ 移进移进0T2 7id+id$ 移进移进0T2 7id5+id$ 按按Fid归约归约0T2 7F10+id$ 按按TT F归归约约.3.5 LR分析器分析器栈栈输输入入动动作作0id id+id$ 移进移进0id5 id+id$ 按按Fid归约归约0F3 id+id$ 按按TF归约归约0T2 id+id$ 移进移进0T2 7id+id$ 移进移进0T2 7id5+id$ 按按Fid归约归约0T2 7F10+id$ 按按TT F归归约约.0E1$3.5 LR分析器分析器栈栈输输入入动动作作0id i

67、d+id$ 移进移进0id5 id+id$ 按按Fid归约归约0F3 id+id$ 按按TF归约归约0T2 id+id$ 移进移进0T2 7id+id$ 移进移进0T2 7id5+id$ 按按Fid归约归约0T2 7F10+id$ 按按TT F归归约约.0E1$接受接受3.5 LR分析器分析器 3.5.2LR文法和文法和LR分析方法的特点分析方法的特点1、概念、概念活前缀：右句型的前缀，该前缀不超过最右句柄活前缀：右句型的前缀，该前缀不超过最右句柄的右端的右端S *rm A w rm w 的任何前缀（包括的任何前缀（包括和和本身）都是活前缀本身）都是活前缀3.5 LR分析器分析器 3.5.

68、2LR文法和文法和LR分析方法的特点分析方法的特点1、概念、概念活前缀：右句型的前缀，该前缀不超过最右句柄活前缀：右句型的前缀，该前缀不超过最右句柄的右端的右端2、定义、定义LR文法文法：我们能为之构造出所有条目都唯一的我们能为之构造出所有条目都唯一的LR分析表分析表3.5 LR分析器分析器 3、LR分析方法的特点分析方法的特点栈中的文法符号总是形成一个活前缀栈中的文法符号总是形成一个活前缀3.5 LR分析器分析器栈栈输输入入动动作作0id id+id$ 移进移进0id5 id+id$ 按按Fid归约归约0F3 id+id$ 按按TF归约归约0T2 id+id$ 移进移进0T2 7id+id

69、$ 移进移进0T2 7id5+id$ 按按Fid归约归约0T2 7F10+id$ 按按TT F归归约约.0E1$接受接受3.5 LR分析器分析器 3、LR分析方法的特点分析方法的特点栈中的文法符号总是形成一个活前缀栈中的文法符号总是形成一个活前缀分析表的转移函数本质上是识别活前缀的分析表的转移函数本质上是识别活前缀的DFA3.5 LR分析器分析器例例 E E + T | E T 下表绿色部分构成下表绿色部分构成 T T F |T E识别活前缀识别活前缀DFA的的 F (E )|F id状态转换表状态转换表状态状态动动作作转转移移 id + ()$ ET F 0 s5s41231 s6acc

70、2r2s7r2r23 r4r4r4r44 s5 s4 8233.5 LR分析器分析器 3、LR分析方法的特点分析方法的特点栈中的文法符号总是形成一个活前缀栈中的文法符号总是形成一个活前缀分析表的转移函数本质上是识别活前缀的分析表的转移函数本质上是识别活前缀的DFA栈顶的状态符号包含了确定句柄所需要的一切信息栈顶的状态符号包含了确定句柄所需要的一切信息3.5 LR分析器分析器栈栈输输入入动动作作0id id+id$ 移进移进0id5 id+id$ 按按Fid归约归约0F3 id+id$ 按按TF归约归约0T2 id+id$ 移进移进0T2 7id+id$ 移进移进0T2 7id5+id$ 按按

71、Fid归约归约0T2 7F10+id$ 按按TT F归归约约.0E1$接受接受3.5 LR分析器分析器 3、LR分析方法的特点分析方法的特点栈中的文法符号总是形成一个活前缀栈中的文法符号总是形成一个活前缀分析表的转移函数本质上是识别活前缀的分析表的转移函数本质上是识别活前缀的DFA栈顶的状态符号包含了确定句柄所需要的一切信息栈顶的状态符号包含了确定句柄所需要的一切信息是已知的最一般的无回溯的移进是已知的最一般的无回溯的移进归约方法归约方法能分析的文法类是预测分析法能分析的文法类的真能分析的文法类是预测分析法能分析的文法类的真超集超集能及时发现语法错误能及时发现语法错误手工构造分析表的工作量太

72、大手工构造分析表的工作量太大3.5 LR分析器分析器 4、LR分析方法和分析方法和LL分析方法的比较分析方法的比较LR(1)方方法法 LL( (1)方方法法建立分析树的方式建立分析树的方式自自下下而而上上自自上上而而下下 3.5 LR分析器分析器 4、LR分析方法和分析方法和LL分析方法的比较分析方法的比较LR(1)方方法法 LL( (1)方方法法建立分析树的方式建立分析树的方式自自下下而而上上自自上上而而下下归约还是推导归约还是推导规规范范归归约约最最左左推推导导 3.5 LR分析器分析器 4、LR分析方法和分析方法和LL分析方法的比较分析方法的比较在下面的推导中，最后一步用的

73、是在下面的推导中，最后一步用的是Al S rm rm A b w rm l b w LL(1)决定用该决定用该产生式的位置产生式的位置LR(1)决定用该决定用该产生式的位置产生式的位置3.5 LR分析器分析器 4、LR分析方法和分析方法和LL分析方法的比较分析方法的比较LR(1)方方法法 LL( (1)方方法法建立分析树的方式建立分析树的方式自自下下而而上上自自上上而而下下归约还是推导归约还是推导规规范范归归约约最最左左推推导导决定使用产生式的决定使用产生式的时机时机看见产生式整个看见产生式整个右部推出的终结右部推出的终结符串后才算是看符串后才算是看准了用哪个产生准了用哪个产生式进

74、行归约式进行归约看见产生式右看见产生式右部推出的第一部推出的第一个终结符后便个终结符后便确定用哪个产确定用哪个产生式进行推导生式进行推导 3.5 LR分析器分析器 4、LR分析方法和分析方法和LL分析方法的比较分析方法的比较LR(1)方方法法 LL( (1)方方法法对文法的显式限制对文法的显式限制对文法没有限制对文法没有限制无左递归、无无左递归、无公共左因子公共左因子3.5 LR分析器分析器 4、LR分析方法和分析方法和LL分析方法的比较分析方法的比较LR(1)方方法法 LL( (1)方方法法对文法的显式限制对文法的显式限制对文法没有限制对文法没有限制无左递归、无无左递归、无公共左

75、因子公共左因子分析表比较分析表比较状态状态文法符号文法符号分析表大分析表大非非终终结结符符终终结结符符分析表小分析表小3.5 LR分析器分析器 4、LR分析方法和分析方法和LL分析方法的比较分析方法的比较LR(1)方方法法 LL( (1)方方法法对文法的显式限制对文法的显式限制对文法没有限制对文法没有限制无左递归、无无左递归、无公共左因子公共左因子分析表比较分析表比较状态状态文法符号文法符号分析表大分析表大非非终终结结符符终终结结符符分析表小分析表小分析栈比较分析栈比较状态栈状态栈，通常状通常状态比文法符号包态比文法符号包含更多信息含更多信息文法符号栈文法符号栈 3.5 LR分析

76、器分析器 4、LR分析方法和分析方法和LL分析方法的比较分析方法的比较LR(1)方方法法 LL( (1)方方法法确定句柄确定句柄根据栈顶状态和根据栈顶状态和下一个符号便可下一个符号便可以确定句柄和归以确定句柄和归约所用产生式约所用产生式无句柄概念无句柄概念 3.5 LR分析器分析器 4、LR分析方法和分析方法和LL分析方法的比较分析方法的比较LR(1)方方法法 LL( (1)方方法法确定句柄确定句柄根据栈顶状态和根据栈顶状态和下一个符号便可下一个符号便可以确定句柄和归以确定句柄和归约所用产生式约所用产生式无句柄概念无句柄概念语法错误语法错误决不会将出错点决不会将出错点后的符号移

77、入分后的符号移入分析栈析栈和和LR一一样样，决决不不会会读读过过出出错错点而不报错点而不报错3.5 LR分析器分析器 3.5.3构造构造SLR分析表分析表术语：术语：LR(0)项目项目（简称（简称项目项目）在右部的某个地方加点的产生式在右部的某个地方加点的产生式3.5 LR分析器分析器 3.5.3构造构造SLR分析表分析表术语：术语：LR(0)项目项目（简称（简称项目项目）在右部的某个地方加点的产生式在右部的某个地方加点的产生式加点的目的是用来表示分析过程中的状态加点的目的是用来表示分析过程中的状态3.5 LR分析器分析器 3.5.3构造构造SLR分析表分析表术语：术语：LR(0)项目项目（

78、简称（简称项目项目）在右部的某个地方加点的产生式在右部的某个地方加点的产生式加点的目的是用来表示分析过程中的状态加点的目的是用来表示分析过程中的状态exprexpr+term 3.5 LR分析器分析器 3.5.3构造构造SLR分析表分析表术语：术语：LR(0)项目项目（简称（简称项目项目）在右部的某个地方加点的产生式在右部的某个地方加点的产生式加点的目的是用来表示分析过程中的状态加点的目的是用来表示分析过程中的状态exprexpr+term*termfactor 3.5 LR分析器分析器 3.5.3构造构造SLR分析表分析表术语：术语：LR(0)项目项目（简称（简称项目项目）在右部的某个地方加

79、点的产生式在右部的某个地方加点的产生式加点的目的是用来表示分析过程中的状态加点的目的是用来表示分析过程中的状态exprexpr+term*termfactor 3.5 LR分析器分析器 3.5.3构造构造SLR分析表分析表术语：术语：LR(0)项目项目（简称（简称项目项目）在右部的某个地方加点的产生式在右部的某个地方加点的产生式加点的目的是用来表示分析过程中的状态加点的目的是用来表示分析过程中的状态例例 AXYZ对应有四个项目对应有四个项目A XYZA XYZA XYZA XYZ例例 A只有一个项目和它对应只有一个项目和它对应A 3.5 LR分析器分析器构造构造SLR分析表的两大步骤分析表的

80、两大步骤1、从文法构造识别活前缀的、从文法构造识别活前缀的DFA2、从上述、从上述DFA构造分析表构造分析表3.5 LR分析器分析器 1、从文法构造识别活前缀的、从文法构造识别活前缀的DFA1）拓广文法）拓广文法E E +T | TT T F |F F (E )|id 3.5 LR分析器分析器 1、从文法构造识别活前缀的、从文法构造识别活前缀的DFA1）拓广文法）拓广文法E EE E +T | TT T F |F F (E )|id 3.5 LR分析器分析器 1、从文法构造识别活前缀的、从文法构造识别活前缀的DFA2）构造）构造LR(0)项目集规范族项目集规范族I0:EE3.5 LR分析器分析

81、器 1、从文法构造识别活前缀的、从文法构造识别活前缀的DFA2）构造）构造LR(0)项目集规范族项目集规范族I0:EEE E +T E T3.5 LR分析器分析器 1、从文法构造识别活前缀的、从文法构造识别活前缀的DFA2）构造）构造LR(0)项目集规范族项目集规范族I0:EEE E +T E TT T F T F3.5 LR分析器分析器 1、从文法构造识别活前缀的、从文法构造识别活前缀的DFA2）构造）构造LR(0)项目集规范族项目集规范族I0:EEE E +T E TT T FT FF (E)F id3.5 LR分析器分析器 1、从文法构造识别活前缀的、从文法构造识别活前缀的DFA2）构造

82、）构造LR(0)项目集规范族项目集规范族I0:EE( (核心项目核心项目) )E E +T E T( (非核心项目，非核心项目，T T F 通过对核心项目求闭包通过对核心项目求闭包T F 而获得而获得) )F (E)F id3.5 LR分析器分析器 1、从文法构造识别活前缀的、从文法构造识别活前缀的DFA2）构造）构造LR(0)项目集规范族项目集规范族I0:I1:EEE E E E +T E E+ T E TT T F T FF (E)F idE3.5 LR分析器分析器 1、从文法构造识别活前缀的、从文法构造识别活前缀的DFA2）构造）构造LR(0)项目集规范族项目集规范族I0:I1:EEE

83、E E E +T E E+ T E TT T F I1:=goto(I0,E )T FF (E)F idE3.5 LR分析器分析器 1、从文法构造识别活前缀的、从文法构造识别活前缀的DFA2）构造）构造LR(0)项目集规范族项目集规范族I0:I1:EEE E E E +T E E+ T E TT T F I2:T FE T F (E)T T FF idET3.5 LR分析器分析器 1、从文法构造识别活前缀的、从文法构造识别活前缀的DFA2）构造构造LR(0)项目集规范族项目集规范族I0:I1:EEE E E E +T E E+ T E TT T F I2:T FE T F (E)T T FF

84、idI3:T FETF3.5 LR分析器分析器 I0:I4:EEF (E)E E +T E TT T FT FF (E)F id(3.5 LR分析器分析器 I0:I4:EEF (E)E E +T E E + T E TE TT T FT T FT FT FF (E)F (E)F idF id(3.5 LR分析器分析器 I0:I4:EEF (E)E E +T E E + T E TE TT T FT T FT FT FF (E)F (E)F idF idI5:F id(id3.5 LR分析器分析器 I1I0EI3I2I4I5TF(id 3.5 LR分析器分析器 I1I0EI3I2I4I5TF(i

85、dI1:E E E E+ T 3.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI1:E E E E+ TI6 :EE +TTT F TFF(E)Fid+3.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI1: I2:E EET E E+ TTT F I6 :EE +TTT F TFF(E)Fid+3.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI1: I2:E EET E E+ TTT F I6 :I7:EE +TTT F TT F F(E)TFFidF(E)Fid+ 3.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI3:T F 无状态转换

86、无状态转换3.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI4:F (E )E E + TE TT T F T FF ( E )F id 3.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI4: I8:F (E )F(E)E E + TE E+ T E TT T F T FF ( E )F id E3.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI4: I8:F (E )F(E)E E + TE E+ T E TT T F I2:T FETF ( E )TT F F id TE3.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI4: I8:F

87、 (E )F(E)E E + TE E+ T E TT T F I2:T FETF ( E )TT F F id I3:TFTFE3.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI4: I8:F (E )F(E)E E + TE E+ T E TT T F I2:T FETF ( E )TT F F id I3:TFI4:F(E).TF(E3.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI4: I8:F (E )F(E)E E + TE E+ T E TT T F I2:T FETF ( E )TT F F id I3:TFI4:I5:F(E)F id.TF(idE

88、3.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI5:F id 无状无状态转换态转换3.5 LR分析器分析器 I1I0+EI6I3I2I4I8I7I5指向指向I2指向指向I3T* *F(Eidid(FT3.5 LR分析器分析器 I1I0+指向指向I7EI6I9I3I2I4I11I8I7I10* *TI5指向指向I4指向指向I3指向指向I5指向指向I4指向指向I5指向指向I6指向指向I2指向指向I3F(FTid* *id(F(Eid+)id(FTE E E+T E+T F E+T id E+T F id把所有状态都把所有状态都作为接受状态作为接受状态这是一个这是一个DFAE+T F

89、的所有前缀都可接受的所有前缀都可接受3.5 LR分析器分析器 I0:E EE E +TE TT T FT FF (E)F id 也可以构造一个识别活前缀的也可以构造一个识别活前缀的NFA N3.5 LR分析器分析器 I0:E E E EE E E E +T E T E E +T E TT T FT F T T F T FF (E)F idF (E)F idE 也可以构造一个识别活前缀的也可以构造一个识别活前缀的NFA N 每个项目一个状态每个项目一个状态 3.5 LR分析器分析器从文法构造的识别活前缀的从文法构造的识别活前缀的DFA的一些特点的一些特点概念：概念：有效项目有效项目如果如果S

90、*rm Aw rm 1 2w，那么就说那么就说项目项目A 1 2对活前缀对活前缀1是是有效的有效的（1）一个项目可能对好几个活前缀都是有效的一个项目可能对好几个活前缀都是有效的E E+T对对和和(这两个活前缀都有效这两个活前缀都有效E E E+T( ， 1都为空都为空)E E (E) (E+T)( =“(”， 1为空为空)该该DFA读过读过和和(后到达不同的状态，那么项目后到达不同的状态，那么项目E E+T就出现在对应的不同项目集中就出现在对应的不同项目集中3.5 LR分析器分析器从文法构造的识别活前缀的从文法构造的识别活前缀的DFA的一些特点的一些特点概念：概念：有效项目有效项目如果如

91、果S*rm Aw rm 1 2w，那么就说那么就说项目项目A 1 2对活前缀对活前缀1是是有效的有效的（1）一个项目可能对好几个活前缀都是有效的一个项目可能对好几个活前缀都是有效的从项目从项目A 1 2对活前缀对活前缀1有效这个事实可有效这个事实可以知道以知道如果如果 2 ，应该移进，应该移进如果如果 2= ，应该用产生式应该用产生式A 1归约归约3.5 LR分析器分析器从文法构造的识别活前缀的从文法构造的识别活前缀的DFA的一些特点的一些特点概念：概念：有效项目有效项目如果如果S*rm Aw rm 1 2w，那么就说那么就说项目项目A 1 2对活前缀对活前缀1是是有效的有效的（1）一个项

92、目可能对好几个活前缀都是有效的一个项目可能对好几个活前缀都是有效的（2）一个活前缀可能有多个有效项目一个活前缀可能有多个有效项目一个活前缀一个活前缀的有效项目集就是从这个的有效项目集就是从这个DFA的初的初态出发，沿着标记为态出发，沿着标记为的路径到达的那个项目集（状的路径到达的那个项目集（状态）态）3.5 LR分析器分析器例例串串E+T 是活前缀，读完它后，是活前缀，读完它后，DFA处于处于状态状态I I7 I7:TT F,F(E ),Fid E E E EE E E+T E+T E+T E+T F E+T F E+T F E+T id E+T (E) E+T id E+T F id

93、3.5 LR分析器分析器构造构造SLR分析表的两大步骤分析表的两大步骤1、从文法构造识别活前缀的、从文法构造识别活前缀的DFA2、从上述、从上述DFA构造构造分析表分析表3.5 LR分析器分析器 2、从、从DFA构造构造SLR分析表分析表状态状态i从从Ii构造，它的构造，它的action函数如下确定：函数如下确定：如果如果 A a 在在Ii中，并且中，并且goto(Ii,a )= Ij，那那么置么置actioni,a为为sj如果如果A 在在Ii中，那么对中，那么对FOLLOW(A)中的所中的所有有a，置置actioni,a为为rj, ,j是产生式是产生式 A 的编号的编号如果如果SS在在Ii

94、中，那么置中，那么置actioni,$为接受为接受acc如果出现动作冲突，那么该文法就不是如果出现动作冲突，那么该文法就不是SLR(1)的的3.5 LR分析器分析器 2、从、从DFA构造构造SLR分析表分析表状态状态i从从Ii构造，它的构造，它的action函数如下确定：函数如下确定： . . . . . .使用下面规则构造状态使用下面规则构造状态i的的goto函数：函数：对所有的非终结符对所有的非终结符A，如果如果goto(Ii,A)= Ij, , 那么那么gotoi,A=j3.5 LR分析器分析器 2、从、从DFA构造构造SLR分析表分析表状态状态i从从Ii构造，它的构造，它的action

95、函数如下确定：函数如下确定： . . . . . .使用下面规则构造状态使用下面规则构造状态i的的goto函数：函数： . . . . . .不能由上面两步定义的条目都置为不能由上面两步定义的条目都置为error分析器的初始状态是包含分析器的初始状态是包含SS的项目集的项目集对应的状态对应的状态3.5 LR分析器分析器例例 I2:E TT T F因为因为FOLLOW(E)=$,+,), 所以所以action2,$=action2,+=action2,)=r2action2, =s73.5 LR分析器分析器例例 SLR(1)文法的描述能力有限文法的描述能力有限S V =ES EV EV id

96、E VI0 : S S S V =ES EV EV idE VI2 : S V =EE VV 第一项目使得第一项目使得action2,=s6第二项目使得第二项目使得action2,=为按为按EV归约，因为归约，因为=是是E的一个后继符的一个后继符=是是E的一个后继符：的一个后继符： S $V =E $ E =E $3.5 LR分析器分析器例例 SLR(1)文法的描述能力有限文法的描述能力有限S V =ES EV EV idE VI0 : S S S V =ES EV EV idE VI2 : S V =EE VV 第一项目使得第一项目使得action2,=s6第二项目使得第二项目使得acti

97、on2,=为按为按EV归约，因为归约，因为=是是E的一个后继符的一个后继符在所关注场合在所关注场合E的后继是的后继是$： S $V =E $ E =E $S $E $ V $3.5 LR分析器分析器 3.5.4 构造规范的构造规范的LR分析表分析表LR(1)项目：项目：重新定义项目重新定义项目，让它带上搜索符，成为如下形式让它带上搜索符，成为如下形式A ,aLR(1)项目项目A ,a对活前缀对活前缀有效：有效：如果存在着推导如果存在着推导S *rm Aw rm w，其中：其中： =；a是是w的第一个符号，或者的第一个符号，或者w是是且且a是是$3.5 LR分析器分析器例例 S BBB b

98、B |a从最右推导从最右推导S *rmbbBbarm bbbBba看出：看出： BbB,b对活前缀对活前缀 =bbb是有效的是有效的对于项目对于项目A ,a，当当为空时，是根据搜索为空时，是根据搜索符符a来填表（归约项目），而不是根据来填表（归约项目），而不是根据A的后继符来的后继符来填表填表3.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/a3.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/aB bB,b/aB a,b/aI3B a,b/aI4ab3.5 LR

99、分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/aB bB,b/aB a,b/aI3B a,b/aI4aabbS BB,$I5B bB,$B bB,$B a,$I6B bB,$I9B a,$I7B bB,b/aI8BbbBaaB3.5 LR分析器分析器构造规范的构造规范的LR分析表分析表(1)基于基于LR(1)项目来构造识别项目来构造识别G 活前缀的活前缀的DFA(2)从从Ii构造分析器的状态构造分析器的状态i,状态状态i的的action函数如下确定函数如下确定如果如果A a ,b在在Ii中，且中，且

100、goto(Ii,a)= Ij ，那那么置么置actioni,a为为sj如果如果A , a在在Ii中，且中，且A S ，那么置那么置actioni,a为为rj如果如果SS, $在在Ii中，那么置中，那么置actioni,$=acc如果用上面规则构造出现了冲突，那么文法就不是如果用上面规则构造出现了冲突，那么文法就不是LR(1)的的3.5 LR分析器分析器构造规范的构造规范的LR分析表分析表(1)基于基于LR(1)项目来构造识别项目来构造识别G 活前缀的活前缀的DFA(2)从从Ii构造分析器的状态构造分析器的状态i,状态状态i的的action函数如下确定函数如下确定 .(3)状态状态i的的got

101、o函数如下确定：函数如下确定：如果如果goto(Ii,A)= Ij,那么那么gotoi,A=j3.5 LR分析器分析器构造规范的构造规范的LR分析表分析表(1)基于基于LR(1)项目来构造识别项目来构造识别G 活前缀的活前缀的DFA(2)从从Ii构造分析器的状态构造分析器的状态i,状态状态i的的action函数如下确定函数如下确定 .(3)状态状态i的的goto函数如下确定：函数如下确定：.(4)用上面规则未能定义的所有条目都置为用上面规则未能定义的所有条目都置为error3.5 LR分析器分析器构造规范的构造规范的LR分析表分析表(1)基于基于LR(1)项目来构造识别项目来构造识别G 活

102、前缀的活前缀的DFA(2)从从Ii构造分析器的状态构造分析器的状态i,状态状态i的的action函数如下确定函数如下确定 .(3)状态状态i的的goto函数如下确定：函数如下确定：.(4)用上面规则未能定义的所有条目都置为用上面规则未能定义的所有条目都置为error(5)分析器的初始状态是包含分析器的初始状态是包含SS,$的项目集对应的项目集对应的状态的状态3.5 LR分析器分析器先前基于先前基于SLR(1)有移进有移进- -归约冲突的例子，在归约冲突的例子，在基于规范基于规范LR(1)时无冲突时无冲突S V =ES EV EV idE VI0 : S S，$S V =E,$S E,$V E

103、,=/$V id,=/$E V,$I2 : S V =E,$E V,$V 3.5 LR分析器分析器 3.5.5 构造构造LALR分析表分析表研究研究LALR的的原因原因规范规范LR分析表的状态数偏多分析表的状态数偏多LALR特点特点LALR和和SLR的分析表有同样多的状态，比规范的分析表有同样多的状态，比规范LR分析表要小得多分析表要小得多LALR的能力介于的能力介于SLR和和规范规范LR之间之间LALR的能力在很多情况下已经够用的能力在很多情况下已经够用LALR分析表构造方法分析表构造方法通过合并规范通过合并规范LR(1)项目集来得到项目集来得到3.5 LR分析器分析器 S S,$I0S B

104、B,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/aB bB,b/aB a,b/aI3B a,b/aI4aabbS BB,$I5B bB,$B bB,$B a,$I6B bB,$I9B a,$I7B bB,b/aI8BbbBaaBI4和和I7仅搜索符不一样仅搜索符不一样3.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/aB bB,b/aB a,b/aI3B a,b/aI4aabbS BB,$I5B bB,$B bB,$B a,$I6B b

105、B,$I9B a,$I7B bB,b/aI8BbbBaaBI4和和I7合并合并3.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/aB bB,b/aB a,b/aI3B a,b/aI4aabbS BB,$I5B bB,$B bB,$B a,$I6B bB,$I9B a,$I7B bB,b/aI8BbbBaaB输入为输入为bbabba$3.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/aB bB,

106、b/aB a,b/aI3B a,b/aI4aabbS BB,$I5B bB,$B bB,$B a,$I6B bB,$I9B a,$I7B bB,b/aI8BbbBaaB输入为输入为bba$3.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/aB bB,b/aB a,b/aI3B a,b/aI4aabbS BB,$I5B bB,$B bB,$B a,$I6B bB,$I9B a,$I7B bB,b/aI8BbbBaaB有三组同心集，都合并有三组同心集，都合并3.5 LR分析器分析器 S S,$I0

107、S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/a/$B bB,b/a/$B a,b/a/$I36B a,b/a/$I47aabbS BB,$I5B bB,b/a/$I89BbBa3.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/a/$B bB,b/a/$B a,b/a/$I36B a,b/a/$I47aabbS BB,$I5B bB,b/a/$I89BbBa栈栈输入输入0bba$3.5 LR分析器分析器 S S,$I0S BB,

108、$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/a/$B bB,b/a/$B a,b/a/$I36B a,b/a/$I47aabbS BB,$I5B bB,b/a/$I89BbBa栈栈输入输入0b36ba$3.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/a/$B bB,b/a/$B a,b/a/$I36B a,b/a/$I47aabbS BB,$I5B bB,b/a/$I89BbBa栈栈输入输入0b36b36a$3.5 LR分析器分析器

109、S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/a/$B bB,b/a/$B a,b/a/$I36B a,b/a/$I47aabbS BB,$I5B bB,b/a/$I89BbBa栈栈输入输入0b36b36a47$3.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/a/$B bB,b/a/$B a,b/a/$I36B a,b/a/$I47aabbS BB,$I5B bB,b/a/$I89BbBa栈栈输入输入0b36b3

110、6B89$3.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/a/$B bB,b/a/$B a,b/a/$I36B a,b/a/$I47aabbS BB,$I5B bB,b/a/$I89BbBa栈栈输入输入0b36B89$3.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/a/$B bB,b/a/$B a,b/a/$I36B a,b/a/$I47aabbS BB,$I5B bB,b/a/$I89B

111、bBa栈栈输入输入0B2$报错报错3.5 LR分析器分析器 1、合并同心、合并同心项目集项目集可能会引起冲突可能会引起冲突同心的同心的LR(1)项目集：项目集：略去搜索符后它们是相同的集合略去搜索符后它们是相同的集合3.5 LR分析器分析器 1、合并同心、合并同心项目集项目集可能会引起冲突可能会引起冲突同心集的合并不会引起新的移进同心集的合并不会引起新的移进归约冲突归约冲突项目集项目集1项目集项目集2A ,aB a ,b.若合并后有冲突若合并后有冲突3.5 LR分析器分析器 1、合并同心、合并同心项目集项目集可能会引起冲突可能会引起冲突同心集的合并不会引起新的移进同心集的合并不会引起新的移进

112、归约冲突归约冲突项目集项目集1项目集项目集2A ,aB a ,bB a ,cA ,d.则合并前就有冲突则合并前就有冲突3.5 LR分析器分析器 1、合并同心、合并同心项目集项目集可能会引起冲突可能会引起冲突同心集的合并不会引起新的移进同心集的合并不会引起新的移进归约冲突归约冲突同心集的合并有可能产生新的归约同心集的合并有可能产生新的归约归约冲突归约冲突S SS aAd | bBd | aBe| bAeA c B c对对ac有效的项目集有效的项目集A c ,dB c ,e 对对bc有效的项目集有效的项目集A c ,eB c ,d 合并同心合并同心集后集后A c ,d/eB c ,d/e 该

113、文法是该文法是LR(1)的，的，但不是但不是LALR(1)的的3.5 LR分析器分析器 2、构造、构造LALR(1)分析表分析表(1)构造构造LR(1)项目集规范族项目集规范族C=I0,I1,In(2)寻找寻找LR(1)项目集规范族中同心的项目集，项目集规范族中同心的项目集，用它们的并集代替它们用它们的并集代替它们(3)按构造规范按构造规范LR(1)分析表的方式构造分析表分析表的方式构造分析表3.5 LR分析器分析器下面文法是下面文法是LALR(1)的，因无同心集可合并的，因无同心集可合并但不是但不是SLR(1)的的S V =ES EV EV idE VI0 : S S，$S V =E,$S

114、 E,$V E,=/$V id,=/$E V,$I2 : S V =E,$E V,$V 3.5 LR分析器分析器 3.5.6 非非LR的上下文无关结构的上下文无关结构若自左向右扫描的移进若自左向右扫描的移进归约分析器能及归约分析器能及时识别出现在栈顶的句柄，那么相应的文法时识别出现在栈顶的句柄，那么相应的文法就是就是LR的的语言语言L =wwR|w (a|b)*的文法的文法S aSa |bSb | 不是不是LR的的ababbbbaba语言语言L =wcwR|w (a|b)*的文法的文法S aSa |bSb |c是是LR的的ababbcbbaba3.5 LR分析器分析器例例为语言为语言L

116、语言为语言L=ambn|nm 0写三个文法写三个文法, ,它们分别是它们分别是LR(1)的、二义的和非二义且非的、二义的和非二义且非LR(1)的的LR(1)文法：文法：S AB A aAb | B Bb| b非二义且非非二义且非LR(1)的的文法文法：S aSb|BBBb|b二义的二义的文法：文法：S aSb|Sb|ba a a b b b b b3.6 二义文法的应用二义文法的应用二义文法的特点：二义文法的特点：二义文法决不是二义文法决不是LR文法文法简洁、自然简洁、自然例例二义文法二义文法 E E + E |E E |(E)|id非非二义的文法：二义的文法：E E + T |TT T

117、F |FF (E) |id3.6 二义文法的应用二义文法的应用二义文法的特点：二义文法的特点：二义文法决不是二义文法决不是LR文法文法简洁、自然简洁、自然可以用文法以外的信息来消除二义可以用文法以外的信息来消除二义语法分析的效率高（基于消除二义后得到的语法分析的效率高（基于消除二义后得到的分析表）分析表）3.6 二义文法的应用二义文法的应用 3.6.1 使用文法以外信息来解决分析动作冲突使用文法以外信息来解决分析动作冲突例例二义文法二义文法 E E + E |E E |(E)|id规定：规定：优先级高于优先级高于+，两者都是左结合两者都是左结合3.6 二义文法的应用二义文法的应用 3.6

118、.1 使用文法以外信息来解决分析动作冲突使用文法以外信息来解决分析动作冲突例例二义文法二义文法 E E + E |E E |(E)|id规定：规定：优先级高于优先级高于+，两者都是左结合两者都是左结合LR(0)项目集项目集I7E E+ EE E+EE E E3.6 二义文法的应用二义文法的应用 3.6.1 使用文法以外信息来解决分析动作冲突使用文法以外信息来解决分析动作冲突例例二义文法二义文法 E E + E |E E |(E)|id规定：规定：优先级高于优先级高于+，两者都是左结合两者都是左结合LR(0)项目集项目集I7E E+ EE E+Eid+id+id E E E面临面临+，归

119、约归约3.6 二义文法的应用二义文法的应用 3.6.1 使用文法以外信息来解决分析动作冲突使用文法以外信息来解决分析动作冲突例例二义文法二义文法 E E + E |E E |(E)|id规定：规定：优先级高于优先级高于+，两者都是左结合两者都是左结合LR(0)项目集项目集I7E E+ EE E+Eid+id+id E E Eid+id id 面临面临+，归约归约面临面临，移进移进3.6 二义文法的应用二义文法的应用 3.6.1 使用文法以外信息来解决分析动作冲突使用文法以外信息来解决分析动作冲突例例二义文法二义文法 E E + E |E E |(E)|id规定：规定：优先级高于优先级

120、高于+，两者都是左结合两者都是左结合LR(0)项目集项目集I7E E+ EE E+Eid+id+id E E Eid+id id 面临面临+，归约归约面临面临，移进移进面临面临)和和$，归约，归约3.6 二义文法的应用二义文法的应用 3.6.1 使用文法以外信息来解决分析动作冲突使用文法以外信息来解决分析动作冲突例例二义文法二义文法 E E + E |E E |(E)|id规定：规定：优先级高于优先级高于+，两者都是左结合两者都是左结合LR(0)项目集项目集I8E E EE E+EE E E3.6 二义文法的应用二义文法的应用 3.6.1 使用文法以外信息来解决分析动作冲突使用文法以外信

121、息来解决分析动作冲突例例二义文法二义文法 E E + E |E E |(E)|id规定：规定：优先级高于优先级高于+，两者都是左结合两者都是左结合LR(0)项目集项目集I8E E EE E+Eid id+id E E E面临面临+，归约归约3.6 二义文法的应用二义文法的应用 3.6.1 使用文法以外信息来解决分析动作冲突使用文法以外信息来解决分析动作冲突例例二义文法二义文法 E E + E |E E |(E)|id规定：规定：优先级高于优先级高于+，两者都是左结合两者都是左结合LR(0)项目集项目集I8E E EE E+Eid id+id E E Eid id id面临面临+，归约归

122、约面临面临，归约归约3.6 二义文法的应用二义文法的应用 3.6.1 使用文法以外信息来解决分析动作冲突使用文法以外信息来解决分析动作冲突例例二义文法二义文法 E E + E |E E |(E)|id规定：规定：优先级高于优先级高于+，两者都是左结合两者都是左结合LR(0)项目集项目集I8E E EE E+Eid id+id E E Eid id id 面临面临+，归约归约面临面临，归约归约面临面临)和和$，归约，归约3.6 二义文法的应用二义文法的应用 3.6.2特殊情况产生式引起的二义性特殊情况产生式引起的二义性E E subE supEE E subEE E supEE EE c

123、3.6 二义文法的应用二义文法的应用 3.6.2特殊情况产生式引起的二义性特殊情况产生式引起的二义性E E subE supEE E subEE E supEE EE c从定义形式语言的角度说，第一个产生式从定义形式语言的角度说，第一个产生式是多余的是多余的3.6 二义文法的应用二义文法的应用 3.6.2特殊情况产生式引起的二义性特殊情况产生式引起的二义性E E subE supEE E subEE E supEE EE c联系到语义处理，第一个产生式是必要的联系到语义处理，第一个产生式是必要的3.6 二义文法的应用二义文法的应用 3.6.2特殊情况产生式引起的二义性特殊情况产生式引起的二义性

124、E E subE supEE E subEE E supEE EE c对对a subi sup2，需要下面第一种输出，需要下面第一种输出3.6 二义文法的应用二义文法的应用 3.6.2特殊情况产生式引起的二义性特殊情况产生式引起的二义性E E subE supEI11:E E subE E E subE supE E E supE E E supEE E.E c3.6 二义文法的应用二义文法的应用 3.6.3LR分析的错误恢复分析的错误恢复1、LR分析器分析器在什么情况下发现错误在什么情况下发现错误访问动作表时若遇到出错条目访问动作表时若遇到出错条目访问转移表时它决不会遇到出错条目访问转移表时

125、它决不会遇到出错条目决不会把不正确的后继移进栈决不会把不正确的后继移进栈规范的规范的LR分析器甚至在报告错误之前决不做任分析器甚至在报告错误之前决不做任何无效归约何无效归约3.6 二义文法的应用二义文法的应用 2、紧急方式错误恢复、紧急方式错误恢复s.栈栈. . . . . . . . a . .A发现错误发现错误s :C A A b . . .s1 :C A . . .AAb . . .b3.6 二义文法的应用二义文法的应用 2、紧急方式错误恢复、紧急方式错误恢复(1)退栈，直至出现状态退栈，直至出现状态s, , 它有预先确定的它有预先确定的A的转移的转移s.栈栈. . . . . . .

126、. a . .A发现错误发现错误s :C A A b . . .s1 :C A . . .AAb . . .b3.6 二义文法的应用二义文法的应用 2、紧急方式错误恢复、紧急方式错误恢复(1)退栈，直至出现状态退栈，直至出现状态s, , 它有预先确定的它有预先确定的A的转移的转移(2)抛弃若干输入符号，直至找到抛弃若干输入符号，直至找到a, , 它是它是A的合法后继的合法后继s.栈栈. . . . . . . . a . .As :C A A b . . .s1 :C A . . .AAb . . .b3.6 二义文法的应用二义文法的应用 2、紧急方式错误恢复、紧急方式错误恢复(1)退栈，直至

127、出现状态退栈，直至出现状态s, , 它有预先确定的它有预先确定的A的转移的转移(2)抛弃若干输入符号，直至找到抛弃若干输入符号，直至找到a, , 它是它是A的合法后继的合法后继(3)再把再把A和状态和状态gotos,A压进栈，恢复正常分析压进栈，恢复正常分析ss1.栈栈. . . . . . . . a . .As :C A A b . . .s1 :C A . . .AAb . . .b3.7分析器的生成器分析器的生成器3.7.1分析器的生成器分析器的生成器YaccYacc编译器编译器Yacc源程序源程序translate.yy.tab.cC编译器编译器y.tab.ca.outa.out输入

128、输入输出输出3.7分析器的生成器分析器的生成器3.7.2用用Yacc处理二义文法处理二义文法例例台式计算器台式计算器输入一个表达式并回车，显示计算结果输入一个表达式并回车，显示计算结果也可以输入一个空白行也可以输入一个空白行3.7分析器的生成器分析器的生成器%#include#include#defineYYSTYPEdouble/ 将将栈栈定定义义为为double类类型型 /%tokenNUMBER%left+ %left /%rightUMINUS%3.7分析器的生成器分析器的生成器lines:linesexprnprintf(“%gn”,$2)|linesn|/ /;expr:expr

130、看成是-(5+10),还是还是(-5)+10?取后者取后者3.7分析器的生成器分析器的生成器yylex()intc;while(c=getchar()=);if(c=.)|(isdigit(c)ungetc(c,stdin);scanf(“%lf”,&yylval);returnNUMBER;returnc;3.7分析器的生成器分析器的生成器3.7.3Yacc的错误恢复的错误恢复编译器设计者编译器设计者的工作的工作决定哪些决定哪些“主要的主要的”非终结符将有错误恢复与它非终结符将有错误恢复与它们相关联们相关联加入加入A error 的的错误产生式错误产生式，其中，其中A是主要非是主要非终结符，

131、终结符，是文法符号串是文法符号串为这样的产生式配上语义动作为这样的产生式配上语义动作Yacc把错误产生式当作普通产生式处理把错误产生式当作普通产生式处理3.7分析器的生成器分析器的生成器遇到语法错误时遇到语法错误时s.栈栈. . . . . . . . . . .A发现错误发现错误s :C 1A 2A error . . .s1:C 1A 2. . .As2:A error . . .error 3.7分析器的生成器分析器的生成器遇到语法错误时遇到语法错误时从栈中弹出状态，直到发现栈顶状态的项目集包从栈中弹出状态，直到发现栈顶状态的项目集包含形为含形为A error 的项目为止的项目为止s.

132、栈栈. . . . . . . . . . .A发现错误发现错误s :C 1A 2A error . . .s1:C 1A 2. . .As2:A error . . .error 3.7分析器的生成器分析器的生成器遇到语法错误时遇到语法错误时从栈中弹出状态，直到发现栈顶状态的项目集包从栈中弹出状态，直到发现栈顶状态的项目集包含形为含形为A error 的项目为止的项目为止把虚构的终结符把虚构的终结符error“移进移进”栈栈ss2.栈栈. . . . . . . . . . .A发现错误发现错误s :C 1A 2A error . . .s1:C 1A 2. . .As2:A error .

133、 . .error 3.7分析器的生成器分析器的生成器遇到语法错误时遇到语法错误时从栈中弹出状态，直到发现栈顶状态的项目集包从栈中弹出状态，直到发现栈顶状态的项目集包含形为含形为A error 的项目为止的项目为止把虚构的终结符把虚构的终结符error“移进移进”栈栈忽略若干输入符号，直至找到忽略若干输入符号，直至找到，把把移进栈移进栈栈栈. . . . . . . . . . .As :C 1A 2A error . . .s1:C 1A 2. . .As2:A error . . .error ss2.3.7分析器的生成器分析器的生成器遇到语法错误时遇到语法错误时从栈中弹出状态，直到发

134、现栈顶状态的项目集包从栈中弹出状态，直到发现栈顶状态的项目集包含形为含形为A error 的项目为止的项目为止把虚构的终结符把虚构的终结符error“移进移进”栈栈忽略若干输入符号，直至找到忽略若干输入符号，直至找到，把把移进栈移进栈把把error 归约为归约为A，恢复正常分析恢复正常分析ss1.栈栈. . . . . . . . . . .As :C 1A 2A error . . .s1:C 1A 2. . .As2:A error . . .error 3.7分析器的生成器分析器的生成器lines :linesexprnprintf(“%gn”,$2)|linesn|/ /|erro

135、rn yyerror(“重重新新输输入入上上一一行行”);yyerrok;本本章章要要点点文法和语言的基本知识文法和语言的基本知识自自上上而而下下的的分分析析方方法法：预预测测分分析析，非非递递归归的的预测分析，预测分析，LL(1)文法文法自自下下而而上上的的分分析析方方法法：SLR(1)方方法法，规规范范LR(1)方法和方法和LALR(1)方法方法LR方法如何用于二义文法方法如何用于二义文法语法分析的错误恢复方法语法分析的错误恢复方法例例题题1下面的二义文法描述命题演算公式的语法，下面的二义文法描述命题演算公式的语法，为它写一个等价的非二义文法为它写一个等价的非二义文法SSandS|SorS

136、|notS|p|q|(S)非二义文法的产生式如下：非二义文法的产生式如下：EEorT|TTTandF|FFnotF|(E)|p|q例例题题1下面的二义文法描述命题演算公式的语法，下面的二义文法描述命题演算公式的语法，为它写一个等价的非二义文法为它写一个等价的非二义文法SSandS|SorS|notS|p|q|(S)非二义文法的产生式如下：非二义文法的产生式如下：EEorT|TTTandF|FFnotE|(E)|p|qnotpandq有两种不同的最左推导有两种不同的最左推导例例题题2设设计计一一个个文文法法: :字字母母表表a,b上上a和和b的的个个数数相相等等的所有串的所有串的集合的集合二义文

138、gindeclist ;statement enddeclist d;declist|dstatement s;statement|s该文法产生的句子的形式是该文法产生的句子的形式是begind ;d;d;s;s ;s end修改后的文法如下：修改后的文法如下：program begindeclist statement enddeclist d;declist|d;statement s;statement|s例例题题5一个一个C语言的文件如下，第四行的语言的文件如下，第四行的if误写成误写成fi：longgcd(p,q)longp,q;fi(p%q=0)returnq;elsereturngcd(q,p%q);基于基于LALR（1）方法的一个编译器的报错情况如下：方法的一个编译器的报错情况如下：parseerrorbeforereturn(line5).是否违反了是否违反了LR分析的活前缀性质分析的活前缀性质习习题题第一次：第一次：3.2,3.4(b)(c),3.6(a)(b)第二次：第二次：3.8第三次：第三次：3.15第四次：第四次：3.18(a)第五次：第五次：3.21,3.23第六次：第六次：3.27,3.31

展开阅读全文

编译原理语法分析3

最新文档