文法与语法分析(中).ppt

第04章 文法与语法分析,主要内容： 语法分析概述 文法 进行语法分析的几种方法 语法错误处理,4.5 自底向上分析LR分析概述,自底向上分析的思想和主要问题 几种LR分析方法： LR(0) SLR(1) LR(1) LALR(1),主要内容：,LR的几个基本概念 识别归约活前缀的识别器 LR(0)分析算法 SLR(1)分析算法,4.5.1 LR的几个基本概念,短语：设S是文法的开始符，是句型(即有S *），如果满足条件： S * A A + 则称是句型的一个短语。 直接短语（简单短语）：如果满足条件： S * A A 则称是句型的一个简单短语。 句柄：一个句型可能有多个简单短语，其中最左的简单短语称之为句柄。,句型:(E)*i+F 短语: 1.(E)*i+F 2.(E)*i 3.(E) 4. i 5. F 简单短语： (E),i,F 句柄：(E),例：,作业： 书 Page129 习题 7、8 文法GE: E T | E + T T F | T * F F ( E ) | i i (1) *i (2) +i (3)是G的一个句子， （1）画出该句子的语法分析树 （2）给出该句子的所有短语，简单短语，句柄,4.5.2 活前缀,规范推导：即最右推导。 规范归约：即最左归约。 规范句型：用最右推导导出的句型(也称右句型）。 规范前缀：若存在规范句型，且是终极符串或空串，则称为规范前缀。 活前缀：对个规范前缀，如果： 1 不含简单短语（移入型活前缀） 或 2 含一个简单短语，但其后没有符号（归约型活前缀） 则称规范前缀为活前缀；它表示符号栈中的内容，即输入串中已被分析过的部分。,例：S aAcBe 1 A b 2 A Ab 3 B d 4 输入流：abbcde。 规范推导过程为：,逆过程:(分析栈，输入流) ( -, abbcde) (a,bbcde) /a为移入活前缀 (ab,bcde) /ab为归约活前缀 (aA,bcde) /aA为移入活前缀 (aAb,cde) /aAb为归约活前缀 (aA,cde) /aA为移入活前缀 (aAc,de) /aAc为移入活前缀 (aAcd,e) /aAcd为归约活前缀 (aAcB,e) /aAcB为移入活前缀 (aAcBe,-)/aAcBe为归约活前缀 (S,-) /S为规范前缀,S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1,4.5.3 归约活前缀识别器-LR(0)自动机,LR(0)归约活前缀定理：简称派生定理，设增广产生式为0SS，则定理内容如下： 1 S0是LR(0)归约活前缀。 2 若Ap是LR(0)归约活前缀，且 qA是产生式，则q也是LR(0) 归约活前缀。,例，设文法GS: 1 S aAc 2 A Abb 3 A b,求归约活前缀集如下： aAc1 aAbb2 /因为SaAc1 aAbb2c1 ab3 /因为SaAc1 ab3c1 以上结果见上图。,PA自动机：假设产生式1ZA，则可构造如下Z产生式自动机，并记为PA(Z)。 GA自动机：假设给定文法G的一组PA自动机：PA(A1),PA(An)，则按如下方法构造的自动机称为G文法自动机，记为GA(G). 1 将PA(S)的初始状态作为GA(G)的初始状态； 2 连接各PA自动机； 3 把原所有PA(Ai)的终止状态作为GA(G)的终止状态。,例，设文法GS: 1 Z A 2 A aAa 3 A b,解：PA自动机见右上图；GA自动机见左下图，其确定化后见右下图：,LR(0)项目：若A是产生式，则称A为LR(0)项目(简称项目），也写作p形式。 项目集的投影：假设SS是LR(0)项目集，则称下面nextstates(SS,X)为SS关于X的投影集： nextstates(SS,X)=AX|AXSS, X(VTVN) 项目集的闭包：假设IS是LR(0)项目集，则称下面CLOSURE(IS)为IS的闭包集： CLOSURE(IS)= IS A |BACLOSURE(IS) AG,例：假设GS: S , DaA, AaB, ABa, B b，求close(DaA) 。 解： close(DaA) =DaA, AaB, ABa, Bb,LR(0)项目表示法：有三种模式：A（产生式模式）、p（归约号模式）、p,i（坐标型模式）。 project函数：假设给定项目集IS，则： project(IS,X)=AX|AXIS 它表示IS中“”后符号为X的项目集。 shift函数：假设给定项目集IS，则： shift(IS)=AX|AXIS 它表示IS中“”右移一位所得的项目集。 goto函数：假设给定项目集IS，则： goto(IS,X)=close(shift(project(IS,X) 它表示IS状态的X输出边所指向状态的项目集闭包。,例：Gs:EE+T, ET, T T *P, TP , Pid , P (E),LR(0)状态机的构造,1初始化：ss0=close(ZS); AllStateSet=ss0; UnHandledStateSet=ss0; 2判断结束：若UnHandledStateSet空，则结束，否则转3； 3从UnHandledStateSet选择一个状态ss，并做对每个符号a 做下面动作： 1) 求ss1 = goto(ss,a)，若ss1空，则TTss,a=空； 2) 否则，检查在AllStateSet中有无ss1; 若无，则把ss1追加到UnHandledStateSet和 AllStateSet中，并构造ss(a)ss1； 否则，构造ss(a)ss1； 4从UnHandledStateSet中删除状态ss，并转向步骤2。,例1：文法G： S E E aA|bB A cA|d B cB|d,文法G： S E E aA|bB A cA|d B cB|d,文法G： S E E aA|bB A cA|d B cB|d,文法G： S E E aA|bB A cA|d B cB|d,文法G： S E E aA|bB A cA|d B cB|d,例2：构造LR(0)状态机 S E E E + T E T T id T ( E ),Gs:S E ，E E + T ， E T ， T id ， T ( E ),LR(0)_DFA局限性： 1）它是一归约活前缀的接受器，而不是文法句子的接受器； 2）只靠LR(0)_DFA不足以进行LR分析。 例：文法：0SS 1SbA 2ScA 3Aa,注：在状太3中，当a归约到A时，存在两种可能，不好选择。,作业： 文法定义如下： Z S S (S) S | 构造该文法的LR(0)状态机，要求不含有空输出边。,LR分析模型,LR分析器的组成：1）LR分析器；2）分析表；3）分析栈。 LR分析器的构造： 1、构造识别文法活前缀的确定有限自动机； 2、根据该自动机构造相应的分析表(ACTION表、GOTO表),4.5.4 LR(0)文法及其分析算法,LR(0)文法：如果文法中每个状态都没有冲突，而且不依赖于输入符号。 LR(0)_DFA中的状态： 1 移入状态： 2 归约状态： p 3 初始状态： 移入项目：形如 Aap 的项目； 归约项目：形如 Ap 的项目； 接受项目：形如 ZSp 的项目。,n,n,LR(0)分析表的内容,Action矩阵：行代表状态，列代表输入符（终极符），而矩阵元素则表示相应的分析动作： Shift j / Reduce P / Accept / Error Goto矩阵：行代表状态，而列则代表语法符号（非终极符），而矩阵元素则表示归约后的转向状态。,LR(0)分析表的构造方法：,Action表 Action(S,a)= Shift j 当S有到Sj的a输出边 Action(S,a)= Reduce p .当S是p-归约状态 Action(S,#)= Accept 当S是接受状态 Action(S,a)= Error .其他情形 GOTO表 Goto(S,A)= S 当S有到S的A输出边，A为非终极符,文法G： (0) S E (1) E aA (2) E bB (3) A cA (4) A d (5) B cB (6) B d,移入动作：设Sit的ai输入边所指向的状态为S*,归约动作：设按AXk+1Xk+2Xt进行归约，则首先归约为A,Sik的A输出边所指向的状态设为S*，则格局变为：,设当前格局是：,LR(0)分析器的工作过程,LR(0)驱动程序,Void LR(0)_Driver(void) push(S0) ；read(a)； L：S = LR(0)_action(stack(top),a); switch ( S ) case Error : error()； case Accept : accept()； case Shift j : Push(Sj); read(a); goto L; case Reduce p : Pop(|P|)； S = LR(0)_goto(stack(top),Ap)； Push(S); goto L; ,文法G： (0) S E (1) E aA (2) E bB (3) A cA (4) A d (5) B cB (6) B d,表4.4 对输入串bccd的LR(0)分析过程,注：ACTIONS,a=Sj，则移进； ACTIONS,a= rj，则归约； GOTOS,A=j，则j进栈； ACTIONS,a=acc ，则成功。,LR(0)分析器的工作过程,作业：已知文法G： Z aAc1 A bB 2 | ba3 B dB 4 | e 5 构造文法的LR(0)状态机，Action表和 goto表，并给出符号串abdec的LR(0) 分析过程。,4.5.5 SLR(1)文法及其分析算法,LR(0)局限性： 1）LR(0)方法对文法的要求严格。 2）LR(0)方法容易出现冲突状态。 LR(0)受限原因：它要求每个状态只做一种分析动作，而且不考虑输入流信息。 SLR(1)特点：使用LR(0)_DFA，但在归约时查看后继符号。,如果某个状态有如下项目集： A , B , Dd ，则存在着归约-归约，归约-移入冲突 解决方法： 若，当前输入符Follow(A)，则用A 归约； 若，当前输入符Follow(B)，则用B 归约； 若，当前输入符=d，则移入。,SLR(1)分析条件,若存在着状态： A1 1 ，An n ， B11a1r1 ，Bnnanrn 则要求： Follow(A1)Follow(An)a1,an=,SLR(1)分析表的构造方法：,Action表 Action(S,a)= Shift j 当S有到Sj的a输出边 Action(S,a)= Reduce p .当S是p-归约状态， 且aFollow(Ap) Action(S,#)= Accept 当S是接受状态 Action(S,a)= Error .其他情形 GOTO表 Goto(S,A)= S 当S有到S的A输出边，A为非终极符,例:文法GE:,SE # 1 EE + T 2 ET 3 TT P 4 TP 5 Pid 6 P( E ) 7,图4.5.24 SLR(1)_DFA（注：状态7和11有LR(0)冲突）,1 SE # 2 EE + T 3 ET 4 TT P 5 TP 6 Pid 7 P( E ) Follow(S)=# Follow(E)=+,),# Follow(T)=+,*,),# Follow(P)=+,*,),#,见P102图4.5.5.3,SLR(1)分析表,SLR(1)驱动程序,Void SLR_Driver(void) /同LR(0)算法一样 push(S0) ；read(a)； L：S = SLR_action(stack(top),a); switch ( S ) case Error : error()； case Accept : accept()； case Shift j : Push(Sj); read(a); goto L; case Reduce p : Pop(|P|)； S = SLR_goto(stack(top),Ap)； Push(S); goto L; ,1 SE # ，2 EE + T ，3 ET ， 4 TT P 5 TP ，6 Pid ，7 P( E ),分析栈 符号栈 输入串 动作 转向 0 # id id+id# S5 0,5 # id id+id# R6 4 0,4 #P id+id# R5 7 0,7 #T id+id# S8 0,7,8 #T id+id# S5 0,7,8,5 #Tid +id# R6 9 0,7,8,9 #TP +id# R4 7 0,7 #T +id# R3 1 0,1 #E +id# S3 0,1,