编译原理简明教程（第3版）-课件 第5章 语法分析-自顶向下

新工科建设·计算机类系列教材

免费提供编译原理16目录第一章

概述第二章形式语言理论基础第三章自动机理论基础第四章词法分析第五章语法分析—自顶向下分析方法第六章语法分析—自底向上分析方法第七章语义分析及中间代码的生成第八章代码优化第九章目标代码的生成第十章符号表和出错处理第十一章

面向对象语言的编译第十二章

并行编译技术第十三章

并行编译技术25语法分析

----自顶向下分析方法学习目标自上而下语法分析的基本思想自上而下语法分析面临的问题及解决方法消除左递归的方法First集、Follow集、Select集的求法LL（1）分析方法递归子程序分析方法3语法分析是编译过程的核心部分。

-----在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析自顶向下如LL(k)，递归下降分析法等自底向上如LR(K)，简单优先分析法等4

目录5.1自顶向下语法分析技术5.2LL(K)语法分析方法5.3递归下降语法分析方法5.4本章小结55.1自顶向下语法分析技术

从文法的开始符号出发,向下推导,看能否推出待分析的符号串,如果能推出,说明该符号串是符合语言语法的句子,否则不是句子。61231.从文法的开始符号出发2.

向下推导3.推导出句子

5.1.1自顶向下语法分析思想例:文法G[S]:SABAab

Bcd|cBd判断abccdd是否是句子。(1)自顶向下构造语法树SABabcBdcd(2)推导SABAcBd

Accdd

abccdd75.1.2三种终结符号集1.First集(首符号集)

定义:文法G[S]:字汇表V,则符号串β的首符号集

First(β)={a|βay,a∈VT,y∈V*}特别,若β=ε,则First(β)=Φ*例：G[S]：SApSBqAa|cAFirst(dB)={d}Bb|dBFirst(Ap)={a,c}First(Bq)={b,d}8例:G[E]:EE+T|TTT*F|FF(E)|i则:First(E+T)={(,i}First(T)={(,i}First(T*F)={(,i}First(F)={(,i}First((E))={(}First(i)={i}92.Follow集(向前看集)定义:文法G[S],非终结符号U的向前看集

Follow(U)={a|S

…Ua…,a∈VTU{#}}

特别,当a=ε时,视U后面的符号为”#”****∵E

E,E

E+T,E

(E)∴Follow(E)={#,+,)}Follow(T)={#,+,*,)}Follow(F)={#,+,*,)}103.Select集(可选集)定义:文法G[S],有规则A

β

则该规则的可选集为:11例:对于G[E]select(EE+T)=First(E+T)={(,i}select(ET)=First(T)={(,i}select(TT*F)=First(T*F)={(,i}select(TF)=First(F)={(,i}select(F(E))=First((E))={(}select(Fi)=First(i)={i}12例:G[S]:SaBc|bBBbB|d|εSelect(Bε)=Follow(B)={#,c}135.1.3自顶向下语法分析难点1.左递归问题例:G[S]:

SSa|b

分析baaSS

S

S

S

SbSaSaSaSaSa

bSaSaSab…14分析时可能出现:

(1)回溯

(2)死循环,在没有对当前输入符号匹配就进入处理S的过程，无法确定什么时候才用Sb替换,

造成死循环.解决方法:

文法的实用限制(算法6)消除左递归扩充的BNF表示法152.回溯问题

在分析中，假定被代换的最左非终结符A存在n条规则,Ax1|x2|…|xn，难以确定采用哪个规则，若从x1到xn逐个来试,则效率太低。A的候选式:x1,x2,…xn

在自顶向下分析过程中，对候选式的选择可根据当前输入符号来决定.16首先:对每条规则A

β,

First(β)β≠ε求Select(Aβ)=

Follow(A)β=ε当β≠ε时,对于当前输入符号a,若

a∈First(β)则可选Aβ进行推导,但A有n个候选式,∴分两种情况.17

(1)首符号不同例:G[A]:AaB|bA

BbaA|c

{First(aB)={a}}∩{First(bA)={b}}=Φ{First(baA)={b}}∩{First(c)={c}}=Φ

分析符号串bbabaacAbA

bbA

bbaB

bbabaA

bbabaaB

bbabaacFirst(xi)∩First(xj)=Φ(i≠j)若a∈First(xk),则选用Axk来推导18

(2)首符号相同即对于A

αx1|αx2...|αxn改为A

α(x1|x2...|xn)进一步A

αBBx1|x2...|xn

First(xi)∩First(xj)≠Φ(i≠j)解决方法:“左提左因子”修改文法19例:U

αx1|αx2|x3|…|xn

且First(xi)∩First(xj)=Φ,(i,j≥3,i≠j)

First(xi)≠α,(i=3,4,…n)

采用

UαV|x3|…|xn

Vx1|x220例:G[S]:SifBthenS1elseS2|ifBthenS1

改为:

SifBthenS1TTelseS2|ε215.1.4确定的自顶向下语法分析思想22不确定的自顶向下分析思想例:G[S]:SxAy

Aab|a

分析xay是否句子

SxAy

a(3)SxAy

(1)SxAy

ab(2)分析过程:(1)(2)(1)(3)出现回溯.23例:

G[E]:ET|EATTF|TMFF(E)|i分析符号串i+i*iA+|-M*|/24推导:E

T

F

i

T

TMF

FMF

iMF

i*F

i*i

EAT

EAF

TAF

FAF

i+i

TAT

i+T

i+TMF

i+i*i

++推导过程是一个不断试探的过程,出现回溯现象，所以又称带回溯的自顶向下分析方法(效率低，代价高)原因:推导过程中有多个侯选式可供选择.255.2LL(K)语法分析方法

LL(k)是一种确定的自顶向下分析法:扫描输入串,同时从文法的识别符号开始产生句子的最左推导,每一步推导时向前看k个符号,以确定当前应选规则.k=1,即LL(1),简单易懂,应用较多.265.2.1LL(1)语法分析思想例:

G[S]:SaBc|bB

BbB|d

对句子abbdc进行分析.

从左到右扫描abbdc,对照规则，对第一个字符a,只能用

SaBc,第二个符号b,只能用BbB

SaB

cbB

bB

d

由此,LL(1)的基本思想就是根据输入串的当前符号唯一确定所选规则进行推导.

abbBcabbdcSaBc

abBc275.2.2LL(1)语法分析方法的逻辑结构a1a2a3…ai…am#输入串

控制程序分析表分析器x1x2….xn#分析栈输入串a1a2a3…am#,以定界符”#”作为结尾分析表:M[A,a](A为栈中元素,a为输入字符285.2.3LL(1)语法分析方法1.LL(1)文法

对于文法G[S],其每个非终结符的不同规则具有不相交的select集.即对于Ux1|x2|…|xn,有select(Uxi)∩select(Uxj)=Φ,(i≠j)292.LL(1)语法分析表的生成LL(1)分析过程当前句型的右端部分x1x2…xm#(xi∈V)待分析串的右端部分y1y2…yn#(yi∈VT)

x1x2…xm#305.2.3LL(1)分析方法分几种情况:1)当x1∈VN，由y1选择相应规则替换x12)当x1∈VT,若x1=y1≠#,则说明x1与y1匹配,分别删去x1,y1,继续分析.

若x1≠

y1,则说明不匹配，进行出错处理3)若x1=y1=#,说明全部匹配,分析成功.LL(1)分析程序见P77--78315.2.3LL(1)分析方法例:G[A]:AaBc

BbB|eB|d

分析abbdc#设计文法的分析表:

abcdeAAaBcBBbBBdBeB325.2.3LL(1)分析方法分析栈输入符号产生式匹配删除#A abbdc##cBa abbdc# AaBc#cB bbdc#a#cBb bbdc# BbB#cB bdc#b#cBb bdc# BbB#cB dc#b#cd dc# Bd#c c#d# #c33(1)LL(1)分析器工作过程(2)LL(1)语法分析表的构造

LL(1)分析表反映分析栈中元素与输入串中元素的匹配关系.记M[A,a]几个约定:

C:继续读入下一字符

R:重读当前字符RE(β):用β的逆串替换栈顶符号.34构造LL(1)分析表的算法如下:35

36例:G’[A]:AaBc

BbB|eB|d先求各规则的select集Select(AaBc)={a}Select(BbB)={b}Select(BeB)={e}Select(Bd)={d}且c不出现在任何规则右部的首部.37构造LL(1)分析表:abcde#ABc#cB/CB/Cε/CB/Cε/Csucc38分析abbedc的过程分析栈余留输入串 动作#Aabbedc# cB/C#cBbbedc#B/C#cBbedc# B/C#cBedc# B/C#cBdc# ε/C

#cc# ε/C

## succ39例5－6表达式文法G[E]：E→EAT|TT→TMF|FF→(E)|iA→+|-M→*|/消除左递归求select集构造分析表分析符号串40例5－61.消除左递归41例5－62.求select集423.构造分析表434.分析符号串44例文法G[S]S

abB

A

SC|BAA|εVN={S,A,B,C}B

AbAVT={a,b,c}C

B|c45判断此文法是不是LL(1)文法:Select(SabB)={a}Select(ASC)={a}Select(ABAA)={a,b}Select(Aε)={a,b,#}Select(CB)={a,b}Select(Cc)={c}Selcet(BAbA)={a,b}

∴不是LL(1)文法。构造出的分析表含有多重定义。∩=Φ∩≠Φ46注：有些不是LL(1)文法的文法，经过修改（如左提左因子，消除左递归等）可化为LL(1)文法，但并不是所有的非LL(1)文法都能改造为LL(1)文法。47例对于文法G[Z]:

ZAU|BR

AaAU|b

BaBR|b

Uc

Rd

First(AU)∩First(BR)={a,b}≠Φ

所以，不是一个LL(1)文法

485.3递归下降语法分析方法5.3.1递归下降语法分析方法的实现思想是一种确定的自顶向下分析法。又称递归子程序分析法。思想：对文法中每个非终结符（代表语法成分）编写一个子程序（或递