语法分析-自上而下分析.ppt

《语法分析-自上而下分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第四章语法分析-自上而下分析第四章语法分析-自上而下分析4.1语法分析器的功能4.2自上而下分析面临的问题4.3LL(1)分析法•一、直接左递归的消除•二、提取左因子、消除回溯•三、LL(1)分析法4.4递归下降分析程序构造4.5LL(1)分析中的错误处理主要内容：7/25/20212中南大学软件学院陈志刚4.1语法分析器的功能语法分析是编译过程的核心部分。语法分析的任务：在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语言的语法结构用上下文无关文法描述。7/25/20213

2、中南大学软件学院陈志刚词法分析器符号表编译程序后续部分语法分析器源程序单词符号取下一单词符号语法分析树图4-1语法分析器在编译程序中的地位7/25/20214中南大学软件学院陈志刚语法分析器的功能：按照文法的产生式，识别输入符号串是否为一个句子。这里所说的输入串是指由单词符号（文法的终结符）组成的有限序列。关键：对一个文法，当给你一串（终结）符号时，怎样知道它是不是该文法的一个句子呢？这就要判断，看是否能从文法的开始符号出发推导出这个字符串。或者，从概念上讲，就是要建立一棵与输入串相匹配的语法分析树。7/

3、25/20215中南大学软件学院陈志刚语法分析的方法：自下而上分析法基本思想：从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；或者说，从语法树的末端开始，步步向上“归约”，直到根结。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。自上而下分析法基本思想：从文法的开始符号出发，根据文法的产生式规则正向推导出给定句子的一种方法；或者说，从树根开始，往下构造语法树，直到建立每个叶的分析方法。7/25/20216中南大学软件学院陈志刚4.2自上而下分析面临的问题顾名思义，自上而下就是从

4、文法的开始符号出发，向下推导，推出句子。带回溯的分析方法不带回溯的递归子程序（递归下降）分析方法自上而下分析的主旨：对任意输入串，试图用一切可能的办法，从文法开始符号（根结）出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。7/25/20217中南大学软件学院陈志刚这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。例4-1假定有文法：(1)S→xAy(2)A→**

5、*分析输入串x*y(记为)。7/25/20218中南大学软件学院陈志刚实现这种自上而下的带

6、回溯试探法的一个简单途径是让每个非终结符对应一个递归子程序。每个这种子程序可作为一个布尔过程。一旦发现它的某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回“真”值；否则，保持原来的语法树和IP值不变，并返回“假”值。7/25/20219中南大学软件学院陈志刚面临的问题：首先，是文法的左递归性问题。一个文法是含有左递归的，如果存在非终结符P含有左递归的文法将使上述的自上而下的分析过程陷入无限循环。即当试图用P去匹配输入串时，我们会发现，在没有识别任何输入符号的情况下，又得重新要求P去进行新的匹配。7

7、/25/202110中南大学软件学院陈志刚其次，由于回溯就碰到一大堆麻烦事情。如果我们走了一大段错路，最后必须回头，那么，就应把已经做的一大堆语义工作推倒重来。第三，在上述的自上而下分析过程中，当一个非终结符用某一个候选匹配成功时，这种成功可能仅是暂时的。第四，当最终报告分析不成功时，我们难于知道输入串中出错的确切位置。最后，由于带回溯的自上而下分析实际上采用了一种穷尽一切可能的试探法，因此效率很低，代价极高。7/25/202111中南大学软件学院陈志刚一、左递归的消除使用自顶向下的任何一种算法必须消除左

8、递归和提取公共左因子。1、直接左递归的消除若文法中有形如P→Pα的产生式，则称直接左递归，如A→Ab

9、a。设，有P→Pα

10、β，若α≠ε，β不以P开头（否则不可能消除左递归）。则改写为：可消除左递归。4.3LL(1)分析法7/25/202112中南大学软件学院陈志刚一般地，若αi≠ε，βj不以P开头，则可改写为：从而消除直接左递归。例：S→Sabc

11、Sab

12、ab消除直接左递归得：7/25/202113中南大学软件学院陈志刚2、完全消除左递归分析虽不含直接左递归，但所以含有左递归。如果文法G不含回路（），也不

13、含ε产生式，则下列算法可消除左递归（完全）①把G的非终结符按任意顺序排列成P1,…,Pn②fori:=1tondobeginforj:=1toi-1do把形如的规则改写成，其中；消除关于的直接左递归end;③化简由②得到的文法（取消无用非终结符产生式）7/25/202114中南大学软件学院陈志刚例：上述文法①排序：S,Q,R②循环：i=1时，处理S→Qc

14、c，消除直接左递归，不变i=2时，处理Q→Rb

15、b，j=1，把有关Q的产