高级程序设计语言编译原理--文法和语言与语法分析.pdf

第四讲文法和语言与语法分析1-上下文无关文法（LL文法和LR文法）与语法分析程序设计编铎廨理：锦：周密哌2回忆语法分析的任务是把词法分析的结果单词符 号审进一步分解成各类语法单位（语法范畴），并 分析它们之间的层次关系输出语法树。_声法分析器V单词符号串-由单词符号（终结符）和语法范畴,（语法变量或称非终结符）构成组成的语法树（语义分析的原始数据）（词法分析）（创建）编年原理：耕，周/顺 3、文法和形式语言的定义二、上下文无关文法及其语法树 三、两种语法分析思想的形成四、自上而下的语法分析方法五、自下而上的语法分析方法*六、语法分析器的自动产生编锦原理：褂：周嗡顺4文法和形式语言的定义回忆：程序语言的词法规则是可用表来 描述的，而在词法分析器的讨论和自动产生中,词法是用正规式来描述定义的。现在：程序语言的语法规则的定义和描 述用什么呢？-文法！编铎原理：讲：周市顺5文法与语言文法是描述语言语法结构的一组形式规则。即是定义符号串（程序）集合（语言）的工具。它 必须具备如下特点：准确又易于理解；由它定义形成的语言有利于句子分析和 翻译;通过它能自动产生有效的语法分析程序。编铎廨理：锦：周密哌6文法与语言W _（形式）语言：若LHE*则称L是上的一个形式|语言。其中，X是基本符号集（有限集），1 X*是工上基本符号串集（一般为无限集），例子：c语言是基本符号字母表上符号串集的子集合，每个c程序都是基本符号字母表上的符号串，是c语言中的一个元素。假定E=a,b,c则L1 二a,b,c,L2二a,aa,ab,L3=c,cc可表示字 V 母表上的三个不同的形式语言。这里描述语言的方法是用枚举法。/若E=a,b,E上的一个形式语言为E上所有可能的符号串集。即L二a,b,ab,ba,aa,bb,，此时用枚举法已经无法表示该语言了。编年原理：耕；周/顺7文法与语言文法（形式）定义：我们见四元式来作为描述一 个语言L的工具（会发生什么），用G表示。即Gm（Vt,Vn,P,S）其 中：Vt是终结符集合（有限集）一一单词符号集合即组成语言的不可再分的 基本符号。元素一般用小写英文字母表示。如常量、基本字等。Vn是非终结符集合（有限集）一一用来表示语法范畴的语法变量。往往 卜由它可以生成多个单词符号和其它非终结符等序列。元素一般用大写英文 1字母表示。如表达式、语句、分程序、过程等。VnnVt=（pS是文法开始符号Vn 特殊非终结符号，它必须至少在某个产生 式左端出现一次。它代表所定义语言中我们最终感兴趣语法范畴。P是产生式（规则式）集合（有限集）一一定义语法范畴的一种书写规则o 形式：xAyfxa y A eVn,x,y,a e（Vt U Vn）*某即关于 A 的一条产 生规则。编铎廨理：锦：周密哌8文法与语言例子：定义一个语法范畴，有时需要好几个产生式，有 时还需要含有递归的产生式。如定义一个算术表达式的产生式如下:G:E3iE3E+EE3E*EE3(E)人 语言元素i+i的推导过程-S 二 E 二E+E=E+i=i+i1 i 语法单位：i，i，E，E，E+E,E 其中：i代表单词符号即变量或常数，另十、*、(、)也是单词符号。+可见，文法定义了一个语言。记为L(G)=a|S=a,a Vt+,P编铎廨理：锦：周密哌9?假定=a,b,而上的一个形式语言L为上所 有可能的非空符号串集，则该语言L用文法G怎样来描述。答：G 三(Vt=a,b,Vn=A,S 三 A,P=A3a,A3b,A3Aa,A3Ab)贝L L=L(G)证：A=a|b|Aa|Ab=(a|b)|A(a|b)=(a|b)(a|b)*文法是定义语言的好工具：只要定义它含哪些语r法范畴(Vn),每个语法范畴所含语法单位之间的关系(P),还有基本单词符号集(Vt),最大的语法范畴是谁(S)。这 四元一定，则文法就定义了一个语言一一由S和P所能产 生出的终结符串集。记为L(G)。即+L(G)=a|S=a,a Vt*P编锌廨理：锦：周密哌10文法性质类型与语言1 一个文法G,若P中任一产生式形如A3a,有、AVn,a（VnUVt）+（或。（VnU Vt）*）,贝iJG为（扩充）上下文无关文法。（2型）,一个文法G,若P中任一产生式形如Afa B或A3a 有A,BGVn,a evt+,贝ijG为正规文法。.（3 型）一个文法G,若P中任-产生式形如a Ap y PV 有丫 e（VnUVt）+,a,p （VnUVt）*,仅S 例外,但此时S不得出现F在任何产生式右部。则G为上下文有关文法。（1型）1 一个文法G,若P中任一产生式形如a fB有Q，B （VnUVt）*且。嗨即母制非终轴符，贝1JG为短语文法。（0型文法性质类型与语言 1型文法G的另种等价定义:若P中任一产生式形如a*有。E(VnUVt)+,p E(Vn U Vt)*,且|a|E+E=E+i=i+iE9(E)|i语法单位:i，i，E，E，E+E,E推导、句型、句子和语言直接推导：x=y 如：E+E=E+iG 用一次规则式，替换一个非终结符如：E+E=i+i 推导：x=yG 用若干次规则式，替换若干个非终结符如：E+E=E+Ej义推导：x二二二二y.G 不用(x=y)或用若干次规则式4 R 如：E=E+E=E+最右推导：x=y(规范推导)G 每次替换x中最右边的非终结符编铎廨理：锦：周密哌13 句型：若有开始符S=x的广义推导，贝卜为G的句型。G 句子：若有开始符S=x且*丫/,贝Ijx为G的句子。G 语言：L=x|S=x且xVt*,则L为G描述的语言。G 文法的等价：若L(G1)=L(G2),则G1三G2。正规文法与正规式的等价：若L(G)=L(A),则G三A o 正规文法与自动机的等价：若L(G)=L(M),则G三M o编铎廨理：锦：周密哌14、上下文无关文法及其语法树文法的递归性、规范句型、短语与句柄 直接左(右)递归：G中有产生式形如A今A(A.A)左(右)递归、递归A=-=A(A=-=A)递归A=-=A 规范句型：由开始符号可用最右推导得到的句型。编年原理：耕；周/顺15 规范句型：由开始符号可用最右推导得到的句型。E=(E)=(E+E)=(i+E)=(i+i)不是最右推导E=(E)=(E+E)=(E+i)=(i+i)是最右推导后者每个句型均为规范句型。短语：设G,S且xuy是一句型，并有UVn,使得S=xUy=xuy u (Vn U Vt)+,x,y (Vn U Vt)*,G G则称子串u是句型xuy的短语。编铎廨理：耕，周帝顺16 短语：设G,S且xuy是一句型，并有UVn,使得 东+S=xUy=xuy u (Vn U Vt)x,y (Vn U Vt)*,Q Q则称子串U是句型xuy的短语。直接短语：设G,S且xuy是一句型，并有UVn,使 得 S=xUy=xuy u (Vn U Vt)x,y (Vn U Vt)*,Q Q广 则称子串U是句型xuy的直接短语(简单短语)。句柄：一个句型中最左边的直接短语称为句柄。编年原理：耕；周/顺17?给出文法G，中句子(i*i+i)*i的规范 推导过程。并求句型P*(T+i)+i的所有简单 短语和句柄。GT P)T+时E T iE T P编锌廨理：褂：周市顺18语义的二义性:句子的二义性:若该句子有两个不同的规范推导,则称此句子为二义的。例如：（i+i*i）E=（E）=（E+E）=（E+E*E）=（E+E*i）=（E+i*i）=（i+i*i）E=（E）=（E*E）=（E*i）=（E+E*i）=（E+i*i）=（i+i*i）文法的二义性：若该文法中有二义的句子，则称 此文法为二义的。语言的二义性：若所有描述该语言的文法都具有 二义，则称此语言是二义的。注意：二义性是不可判别的。编锌廨理：锦：周密哌19A=BaD=bBaD=bbaD=bbaBaD=bbaBad=bbabad推导过程的语法树-生长树 语法树的性质和有关结论:编铎廨理：锦：周密哌20bbabad=bBabad=Babad=BaBad=BaBaD=BaDBaD=BaBaD=BaBad=Babad=bBabad=bbabad用对语法树的剪枝法和语法树性质构造上述例子中句子bbabad 的规范推导。编年原理：耕；周/顺22一、两种语法分析思想的形成从构造一个句子的规范推导的过程和生长一棵句子 i的语法树的过程可得对一个句子的语法分析方法。I 自上而下的方法一一试长语法树（规范推导）：从开始 I符号起，根据已知终结符号串，试着去选择产生式，用其右部 代替最右边的非终结符号，最后得到的一个句子，若该句子与 已知串相同，则合符语法，否则，我们“可小伏，”不合语法O 自下而上的方法一一归约句柄法（剪枝）:假定一个终 结符号串是一个句子，每次归约它的句柄，最终若为文法开始 符号，则我们的假定是正确的。即该终结符号串合符语法，否 则，我们“可应伏，不合语法。编锌原理饼，尚有喉23几个结论1.自下而上语法分析法是规范推导的逆过程即规范归约（最左归约），其关键是找每个句型的句柄。若找到即可归约成某个非终结符，再继续下去 最后能归约到开始符号则句子正确。自上而下语法分析是规范推导（最右推导）的过程，其关键是选择用来推 导的产生式。最后能推导出所要分析的句子则该句子正确。2.一个语言可以有不同的文法描述3.为了对句子的语法结构进行确定的可行性分析，只考虑也只需考虑 规范推导或最左推导。4.对于一个程序语言来说，为了对每个语句的分析是唯一的，常希望 描述它的文法是无二义的。但是二义文法并非坏事，在一定条件下，可以控 制和驾驭。5.可以证明二义性问题是不可判定的。6.。型语言1型语言2型语言3型语言，但文法：短语文法（上下文有关文法（上下文无关文法（正规文法短语文法（扩充上下文无关文法（上下文无关文法上下文有关文法（不一定扩充上下文无关文法编年原理：耕；周/顺24四、自上而下的语法分析方法递归下降子程序分析法先对文法加以改造，使分析能正常进行。步骤：(I)文法变换之一-消除直接、间接左递归(P89有算法)(II)文法变换之二-提取直接、间接左因子 Head(。)的概念定义：c(VtIJVn)+Head(a)=a|a-aVT 想要发现G中的左因子，可以这样去考察：若Afaja21a3口%则考察Head(ai)ClHeadQj 尸？=(p(iJ=1,2,再 且堵)只要不空就提取它(即进行文法变换)，直至新文法关于非终结符A的产生式有 Head(a)ClHead(p户 为止。(III)产生式的递归子程序问题用Follow(R)来解决Follow(R)的概念定义：(R e Vn)Follow(R)=a|ReVn,aeVT,S是文法开始符或Follow(R)=a|a是允许紧跟在R后面的终结符编铎廨理：锦：周密哌25递归下降子程序分析法递归子程序分析法的改进思想：(先举例看看)例：ABc|DE|s这样的人含产生式所对应的子程序设计。即从生长树上来看叶子A面临的输入符ch怎么办？处理方法：(算法)P(A)：begin if ch Head(Bc)then P(Bc)else*选择A9Bcif ch e Head(DE)then P(DE)else*选择AfDE if ch e Follow(A)then ERROR/*选择A消失 end下面只要解决Head(a)和Follow(R)集合的求法：编铎廨理：锦：周密哌26递归下降子程序分析法下面只要解决Head(a)和Follow(R)集合的求法：Head(a)=a|aa.VT a(VT U VN)+的求法:I)求每一个X VtU Vn 的 Head(X)若XVt 则XHead(X)若XVn且 X-a贝I a e Head(X)若XY.Y eVN 则把 Head(Y)力口入 Head(X)若X-Y1Y2Y3.Yn 且 丫1丫2丫3.*贝I把 Head(Yj+1)s加入 Head(X)。其中 j=lnJ 特别地，Y1Y2Y3YJfe贝I把同 加入Head(X)重复第步。II)再求Head(a)：ae(VTUVN)+若a 三 a.VT 则 a Head(a)若a 三 Y.YeVN 贝把 Head(Y)e加入 Head(a)若a三 丫1丫2丫3.丫”且丫1丫2丫3Yj贝Ll把 Head(Yj+1)s加入 Head(a)o 其中 j=l.n-l特别地，丫1丫2丫3.丫口*8则把加入Head(a)编铎廨理：锦：周密哌27递归下降子程序分析法下面只要解决Head(a)和Follow(R)集合的求法：Follow(R)=a|S3Ra.,ReVn,aeVT,S是开始符的求法:若R是开始符号，则#eFollow(R)(因为文法将扩展为S，-#R#)若Q-aRp a5pe(VTU VN)+RevN_a 不成立。则 Head(3)s加入Follow(R)若Q-aR 或 Q-aRp a9pe(VTUVN)+RVN且P*e。则应把 Follow(Q)加入 Follow(R)中。重复第步。注意：求Follow(R)要涉及求Head集合。例：考虑文法G，(E)：G，：E9TE，E+TEB T3FTT，f*FT，归 F-(E)|i(注意扩充文法S，-#e#)-FH的求出G:EE+T|TT3T*F|F(E)|i编锌廨理：锦：周密顺28 LL文法的定义与递归子程序分析法的改进（构造预测分析表）预测分析程序（递归子程序分析法的升华）LL(1)文法的定义：若文法G满足如下条件：无左递归。无公共左因子。即若Af。/0(2匕H n则Head(a )A Head(a j)=(p(i,j=l,2,n 且iW j)若 Afa Ja 2|a 3|.|a n 白贝!)Head(a )A Follow(R)=(p(i=l5 2,n)递归子程序的一般结构A-a Ja 2|a 3|.a n算法处理方法：P（A）：begin if ch if ch|e这样的产生式所对应的子程序设计。Head(a)then Head(a 2)thenP(a i)elseP(a 2)elseendif ifch ch Head(a n)then P(a n)else Follow(A)then ERROR编铎廨理：锦：周密哌29构造预测分析表算法1.对文法G的每个产生式A 3a执行第二步和第三步；2.对每个终结符a Head(a),把Afa加至A,a中，3.若Head(a),则对任何 b Follow(A)把 A 3a加至A,b中，4.把所有无定义的A,a标上“出错标志”。可以证明，一个文法G的预测分析表不含多重入口，当且仅当该文法是LLo预测分析算法及程序：(P94图5.11)LL(1)分析程序的自动构造-分析栈+LL(k)分析表+预测分析算法-LL(k)分析法分析栈#E 输入符 i+i*i#top fch LL(1)分析表(LL分析表的演变和优化)编锌廨理：褂：周密顺30预测分析算法：BEGIN 首先把中然后把文法开始符号推入栈；把第一个输入符号读进ch;FLAG：=TRUE；WHILE FLAG DOBEGIN把栈顶符号上托出去并放在X中；IF X e Vt THENIF X=ch THEN把下一个输入符号读进chELSE ERRORELSE IF THENIF X=ch THEN FLAG:=FALSE ELSE ERRORELSE IF X,ch=X-X1X2.XK THEN 把XX K_p.,X1推进栈ELSE ERROREND OF WHILE;STOP/*分析成功，过程完毕*/END编铎廨理：锦：周密哌31五、自下而上的语法分析方法寻找句柄，无一般方法，因此很困难。我们可以从描述语言的文法上考虑，用一些具有特殊性质（限制）的文法，它们既可描述该语言，而又好进行语法分析（如找 句柄）。前面曾说过我们研究文法的目的有二：一是描述语言，二 是进行语法分析和翻译。卜 算符文法与算符优先文法：当文法满足一定条件时，可用简单方法识别出句柄来，从而 法到归约分析的目的，算符优先文法就是这样的一种文法。算符文法：若一个文法G中，不含有如下形式的产生式：P+.RQ R,QeVn则称G为算符文法。编锌原理：耕；周/顺32算符文法的句型特点：算符文法的句型一定形如：（自证）F Ni/N2a2Nii Hn-Kn 其中 产丫1 VNU e 算符优先文法：若一个不含-产生式（形如P3e）的算符文1,法G中，任意两a,bEVT,至多只有下列关系中的一个：、a=b,ab,aba的优先级等同b a的优先级高于b a的优先级低于b 其中a二bWG中含有形如P）.ab 或P3aQb.产生式；.136中含有形如1）f.耻.产生式，而 R+）.a 或 R+3.aQ；abWG中含有形如P9.aR.产生式，而 R+f b.或 R+f Qb.；R,Q,P e VN则称这个文法G为算符优先文法。编锌原理饼，尚有喉33算符优先文法G中终结符之间有特定关系。如下表算符优ab.da=b d直观的算符优先关系表与算符优先分析法：(举例说明)，算术表达式文法G：E3#E#E 今 E+E|E*E|EAE|(E)|i其中F3#E#产生式是为了采用算符优先分析法而增加的一个约定产生式，“产为特殊终结符，作为句子的括号。根据日常算术运算的经验优先级，G的优先关系表如下:出ii,i(,(#,)i,)(,#)显然是不合法子串。编年原理：耕；周/顺34直观算符优先分析法：1)两个工作栈和一个字符变量：OPTR栈：OPND栈：a字符变量：2)算法：对于文法G,有OPTR栈底:=#;输入串尾:=#;OPND 栈:=空;START:READ(a);/读入当前符号进字符变量/IF a=i THEN BEGIN PUSH(a,OPND);GOTO START END;DO WHILE 0aBEGIN IF OPND 中操作数少于二个 THEN ERROR;X:=POP(OPND);PUSH(POP(OPND)OxQPND);O-POP(OPTR)END;CASE OF0=a:IF 6=(AND a=)THEN BEGIN POP(OPTR);GOTO START END;IF e=#AND a=#THENIF OPND中操作数有且只有一项 THEN WRITENCOK5)ELSE ERROR;0a:PUSH(a,OPTR);GOTO START;OTHERWISE:ERROR;ENDCASE编铎廨理：锦：周密哌35下面的问题就是构造算符优先关系表：I)求FirstVT(R)(算法书上Pl 12)II)求LastVT(R)(算法书上Pl 14)III)造分析表：=有形如Afab或AfaRb 有形如A3.Rb 则LastVT(R)b 算符优先关系表的查比效率：提高法一-优先函数 优先函数如果存在将有无穷多组。优先函数的叠代矩阵求法。编锌原理饼，尚有喉36寻找句柄的有效方法-LR(K)文法与识别活前缀的有限自 动机回忆：最右推导：在推导的任何一步其中a、p是句型，都是 对a中的最右非终结符进行替换，最右推导被称为规范推导。由规范推导所得的句型称为规范句型。GS：S-E EE+T|T T-(E)|int推导 S=E=T=(EA(E+D=(E+int)=(T+int 尸(int+int)规范归约：假定a是G6勺一个句子，称序列或1，口。是01的 一个规范归约。如果该序列满足：(1)an=a(2)a0为文法的开始符号(3)对任何j,0jQ 接受项目，形如S，S注息:A-g的LR(O)项目只有一个即A且是归约项目。编铎廨理：锦：周密哌39LR(O)项目集规范族的构造与识别活前缀的有限自动机(举例来说)G:EaA|bB AcA|d BcB|d项目集:(0)S，集.E E，aA Ef.bB A cA A6d B，cB B6 dS，3E.E3a.A Eb.B Ac.A A3d.Bc.B B3d.E3aA.E3bB.A3cA.B3cB.LR(O)项目集规范族算法：设C=10,Il,.In编年原理：耕；周/顺40LR(O)项目集规范族算法：设C=I。，1,.In)Procedure itemsets(G5);Be.in C:=CLOSURE(SfS)RepeatFor C中每一项目集I和每一文法符号x Doif G0(I,x)非空且不属于CThen把G0(I,x)放入C中Until C不再增大End;识别活前缀的有限自动机：（黑板演示）一次性构造识别活前缀的DFA。编铎廨理：锦：周密哌41 LR(0)分析表的构造(动作ACTION与转换函数GOTO)动作 ACTION：移进 记为si其中s表示移进，i表示移进后进入第i状态;归约记为rj其中r表示归约，j表示用第就j号产生式；接受记为acc报错转换函数GOTO:sj=GOTO(si,a)表示栈顶状态si面临符号a,转入sj状态。ACTIONGOTO状态aBcd#EAB0S2S311Acc2S5S643S8S974r 1r 1r 1r 1r 15S5S6106r4r4r4r4r47r2r2r2r2r28S8S9119r6r6r6r6r610r3r3r3r3r311r5r5r5r5r5编锌原理：锦：周密哌42 SLR(l)分析表的构造G(S):(0)SS(1)SrD(2)D-Di(3)DiLR(0)项目集规范族10:Sf.S13:Sr D.S r DDD.i11:S-S.14:D-i.12:Sr.D15:DDi.D.DiD.i其中13中含有移进/归约冲突,故文法不是LR(0)的，如何解决?由于FollownHead(p)=#n=，故SLR分析表：状态ACTIONGOTOri#SD0S211Acc2S433S5rl4r3r3r35r2r2r2注：发现 LR(0)项目 冲突时(移 进/归约、归约/归约),若用考虑 Follow(R)、Head(a)两两交均空 时，则得到 SLR(l)分析 法。即此时 的文法定是 SLR(1)文法编铎廨理：锦：周密哌43 LR(1)分析表的构造先考虑如下文法：G(S)：(0)SS S3BB B9aB B3b 随然此文法是LR(0)文法因为LR(0)项目集中无冲突项目,但用做1LR(1)、LALR(l)-LR同心项目集合并分析表构造的例子很简单状态ACTIONGOTOab#SB0S3S4121Acc2S6S753S3S484r3r35rl6S6S797R38r2r29r210:S6S#II:SS.#S3.BB#12:S3B.B#B.aBa/bB.aB#Bfba/bB.b#13:Ba.Ba/b16:B3a.B#BfAba/bB.Ab#Bfba/bB6b#14:Bb.a/b17:B3b.#18:BaB.a/b19:BaB.#15:SBB.#编年原理：耕；周/顺44 LR（1）分析表的构造置ip指向输入串w的第一个符号；令S为栈顶状态；a是ip指向的符号；重复beginif ACTION PS,al=Sj thenbegin PUSH j,a（进栈）;ip前进（指向下一输入符号）endelZTif ACTIONS,a.（第 j条产生式为Af似then be.in pop p 项；令当前栈顶状态为早;push GOTO S A和A（进栈）endelse if ACTIONs,a=acc then return（成功）else errorend,重复编铎廨理：锦：周密哌45 LR分析算法（如图）Input#1编铎廨理：锦：周密哌46六、语法分析器的 自动产生略!编铎廨理：锦：周密哌47习P166 2、题3、11、18编用廨理锦；周市哌48复习题一.形式语言与文法？文法与正规式在描述语言的上的特点？二.句型、短语、直接短语、句柄与分析树?二义句子、二义文法、二义语言之 关系三.语法树和两种语法分析思想？它们的关键在哪里？四.递归子程序的问题是什么？LL文法与预测分析法？LL(k)文法和方法类 似。五.预测分析表的作用及其“预测”的含义何在？六.LR(O)项目集规范族的含义?什么是归约项目、待约项目、移进项目和接受 项目？七.如何构造LR的识别活前缀确定的有限自动机?LR(k)文法和方法类似。八.什么叫YACC原语？YACC编译程序的作用如何？YACC程序的结构怎样？九.实习题语法分析程序的编写-一由文法构造递归下降语法分析源代码程序.十.文法LL、LR(O)、SLR(O)、SLR(l)、LALR和LR文法的相互之间 关系？它们与二义文法的关系？编铎廨理：锦：周密哌49第四讲讲究编铎廨理：讲:周市哌50愉快的学习整个学习过程将成为发现问题研究问题 分析问题机动灵活应用理论工具解决问 题到智能解决问题的科学研究过程。只要你有科学研究的态度并把上课看成 是探索讨论，轻松而注意力集中，应该 是非常能力的一种培养发展，对你有很 重要的意义。编铎廨理：锦：周密哌51算符优先关系表显然：ii,i（,（#，）i,x，#）是不合法子串。+*Ai()#+*A1(#=编铎廨理：锦：周密哌52预测分析算法框图编用原理：神：周市顺53