编译原理(第5章)

1、SAA c a b d c a b d c a b d 规约规约过程：过程： cabd cAd S从从输入串输入串开始，逐步进行开始，逐步进行“归约归约”，直，直至到至到文法的开始符号文法的开始符号。bb1 # bbcde# 移进2 #b bcde# 归约(Ab)3 #A bcde# 移进4 #Ab cde# 归约(AAb)5 #A cde# 移进6 #Ac de# 移进7 #Acd e# 归约(Bd)8 #AcB e# 移进9 #AcBe # 归约(SAcBe)10 #S # 接受#bbdAcc de#BeS bbbbcde Abcde Acde AcBe S 例2: 对于文法 （1） E

2、T （2） E E+T （3） T F （4） T T*F （5） F i （6） F (E) 给出句子 i1*i2+i3的分析步骤步骤符号栈剩余输入串动作1#i1*i2+i3# 移进 2#i1*i2+i3# 归约 Fi 3#F*i2+i3# 归约 TF4#T*i2+i3# 移进 5#T*i2+i3# 移进6#T*i2+i3# 归约 Fi7#T*F+i3# 归约 TT*F8#T+i3# 归约 ET9#E+i3# 移进10#E+i3# 移进11#E+i3# 归约 Fi12#E+F# 归约 TF13#E+T# 归约 EE+T14#E# 接受（1） E T （2） E E+T（3） T F （4）

3、T T*F（5） F i （6） F (E)(规约？规约？)T F？移进归约分析中的问题移进归约分析中的问题w 1) 1) 移进移进- -归约冲突归约冲突 在分析到某一步时，既可以移进，又可以归约上例第4)步可以移进*，也可以按产生式ET进行归约。w 2) 2) 归约归约- -归约冲突归约冲突存在两个可选的句柄，可对栈顶符号进行归约例如上述第7)步，可以用TF进行归约，又可以按 TT*F 进行归约。w 各种分析方法中处理冲突的技术不同各种分析方法中处理冲突的技术不同C. 主要分析方法主要分析方法: (1)算符优先分析法算符优先分析法 T+T*F+i，T+T*F不是素短语，不是素短语，因为其中包

4、含了素短语因为其中包含了素短语T*F。 T不是素短语，因为其中没有终不是素短语，因为其中没有终结符号。结符号。o 句型句型T+T*F+i的的短语有哪些？短语有哪些？直接短语有哪些？素短语是什么？直接短语有哪些？素短语是什么？EE+TEET+FiT*FT例 已知语法G： 试找出符号串(a)和(A(SaA)(b)的短语 直接短语和句柄(如果有的话)。S(AS) | (b)A(SaA) | (a) 符号串(a)不是语法的句型，因此 它没有短语直接短语和句柄。 分析 S(AS)(a)S)(a)S(AS)(A(AS)(A(A(b) (A(SaA)(b)符号串(A(SaA)(b)是语法的句型，画出该句型的

5、语法树如下图：S(AS) | (b)A(SaA) | (a)从句型的语法树求 短语: (A(SaA)(b) (SaA)(b) (SaA) (b)直接短语：（SaA)、(b)句柄：(SaA) S A ( S )A ( S )(S a A ) ) b ( S(AS) | (b)A(SaA) | (a)对于句型(A(SaA)(b)算符优先分析法算符优先分析法算符优先分析法算符优先分析法+算符优先分析法算符优先分析法算符优先分析法算符优先分析法b(a)+ 算符优先分析法算符优先分析法算符优先分析法算符优先分析法+算符优先分析法算符优先分析法+算符优先分析法算符优先分析法算符优先分析法算符优先分析法算符

6、优先分析法算符优先分析法算符优先分析法算符优先分析法算符优先分析法算符优先分析法算符优先分析法算符优先分析法算符优先分析法算符优先分析法Sa|b|(A)ASdA|Su 和和时候移进时候移进时归约时归约u注意注意:归约串是根据优先关归约串是根据优先关系得来的系得来的(上页上页PPT中的结论中的结论)而不是产生式而不是产生式!u归约到一个非终结符即可归约到一个非终结符即可. 不必和产生式对应起来不必和产生式对应起来(b) 一般分析一般分析技术得到得到技术得到得到的语法树的语法树(a) 算符优先算符优先分析技术得到分析技术得到得到的语法树得到的语法树(SA)dSSAabSa|b|(A)ASdA|S(

7、NN)dNNab(b) 一般分析一般分析技术得到得到技术得到得到的语法树的语法树(a) 算符优先算符优先分析技术得到分析技术得到得到的语法树得到的语法树FZ+T*EFiF)(+FFiiiEE+T*ETTF)(+EFFiiFiFTTZiC. 主要分析方法主要分析方法: (2)LR分析法分析法步骤符号栈剩余输入串动作1#i1*i2+i3# 移进 2#i1*i2+i3# 归约 Fi 3#F*i2+i3# 归约 TF4#T*i2+i3# 移进 5#T*i2+i3# 移进6#T*i2+i3# 归约 Fi7#T*F+i3# 归约 TT*F8#T+i3# 归约 ET9#E+i3# 移进10#E+i3# 移进

8、11#E+i3# 归约 Fi12#E+F# 归约 TF13#E+T# 归约 EE+T14#E# 接受（1） E T （2） E E+T（3） T F （4） T T*F（5） F i （6） F (E)(规约？规约？)T F？+EE+TFi3TTF*i2Fi1c dBeAbAbSc dBeAAbScdBeAScBeAS 0 # i1*i2+i3# 预备预备 #i1 *i2+i3# 移进移进2 #F *i2+i3# 归约归约(Fi)3 #T *i2+i3# 归约归约(TF)4 # T* i2+i3# 移进移进5 # T*i2 +i3# 移进移进6 # T*F +i3#归约归约(Fi)7 #T +

9、i3#归约归约(TT*F)8 #E +i3#归约归约(ET) # E+ i3#移进移进 # E+ i3 # 移进移进 # E+ F # 归约归约(Fi) # E+ T # 归约归约(TF) #E # 归约归约(EE+T)1 #E # 接受接受EE+TFi3TTF*i2Fi1EE+TFi3TTF*i2FEE+TFi3TTF*i2EE+TFi3TTF*EE+TFi3TEE+TFi3EE+TFEE+TEC. 主要分析方法主要分析方法: (2)LR分析法分析法C. 主要分析方法主要分析方法: (2)LR分析法分析法a1a2an#总控程序输入串(源程序)分析栈输出分析结果Ija1a2ai an#输入串输

10、入串a1a2ai an# 输入串其其LR分析表如下页，分析输入串分析表如下页，分析输入串i*i+i i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 A C C EP T 2 R2 S7 R2 R2 3 R4 R4 R4 R4 4 S5 S4 8 2 3 5 R6 R6 R6 R6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 R1 S7 R1 R1 10 R3 R3 R3 R3 11 R5 R5 R5 R5 i + * ( ) # E T F 0 S5 S4 1 2 3 1 S6 A C C EP T 2 R2 S7 R2 R2 3 R4 R4

11、R4 R4 4 S5 S4 8 2 3 5 R6 R6 R6 R6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 R1 S7 R1 R1 10 R3 R3 R3 R3 11 R5 R5 R5 R5 0 0 # ( )# S2 1 02 #( )# r3 32 023 #(S )# S43 0234 #(S) # r3 54 02345 #(S)S # r2 15 01 #S # acc78 0 # i1*i2+i3# 预备预备 #i1 *i2+i3# 移进移进2 #F *i2+i3# 归约归约(Fi)3 #T *i2+i3# 归约归约(TF)4 # T* i2+i3# 移

12、进移进5 # T*i2 +i3# 移进移进6 # T*F +i3#归约归约(Fi)7 #T +i3#归约归约(TT*F)8 #E +i3#归约归约(ET) # E+ i3#移进移进 # E+ i3 # 移进移进 # E+ F # 归约归约(Fi) # E+ T # 归约归约(TF) #E # 归约归约(EE+T)1 #E # 接受接受LR(0)项目与活前缀、句柄的关系：项目与活前缀、句柄的关系： #a A c B e # 移进句子句子abbcde分析到某一分析到某一步的时候状步的时候状态如右：态如右：分析到该步骤时生成的句型分析到该步骤时生成的句型该句型的一该句型的一个活前缀个活前缀当前要归约

13、的句柄是当前要归约的句柄是AcBe其中：其中：AcB已分析完毕进栈，已分析完毕进栈，而而e还未分析（进栈），用项还未分析（进栈），用项目目C-AcB e表示表示添加一个新的开始符号添加一个新的开始符号S，使，使S-S (S为原来的开始符号）为原来的开始符号）目的在于使最终求得的目的在于使最终求得的action表只含有表只含有唯一一个接受状态唯一一个接受状态AbSAAaAAb SA Aa AAaA abAA SA AaAAbAbSAAaAAaAAbAaAabAAabSA AaAAbAb SA Aa AAaAAbAaA abAAabI1I0I2I3I40: SA AaAAb2:Ab 3:SA 1:

14、Aa AAaAAb4:AaA abAAabLR(0)项目集规范族项目集规范族I0: S.S S.aA S.bBI1: (I0,S) SS.I2: (I0,a) Sa.A A.cA A.d I3: (I0,b) Sb.B B.cB B.dI4: (I2,c) Ac.A A.cA A.dI5: (I3,c) Bc.B B.cB B.dI6: (I2,A) SaA.I7: (I3,B) SbB.I8: (I4,A) AcA.I9: (I5,B) BcB.I10 : (I2,d) Ad.I11: (I3,d) Bd.(I4,c)(I5,c)(I4,d)(I5,d)Ac.AA.cAA.d I4Sa.AA

15、.cAA.d I2Sb.BB.cBB.d I3Bc.BB.cBB.d I5S.SS.aAS.bB I0startSS. I1AcA. I8SaA. I6Ad. I10AddAcabSSbB. I7BcB. I9Bd. I11BddBccc I4I2I3I5I0startI1I8I6I10AddAcabSI7I9I11BddBcccSLR分析表的构造分析表的构造SLR分析表的构造分析表的构造action goto 状态状态 i r # S D 0 1 2 3 4 6 S2 acc S4 S6 r1 r3 r3r 2 r2 1 3 follow(A)=d,cACTION GOTO a c e b

16、d # S A 012345 r5 S967 r7 S11 891011RRRRRRRRRR ACTION GOTO a c e b d # S A 01234 67 891011 S2S31Acc S54 S76S8r5S9S10S11r5r1 r3r2r4LR(1)比比SLR（1）能力强）能力强I1:SS ,#I5:Li ,=/#I7:L*R ,=/#I8:RL ,=/#I9:SL=R ,#I3:SR ,#I12:Li ,#I10:RL ,#I13:L*R ,#I0:S S,# S L=R,# S R,# L *R,=/#L i,=/# R L,# I4: L *R,=/# R L,=/#

17、L i,=/# L *R,=/#I6:S L= R,# R L,# L *R,# L i,# I11:L * R,# R L,# L *R,# L i,# I2:S L =R,# R L,# sR=LRii*iiRLLRL*LR(1)项目集及转换函数项目集及转换函数I6:S a B,# B aB,#B b,# LR(1)项目集和转换函数项目集和转换函数I0:S S,# S BB,#B aB,a/bB b,a/b I1:S S ,#I2:S B B,# B aB,#B b,# I5:S BB ,#I3:B a B,a/b B aB,a/b B b,a/b I4:B b ,a/bI7:B b ,#

18、I9:B aB ,#I8:B aB ,a/bSBBabbbBBaab aACTIONGOTOab#SB状态LR(1)分析表分析表I3:B a B,a/b B aB,a/b B b,a/b I6:S a B,# B aB,#B b,# I4:B b ,a/bI7:B b ,#I8:B aB ,a/bI9:B aB ,#文法文法 G的的LR(1) 的两个项目集的两个项目集 Ii和和Ij在去掉各项中搜索符之后在去掉各项中搜索符之后是相同的，则称这是相同的，则称这 两个项目集两个项目集是是同心同心的的在合并同心时，以某种方式合并在合并同心时，以某种方式合并 LR(1) 分析表中的分析表中的ACTION

19、 表和表和 GOTO 表的表的对应项，可得到一张分析表对应项，可得到一张分析表I3:B a B,a/b B aB,a/b B b,a/b I6:S a B,# B aB,#B b,# I4:B b ,a/bI7:B b ,#I8:B aB ,a/bI9:B aB ,#ACTIONGOTOab#SB状态LR(1)分析表分析表ab#SBACTIONGOTO状态LALR(1)分析表I1:SS ,#I5:Li ,=/#I7:L*R ,=/#I8:RL ,=/#I9:SL=R ,#I3:SR ,#I12:Li ,#I10:RL ,#I13:L*R ,#I0:S S,# S L=R,# S R,# L *

20、R,=/#L i,=/# R L,# I4: L *R,=/# R L,=/#L i,=/# L *R,=/#I6:S L= R,# R L,# L *R,# L i,# I11:L * R,# R L,# L *R,# L i,# I2:S L =R,# R L,# sR=LRii*iiRLLRL*LR(1)项目集及转换函数项目集及转换函数ACTIONGOTO=*i#SLR状态LALR(1)分析表 LEXYACC代码产生支撑代码产生支撑函数函数教材教材3.4P.86-91返回一个整数值（可能出现返回一个整数值（可能出现的单词种别），传递给谁？的单词种别），传递给谁？如果希望某个元符号（如如果

21、希望某个元符号（如+、？）表示其自身，可在它、？）表示其自身，可在它前面加反斜线前面加反斜线字符字符 含义含义 A-Z, 0-9, a-z 构成了部分模式的字符和数字。构成了部分模式的字符和数字。. 匹配任意字符，除了匹配任意字符，除了 n。- 用来指定范围。例如：用来指定范围。例如：A-Z 指从指从 A 到到 Z 之间的所有之间的所有字符。字符。 一个字符集合。匹配括号内的一个字符集合。匹配括号内的 任意任意 字符。如果第一字符。如果第一个字符是个字符是 那么它表示否定模式。例如：那么它表示否定模式。例如：abC 匹配匹配 a, b 和和 C中的任何一个。中的任何一个。 * 匹配匹配 0个个

22、或者多个上述的模式。或者多个上述的模式。 + 匹配匹配 1个个或者多个上述模式。或者多个上述模式。 ? 匹配匹配 0个或个或1个个上述模式。上述模式。 $ 作为模式的最后一个字符匹配一行的结尾。作为模式的最后一个字符匹配一行的结尾。字符字符 含义含义 指出一个模式可能出现的次数。指出一个模式可能出现的次数。 例如：例如：A1,3 表示表示 A 可能出现可能出现1次或次或3次。次。 用来转义元字符。同样用来覆盖字符在此表中用来转义元字符。同样用来覆盖字符在此表中定义的特殊意义，只取字符的本意。定义的特殊意义，只取字符的本意。 否定。否定。| 表达式间的逻辑或。表达式间的逻辑或。 字符的字面含义。

23、元字符具有。字符的字面含义。元字符具有。/ 向前匹配。如果在匹配的模版中的向前匹配。如果在匹配的模版中的“/”后跟有后后跟有后续表达式，只匹配模版中续表达式，只匹配模版中“/”前面的部分。如：前面的部分。如：如果输入如果输入 A01，那么在模版，那么在模版 A0/1 中的中的 A0 是匹是匹配的。配的。( ) 将一系列常规表达式分组。将一系列常规表达式分组。常规表达式常规表达式 含义含义 jokers 匹配匹配 jokes 或或 joker。A1,2shis+ 匹配匹配 AAshis, Ashis, Ashiss, Ashisss。(Ab-e)+ 匹配在匹配在 A 出现位置后跟随的从出现位置后

24、跟随的从 b 到到 e 的的所有字符中的所有字符中的 1 个或个或 多个。多个。标记标记 相关表达式相关表达式 含义含义 数字数字(digit)(0-9)+1个或多个数字个或多个数字字符字符(letter)A-Za-z任意字符任意字符空格空格(blank) 一个空格一个空格字字(word)(letter)+1个或多个个或多个 chars 标识符标识符(id)(字符字符)+(数字数字)*(字字符符)*(数字数字)*yyinFILE* 类型。类型。 它指向它指向 lexer 正在解析的当前文件。正在解析的当前文件。yyoutFILE* 类型。类型。 它指向记录它指向记录 lexer 输出的位置。输

25、出的位置。 缺缺省情况下，省情况下，yyin 和和 yyout 都指向标准输入和输出。都指向标准输入和输出。yytext匹配模式的文本存储在这一变量中（匹配模式的文本存储在这一变量中（char*）（）（1个指向词素开头的指针）个指向词素开头的指针）yyleng给出匹配模式的长度（存放刚找到的词素的长度）给出匹配模式的长度（存放刚找到的词素的长度）yylineno 提供当前的行数信息。（提供当前的行数信息。（lexer不一定支持。）不一定支持。）yylex()这一函数开始分析。这一函数开始分析。 它由它由 Lex 自动生成。自动生成。yywrap()这一函数在文件（或输入）的末尾调用。如果函这一

26、函数在文件（或输入）的末尾调用。如果函数的返回值是数的返回值是1，就停止解析。，就停止解析。 因此它可以用因此它可以用来解析多个文件。代码可以写在第三段，这来解析多个文件。代码可以写在第三段，这就能够解析多个文件。就能够解析多个文件。 方法是使用方法是使用 yyin 文件文件指针（见上表）指向不同的文件，直到所有指针（见上表）指向不同的文件，直到所有的文件都被解析。最后，的文件都被解析。最后，yywrap() 可以返回可以返回 1 来表示解析的结束。来表示解析的结束。yyless(int n)这一函数可以用来送回除了前这一函数可以用来送回除了前n 个字符外的所有个字符外的所有读出标记。读出标记

27、。yymore()这一函数告诉这一函数告诉 Lexer 将下一个标记附加到当前将下一个标记附加到当前标记后。标记后。Yacc编译器编译器Yacc源程序源程序calc.ycalc.tab.cC编译器编译器calc.tab.ca.outa.out输入输入输出输出YACCYet Another Compiler CompilerYACC内部使用符号内部使用符号名称名称含义含义y.tab.cyacc 输出文件名输出文件名y.tab.hyacc 生成的头文件生成的头文件yyparseyacc分析主函数分析主函数yylval属性栈顶（对应符号的）值属性栈顶（对应符号的）值yyerror错误信息的输出函数错

28、误信息的输出函数erroryacc中中“错误错误”伪记号伪记号yyerrok出错后重置分析栈于正常工作状态出错后重置分析栈于正常工作状态YYSTYPE定义属性栈值类型定义属性栈值类型yydebug值为值为1时，产生分析器运行信息时，产生分析器运行信息YACC中的定义机制中的定义机制 定义定义含义含义%token定义记号（终结符）定义记号（终结符）%start定义开始符号定义开始符号%union定义定义YYSTYPE,允许符号的值允许符号的值有不同的类型有不同的类型%type定义符号的值类型定义符号的值类型%left算符优先级、左、右结合性算符优先级、左、右结合性%right位置越前，优先级越低

29、位置越前，优先级越低%nonassoc算符不可结合，如算符不可结合，如abcYACC描述文件描述文件w 由三部分组成由三部分组成 定义段（定义段（definitions） 规则段（规则段（rules） 辅助程序段辅助程序段w 定义段定义段q%/* 合法的合法的C声明、包含文件、宏定义等声明、包含文件、宏定义等 */ #include #include %q 单词符号的说明，如单词符号的说明，如 %token digit 算符优先级、结合性的说明（注意书写的先后算符优先级、结合性的说明（注意书写的先后次序）次序） %left + - 低优先级的算符说明位置在前低优先级的算符说明位置在前 %lef

30、t * / %right 优先级越高，位置越后优先级越高，位置越后 开始符号（缺省时为第一个产生式的左部符号）开始符号（缺省时为第一个产生式的左部符号） %start symbol w 规则段规则段A : 1 语义动作语义动作1 | 2 语义动作语义动作2 | | n 语义动作语义动作n | 没有没有,则使用缺省的语义动作则使用缺省的语义动作 ; 产生式结束用产生式结束用分号分号标记标记 语义动作是语义动作是C的语句序列（在一对的语句序列（在一对中间），中间），可以引用声明段中定义的可以引用声明段中定义的C变量、宏等，还变量、宏等，还可以使用可以使用yacc的伪变量。的伪变量。 语义动作一般是

31、语义动作一般是在产生式右部分在产生式右部分析完，归约动作析完，归约动作进行前执行。进行前执行。w 规则段（续）规则段（续）yacc中的伪变量（类型缺省为整型）中的伪变量（类型缺省为整型） $ - 产生式左部非终结符的产生式左部非终结符的“值值” $i - 产生式右部第产生式右部第i个文法符号的个文法符号的“值值” yacc中有一个与分析栈中有一个与分析栈“平行平行”的属性值栈的属性值栈如：如： E : E + T $ = $1 + $3; | T $ = $1 /* 这是缺省的语义动作；可以省略这是缺省的语义动作；可以省略*/ ; + T $3E $1 分析栈分析栈属性栈属性栈.w 辅助程序段

32、辅助程序段用户自定义的用户自定义的C程序，如程序，如#include “lex.yy.c” int main(void) yyparse(); return 0; void yyerror(char* s) fprintf(stderr, %sn, s); 例例 简单的算术计算器简单的算术计算器w 输入一个表达式并回车，显示计算结果。输入一个表达式并回车，显示计算结果。w 也可以输入一个空白行。也可以输入一个空白行。输入输入 -100 + 20 * 6 显示显示 20 例例: 简单的算术表达式计算器简单的算术表达式计算器/* 定义段：定义段：*/% #include #include void yyerror(char*);%token DIGIT %left + -%left * /%right UMINUS% /* 规则段：规则段：*/Line : Expr n printf( the value is %dn,$1);