三下-编译原理

第5章自底向上的自顶向下(TopDown)的分析自底向上(BottomUp)的分析1PAGEPAGE7自底向上分 文法为 句子分析句子分析 abbcd回忆几个概短语如果Ｓ*αAβandA+γ，则称γ是句型αγβ的相对于直接(简单)如果Ｓ*αAβandAγ，则称γ是句型αγβ的相对于变量A的直接(简单)短语(immediatephrase)句柄回忆几个概规范归设α为文法G的句子，如①α=αnαn-每个i(1<i≤n)，αi-1是将句型αi中的句则称序列αn，...，α1为α的规范归约语法分析树的生成再演——SA

A

B abbcdeB→d A→bbA→Ab

是什么关

abbcde

B→dd A→b A→Ab d

栈内容特点：不含当前句型栈内容特点：不含当前句型的句柄后的任何符

栈+栈+输入缓冲区剩余=#当前“句?栈中内分析设想——分析器框控制分析进程，输出分析结果——产生式序保存输入符号(token)保存语法符号——已经处理的部分结果(前缀栈栈内容+输入缓冲区内容＝前“句型”#栈内不含当前句型的句柄后的任何符分析控制分析控制程栈输入缓冲区(符号序列idid+id＊id控制程栈内容+输入缓冲区内容＝前“句型”#栈内不含当前句型的句柄后的任何符分析设想——系统运开始格栈：#；输入栈压入栈移进归约正常结束格#S，输入缓冲区系系统如何发现句柄已经在栈顶E→idE→(E)E→E+E→EE→idE→(E)E→E+E→E*EEE→E→idEE→E→idE→E→E*EE→E+ 例分析过程动 输入缓冲初始 移 归约 移 移 归约 移 移 归约 归约 归约

Eid1

E→idE→E→idE→E→E+E→E*E id2E

EEE id3分析器的四种动移进：将下一输入符号移入接受：分析成出错：出错处回回头想想——决定移进和归约的依据是什编译原(Principlesof 讲：上次课主要内+T语法+T记的语法符号可以看 0T3边，表示处理程序对0T36ε6作上次课主要内**0T3ε6E7F7F T(E)上次课主要内递归子程序上次课主要内自底向上的分“句柄”是否在栈顶形上次课主要内系统框

控制程id+控制程

例分析过程动 输入缓冲初始 移 归约 移 移 归约 移 移 归约 归约 归约E→E+E

Eid1

EEE→idE→E→EEE→idE→E→E+E→E*

EEE id3

移进归约分析中的问第6步#E+id2据E→id对id2归约之 移第7步可以移进移 也可以按产生式E→E+E归归 移进归约分析中的问归约归约存在两个可用的产生AabbcAabbcdeAabbcd不同分析方法处理方法不如何识别句柄利用

根据归约的先后次序为句型中相邻的符号规定优先关a1…ai-1≮ai≡ai+1≡…≡aj-状态

E→idE→(E)E→E+E→E*句柄是否形成=例如：E→E+E 等待归约出 等待移进 等待归约出 句柄已经形成，归约出新的 算符优先分析算术表达式分析的启算符优先关系的直观意 +的优先级低于 的优先级等于+ +(左边)的优先级高于+(右边方算术表达式文法的再分句型句型的特征(E+E)*(E-这些算符之间存在优先算符文如果文法G=(V,T,P,S)中不存在形的产生式，则称之为算符文法(OGOperator即：如果文法G中不存在具有相邻非终结符算符间的优先关间(a，b在后)的优先关系如下a≡bA→…ab…∈Pa≮bA→…aB…∈P且(B+b…或者a≯bA→…Bb…∈P且(B+…a或者算符优先文对OGG=(V，T，P，S)，如果a,b∈T,a≡b,a≮b,a≯b至多有一个成立，则称之为算符优先文法(OPG—OperatorPrecedenceGrammar)在无ε产生式的算符文法中，如果任意两个终结符之间至多有一种优先关系，则称为算符优先文法存在优先+≮存在优先+≮*id≯+≮id≯+≯*≯↑≯*id≯*#≮≯E→E+｜E-｜E*｜E/｜｜(E｜例直观的算符优先

≮≮➢➢≮≮≮➢➢≮≮≮得到这张表≯≯≮≮≮

≮≮≮ 算符优先关系的确优先关系的确a≮bB→…aA…∈P且(A+b…或者需求出非终结符A派生出的a≯bB→…Ab…∈P且(A+…a或者需求出非终结符A派生出的最后一个终结符构成的集对于OGG=(V,T,P,S)，定FIRSTOP(A)={b|A+b…或者LASTOP(Ab|A+…b或者求FIRSTOP和初值(扫描所有产生式ifA→a…∈P或A→Ba…∈P

ifA→…a∈P或AaB迭代(扫描所有产生式

ifA→B…∈P

将FIRSTOP(B)ifA→…B∈Pthen将LASTOP(B)设设计程序：求FIRSTOP、E→E+T|E-T|TT→T*F|T/F|F量量E+ - id / * )E+-id/* )/*F()F())*id/*T具体)*id/*T算符优先关系的确如果A→…ab；A→…aBb…，如果则对如果则对算符优先关系表的构造如果XiXi+1∈TT则如果XiXi+1Xi+2∈TVT则如果XiXi+1∈TV则如果XiXi+1∈VT则a∈LASTOP(Xi)，E→E+T|E-T|TT→T*F|T/F|F语法变 +,-,*,/,(, +,-,*,/,), *,/,(, *,/,), (, ),

≯≯≮≮≮

id

id

E→E+T|E-例分E→E+T|E-#≮id≯+id*id#≮F+≮id≯*id#≮F+≮F*≮id#≮F+≮F*≮id≯#≮F+≮F*F#≮F+≮F*F≯#≮F+T≯#E问有时未归约真正的句柄不是严格最左归归约的符号串有时与产生式右部仍能正确识别句子的原OP未定义非终结符之间的优先关系，不能识别由单一非终结符组成的句柄算符优先分析过程识别的“句柄”为最短(LPP：LeftmostPrime素短语与最短素短语(Primeγ是短语：S*αAβandγ至少含一个终结且不含更小的含终结符的短称γ是句型αγβ的相对于变量A的素短E→E+T|TT→T*F|F 句型F+T*F+id的短语有 T*F为最短语，是

归约的对 F+T*F EEEEEEEEEEid+E*id+文法间句型”的 素短语与最短设句型的一般形#N1a1N2a2…Nnan#(Ni∈V∪{ε},ai它的最短语是满足下列条件的最左子NiaiNi+1ai+1…Njaj其中：ai-ai≡ai+1≡…≡aj-1≡aj编译原(Principlesof 讲：上次课主要内基本动作——移进、归约、接受、出处移进归归约归上次课主要内优先a1…ai-1≮ai≡ai+1≡…≡aj-根据优先级比较的结果决定移近、归上次课主要内算符优先文优先关系的定a≡bA→…ab…∈Pa≮bA→…aB…∈P且(B+b…或者a≯bA→…Bb…∈P且(B+…a或者上次课主要内算符优先文法(OPG)a≡b，a≮b，a≯b至对每个语法变量求FIRSTOP和ifA→a…∈P或A→Ba…∈PthenifA→…a∈P或A→…aBthenifA→B…∈PthenFIRSTOP(B)放入ifA→…B∈PthenLASTOP(B)放入上次课主要内对顺序Xi≡Xi+1/Xi≡Xi+2(Xi+1是变量Xi+1是变量 aXi是变量 a算符的栈内/外优先级比上次课主要内被归约对#N1a1N2a2…NiaiNi+1ai+1…NjajNj+1aj+1…Nnan其中：ai-ai≡ai+1≡…≡aj-1≡aj最短素短语：短语、含终极符、最算符优先函算符优先分析算原理：识别句柄并归a1…ai-1≮ai≡ai+1≡…≡aj-首先利用≯找到“句柄”尾，再回头利≮比较栈顶和下一输入符号的关系，如果是找到后弹出“句柄”，归约为非终结符算符优先分析的系统组移进归约分析器+优先关系分析算法参照输入串、优先关系表，完成一系列归约，生成语法分析树——输出产生id+id*id的分析过id+id*id和运算符栈？是否有更简单的比较优先级的

E→idE→idE→E→E*E→E+算符优先函f(a)<g(b)，如果af(a)=g(b)，如果af(a)>g(b)，如果a优点：节省空间(n2→2n)便于执行比较运如：id≯id不存在，但f(id)与g(id)算符优先函例E→E+E|E-ffg+21-21*43/43↑45(05)60构造优先函数的算法不是唯一aT{#},建立两个结点fa和a，b 若ab或者ab则从fa至gb 若ab或者a≡b则从gb至fa画一条弧若图中无环，则存在优先函f(a)和g(b)等于从fa和gb+*#+≮≯≯≯≮≯≯*≮≯≯≯#≮≮≮+*#f4240g5130优

算符优先分析法优缺缺习题P2116、9.1、练习：给出布尔表达式的文法，构造其算优先关系BE→BEorBT|BT→BTandBF|BF→notBP→(BE)|true|算符优先分析法的改进必须是算符优先文法：文法书写限制 如何根据希望设计分析文能否利用产生式去分析的“进程”——LR(Left-Right)例

S→

(ε-)闭(ε-)闭添加S'→S：S'→.S(分析开始，S'→S.(分析成功5.35.3LR(Left-Right)LR(k)分析从语言的文法描述入手，探讨当前“规范L：从左R：最右推导对应的最左归约k：超前读入k个符号，以确定归约用的产为语法分析器的自动生成提供了基文法G=(V,T,P,S)的(Augmented)文G'=(V∪{S'},T,P∪{S'→S},S'),S'→.S，例(续

接受项S待约项B

例 (3)形如A→α.β形如A→α.β项目刻画了分析进展式式

归约项 a一、基本概念一、基本概念——LR(0)项例 移进(Shift)待约(Reducing)项目 归约(Reduce)项目项目A→X1…Xi-1.Xi…Xn表示分析进展程B

B (3)

b

abbab

Ba 规范族项目集规范族项目集(ε-闭包(ε-闭包形如A→α.β的形如A→α.β的项目集合

(2) (3)Ba一、基本概念——项目集闭项目集I的闭包算法：求J=J∪{B→.γ|A→α.Bβ∈J,untilJ不再扩例例 b项 Kernel

例(0)(1)b

(2) (3)

二二、LR(0)分析LR(0)、LR(0)、、LR(1)、动作表转移表ab#SB01212536456

an

#………Xm-#………Xm-………Sm-

四、四、LR分析器主控程序(LR分析算法开始时分析栈中为和开始状态0，置输入指针ip指向w#的第一个符号……… ０#转移动作LR主控程态并并 输 动作说0#bab##bab#0#Bab##Bab##Bab##Bab##BaB##BaB#

babbab的分析过程#BB##BB#0 # #(s0s1…sm(s0s1…sm，#X1X2…Xm,初始情况：初始a1a2…an

一般情况：当前s0s1… #X ifaction[sm,aisj(shiftj)then格局变s0s1…sm 当前格当前格 ifaction[sm,airj(reducej)then表示用第j个产s0s1…sm-#X1…Xm-kＢ再查goto表，当goto[sm-k,Ｂ]=jthen格局变s0s1…sm-k#X1…Xm-kＢifaction[sm,ai]=accthen分析成s是栈顶状态aipifaction[s,a]=si(shifti)使ip指向下一符号{把符号a和状态使ip指向下一符号elseifaction[s,a]=rj(reduceA→β){2*|β|把A和goto[s',A]先后压入栈中；输出产生式A→β}elseifaction[s,a]=acc 输 动作说0#bab##bab#0#Bab##Bab##Bab##Bab#

bab的分析过程中栈内容的#BB##BB#0#BaB#goto(3,B)=6#BaB#

# #(Canonical(CanonicalSentential六、栈内规范句型六、栈内…………

LR主控程

转移转移动作 (Canonical(CanonicalSentential规范句型的不含句柄右侧任意符号的缀称为规范句型的活前缀(Active例：idid*id的分析句型Eid*id和EE*活前 活前S*rmαAwrm (Canonical(CanonicalSentential换角度理活前缀与句柄的包含句柄： 项目集I的闭包七、LR(0)分析表的构造项目集I的闭包

b

a

Iε-闭

表达表达式文法的处文法

I I

F

F→(.E

F→

)

项目

闭

后继项目(SuccessiveA→α.Xβ的后继项目是七、后继项目(SuccessiveA→α.Xβ的后继项目是

b

a

I

a编译原(Principlesof 讲：LR分析思用LR分析思用形如A→α.β的项目构成状LR(0)项目分移进项目待约项目：S→b.BB归约项目:文法上次课

过项目“展开 I 4b项

IKernel

上次课主要内动作表转移表ab#SB01212536456转移：goto………Xm-………Sm-

上次课主要内 LR主控程

转移转移动作分析过

活前七、LR(0)分析表的构造——闭包之间的转闭包之间的转

b

a

I

aI I

F

F→(.E

F→

规范

)七、LR(0)分析表的构计算LR(0)项目集规范族C(分析器状态集合设文法G=(V，T，P，S) 文法称C为G'的LR(0)项目集规范族(Canonical七、LR(0)分析表的构——计算LR(0)项目集规范族C(分析器状态集合C:={closure({S'→.S})};forI∈C，ifgo(I,X)≠Φ&go(I,X)CuntilC不变 表达式文法的项目集规C={{E'→.E{E'→E.,→E.+T},{E→T.T→T.*F},{F→(.E{F→id.},{T→T*.F,F→.(E),F→.id},{F→ I I

F

F→(.E

F→

)七、LR(0)分析表的构造——识 法所有规范句型活前缀的 的所有规范句型活前缀的DFA:M=(C,V∪T,go,I0,I0=CLOSURE({S'思考如何在计算机中一个文法的LR(0项目集规范族最节省空间？如果某文法有这些产生式的右部的最大长度为，问：你所给出的方案需要的空间与n和m什么样的关系编译原(Principlesof 讲：上次课主要内分析器的运action[s,a]=si(shiftaction[s,a]=rj(reducebyproduct项目集闭CLOSURE(I)=I∪{B→.γ|A→α.Bβ∈I,后继项目:A→α.Xβ上次课主要内闭包之间的转移I0=CLOSURE({S'识别规范句型活前缀的M=(C,V∪T,go,I0,例按照LR(0)分析需求，分别构造识下列文法的所有规范句型活前缀 LR(0)方法能解决这个吗文法为

语法树 句子分析句子分析 abbcd句型活前缀的FA的状态转移图， 七、LR(0)分析表构0为开始状对ifA→α.aβ∈IiandifA→α.Bβ∈Iiand

thenaction[i,a]=sj;thengoto[i,B]=j;ifif

thenfora∈T∪{#}doaction[i,a]=rj;thenaction[i,#]=acc;所有空格置 I I

F

F→(.E

F→

(构造

)

状态+*()#ETF012312348235存在移693归789八、LR(0)不是总29项目集I的相归约-归约(Reduce/Reduce ):I中至移进-归约(Shift/Reduce I相容(Consistent):既无归约-归约，又无移进-归约I不相容I中有归约-归约或者移进-LR(0)文法：I∈C例例

0

I

I ab

I9: I7:I

0

I:

ab

如何构造分I9:

I7:动作表转移表abcd#SAB012311223644r6/765673859九、SLR(1)分析表0为开始状对ifA→α.aβ∈IiandifA→α.Bβ∈Iiand

thenaction[i,a]=sj;thengoto[i,B]=j;ifA→α.∈Iiif

thenforthen

cii,a]=j所有空格置例表达式文法的例表达式文法的SLR(1)分析(3)(4)(4)(5)(6)(6) I I

F

F→(.E

F→

)在状态2、9出 )该文法不是LR(0)文法

构造表达式文法的SLR分析(1)(1)(2)(3)(4)(5)(6)FOLLOW(E)={),+,#FOLLOW(T)={),+,#,*FOLLOW(F)={),+,#,* I I

F

*

IFOLLOW(E)={),+,# TT F→(.E

F→

)

状态状态+*()#ETF012312348235693789E),E),+,T),+,#,F),+,#,状态转移图SLR(1)分析的特描述能力强于LL(1SLR(1文法：SLR(1)分析表无SLR(1)分析的局限如果SLR(1)分析表仍有多重 约或归约-归约)，则说明该文法不是SLR(1)文法；说明仅使用LR(0项目集和FOLLOW集 =*

L→idSLR分析中的——更强的分析方I2={S→L.=R,R→L.输入符号为=时，出现了移进归约SL.=RI2且 action[2,=]=ShiftRLI2且=∈FOLLOW(R action[2,=]=ReduceR→要的信息

SS'→S.,#

S→.R

,=

R→.L

8'-L→.id,=

L→idII3

S→R.

*

L→.id

id I6''-II5'-L→id

L→idSLR(1)分析的基本步1、编写文法，求Follow2、求识别所有活前缀的3、构造SLR(1)分析Yacc(YETANOTHERCOMPILER'SCOMPILER)简%{%开始符词汇表：% n1,n2,…(自动定义种别码%tokenn1,i1(用户指定种别码%tokennh,ih(用户指定种别码类型说 其它说明%%规则部 给出文则的描%%程序部 扫描器和语义动作程输出：LALR(1)分析yylex(yylex({intwhile((c=getchar())==‘‘if(isdigit(c))yylval=c–while(isdigit(c=getcharyylval=yylval*10+(c-'0'ungetc(c,stdinretun} return}/*表达式计算%%token :expr‘\n'{printf(“\n”,;expr:expr‘+' {$$=$1+$3;|expr‘-' {$$=$1-$3;| /*$$=$1;term:term‘*' {$$=$1*$3;|term‘/' {$$=$1/$3;| /*$$=$1;factor:‘(‘espr {$$=$2;| /*$$=$1;基本框控制算基于LR分析表(动作和状态转移

P21212、S ABA| BaB|2、已知文法AaAd|aAb|，判断该文法是否