《自底向上语法分析》PPT课件.ppt

《《自底向上语法分析》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章　自底向上语法分析明确自底向上语法分析的基本分析方法。掌握算符优先分析的方法,会使用算符优先分析法分析句子教学目标6.1自底向上分析法[<无符号整数>]<数字串><数字><数字串><数字>01<无符号整数>==><数字串><数字>==><数字串>0==>10<数字>0==><数字串>==>规范规约与规范推导互为逆过程G[<无符号整数>]<无符号整数>→<数字串><数字串>→<数字串><数字>

2、<数字><数字>→0

3、1

4、2

5、3

6、……

7、9【例6.1】G[S]:SaPcQePbPPbQd分析句子abbc

8、de#文法G[S]：(1)S→aPcQe(2)P→b(3)P→Pb(4)Q→dabbcde步骤符号栈输入符号串动作1）#abbcde#移进2）#abbcde#移进P3）#abbcde#归约(P→b)4）#aPbcde#移进P5）#aPbcde#归约(P→Pb)6）#aPcde#移进7）#aPcde#移进Q8）#aPcde#归约(Q→d)9）#aPcQe#移进11）#S#接受S10）#aPcQe#归约SaPcQeaPcdeaPbcdeabbcde从输入符号串开始，通过重复查找当前句型的“可归约串”并利用

9、有关规则进行规约若能规约为文法的识别符号,则表示分析成功,输入符号串是文法的合法句子,否则有语法错误.基本思想算符优先分析法LR分析法最左素短语句柄关键：找出当前句型的“可归约串x”给定文法G[S],δ为该文法的句型,若S==>Aδ,且A==>,则是句型δ相对于A的短语；若S==>Aδ,且A==>,则是句型δ相对于A的简单短语。**＋直观理解：短语就是某句型中的子串，这个子串是由某个非终结符通过至少一步推导得到的子串，而简单短语就是由某个非终结符通过一步推导得到的子串。1.短语和简单短语

10、从语法树找句型的短语和简单短语设A是句型αβδ的某一子树的根，其中β是形成此子树的末端结点的符号串，则β是短语。若这个子树只有一层分支（称简单子树），则β简单短语。例:文法G[E]E::=E+T

11、TT::=T*F

12、FF::=(E)

13、iETE+T+FiET求句型T+T+i的短语、简单短语短语：T+T+i,T+T,T,i简单短语：T,i设A是句型αβδ的某一子树的根，其中β是形成此子树的末端结点的符号串，则β是短语。若这个子树只有一层分支，则β是简单短语。任一句型的最左简单短语称为该句型的句柄。给定句型找句柄的步骤

14、：短语简单短语句柄注意：短语、简单短语是相对于句型而言，一个句型可能有多个短语、简单短语，句柄只能有一个。2.句柄ETE+T+FiET短语：T+T+i,T+T,T,i简单短语：T,i求句型T+T+i的句柄例:文法G[E]E::=E+T

15、TT::=T*F

16、FF::=(E)

17、i句柄：T素短语是一个短语,它至少包含有一个终结符号,并且除它自身以外不再包含其他素短语.其中最左边的素短语称为最左素短语。3.素短语ETE+T+FiET短语：T+T+i,T+T,T,i简单短语：T,i句柄：T素短语：T+T和i最左素短语：T+

18、T课堂练习：分别求句型E＋i、E+F的短语、简单短语、句柄、素短语、最左素短语ETF+iE短语：E+i,i简单短语：i句柄：i素短语：i最左素短语：i短语：E+F,F简单短语：F句柄：F素短语：E+F最左素短语：E+FETF+E例:文法G[E]E→E+T

19、TT→T*F

20、FF→(E)

21、iETE+T+TTF*FiE短语：T+T*F+i,T+T*F,T,T*F,i简单短语：T,T*F,i句柄：T素短语：T*F和i（因为T不包含终结符,T+T*F+i和T+T*F包含其他素短语）最左素短语：T*F例:文法G[E]E→E+

22、T

23、TT→T*F

24、FF→(E)

25、i【例6.2】求句型T+T*F+i的短语、简单短语、句柄、素短语、最左素短语6.2算符优先分析法一种经典的自底向上分析法,简单直观,适于表达式的分析仿照算术表达式的四则运算过程基本思想：将句型中的终结符当作“算符”，规定算符之间的优先关系，通过比较相邻算符的优先次序来确定句型的可归约串并进行归约。1.乘除的优先大于加减2.同优先级的运算符左大于右3.括号内的优先级大于括号外a1a2a3…ai…an#优先关系表总控程序X1…Xn-1Xn#分析器的逻辑结构：优先关系表、分析栈、总控程

26、序文法符号【例6.3】G[E]E∷=E+E

27、E*E

28、(E)

29、i优先关系的定义:设a,b为可能相邻的终结符定义:aba的优先级等于baba的优先级小于baba的优先级大于b不同于数学中的＝、＜、＞，不存在对称关系.＞＜..=优先关系表（算法的核心）E∷=E+E

30、E*E

31、(E)

32、i空白处表示这两个终结符不能相邻,故没优先关系算符优先文法算符文法的定义例若文法中无形如A→·¨BC·¨的规则，