语法分析 编译原理.doc

语法分析————自上而下分析4.1语法分析——自上而下分析
内容语法分析的任务与分类自上而下分析面临的问题递归下降分析程序构造LL(1)分析法LL(1)分析法

句型,句子,句型,句子,语言的定义
句型句子
*x,有文法G则称x是文法G有文法G,若Sx,且x∈VT*,则称x是文法G的句子.的句子.*x,有文法G则称x是文法G有文法G,若Sx,且x∈V*,则称x是文法G的句型.句型.

例:G:S→0S1,S→01S→0S1,S0S100S11000S11100001111

上下文无关文法的句型的推导上下文无关文法的句型的推导的句型的
最左(最右)推导:最左(最右)推导:在推导的任何一步αβ,其中α,β是句型,都是对α中其中α是句型,都是对α的最左(的最左(右)非终结符进行替换最右推导被称为规范推导.最右推导被称为规范推导.由规范推导所得的句型称为规范句型

句型的分析
句型分析就是识别一个符号串是否为某文法
的句型,是某个推导的构造过程.的句型,是某个推导的构造过程.在语言的编译实现中,在语言的编译实现中,把完成句型分析的程序称为分析程序或识别程序.分析算法又称识别算法.从左到右的分析算法,即总是从左到右地识别输入符号串,别输入符号串,首先识别符号串中的最左符进而依次识别右边的一个符号.号,进而依次识别右边的一个符号.

语法分析的任务:
L(对任一给定w∈VT*,判断w∈L(G)?语法分析器:按照产生式规则,做识别w语法分析器:按照产生式规则,做识别w的工作

源程序

单词符号

词法分析器

取下一个单词符号

语法分析器

语法分析

编译程序后续部分

符号表

语法分析器在编译程序中的地位

语法分析算法分类语法分析算法分类
分析算法分类:分析算法分类:

自上而下分析法(自顶向下):自上而下分析法(自顶向下)
从文法的开始符号出发,反复使用各种产生从文法的开始符号出发,寻找与输入符号匹配的最左推导.最左推导式,寻找与输入符号匹配的最左推导.自下而上分析法(自底向上):自下而上分析法(自底向上)从输入符号串开始,逐步进行归约(最右推从输入符号串开始,逐步进行归约(最右推导的逆过程),直至归约到文法的开始符号.),直至归约到文法的开始符号导的逆过程),直至归约到文法的开始符号.

语法分析方法综述:语法分析方法综述:递归子程序自顶向下预测分析(LL(分析器)预测分析(LL(1)分析器)(LL算符优先自底向上LR(0),SLR(1),LR(1),LALR(LR(0),SLR(1),LR(1),LALR(1)

自上而下语法分析的一般过程

从文法的开始符号出发,反复使用各种产生式,从文法的开始符号出发,反复使用各种产生式,寻找与输入符号匹配的最左推导.最左推导与输入符号匹配的最左推导.如果能够推导出,则该输入串是给定文法的句子;如果不能推导出,则该输入串不是给定文法的句子.

主旨:从文法开始符号出发,自上而下的为输主旨:从文法开始符号出发,自上而下的为输入串建立一棵语法树.入串建立一棵语法树.

自顶向下语法分析要解决的关键问题
假定要被代换的最左非终结符号是B且有n假定要被代换的最左非终结符号是B,且有n条规则:条规则:B→A1|A2|…|An,那么如何确定用|A哪个右部去替代B哪个右部去替代B?
例1:文法G(S):S→pA文法G(S):G(S)S→qBA→cAdA→a输入串W=pccadd

SpApcAdpccAddpccadd

相应的语法树:相应的语法树:
SPAPAcAdSPSAPSA

S→pAS→qBA→cAdA→aW=pccadd

cAdcAd

cAdcAda

文法G(S):S→pA文法G(S):G(S)A→cAd该文法的特点:该文法的特点:

S→qBA→a

(1)每个产生式的右部都由终结符号开始;每个产生式的右部都由终结符号开始;终结符号开始如果两个产生式有相同的左部,(2)如果两个产生式有相同的左部,则它们的右部由不同的终结符开始.不同的终结符开始的右部由不同的终结符开始.对于这样的文法,对于这样的文法,其推导过程可以根据当前的输入符号决定选择哪个产生式往下推导,因此,输入符号决定选择哪个产生式往下推导,因此,分析过程是唯一确定唯一确定的分析过程是唯一确定的.

文法G:文法G:S—>cAd

A—>ab

A—>a

输入串w输入串w:cad
S

IP
cAad

分析过程:分析过程:
)报告失败,撤销A43)IP—>'a'A的子报告失败,撤销IP———d;d;2)α=cA输入串;1)wA;输入串;回到A;树,回到——输入串扩展,第一式ab,A扩展,第一式ab,IP—IP—IP—与IP—IP''IP—>指针回退到IP