语法分析——自底向上.ppt

语法分析概述 短语、直接短语及句柄 算符优先分析 LR分析 LR分析的错误处理与恢复 语法分析程序自动生成器,第五章 语法分析 自底向上,2,基本思想：从输入串开始逐步归约 基本问题：归约的问题 优先分析法 优先文法、算符优先文法 优先算符 优先函数的构造 分析方法 基础知识 LR(0)项目及项目集 LR(1)项目及项目集 规范句型活前缀 LR分析法 LR分析器 分析栈、分析表 分析方法 LR分析表的构造 实现技术移进归约,自下而上语法分析,5.1自下而上的语法分析,CompilerPrinciples,3,自下而上分析基本思想 从给定的输入串$开始，不断寻找子串与文法G中某个产生式P的候选式进行匹配，并用P的左部代替(归约)之，逐步归约到S,CompilerPrinciples,4,1.归约与语法分析树 例 文法 GS: (1)SaAcBe (2)Ab (3)AAb (4)Bd W=abbcde，构造其语法分析树：,S,5,2.移进归约,动作：,符号栈：,移进a,移进b,归约b,移进b,归约Ab,移进c,移进d,归约d,归约aAcBe,移进e,归约产生式：,(2),(3),(4),(1),例 文法 GS: (1)SaAcBe (2)Ab (3)AAb (4)Bd,5.1自下而上的语法分析,CompilerPrinciples,6,自下而上分析的关键 ： (1) 确定可归约串 (2) 如何归约,归约条件,归约原则,5.1.2 规范规约与句柄,定义： 定义5.1 短语： 令G是一个文法，S是开始符号，是文法G的一个句型，如果有 S * A且A +， 则称是句型相对于非终结符A的短语。 特别的，如果有A ，则称是句型相对于规则A的直接短语（简单短语） 定义5.2 句柄： 一个句型的最左直接短语称为该句型的句柄。,CompilerPrinciples,7,5.1.2 规范规约与句柄,注意： 直接短语一定是短语； 句柄一定是直接短语且具有最左性； 句子的句柄是语法树中最左子树的所有叶节点从左到右的排列或在句子的规范推导序列中，最后使用的产生式的右部；,CompilerPrinciples,8,思考： 用什么方法找出所有短语、直接短语和句柄？,例： 设有文法G和输入串$ G: SaAcB AP Pab Bd $: aabcd 对$存在推导 S= aAcB= aPcB= aabcB= aabcd,CompilerPrinciples,9,例,例：文法GE: E E+TT T T*F|F F (E)|i 求句型T+T+i的短语、简单短语和句柄 短语：T+T+i、T+T、T、i 简单短语：T、i 句柄：T,CompilerPrinciples,10,规范归约,假定是文法G的一个句子，有序列n, n-1, 0 ，如果此序列满足： . n ; . 0S; . 对任何i,0in, i-1是从i经把句柄替换为相应产生式的左部符号而得到的 称此序列是 的一个规范归约,11,规范归约是关于的一个最右推导的逆过程，因此规范归约也称最左归约； 例5.1 设有文法G1和输入字符串abbcde (1) SaABe (2) AAbc (3) Ab (4) Bd S aABe aAde aAbcde abbcde R R R R,CompilerPrinciples,12,规范归约,（1）,（1）,（2）,（2）,（3）,（3）,（4）,（4）,13,基本思想：从输入串开始逐步归约 基本问题：归约的问题 优先分析法 优先文法、算符优先文法 优先算符 优先函数的构造 分析方法 基础知识 LR(0)项目及项目集 LR(1)项目及项目集 规范句型活前缀 LR分析法 LR分析器 分析栈、分析表 分析方法 LR分析表的构造 二义性文法的分析 实现技术移进归约,自下而上语法分析,5.2.1直观的优先分析方法,基本思想 对给定的G按照一定原则求出G的文法符号间的优先关系，按照优先关系寻找句柄实施归约。,CompilerPrinciples,14,a b 表示的a优先关系低于b a b 表示的a优先关系高于b a b 表示的a优先关系同等于b,优先关系,确定优先关系的规则,（1）X Y 当且仅当G中存在产生式A XY （在语法树的同一层） （2） X Y 当且仅当G中存在产生式A XB，且B Y （ Y 在 X 的下一层） （3）X Y 当且仅当G中存在产生式A BD，且B X和D Y （ X在 Y 的下一层或X比 Y先归约规范归约/最左归约 ）,+,+,*,例：有文法G(S): SbAb A( B | a BAa ) 解：文法符号优先关系推导如下： (1) 求关系: 由SbAb ， A( B， BAa ) b A， A b， ( B， A a， a ),(2) 求关系： 由SbAb 且A （B 可得 b ( A a 可得 b a 由A( B 且B ( B 可得 ( B aa 可得 ( a B Aa ) 可得 ( A,(3) 求关系: 由SbAb，且A) 可得 ) b AB 可得 B b A a 可得 a b 由BAa )，且A) 可得 ) a Aa 可得 a a AB 可得 B a,+,优先关系矩阵表示法：,简单优先文法的定义： （1）在文法符号集中，任意两个符号之间最多只有一种优先关系； （2）在文法中任意两个产生式没有相同的右部。,优先表,CompilerPrinciples,21,优先表,例5.2 设有文法G (1) S aSb (2) Sab 输入字符串aabb，请分析,注意：优先关系既非对称，也不传递。,简单优先分析法特点： 只是用于简单优先文法，准确规范，但分析效率低，实际使用价值不大； 算符优先分析法的提出： 只考虑算符（终结符）之间的优先关系，不考虑非终结符之间的优先关系。,CompilerPrinciples,22,5.2.2.算符优先文法的定义,定义 ( 算符文法 ) 设有一文法G，如果G中没有 形规则，且没有的规则，其中，N ，则称文法G是算符文法(OG)。 例5.3 设有文法G (1) E EAE | （E）| i (2) A + | | * E E+E | E E | E * E | i,23,非OG,OG,定义命题： 算符文法的任何句型都不会含有两个相邻的非终结符。,5.2.2.算符优先文法的定义, 定义：算符优先文法 设G是一不含 形规则的算符文法，则对于任何两个终结符a，b有： ab，当且仅当文法G中有形如 A ab或A aBb的规则： ab，当且仅当文法G中有形如A aB的规则，其中B=b 或B= Cb； a b，当且仅当文法G中有形如A Bb的规则，其中B = a或B= aC。 若文法G中所有终结符号之间最多只满足这三者关系之一，则称文法G是算符优先文法(OPG文法)。 其中：a、b VT ;A、B、C VN；“” (VT VN)*,24,说明 ： (1) OPG一定是OG； (2) OPG不含产生式； (3) OPG满足定义 的。,5.2.2.算符优先文法的定义,例5.4 设文法G(P)： PaQ QbR Ra 考察G(P)是不是算符优先文法。,CompilerPrinciples,25,考察G(P)中的终结符a、b的优先关系： 据定义中的，因存在PaQ且Q=bR, 所以ab ； 据定义中的 ，因存在bR且=a, 所以ba ； b与b, a与a不存在优先关系。所以G(P)是算符优先文法。,5.2.2.算符优先文法的定义,例5.5 设文法G ： S aSb | ab 考察G(P)是不是算符优先文法。,CompilerPrinciples,26,考察G(P)中的终结符a、b的优先关系： 据定义， S aSb | ab ab; 据定义， S aS 且S= a a a; 据定义， S Sb且 S= b b b;,问题： 在计算机中应如何构造算符优先关系表？,5.2.3算符优先关系表的构造,27,优先关系： ab Pab或PaQb 的产生式； ab PaR形式的产生式，且R+b或R+Qb ； ab PRb形式的产生式，且R+ a或R+ aQ； 定义集合： 设P是G的任一非终结符，那么： （1）最左终结符集FIRSTVT FIRSTVT(P)=a|P+a或P+Qa,aVT而Q,PVN （2）最右终结符级LASTVT LASTVT(P)=a|P+a或P+aQ,aVT而Q,PVN,问题： FIRSTVT、LASTVT应如何构造？,（1）FIRSTVT的构造算法： 方法一：根据定义 FIRSTVT(B)可使用如下规则： .若有产生式P a 或PQa，则aFIRSTVT (P)； .若aFIRSTVT (Q)且有产生式PQ ,则a FIRSTVT(P)； 方法二：使用一个布尔数组FRP,a和一个栈Stack,CompilerPrinciples,28,29,具体算法描述如下： a.置FR初值为FALSE; b.用规则1对FRP,a初始化 对每个非终结符P,若有形如P a 或PQa的产生式，则变FRP,a的FALSE为TRUE，同时(P,a)进栈； c.只要Stack非空，则出栈。每退出一项(Q,a)则检查是否有PQ 形式的产生式，若有，则置FRP,a为TRUE,同时(P,a)进栈,直到栈空为止。 当对所有的非终结符执行如上操作之后，就构造出了FIRSTVT集，即： FIRSTVT(P) aFR(P, a)TRUE,方法二：使用一个布尔数组FRP,a和一个栈Stack,例：求非终结符的FISRTVT,GE E #E# EE+T E T TT*F T F F(E) F i,30,FIRSTVT( E)= # FIRSTVT( E)=+FIRSTVT( T)= +,*,(,i FIRSTVT( T)=* FIRSTVT( F)= *,(,i FIRSTVT( F)= (,i,T,T,T,T,T,T,T,T,T,T,例5.6 设文法G( P)： P Qa Q bR R a 据FIRSTVT(G)的算法首先求该文法的数组FR,CompilerPrinciples,31,（2）LASTVT的构造算法： 方法一：根据定义 LASTVT(B)可使用如下规则： .若有产生式Ba或BaC，则aLASTVT(B)； .若aLASTVT(C)且有产生式BC,则aLASTVT(B)； 方法二：使用一个布尔数组PB,a和一个栈Stack,CompilerPrinciples,32,33,具体算法描述如下： a.置P初值为FALSE; b.用规则1对PB,a初始化 对每个非终结符B,若有形如Ba或BaC的产生式，则变PB,a的FALSE为TRUE，同时(B,a)进栈； c.只要Stack非空，则退栈。每退出一项(C,a)则检查是否有BC形式的产生式，若有，则置PB,a为TRUE,直到栈空为止。 当对所有的非终结符执行如上操作之后，我们就构造出了LASTVT集，即： LASTVT(B)= a|PB,a=TRUE ,方法二：使用一个布尔数组PB,a和一个栈Stack,例：求非终结符的FISRTVT和LASTVT,GE E #E# EE+T E T TT*F T F F(E) F i,CompilerPrinciples,34,FIRSTVT( E)= # FIRSTVT( E)=+FIRSTVT( T)= +,*,(,i FIRSTVT( T)=* FIRSTVT( F)= *,(,i FIRSTVT( F)= (,i LASTVT( E)= # LASTVT( E )=+LASTVT( T)= +,*,),i LASTVT( T )=*LASTVT( F)= +,*,),i LASTVT( F)= ),i,5.2.3算符优先关系表的构造,CompilerPrinciples,35,通过检查每个产生式的候选式确定满足关系和的所有终结符对。 ab 对形如Pab或PaQb 产生式； ab 对形如PaR产生式，则对任意bFIRSTVT(R),有ab 成立； ab 对形如PRb产生式，则对任意bLASTVT(R),有ab成立；,36,算法5.2：算符优先关系表的构造算法,输入：文法G及G的FIRSTVT(G)和LASTVT(G) 输出：文法G的优先关系表 方法：for 每条产生式PX1X2Xn for(i=1 ;in ;i+) if (Xi和Xi+1 均为终结符 ) XiXi+1 ; if (in-2且都Xi和Xi2为终结符,Xi1为非终结符) XiXi+2 ； if(Xi为终结符,Xi+1为非终结符 ) for FIRSTVT(Xi+1)中的每个a Xia ； if(Xi为非终结符,Xi+1为终结符 ) for LASTVT(Xi)中的每个a aXi+1 ,例：求算符优先关系表,文法GE： EE+T|T TT*F|F FPF|P P(E)|i,CompilerPrinciples,37,FIRSTVT( E)=+FIRSTVT( T)= +,*, ,(,i FIRSTVT( T)=* FIRSTVT( F)= *, ,(,i FIRSTVT(F )= FIRSTVT( P)= ,(,i FIRSTVT( P)= (,i LASTVT( E )=+LASTVT( T)= +,*,),i, LASTVT( T )=*LASTVT( F)= ,*,),i LASTVT( F)= LASTVT( P)= ,),i LASTVT( P)= ),i,注: 表中的空白表示相对应的终结符对偶没有优先关系。,38,5.2.4算符优先分析算法,CompilerPrinciples,39,仅在终结符间定义优先关系。 算符优先分析并没有对非终结符定义优先关系，所以也就无法对单个非终结符所组成的句柄进行归约。 算符优先不属于规范规约,5.2.4算符优先分析算法,定义素短语: 设G是一个算符文法，是句型 关于A的短语且至少含有一个终结符号，并且除自身外不再含有任何更小的带终结符号的短语，则是句型关于A的素短语。 最左素短语: 处于文法G的句型的最左边的素短语为最左素短语。,最左素短语示例,例GE: EE+TT TT*FF F(E)i 句型：T+T*F+i 短语：T; T*F; T+T*F; i; T+T*F+i 直接短语: T; T*F; i; 句柄： T 素短语：T*F; i 最左素短语:T*F,最左素短语示例,例GE: EE+TT TT*FF F(E)i 考察i*i ? T ?,i,i,素短语,43,由算符文法性质可知： 句型记为： #N1a1 N2a2NnanNn+1 # 其中： ai都是终结符 Ni是非终结符 定理: 算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串 NjajNiaiNi+1 aj-1 aj aj aj+1 ,ai-1 ai ai ai+1 算符文法的任何句型中终结符和非终结符相邻时含终结符的短语必含相邻的非终结符,5.2.4算符优先分析算法,例5.7 设文法G() E ETT T T*F F F(E)I,CompilerPrinciples,44,算符优先分析器的总控程序,算法5.3 初始化。将“”压入栈，栈顶指针p1； 当前输入符号=a； 比较符号栈顶项 b(bVT)与a的优先级； 若ba或 b= a转 ； 若b a转 ；否则 error; a入栈( p+)转 ； /还没形成最左素短语，移进 在栈中寻找满足bn+1bnbn-1b1a的bn，即寻找 最左素短语的头； 将 bn bn-1 b1及有关的非终结符归约到，入栈；若栈中为S与a“”，则end，否则(a)=栈顶转；,CompilerPrinciples,45,CompilerPrinciples,46,文法GE： EE+T|T TT*F|F FPF|P P(E)|i 试用算符优先分析法分析句子i+i*i,练习,例5.8 设有文法G(Z) 和输入串b (aa)b Z bMb M (La L Ma) 文法G(Z)的优先关系表 对句子a(c)b进行分析,CompilerPrinciples,47,CompilerPrinciples,48,步骤 符号栈 优先关系 (a) 输入字符串 动 作 1 b (aa)b 初始化 2 a )b 用Ma归约 6 b(M b 用LMa)归约 9 b(L b 用M(L归约 10 bM = b b进栈 11 bMb 用ZbMb归约 12 Z 分析成功，结束,49,注： a. 归约并没指明应把找到的最左素短语归约到哪个非终结符N，只能是一棵语法树的架子 b. 由于忽略了对单非产生式的归约步骤，所以存在一种危险：可能把非法句子误认为是合法句子 c.对一目运算符和三目运算符不太好处理,5.2.5优先函数的构造, 为什么引入优先函数表 引入优先函数表，是每个终结符仅对应两个优先函数，即栈内和栈外优先函数，则G的优先关系表的大小 = 2(n+1)，且在分析中便于进行终结符之间的比较。,CompilerPrinciples,50,5.2.5优先函数的构造,优先函数表 引入两个优先函数f和g。 其中f()，称为栈内优先函数，g()称为比较优先函数(栈外优先函数)。将每个终结符号与两个优先函数f() 和 g() 相对应，f()，g()自然数，则可有下列优先关系： 若1 2，则 f(1) g(2)； 若1 2，则 f(1) g(2)； 若1 2，则 f(1) g(2) 两种构造优先函数的方法： 有向图(Bell)方法 Floyd方法,CompilerPrinciples,51,5.2.5优先函数的构造,CompilerPrinciples,52,对每个终结符a(包括)，令其对应两个符号fa和ga，画一张以所有fa、ga为结点的方向图。 ab，画一条从fa到gb的弧 ab, 画一条从gb到fa的弧 对每个结点都赋予一个数，此数等于从该结点出发所能到达结点的个数。赋给fa的数作为f(a)，赋给gb的数作为g(b)。 把以上构造出的f和g同原来的优先表相对照，看是否有矛盾。 若无，则f,g即为所求； 若有矛盾，则说明并无优先函数存在。,(1)有向图(Bell)方法,5.2.2.算符优先文法的定义,例5.5 设文法G ： S aSb | ab 试构造文法G(S)的优先函数表。,53,fa fb ga gb,(2),(3),(3),(2),检查构造的优先函数： 对aa，f (a)g (a)有23； 对ab，f (a)g (b)有22； 对bb，f (b) g (b)有32； 因此，优先函数存在。,54,gi,fi,f*,g*,g+,f+,f#,g#,例如文法GE: EE+TTTT*FFFi,优先关系表并非与优先函数表一一对应,CompilerPrinciples,55,如果假定存在函数 f 和 g，则应有： f(a)g(a)， f(a)g(b) f(b)g(a)， f(b)g(b) 按此假设 f (a)g (b) f (b)g(a) f (a)= f (a)f (a),矛盾！,结论： 若从优先关系表构造出的有向图中有环路，则优先函数不存在,CompilerPrinciples,56,文法GE： EE+T|T TT*F|F FPF|P P(E)|i,(2)对前面给出的优先表可以画出如下的有向图，并构造出相应的优先函数：（为简单计省去了i和#）,结论： 优先关系表元素较多时不宜采用BELL图构造优先函数。,(2)Floyd方法 对每一个f和g赋初值,置f(a) = g(b) = 1 迭代,即每一符号对(a, b) 若a b 但f(a ) = g(b ), 则执行g(b ) = f(a ) + 1 若a b 但f(a ) g(b ),则令f(a )和g(b ) 中的较小者等于较大 重复,直至过程收敛为止.,Floyd方法举例,例如文法GE: EE+TT；TT*FF；F(E) | i 的算符优先关系矩阵如右表。优先函数f,g计算如下：,59,练习,例如文法GE: EE+TTTT*FFFi,关于优先函数结论： 对优先函数表每个元素的值增加同一个常数，优先关系不变 有的优先关系表不存在优先函数 不存在优先关系的符号也可比较,60,总结 算符优先分析所确定的可归约串是当前句型的最左素短语 算符优先分析属于自底向上的语法分析,但不是严格的最左归约 算符优先分析只考虑终结符号之间的优先关系 算符优先分析算法很容易程序实现,设有下列文法: A a | (R) T A,T | A R T (1) 计算该文法的FIRSTVT和LASTVT。 (2) 计算该文法的优先关系并产生优先关系表。 (3) 计算该文法的优先函数。 FIRSTVT(A)= a, ( LASTVT(A) = a, ) FIRSTVT(T)= a, (, , LASTVT(T) = a, ) , , FIRSTVT(R)= a, (, , LASTVT(R) = a, ) , ,CompilerPrinciples,61,62,基本思想：从输入串开始逐步归约 基本问题：归约的问题 优先分析法 算符文法、算符优先文法 优先算符 优先函数的构造 分析方法 基础知识 LR(0)项目及项目集 LR(1)项目及项目集 规范句型活前缀 LR分析法 LR分析器 分析栈、分析表 分析方法 LR分析表的构造 二义性文法的分析 实现技术移进归约,自下而上语法分析,文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B d,a,b,b,c,d,e,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进,2） #a bbcde# 移进,4） #aA bcde# 移进,6） #aA cde# 移进,7） #aAc de# 移进,9） #aAcB e# 移进,11） #S # 接受,对输入串abbcde#的移进-规约分析过程,LR分析： 一类对源程序串进行自左向右扫描并进行规范归约的语法分析方法。,CompilerPrinciples,64,L R (K),分析模式：最右推导逆序(规范归约),向前看k个输入字符,扫描模式：自左向右,65,LR分析综述,常见的程序设计语言均能由LR(1)文法产生 四种LR分析器： LR(0)简单,分析能力最低; SLR(1)分析能力强于LR(0); LR(1)分析能力最强,但分析表大; LALR(1)分析能力介于SLR(1)与LR(1)之间,分析表的规模与SLR(1)相同,是最常用的LR分析方法。,66,5.5.1 LR分析器的逻辑结构和工作过程 (1)LR分析法的基本思想： 根据“历史资料”、“现实输入符号”以及对未来的“展望”等三个方面来确定栈顶的符号是否构成了相对于某一产生式的句柄。 （2）LR分析器的逻辑结构 LR分析器的实质是一个带栈的以文法符号为字母表的DFA LR分析器的组成 分析栈 分析表 总控程序,CompilerPrinciples,67,LR分析器总控程序,输出,输入串,分析栈,分析表,LR分析器模型图,(1) 分析栈 辅助完成LR分析的数据结构。 状态Si： 记录分析过程中每一步的“历 史”或“展 望”信息； stack 文法符号Xi: 存放分析过程中移进(VT)和 归约 (VN)的符号； stack初始化:,CompilerPrinciples,68,P,(2) LR分析表 LR分析表是LR分析器的核心。 分析动作表(ACTION表) 规定了状态S面临输入符号a时应该采取什么动作 分析表 状态转换表(GOTO表) 则指出状态S面对文法符号X（非终结符） 时下一状态是什么,CompilerPrinciples,69,VT,VN,LR 分析表,CompilerPrinciples,70,rj( 归约：用第j个产生式归约 ) acc ( 接受：分析成功) action(Si,ai) = error ( 出错：语法错，调出错处理程序 ) Sj( 移进：将ai和第j个状态压入栈),CompilerPrinciples,71,状态转换表 (Goto) Si状态； Xi 非终结符集；,72,j ( 移进：将第j个状态压入栈) goto(Si, Xi ) = error ( 出错：语法错，调出错处理程序 ),CompilerPrinciples,73,注意： goto( Si, Xi ) 意指当前栈顶状态为Si和符号为Xi时转到下一状态。,74,c)总控程序 LR分析器的工作过程： 栈里的状态序列、符号栈的已归约串和输入串所构成的三元式的变化过程： 状态栈 符号栈 剩余符号串 初始三元式： ( s0, #, a1a2an#) 中间三元式： (s0s1sm, #X1X2Xm, aiai+1an#) 接受: (s0sk, #X, #) (X为开始符号，而Actionsk,# 为接受) 一步一步地变换三元式，直至执行“接受”或“报错”为止。,(3) LR分析总控程序 分析开始，将初始状态S0及输入字符串左界符 “”压入分析栈； / 初始化 对分析的某一步，据当前分析栈栈顶Sm，当前 输入符号ai查action表： 转。,75,(i)若action(Sm , ai)Sj，完成移进动作； (ii)若action (Sm,ai)rj，完成归约动作，后查goto表； (iii) 若action(Sm , ai)acc，分析成功； (iv) 若action(Sm , ai)error，出错处理。,步骤,符号栈,剩余符号串,动作,1） # abbcde# 移进 0 S2,2） #a bbcde# 移进 02 S4,4） #aA bcde# 移进 023 S6,6） #aA cde# 移进 023 S5,7） #aAc de# 移进 0235 S8,9） #aAcB e# 移进 02357 S9,11） #S # 接受 01 acc,对输入串abbcde#的LR分析过程：,3） #ab bcde# 归约(Ab) 024 r2 3,5） #aAb cde# 归约(AAb) 0236 r3 3,8） # aAcd e# 归约(Bd) 02358 r4 7,10） #aAcBe # 归约(SaAcBe) 023579 r1 1,状态栈,ACTION,GOTO,Si:移进：将下一状态i和现行输入符号进栈； ri:归约：用第i个产生式归约，同时状态栈与符号栈退出相应的符号，并把GOTO表相应状态和第i个产生式的左部非终结符入栈。,77,例如文法GE: 1、EE+T； 2、ET； 3、TT*F 4、TF 5、F(E) 6、 F i,利用LR分析算法给出符号串i+i*i#的分析过程,例5.10 设有文法G(L)和G (L)的LR分析表 LE，L LE Ea Eb 输入字符串 a, b, a #的分析过程,CompilerPrinciples,78,5.5.2LR(0)分析法,2. LR(0)分析法 在分析的每一步，只要根据当前的栈顶简单状态就能确定分析器的动作，而无需向前查看输入符号。 LR(0)项目集,CompilerPrinciples,79,规范句型的活前缀,定义（前缀） 一个句型的任意首部，称为该句型的一个前缀。 例如 abc为某文法的句型 ，a，ab，abc 该句型的前缀； ac，bcd，c 不是该句型的前缀。,CompilerPrinciples,80,规范句型的活前缀,定义5.7 （活前缀） 规范句型的一个前缀，称为该句型的一个活前缀。,CompilerPrinciples,81,最右推导得到的句型,注意 ： (1) S A，若串是的前缀,是的 活前缀； 当=， 是可归前缀；,R,R,*,规范句型的活前缀,例GE: EE+TT TT*FF F(E)i 求规范句型：E+T*F+i的活前缀,规范句型的活前缀,CompilerPrinciples,83,注意 ： (1) 活前缀特点: 不含句柄之后的任何符号； (2) LR分析中必需使栈中符号始终是活前缀，这样再 从输入串读入几个符号后，构成刚好包含句柄的 活前缀，进而实施归约。,84,4.5.2LR(0)分析法,LR(0)项目： 文法G的每一个产生式的右部添加一个圆点称为G的一个LR(0)项目（简称项目） 圆点用来表示左部符号串已经被识别的位置,CompilerPrinciples,85,例如，产生式AXYZ对应四个项目： AXYZ AXYZ AXYZ AXYZ 约定：A只对应一个项目：A 。 项目反映分析过程中某时刻看到产生式的多大部分。 AXYZ 希望能从后面输入串看到可以从XYZ推导出的符号串。 AXYZ 已经从输入串看到了从X推导出的符号串，并希望能进一步看到YZ推出的符号串。,86,4.5.2LR(0)分析法,活前缀与当前句柄的关系: 活前缀包含句柄的全部符号; 活前缀只含句柄的部分符号 活前缀不含句柄的任何符号,A,A,A ,提示: 通过构造一个识别所有活前缀的自动机,来构造分析表,LR (0) 项目分类,(1) 归约项目：A 这类LR(0)项目表示句柄 恰好包含在栈中,即当前栈顶的部分内容构成了所期望的刚好含句柄的活前缀，应按A进行归约。 (2) 接受项目： S （S是开始符号） 其中S是文法惟一的开始符号。,CompilerPrinciples,87,(3) 移进项目： Aa (aVT) 这类LR(0)项目表示分析栈中是不完全包含句柄的活前缀，为了构成恰好含有句柄的活前缀，还需将a 移进分析栈。 (4) 待约项目： AB (BN) LR(0)项目表示分析栈中是不完全包含句柄的活前缀，为了构成恰好有句柄的活前缀，应先把当前输入字符串中的相应内容先归约到B。,CompilerPrinciples,88,例题： 设文法G(S) SS SA | B A aA | b | Bc 则G(S)的LR(0)项目有： SS SS SA SA SB SB AaA AaA AaA Ab Ab A Bc Bc,CompilerPrinciples,90,例文法GS: (0)SE (1) EaA (2) EbB (3)AcA (4) Ad (5) BcB (6) Bd 它的项目有： 1. SE 2. SE 3. EaA 4. EaA 5. EaA 6. AcA 7. AcA 8. AcA 9. Ad 10. Ad 11. EbB 12. EbB 13. EbB 14. BcB 15. BcB 16. BcB 17. Bd 18. Bd,LR(0)项目集举例,91,LR(0)项目举例,例文法GS:1. SA ; 2.S B; 3.AaAb ; 4.A c; 5.BaBb 6.Bc 拓广的文法G： S S G的LR(0)项目如下：,S S 2. SS 3. S A 4. S A 5. S B 6. S B ,7. A aAb 8. A aAb 9. A aAb 10. A aAb 11. A c 12. A c, B aBb B aBb B aBb B aBb B d B d,92,构造识别活前缀的DFA 方法一： .通过项目构造一个NFA ： 把项目编号，所有编号构成NFA的状态集； 以开始符号S所对应的项目S 为唯一初态 若项目i为：XX1Xi-1XiXn, 而项目j为：XX1XiXi+1Xn ，则从i到j画一条标记为Xi的弧； 若XiVN，则从状态i画弧到所有的Xi状态； .用子集法把NFA确定化为DFA建立LR分析算法的基础。,CompilerPrinciples,93,例5.8 文法 GS: (0)SS (1) SaS|b 它的项目有： 0. SS 1. SS 2. SaS 3. Sa S 4. SaS 5. Sb 6. Sb,I0:SS,I1:SS ,I2:SaS,I5:Sb,I6:Sb ,I3:SaS,I4:SaS,94,(2)确定化,I0: S S SaS Sb,I3:Sb ,I2:SaS SaS Sb,S,a,b,S,I1:SS,I4:SaS,a,b,句子ab的归约： 0-2 -3 ab (b归约到S) 0 - 2-4 aS (aS归约到S) 0 -1 S (S归约到S),提问：DFA如何识别活前缀,CompilerPrinciples,95,例5.9 文法GS: (0)SE (1) EaA (2) EbB (3)AcA (4) Ad (5) BcB (6) Bd 它的项目有： 1. SE 2. SE 3. EaA 4. EaA 5. EaA 6. AcA 7. AcA 8. AcA 9. Ad 10. Ad 11. EbB 12. EbB 13. EbB 14. BcB 15. BcB 16. BcB 17. Bd 18. Bd,CompilerPrinciples,96,(1)构造NFA,CompilerPrinciples,97,(2)确定化,CompilerPrinciples,98,定义5.9 :LR(0)项目集规范族 识别文法G活前缀的DFA项目集的全体称为文法G的LR(0)项目集规范族。 例文法GS: (0)SA (1) AaA|b 的LR(0)项目集规范族C为： C=(S A，AaA，Ab AaA，AaA，Ab AbS AAaA),99,方法二： 通过构造LR(0)项目集规范族来构造DFA的方法。 步骤： a. 构造文法G的拓广文法G: 引进一个新的初态S VN=VNS , VT=VT , P=PSS b. 定义项目集I的闭包CLOSURE(I): .I的任何项目都属于CLOSURE(I)； .若AB属于CLOSURE(I)，那么，对任何关于B的产生式B，项目B也属于CLOSURE(I)； .重复执行上述步骤直至CLOSURE(I)不再增大为止；,100,练习： S aS|b，设I=SS 则closure(I)= SS, SaS, Sb,101,c. 定义状态转换函数GO: 对于项目集I和文法符号X(VNVT),GO(I,X)=CLOSURE(J), 其中: J=任何形如AX的项目AXI 例题： S aS|b，I=SS closure(I)=SS, SaS, Sb 则GO(I,a) =closure（ Sa S =Sa S， SaS, Sb,102,d. 通过闭包和状态转换函数，求出G的LR(0)项目集规范族： 算法: itemsets(G) C= closure ( SS ); /C初始化 do if ( 对C的每个项目集 I 和每个文法符号X,若GO(I, X) 非空且不在C中) 把GO(I, X) 加入C中; while (没有更多的项目可以加入C); e.由项目集规范族画出识别文法所有活前缀的DFA,基本项目,总结：构造识别活前缀的DFA方法二,步骤： a. 构造文法G的拓广文法G: 引进一个新的初态S b. 定义项目集I的闭包CLOSURE(I) c. 定义状态转换函数GO d. 通过闭包和状态转换函数，求出G的LR(0)项目集规范族 e.由项目集规范族画出识别文法所有活前缀的DFA,103,104,S aS|b，I=SS，利用算法构造识别文法GS所有活前缀的DFA I0=closure(I) =SS, SaS, Sb GO(I0,S) =closure（ S S ） =S S =I1 GO(I0,a) =closure（ Sa S) =Sa S， SaS, Sb=I2 GO(I0,b) =closure（ Sb ） =Sb =I3 GO(I1,S) = GO(I1,a) = GO(I1,b) = GO(I2,S) =closure（ Sa S ） = Sa S =I4 GO(I2,a) =I2 GO(I2,b) =I3 GO(I3,S) = GO(I3,a) = GO(I3,b) = GO(I4,S) = GO(I4,a) = GO(I4,b) =,LR(0)项目集规范族: C=I0,I1,I2,I3,I4,105,I0: S S SaS Sb,I3:Sb ,I2:SaS SaS Sb,S,a,b,S,I1:SS,I4:SaS,a,b,CompilerPrinciples,106,6.LR(0)文法的定义： 若一个文法G的拓广文法G的活前缀识别自动机中的每个状态不存在下述情况： a.既含移进项目又含归约项目； b.含有多个归约项目 则称G是一个LR(0)文法 LR(0)文法规范族的每个项目集不包含任何冲突项目。,107,7.LR(0)分析表的构造： 通过DFA来构造LR(0)分析表 项目集Ik的下标k作为分析器的状态。 令含有SS的项目集Ik的下标k作为初态。 构造子表Action、Goto： .若项目Aa Ik且GO(Ik,a)=Ij,aVT,则置Actionk,a为“把(j,a)移进栈”，简记为“sj”； .若项目A Ik，那么对任意aVT(或#)，置Actionk,a为“用产生式A进行归约”，简记为 “rj”；(设A是文法G的第j个产生式),108,7.LR(0)分析表的构造（续）： .若项目SS Ik，则置Actionk,#为“接受”，简记为“acc”； .若GO(Ik,A)=Ij，AVN,则Gotok,A=j； .分析表中凡不能用上述4规则填入信息的空白格均置“报错标志”；,例题:,设文法: SS