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

新工科建设·计算机类系列教材;6;;语法分析是编译过程的核心部分。

-----在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。;;;例:文法G[S]:S?ABA?abB?cd|cBd

判断abccdd是否是句子。

(1)自顶向下构造语法树

S

AB

abcBd

cd;;例:G[E]:E?E+T|T

T?T*F|F

F?(E)|i

则:First(E+T)={(,i}

First(T)={(,i}

First(T*F)={(,i};2.Follow集(向前看集);3.Select集(可选集);例:对于G[E]

select(E?E+T)=First(E+T)={(,i}

select(E?T)=First(T)={(,i}

select(T?T*F)=First(T*F)={(,i}

select(T?F)=First(F)={(,i}

select(F?(E))=First((E))={(}

select(F?i)=First(i)={i}

;例:G[S]:

S?aBc|bB

B?bB|d|ε

Select(B?ε)=Follow(B)={#,c};;分析时可能出现:

(1)回溯

(2)死循环,在没有对当前输入符号匹配就进入处

理S的过程，无法确定什么时候才用S?b替换,

造成死循环.

解决方法:

文法的实用限制(算法6)

消除左递归

扩充的BNF表示法;2.回溯问题;首先:对每条规则A?β,

First(β)β≠ε

求Select(A?β)=

Follow(A)β=ε

当β≠ε时,对于当前输入符号a,若

a∈First(β)

则可选A?β进行推导,但A有n个候选式,

∴分两种情况.;(1)首符号不同;(2)首符号相同;例:U?αx1|αx2|x3|…|xn

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

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

采用U?αV|x3|…|xn

V?x1|x2;例:G[S]:

S?ifBthenS1elseS2|ifBthenS1

改为:

S?ifBthenS1T

T?elseS2|ε;;;例:

G[E]:E?T|EAT

T?F|TMF

F?(E)|i分析符号串i+i*i

A?+|-

M?*|/

;;;;;;2.LL(1)语法分析表的生成;分几种情况:

1)当x1∈VN，由y1选择相应规则替换x1

2)当x1∈VT,若x1=y1≠#,则说明x1与y1匹配,分别删去x1,y1,继续分析.

若x1≠y1,则说明不匹配，进行出错处理

3)若x1=y1=#,说明全部匹配,分析成功.

LL(1)分析程序见P77--78;例:G[A]:A?aBc

B?bB|eB|d

分析abbdc#

设计文法的分析表:

;;(2)LL(1)语法分析表的构造;构造LL(1)分析表的算法如下:;;例:G’[A]:A?aBc

B?bB|eB|d

先求各规则的select集

Select(A?aBc)={a}

Select(B?bB)={b}

Select(B?eB)={e}

Select(B?d)={d}

且c不出现在任何规则右部的首部.;构造LL(1)分析表: