资源描述：
《语法分析编译原理》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、语法分析自上而下分析4」语法分析——自上而下分析内容语法分析的任务与分类自上而下分析面临的问题递归下降分析程序构造LL(1)分析法LL(1)分析法句型,句子，句型，句子，语言的定义句型句子*X,有文法G则称X是文法G有文法G,若Sx,且xWVT*,则称x是文法G的句子.的句子.*x,有文法G则称x是文法G有文法G,若Sx,且xWV*,则称x是文法G的句型句型.例:G:S—OS1,StO1S->OS1,S0S100S11000S11100001111上下文无关文法的句型的推导上下文无关文法的句型的推导的句型的最左（最右）推导：最左（最右）推导:在推导的任何
2、一步叩，其屮（X,卩是句型,都是对（X屮其屮（X是句型，都是对a的最左（的最左（右）非终结符进行替换最右推导被称为规范推导.最右推导被称为规范推导.由规范推导所得的旬型称为规范句型句型的分析句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程.的句型，是某个推导的构造过程.在语言的编译实现屮，在语言的编译实现中,把完成句型分析的程序称为分析程序或识别程序•分析算法乂称识别算法.从左到右的分析算法,即总是从左到右地识别输入符号串，别输入符号串，首先识别符号串中的最左符进而依次识别右边的一个符号.号,进而依次识别右边的一个符号.语法分析的任务：
3、L(对任一给定weVT*,判断weL(G)?语法分析器:按照产生式规则,做识别w语法分析器:按照产生式规则,做识别w的工作源程序单词符号词法分析器取下一个单词符号语法分析器语法分析编译程序后续部分符号表语法分析器在编译程序中的地位语法分析算法分类语法分析算法分类分析算法分类：分析算法分类：自上而下分析法（口顶向下）：自上而下分析法（自顶向下）从文法的开始符号出发，反复使用各种产生从文法的开始符号出发，寻找与输入符号匹配的最左推导.最左推导式,寻找与输入符号匹配的最左推导.自下而上分析法（自底向上）：自下而上分析法（自底向上）从输入符号串开始,逐步进行归约
4、（最右推从输入符号串开始，逐步进行归约（最右推导的逆过程），直至归约到文法的开始符号.）,直至归约到文法的开始符号导的逆过程），直至归约到文法的开始符号.语法分析方法综述：语法分析方法综述：递归子程序自顶向下预测分析(LL(分析器)预测分析(LL(1)分析器)(LL算符优先自底向上LR(O),SLR(1),LR(1),LALR(LR(O),SLR(1),LR(1),LALR(1)自上而下语法分析的一般过程从文法的开始符号出发，反复使用齐种产生式，从文法的开始符号岀发，反复使用各种产生式，寻找与输入符号匹配的最左推导.最左推导与输入符号匹配的最左推导•如果
5、能够推导出，则该输入串是给定文法的句了;如果不能推导出,则该输入串不是给定文法的句子.主旨:从文法开始符号出发，自上而下的为输主旨:从文法开始符号出发，自上而下的为输入串建立一•棵语法树.入串建立一棵语法树.11顶向下语法分析要解决的关键问题假定耍被代换的最左非终结符号是B且有n假定要被代换的最左非终结符号是B,且有n条规则：条规则:B^Al
6、A2
7、...
8、An,那么如何确定用
9、A哪个右部去替代B哪个右部去替代B?例1:文法G(S):S-pA文法G(S):G(S)S->qBA->cAdA^a输入串W=pccaddSpApcAdpccAddpccadd相应
10、的语法树：相应的语法树：SPAPAcAdSPSAPSAS—>pASfqBA—>cAdA—>aW=pccaddcAdcAdcAdcAda文法G(S):S—pA文法G(S):G(S)A—cAd该文法的特点：该文法的特点：S—qBA->a(1)每个产生式的右部都由终结符号开始；每个产生式的右部都由终结符号开始；终结符号开始如果两个产生式有和同的左部,(2)如果两个产生式有和同的左部,则它们的右部由不同的终结符开始.不同的终结符开始的右部由不同的终结符开始.对于这样的文法，对于这样的文法，其推导过程町以根据当前的输入符号决定选择哪个产生式往下推导,因此，输入符号
11、决定选择哪个产生式往下推导,因此，分析过程是唯一确定唯一确定的分析过程是唯一确定的.文法G:文法G:S—>cAdA一>abA一>a输入串w输入串w:cadSIPcAad分析过程：分析过程：)报告失败，撤销A43)IP—>'a'A的了报告失败，撤销IPd;d;2)a=cA输入串;l)wA;输入串;回到A;树，回到——输入串扩•展，第一式ab,A扩展,第一式ab,IP—IP—IP—与IP—IP''IP—>指针回退到IP'c'a指针回退到>—>c'';IP
12、—ab匹配匹配；IP—>'a'与ab匹配；述有替换式未试过
