1、2023-5-191计算机学院计算机学院编 译 原 理 Compiler PrinciplesCompiler Principles 2023-5-192n句型分析：句型分析：就是识别一个符号串是否为某文法的句型，就是识别一个符号串是否为某文法的句型，是某个是某个的构造过程。的构造过程。n分析程序分析程序(识别程序识别程序)：在语言的编译实现中，完成句型在语言的编译实现中，完成句型分析的程序。分析的程序。n从左到右的分析算法：从左到右的分析算法：总是从总是从左左到到右右地识别输入符号地识别输入符号串，首先识别符号串中的串，首先识别符号串中的最左最左符号，进而符号，进而依次识别右边依次识别右边的
2、的一个符号，直到分析结束。一个符号，直到分析结束。2023-5-193q自上而下分析法自上而下分析法 从从文法的开始符号文法的开始符号出发出发，反复使用文法的，反复使用文法的产生式产生式，为，为待识别句子建立一个待识别句子建立一个最左推导最左推导，以寻找与，以寻找与输入符号串输入符号串匹匹配的配的。q自下而上分析法自下而上分析法 从从输入符号串输入符号串开始开始，逐步进行逐步进行归约归约，从，从叶子节点叶子节点，由，由底上向上底上向上逐步建立一棵完整的语法树，直至逐步建立一棵完整的语法树，直至到文法到文法的的开始符号（树根）。开始符号（树根）。2023-5-1942023-5-195 直接左递
3、归直接左递归 若若 P P|、V*且且不以不以P开头开头 串的特点串的特点 .间接左递归间接左递归 若若 P=P 例如：例如：SAa ASb|b *2023-5-196 分析工作要部分地或全部地退回去重做叫回溯。分析工作要部分地或全部地退回去重做叫回溯。严重的效率低，只有在理论上的意义而无实际意义严重的效率低，只有在理论上的意义而无实际意义 文法中，对于某个非终结符号的规则其右部有多个选择，文法中，对于某个非终结符号的规则其右部有多个选择，并根据所面临的输入符号不能准确并根据所面临的输入符号不能准确 的确定所要选择时，就可能的确定所要选择时，就可能出现回溯。出现回溯。2023-5-197202
4、3-5-198方法：方法：n 法一：PP|产生式的符号串为产生式的符号串为.引入一元语言符引入一元语言符号号，x表示表示x可出现任意次。可出现任意次。则：则：PP|改写为改写为P例例1：SAc AAa|b 改为：改为：SAc Aba例例2：EE+T|T TT*F|F 消除左递归：消除左递归：ET+T TF*F2023-5-199n 法二：对左递归对左递归 AA|的非终结符的非终结符A，引入一个新的非终，引入一个新的非终结符结符A，使得：，使得：AA|等价写成：等价写成：一般地：若一般地：若jkAAAA|2121其中其中ii均不以均不以A A打头，则：打头，则：|212121AAAAAAAAAk
5、jj）（或*AAA AA|2023-5-1910n 法二步骤总结Step1：提因子：提因子2023-5-1911例例E E+T|TT T*F|FF (E)|id消除左递归后文法消除左递归后文法 E TE E +TE|T FT T *F T|F (E)|id注意：注意：此方法只能消除出现此方法只能消除出现在产生式的全部在产生式的全部直接左递归直接左递归，不能消除经两步或多步推导不能消除经两步或多步推导所出现的一切所出现的一切间接左递归。间接左递归。Step1：将左递归规则改为右递归：将左递归规则改为右递归2023-5-1912n1 间接左递归产生原因n 产生式右边产生式右边首符号为非终结首符号为
6、非终结符符；n(存在回路存在回路)前面非终结符引用前面非终结符引用后面非终结符，后面非终结后面非终结符，后面非终结符引用前面非终结符。符引用前面非终结符。例例1：SAc|c (1)ABb|b (2)BSa|a (3)对例对例1：l BSa|a 带入带入(2)，得，得 ASab|ab|b l 带入带入S产生式，得产生式，得S Sabc|abc|bc|cl S(abc|bc|c)S SabcS|n 2 消除方法n 找出找出所有所有引用引用前面非终结符前面非终结符的的产生式进行代换，即先变换成产生式进行代换，即先变换成直直接左递归接左递归。2023-5-1913一、消除回溯的途径改写文法例例1 Ux
7、V|xW U,V,WVn,xVt 改写为：改写为：Ux(V|W)更清楚表示更清楚表示 UxZ ZV|W2023-5-1914对于有公共左因子的文法对于有公共左因子的文法A a 1|a 2|a k|，其，其中中 不以不以a a开头，开头，aaV V。提左因子：提左因子：判断判断ade S aA adA ade例：例：Ad|de|f改为：改为：AdA|f A|e 若若 1 2 k还有某些候选式有相同首符号，则依次提取，直还有某些候选式有相同首符号，则依次提取，直到每个候选式的首符号不同为止。到每个候选式的首符号不同为止。提取公因子会引入大量非终结符和提取公因子会引入大量非终结符和产生式。产生式。2
8、023-5-1915n 1 定义 特别的：特别的：则则n 对文法对文法G的所有非终结符的的所有非终结符的每个候选式每个候选式X其其首符号集首符号集为为FIRST(X)。n 对对A的任何两个不同的选择的任何两个不同的选择 i 和和 j，希望有，希望有FIRST(i)FIRST(j)=此时，当要求此时，当要求A匹配输入串时，匹配输入串时，A就可根据所面临第一个输入就可根据所面临第一个输入符号符号a，准确指派某个候选式推导，该候选式即为，准确指派某个候选式推导，该候选式即为aFIRST(X)的的X候选式。候选式。二、FIRST集*2023-5-1916n 2 FIRST（X）构造方法n1).若若X
9、V，则，则FIRST(X)=X；n2).若若X VN，且有，且有Xa，则，则aFIRST(X)；a可为可为；n3).若有若有X Y1Y2YK，Yi(1i K)，则，则 (FIRST(Y1)FIRST(X);若若 FIRST(Y1)，则，则(FIRST(Y2)FIRST(X)；同样，若同样，若 FIRST(Yj)(1j A 且且a FRIST(),V*,V*l 若若S=u A ，且且 =，则，则#FOLLOW(A)三、FOLLOW集对文法对文法G的所有的所有的的定义它的定义它的FOLLOW(A)。对含有对含有的的A的所有候选式的所有候选式 i，希望有，希望有*2023-5-1918l 1).文法
10、的开始符号文法的开始符号S，置，置#FOLLOW(S)；当当AVN为句型的尾符号时，则为句型的尾符号时，则#FOLLOW（A）l 2).对于对于BA，则，则 (FIRST()FOLLOW(A)；l 3).对于对于BA，或，或BA而而 FIRST()，则把则把FOLLOW（B）加至）加至FOLLOW（A）中。）中。l 反复使用反复使用2、3步，直到每个非终结符的步，直到每个非终结符的FOLLOW集不再集不再增大为止。增大为止。n 2 FOLLOW(A)构造方法2023-5-1919 四、LL(1)文法定理：定理：2023-5-1920 1 LL(1)含义：L：从左至右顺序扫描输入串；从左至右顺序
11、扫描输入串；L：按最左推导方式；按最左推导方式；1：每一次推导均向前查看一个输入符号准确指派产生式。每一次推导均向前查看一个输入符号准确指派产生式。2 LL(1)文法性质:没有公共左因子；没有公共左因子；无二义性；无二义性；不含左递归。不含左递归。对对LL(1)文法，可构造一个无回溯自顶向下语法分析程序，方法为：文法，可构造一个无回溯自顶向下语法分析程序，方法为：q预测分析法（LL(1)分析法）2023-5-1921LL(1)分析方法是一种比递归子程序法更有效的自顶向下分析分析方法是一种比递归子程序法更有效的自顶向下分析方法。方法。LL(1)分析使用一个下推栈而不是递归调用来完成分析。分析使用
12、一个下推栈而不是递归调用来完成分析。名称中第一个名称中第一个L表示自左向右顺序扫描输入符号串，第二个表示自左向右顺序扫描输入符号串，第二个L表示分析过程产生一个句子的最左推导。表示分析过程产生一个句子的最左推导。括号中的括号中的1表示每进行一步推导，只需要向前查看一个输入符表示每进行一步推导，只需要向前查看一个输入符号，便能确定当前所应选用的规则。号，便能确定当前所应选用的规则。2023-5-1922LL(1)分析器由一个总控程序（表驱动程序）、一张分析表分析器由一个总控程序（表驱动程序）、一张分析表（预测分析表、（预测分析表、LL(1)分析表）和一个分析栈组成。分析表）和一个分析栈组成。输入
13、符号串：分析栈a1a2an#XZS#LL（1）总控程序分析表输出流栈中存放文法栈中存放文法的符号串，栈的符号串，栈底符号是底符号是#待分析串，从待分析串，从左到右扫描左到右扫描是一个两维数组是一个两维数组MA,a,A是非是非终结符，终结符，a是终是终结符或结符或#2023-5-1923输入符号串输入符号串:指要分析的输入符号串，它以右界符指要分析的输入符号串，它以右界符#作为结尾。作为结尾。分析栈：用来存放一系列文法符号。分析开始时，先将分析栈：用来存放一系列文法符号。分析开始时，先将#入栈，入栈，然后再将文法的开始符号入栈。然后再将文法的开始符号入栈。输出流：分析过程中使用的产生式序列。输出
14、流：分析过程中使用的产生式序列。总控程序：分析器对输入串的分析靠总控程序完成总控程序：分析器对输入串的分析靠总控程序完成.根据分析栈根据分析栈的栈顶符号的栈顶符号X和当前的输入符号和当前的输入符号a，总控程序按照分析表的指示，总控程序按照分析表的指示来决定分析器的动作。工作过程如下：来决定分析器的动作。工作过程如下：2023-5-1924第一步第一步 初始化初始化:分析开始时，首先将符号分析开始时，首先将符号#及文法的开始符号及文法的开始符号S S依次置于分析栈的底部，并把各指示器调整至起始位置，如图依次置于分析栈的底部，并把各指示器调整至起始位置，如图1 1所示。然后，反复执行第二步的操作。
15、所示。然后，反复执行第二步的操作。输入符号串：输入符号串：a1a2an#分析栈：分析栈：S#图图1 1 分析开始时状况分析开始时状况 第二步第二步 假设分析的某一步，分析栈及余留的符号串如图假设分析的某一步，分析栈及余留的符号串如图2 2：a iai+1 an#X1X2Xm-1Xm 图图2 2 分析进行中的状况分析进行中的状况 2023-5-1925(1)(1)若若X X m mVV n n，则查分析表的，则查分析表的X X m m行行a a i i列，假设列，假设M XM X m m，a a i i 为产生式为产生式X X m m Y Y1 1Y Y2 2Y Y k k，则将，则将X X m
16、 m出栈，并将出栈，并将Y Y1 1Y Y2 2Y Y k k反反序入栈，如图序入栈，如图3 3；若；若M XM X m m，a a i i 为为ERRORERROR，则出错。，则出错。a iai+1 an#X1X2Xm-1Y k Y k-1Y1 图图3 3 反序入栈反序入栈 (2)(2)若若X Xm m=a=ai i#，表示栈顶与扫描的符号匹配，则栈顶符号，表示栈顶与扫描的符号匹配，则栈顶符号X X m m出出栈，输入指示器指向下一个符号，否则栈，输入指示器指向下一个符号，否则(即即X Xm maa i i)出错。出错。(3)(3)若若X Xm m=a=a i i=#=#，表示输入串完全匹配
17、，分析成功。，表示输入串完全匹配，分析成功。2023-5-19261 分析表：可用一个二维数组表示，它的每一行与文法的一个非终可用一个二维数组表示，它的每一行与文法的一个非终结符相关联，每一列则与文法的一个终结符号或界符结符相关联，每一列则与文法的一个终结符号或界符“#”相关联。相关联。n元素：元素：MA，a文法产生式文法产生式|error（AVN，aVT#）n 基本思想基本思想 当文法中某一当文法中某一非终结符非终结符呈现在呈现在栈顶栈顶时时,根据当前的根据当前的输入符号输入符号，分析表应指示要用该分析表应指示要用该非终结符的哪一条候选非终结符的哪一条候选式式匹配输入串匹配输入串(即进行下一
18、步最左推导即进行下一步最左推导)根据这个思想，我们可以构造分析表算法根据这个思想，我们可以构造分析表算法!2023-5-1927 分析表元素分析表元素MA,a(AVN,aVT#)，按下述规则确定：，按下述规则确定：对于文法中的对于文法中的每个每个产生式产生式 A1|2|m1）若若aFirst(i)，则置，则置MA,a=“Ai”2）若）若 First(j)，且，且aFollow(A)，则，则 MA,a=“A”3）除上述两种情况外，其余的一切表元素均置为）除上述两种情况外，其余的一切表元素均置为error。2 预测分析表构造算法预测分析表各元素含义为：预测分析表各元素含义为：或指出或指出当前推导当
19、前推导所应使用的所应使用的产生式产生式，或指出或指出输入符号串输入符号串中存在着中存在着语法错误语法错误.2023-5-1928可以证明：一个文法可以证明：一个文法G的预测分析表不含多重的预测分析表不含多重元素，当且仅当该元素，当且仅当该文法是文法是LL(1)LL(1)的。的。2023-5-1929五、结 论对对LL(1)LL(1)文法，总能构造预测分析表，且表中不含多重元素。文法，总能构造预测分析表，且表中不含多重元素。对对非非LL(1)LL(1)文法，尽管可为其建立预测分析表，但表中必出现文法，尽管可为其建立预测分析表，但表中必出现多重元素多重元素。非非LL(1)LL(1)文法文法所造表中
20、所造表中,必有冲突元素。必有冲突元素。n 对某些对某些非非LL(1)文法文法，可通过，可通过，反复，反复等方等方法将其改造成法将其改造成LL(1)文法文法。并非所有的非并非所有的非LL(1)文法都能改造为文法都能改造为LL(1)文法。文法。六、非LL(1)文法的改造2023-5-1930语法分析程序查找规约串依据 a+b#输出带#2023-5-19312023-5-1932一、算符文法定义 算符文法算符文法 CFG G=（VN,VT,P,S）,U,V,W均为非终结均为非终结符，符，x,y均为终结符。均为终结符。如果如果 CFG(不含空产生式不含空产生式)G 中没有形中没有形如如 UVW 的产生
21、式，则称的产生式，则称G 为算符文法（为算符文法（OG）。）。n推论：推论：算符文法的任何句型都不含两个相邻的非终结符。算符文法的任何句型都不含两个相邻的非终结符。ab 表示表示a的优先级低于的优先级低于b a b 表示表示a的优先级等于的优先级等于b a b 表示表示a的优先级大于的优先级大于b 2023-5-1933二、算符优先关系定义 在在OGOG（算符优先文法）中（算符优先文法）中 n x x=y y G G中有形如中有形如UUxyxy或或UU xVy xVy的产生式。的产生式。n x xy y G G中有形如中有形如 U U Wy Wy的产生式的产生式,而而W xW x或或W xVW
22、 xV若若 S xS x或或 S Vx S Vx 则则#2023-5-1934三、算符优先关系计算及其表示n FIRSTVT(W)=y|W y W Vyn LASTVT (W)=x|W x W xVnxy：Uxy或或U xVynxy：每个非终结符：每个非终结符B的的FIRSTVT(B)，形如，形如UxB中，每个中，每个yFIRSTVT(B)，则有，则有xy成立。成立。2023-5-1935对文法的每一非终结符号构造对文法的每一非终结符号构造FIRSTVT集和集和LASTVT集，算集，算法分别如下法分别如下)构造构造FIRSTVT集，置集，置FIRSTVT(A)=若文法中有形如若文法中有形如A
23、b 或或 A Bb的规则，则的规则，则b FIRSTVT(A)若文法中有形如若文法中有形如AB的规则，则的规则，则FIRSTVT(B)FIRSTVT(A)2023-5-1936)构造构造LASTVT集，置集，置LASTVT(A)=若文法中有形如若文法中有形如A a 或或 A a B的规则，则的规则，则a LASTVT(A)若文法中有形如若文法中有形如AB的规则，则的规则，则LASTVT(B)LASTVT(A)(2)(2)形如形如a Aa A的规则右部的规则右部，a FIRSTVT(A)a bSTVT(A)b )形如形如a ba b或或a A ba A b的规则右部的规则右部，a a=b=b(3
24、)#(3)#STVT(S)#2023-5-1937 在在 OG文法文法 G 中，若任意两个终结符间至多只有三种算符中，若任意两个终结符间至多只有三种算符优先关系优先关系=、中的一种算符优先关系存在，则称中的一种算符优先关系存在，则称G 为算符为算符优先文法优先文法(OPG)。算符优先文法是无二义的。算符优先文法是无二义的。2023-5-19381 素短语：素短语：至少含有一个终结符号至少含有一个终结符号，并，并且且除自身之外不再含有任何更小的除自身之外不再含有任何更小的 带带有终结符号的短语有终结符号的短语，则称为，则称为素短语素短语。2 最左素短语：最左素短语：句型最左边的素短语。句型最左边
25、的素短语。算符优先文法句型的最左素短语是算符优先文法句型的最左素短语是唯一的。唯一的。EE+TE+TTT*FFi句型T+T*F+i的语法树最左素短语可能不是相应文法的任何产生式的右部。最左素短语可能不是相应文法的任何产生式的右部。按算符优先关系所确定的归约串恰好是当前句型的最左素短语按算符优先关系所确定的归约串恰好是当前句型的最左素短语2023-5-1939n总控程序总控程序(驱动程序驱动程序)。对所有。对所有LRLR分析器都相同。分析器都相同。n分析表分析表(分析函数分析函数)。不同文法分析表不同，同一文法采用的。不同文法分析表不同，同一文法采用的LRLR分析器不同时，分析表也将不同。分析器
26、不同时，分析表也将不同。n分析栈。分析栈。包括文法符号栈和相应的状态栈。包括文法符号栈和相应的状态栈。总控程序总控程序outputInput(#)LR分析表分析表ACTIONGOTOS0#Sm Xm 状态栈状态栈 符号栈符号栈2023-5-1940 动作表动作表(ACTION)(ACTION)ACTIONS,a：表示在当前状态表示在当前状态S下，面临扫描符号下，面临扫描符号a所应采取的动所应采取的动作。动作有四种：移进、归约、出错、接受。作。动作有四种：移进、归约、出错、接受。转向表转向表(GOTO)(GOTO)GOTOS，X：若：若X VT，表示在当前状态下，读入，表示在当前状态下，读入a应
27、转向什么状态；应转向什么状态；若若X VN，表示当前栈顶句柄归约成，表示当前栈顶句柄归约成X后，应转向什么状态。后，应转向什么状态。移进移进 ai 和和s=gotosm,ai进栈进栈actionsm,ai=归约归约 rj:AXm-r+1Xm-r+2Xm 接受接受 s=gotosm-r,A 出错出错2023-5-1941对于终结符的转向动作，可与其移进动作合并在一起填对于终结符的转向动作，可与其移进动作合并在一起填在动作表中，这样转向表可进行压缩，只保留非终结符转向在动作表中，这样转向表可进行压缩，只保留非终结符转向部分。部分。ACTIONGOTOa1 a2 anS0S1SkA1 A2 AmS5
28、 r4acc282023-5-1942 总控程序的动作由当前栈顶状态总控程序的动作由当前栈顶状态S Smm和扫描符号和扫描符号a ai i查表决定。查表决定。把把(S(Smm,a,ai i)的下一状态的下一状态S=GOTOSS=GOTOSmm，a ai i 连同连同扫描符号扫描符号进栈，栈顶进栈，栈顶成成(S,a(S,ai i)，扫描指针后移；，扫描指针后移；用产生式用产生式A A进行归约。若进行归约。若 的长度为的长度为，则弹出栈顶则弹出栈顶 项，使栈顶项，使栈顶状态变为状态变为S Sm-m-，然后将，然后将(S(Sm-m-,A),A)的下一状态的下一状态S=GOTOSS=GOTOSm-m-
29、,A,A连同连同A A一起一起入入栈，栈顶变为栈，栈顶变为(S,A)(S,A)。扫描指针不动，即不改变现行输入符号。扫描指针不动，即不改变现行输入符号。不管哪一类分析程序，总控程序的动作都一样。2023-5-1943n 特征特征n规范的；n符号栈中的符号是规范句型的前缀，且不含句柄以后的任何符号(活前缀)；n分析决策依据栈顶状态和现行输入符号。识别活前缀的 DFA.n 四种技术四种技术n LR(0)SLR(1)LR(1)2023-5-1944 在规范归约的句型中，不含有句柄以后任何符号的前缀在规范归约的句型中，不含有句柄以后任何符号的前缀称为活前缀。它有两种情况：归态活前缀和非归态活前缀。称为
30、活前缀。它有两种情况：归态活前缀和非归态活前缀。活前缀尾部正好是句柄之尾，这时可进行归约。归约活前缀尾部正好是句柄之尾，这时可进行归约。归约后又会成为另一句型的活前缀。后又会成为另一句型的活前缀。句柄尚未形成，需要继续移进若干符号后才能形成。句柄尚未形成，需要继续移进若干符号后才能形成。2023-5-1945一、LR(0)分析表的基本策略 状态状态DFA状态的转换状态的转换构造文法构造文法的一个的一个，用于识别所有活前缀。，用于识别所有活前缀。由若干由若干LR(0)项目所组成的项目所组成的集合集合来表示。来表示。由分析过程中由分析过程中的的操作引发。操作引发。2023-5-1946n 定义：定
31、义：n对文法对文法G的的每个产生式右部添加一个圆点每个产生式右部添加一个圆点，称为，称为G的一个的一个LR(0)项目项目(简称项目简称项目)。A 或或An 注：注：添加位置不同，叫做不同项目。添加位置不同，叫做不同项目。n用圆点用圆点“”表示识别一个产生式右部符号到达的位置，表示识别一个产生式右部符号到达的位置，项目记录了项目记录了当前活前缀状况。当前活前缀状况。2023-5-1947n LR(0)项目分类项目分类移进移进待归约待归约归约归约接受接受接受项目：接受项目：SS SS 归约项目：归约项目：A 待归约项目：待归约项目：AB B VN移进项目：移进项目：Aa a VT2023-5-19
32、48n 1）定义）定义n项目集是相关项目的集合。是通过对某个基本项目集项目集是相关项目的集合。是通过对某个基本项目集I I通过通过closure(I I)运算求得。运算求得。n 2 2）closure(I)closure(I)构造构造n设设I是文法是文法G的一个的一个LR(0)项目集项目集,closure(I)是从是从I出发用下面三个规出发用下面三个规则构造的项目集则构造的项目集:1I I中每一个项目都中每一个项目都属于属于closure(I(I)；2若项目若项目AB closure(I I)且且BVN，B P，则将则将B加进加进closure(I I)中中。3重复执行重复执行(2)直到直到c
33、losure(I I)不再增不再增大为止。大为止。2023-5-1949 其中，其中，I:项目集，项目集，xV，J=Ax|A x I。含义：含义：对于任意项目集对于任意项目集I，转换到项目，转换到项目J，是由于，是由于I中有中有AX，J中有中有AX，表示识别的活前缀增加了表示识别的活前缀增加了X。XAXI I：AXJ J:go(I,X)=J closure()n 1 1）定义）定义2023-5-1950二、识别所有规范句型全部活前缀的DFA对于一个文法对于一个文法G，可构造，可构造一个一个DFA，由它的状态（项目，由它的状态（项目集）记住当前活前缀状况，该集）记住当前活前缀状况，该DFA能识别
34、能识别G的所有活前缀。的所有活前缀。若状态中项目为若状态中项目为A，则则表示它已处于表示它已处于归态活前缀。归态活前缀。若为若为A则表示它处于则表示它处于非归态活前缀非归态活前缀。DFA的的整个状态集称整个状态集称为为LR(0)项目集规范族项目集规范族。项目项目、项目集项目集、项目集项目集规范族规范族。目的：构造目的：构造LR(0)的的项项目集规范族。目集规范族。2023-5-1951Step 1拓广文法拓广文法G，形成新的文法形成新的文法G。即增加产。即增加产生式生式SS，并令并令S S作为作为G的初态的初态I I0的基本项目的基本项目Step 2定义和构造项定义和构造项目集的闭包。目集的闭
35、包。设设I I是是G的一的一个项目集，个项目集，构构造造I I的闭包的闭包CLOSURE(I I)Step 3确定状态转移确定状态转移。利用利用转换函转换函数数GO实现。实现。Step 3构造构造LR(0)项项目集规范族目集规范族Q。将所有项目集，将所有项目集，以及所有状态以及所有状态间转移构造出间转移构造出来。来。构造算法：构造算法：2023-5-1952DFA M=(VTVN S ,Q 项目集规范族项目集规范族，I0=closureSS，Q，=go(I,X)DFA中每个状态为中每个状态为终态终态，从，从I0出发，沿着出发，沿着有向边有向边可使可使DFA所经历的所经历的任何状态任何状态终止终
36、止其工作，将从其工作，将从I0出发到达该状态所出发到达该状态所经过的经过的弧上的标记弧上的标记依次连接依次连接，即可得到，即可得到DFA到达该状态到达该状态时，时，所识别的某规范句型的一个所识别的某规范句型的一个活前缀活前缀。因此该。因此该DFA可识别所可识别所有活前缀。有活前缀。注意：注意：当当M到达到达只含有只含有归约项目归约项目的项目集时，表明活前缀的项目集时，表明活前缀中已含有相应句柄的全部符号，这些状态称为句柄的识别中已含有相应句柄的全部符号，这些状态称为句柄的识别状态。状态。2023-5-1953三、LR(0)分析表的构造 假定假定C=I0,I1,，In，用整数，用整数0，1，n表
37、示状态表示状态I0,I1,，In，因此，因此，G 的的LR(0)分析表含有状态分析表含有状态0，1，n。令。令含有项目含有项目SS的的Ik的下标的下标k为初态。为初态。ACTION和和GOTO可按如下方可按如下方法构造：法构造：若项目若项目Aa属于属于Ii且且GO(Ii,a)=Ij,aVT，则置，则置ACTIONi,a为为“把状态把状态j和符号和符号a移进栈移进栈”，简，简记为记为“sj”；若若aVN，则置，则置GOTO(i,a)=j;若规约项目若规约项目AIi,则对任何终结符则对任何终结符a,置置ACTIONi,a为为“用产生式用产生式A进行规约进行规约”，简记为，简记为“rj”;其中，假定
38、其中，假定A为文法为文法G的第的第j个产生式；个产生式；若接受项目若接受项目SS属于属于Ik,则置则置ACTIONk,#为为“接受接受”，简记，简记为为“acc”;分析表中凡不能用上述规则填入信息的空白格均置上分析表中凡不能用上述规则填入信息的空白格均置上“出错标志出错标志”。2023-5-1954注意：一个注意：一个LR(0)项目集中不能有下列情况存在：项目集中不能有下列情况存在：1、移进和归约项目同时存在、移进和归约项目同时存在(移进移进-归约冲突归约冲突)形如：形如：Aa，aVT B 2、归约和归约项目同时存在、归约和归约项目同时存在(归约归约-归约冲突归约冲突)形如：形如：A B 20
39、23-5-1955l 对于冲突状态对于冲突状态I中的归约项目中的归约项目A ，不管当前输入符号，都把，不管当前输入符号，都把ACTION表中的状态行所有非终结符列置为表中的状态行所有非终结符列置为rj，其中，其中j为为A 产生式编产生式编号。号。产生冲突的根本原因？产生冲突的根本原因？l 构造分析表时根据不同的扫描符号构造分析表时根据不同的扫描符号a，将，将I中各项目对应的分析动作加中各项目对应的分析动作加以区别，冲突即可解决。以区别，冲突即可解决。l SLR(1)是是LR(0)的一种改进，对有冲突的状态向前查看一个符号，的一种改进，对有冲突的状态向前查看一个符号，以确定作何种动作以确定作何种
40、动作。如何解决？如何解决？一、问题分析2023-5-1956n 定义：定义：对于文法中的非终结符对于文法中的非终结符UVN FOLLOW(U)=a|S Ua，aVT#n 对含冲突的项目集对含冲突的项目集I=X b，A，B，若若b、FOLLOW(A)、FOLLOW(B)两两不相交，则面两两不相交，则面对当前读入符号对当前读入符号a，状态，状态I的解决方法：的解决方法：l 1.若若a=b，则移进。，则移进。l 2.若若a FOLLOW(A)，则用，则用A 进行归约。进行归约。l 3.若若a FOLLOW(B)，则用，则用B 进行归约。进行归约。l 4.此外，报错。此外，报错。*2023-5-195
41、7二、构造SLR(1)分析表的算法 设设C=I0,I1,In,以各项目集以各项目集Ik(k0，,n)的的k作为状态序号，作为状态序号，并以包含并以包含SS的项目集作为初始状态，同时将产生式进行编号。然后按的项目集作为初始状态，同时将产生式进行编号。然后按下列步骤填写下列步骤填写ACTION表和表和GOTO表：表：l 1）若项目）若项目Aa 属于属于Ik状态且状态且GO(Ik,a)=Ij，a为终结符，为终结符，则置则置ACTIONk,a=Sj；即：移进；即：移进a，并转向，并转向Ij状态。状态。l 2）若项目）若项目A Ik，则对任何终结符，则对任何终结符a Follow(A)，置，置ACTIO
42、Nk,a=rj；其中；其中j是产生式是产生式A的编号，即按该产生式的编号，即按该产生式进行进行归约。归约。l 3）若项目）若项目S S属于属于Ik，则置，则置ACTIONk,=acc;l 4）若）若GO(Ik,A)=Ij，A是非终结符，则置是非终结符，则置GOTOk,A=jl 5）分析表中凡不能用步骤）分析表中凡不能用步骤1至至4填入信息的空白项，均置上填入信息的空白项，均置上“出错出错标志标志”。2023-5-1958注注 意！意！l 1)若文法若文法G按上面算法构造出来的分析表不包含多重定义按上面算法构造出来的分析表不包含多重定义项，则该文法项，则该文法G是是SLR(1)文法。文法。l 2
43、)若项目集中存在若项目集中存在A 项目，不应设计相应项目，不应设计相应GO函数以函数以转到其他项目集，因为转到其他项目集，因为A 和和A 是同一项目，都是是同一项目，都是A项目，是归约项目。项目，是归约项目。l 3)二义文法决不是二义文法决不是LR文法。文法。l 4)每个每个SLR(1)文法都不是二义的，但是有很多非二义的文法都不是二义的，但是有很多非二义的文法，包括一些程序设计语言结构，都不是文法，包括一些程序设计语言结构，都不是SLR(1)的，这的，这说明说明SLR(1)文法的描述能力有限。原因是文法的描述能力有限。原因是SLR分析器的构分析器的构造方法没有记住足够多的上下文造方法没有记住
44、足够多的上下文。2023-5-1959SLR(1)规则仅孤立地考察输入符号是否属于与规则仅孤立地考察输入符号是否属于与归约项目归约项目A相关联的集合相关联的集合FOLLOW(A)以确定是以确定是否应按产生式否应按产生式A归约，没有考察符号串归约，没有考察符号串所在所在规规范句型范句型的的“环境环境”没有考察没有考察L在在规范句型规范句型中的中的“上下文上下文”，这就具有一定的片面性。，这就具有一定的片面性。请阅读课本例请阅读课本例4.82023-5-19601）当出现移进）当出现移进-归约冲突时，可选取移进，这样，归约冲突时，可选取移进，这样，这是一个自然的消除二义性的规则。这是一个自然的消除
45、二义性的规则。2）当出现归约）当出现归约-归约冲突时（如课本例归约冲突时（如课本例4.8）情）情形就较复杂，需要有新的解决方法形就较复杂，需要有新的解决方法LR（1）。）。给每个给每个LR(0)项目添加展望信息，即：添加句柄之后可能项目添加展望信息，即：添加句柄之后可能跟的终结符，这些终结符确实跟在跟的终结符，这些终结符确实跟在句柄之后。句柄之后。2023-5-1961一、LR(1)项目定义形如形如的二元式称为的二元式称为LR(1)项目。其项目。其中中A是文法的一个产生式，是文法的一个产生式，a是终结符，称为是终结符，称为。p 预期当栈顶句柄预期当栈顶句柄形成后，若形成后，若扫描到符号扫描到符
46、号a，即可进行归约。此时，即可进行归约。此时，在栈内，在栈内，还未还未入栈，即它展望了句柄后的一个符号。入栈，即它展望了句柄后的一个符号。p 对于多数程序设计语言，向前展望一个符号就足以决对于多数程序设计语言，向前展望一个符号就足以决定归约与否，所以只研究定归约与否，所以只研究在在LR(1)项目中项目中并不多。并不多。2023-5-1962 LR(1)项目项目A ，a 对活前缀对活前缀 是有效的，如果存是有效的，如果存在着推导在着推导S*r m Awr m w，即，即w为规范句型。为规范句型。其中：其中：p（1）=；p（2）a是是w的首符号，若的首符号，若w，则则a#。1)若若a First(
47、w)，即使，即使a Follow(A)，项目，项目(A ，a)也是无效的。也是无效的。2）规范的规范的LR分析法仅考虑有效的分析法仅考虑有效的LR(1)项目。项目。2023-5-1963二、构造LR(1)项目集规范族 I的任何项目都属于的任何项目都属于CLOSURE(I)；若项目若项目(A B，a)属于属于CLOSURE(I)，B 是一是一个产生式，则对于个产生式，则对于FIRST(a)中的每个终结符中的每个终结符b，如果，如果(B ，b)原来不在原来不在CLOSURE(I)中，则把它加进去；中，则把它加进去；重复步骤重复步骤(b)直到直到CLOSURE(I)不再扩大为止。不再扩大为止。因为因
48、为(A B，a)属于属于CLOSURE(I)，则，则(B ，b)也也属于属于CLOSURE(I)，其中，其中b必定是跟在必定是跟在B后面的终结符，即后面的终结符，即b First(a)，若，若 ，则，则b=a。2023-5-1964 令令I是一个项目集，是一个项目集，X是一个文法符号，函数是一个文法符号，函数GO(I,X)定义定义为：为：GO(I,X)=CLOSURE(J)，其中，其中 J=任何形如任何形如(AX，a)的项目的项目|(AX，a)I二、构造LR(1)项目集规范族2023-5-1965 例：LR(1)项目集及规范族的构造 G(S):(0)SS (1)S CC (2)C cC (3)
49、C d若A ,a I 且B P则B ,b I 其中b FIRST(a)I0SS，#S CC，#C cC，c/dC d，c/d2023-5-1966三、构造LR(1)分析表 设设C=I0,I1,In,以各项目集以各项目集Ik(k0，,n)的下标的下标k为分析表中为分析表中的状态，并以包含的状态，并以包含(SS，)的项目的状态为分析表初态。按下列步骤的项目的状态为分析表初态。按下列步骤填写填写ACTION表和表和GOTO表：表：l 1、若项目、若项目(Aa，b)属于属于Ik，且，且GO(Ik，a)=Ij，a为终结符，则为终结符，则置置ACTIONk，a=Sj ；l 2、若项目、若项目(A,a)Ik
50、，则置，则置ACTIONk,a=rj；其中；其中j为为产生式产生式A的编号的编号；l 3、若项目、若项目(SS,#)属于属于Ik，则置，则置ACTIONk,=acc；l 4、若、若GO(Ik,A)=Ij，A是非终结符，则置是非终结符，则置GOTOk,A=j；l 5、分析表中凡不能用步骤、分析表中凡不能用步骤1至至4填入信息的空白项，均置上填入信息的空白项，均置上“error”。2023-5-1967 若文法若文法G构造出的构造出的LR(1)分析表分析表不含多元素，则文法不含多元素，则文法G是是 1）每个）每个LR(1)文法都是文法都是SLR(1)文法，反之不一定文法，反之不一定成立；成立；2）
