资源描述：
《编译原理——编译程序构造实践教程 教学课件 作者 张幸儿 戴新宇 401编译程序构造与实践教程第四章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第四章语法分析——自顶向下分析技术4.1自顶向下分析技术概况4.1.1讨论前提1.基本思想编译程序中进行语法分析的部分称为语法分析程序或称识别程序。语法分析程序在识别过程中，生成相应的内部中间表示，为编译程序的下一阶段语义分析工作作好准备。这内部中间表示可以是语法分析树，也可以是推导或其它形式的中间表示。当存在错误时，语法分析部分将给出报错信息。从语法分析树的角度看，自顶向下分析过程将以识别符号为根结点，试图向下构造语法分析树，其末端结点符号串正好与输入符号串相同。自顶向下识别过程是一个不断往语法分析树中添加分支的过程。因此，自顶向下分析过程是个推导的过程。2.讨论的
2、前提讨论的对象（输入）是符号串(中间表示形式)讨论是以上下文无关文法为基础分析过程从左到右逐个符号地进行因此，自顶向下句型分析的基础文法是上下文无关文法。3.输入与输出输入：词法分析程序的输出(属性字序列)输出：识别出是句子时，输出语法分析树或其他内部中间表示；出错时报错。4.1.2自顶向下分析技术要解决的基本问题当应用自顶向下分析技术进行句型分析时，在每一分析步，关于当前句型中的一个非终结符号进行展开。当关于非终结符号U展开时，对于U，往往可能存在若干个重写规则U∷=u1
3、u2
4、…
5、un因此，自顶向下分析技术要解决的基本问题是：在每一分析步，关于按其展开的非终结符号
6、U存在若干重写规则U∷=u1
7、u2
8、…
9、un时，如何确定替换U的ui(1≤i≤n)。作为分析技术，重要的是如何自动、机械地解决上述基本问题。为什么自顶向下分析技术可行？因为上下文无关文法与推导相关的特性。上下文无关文法与推导相关的一个特性：对于上下文无关文法，如果存在句型x=x1x2…xn，x1x2…xn=>*y则必存在y1、y2、…、yn，使得xi=>*yi(i=1,2,…,n)且y=y1y2…yn。Zx1x2xny=y1y2yn4.1.3自顶向下分析技术的实现思想与应用条件1.自顶向下分析技术的一般实现思想考虑最简单最基本的一种自顶向下分析技术，其基本思
10、想是：在自顶向下分析过程中每一步，将按U为目标进行展开，而关于U存在规则：U::=u1
11、u2
12、…
13、uk时，首先用U::=u1去尝试把U展开成u1。如果可行则继续，否则依次逐个尝试把U展开成u2或u3、…、或uk，直到某个ui(1ik)可行。下面以例说明之。例设有文法G[E]：E::=T+E
14、TT::=F
15、F*TF::=(E)
16、i假定输入符号串为i*i+i。分析过程如下所示。1E2T3+4E5F6*7T11T8i9F12F10i13i(f)1E1E1E1E1E2T3+4E2T3+4E2T3+4E2T3+4E2T3+4E5F5F5F5F6*7T5F6*7T6(7E8)
17、6i8i9F10i(a)(b)(c)(d)(e)从上述构造过程可见：1)每个分析步中关于U展开构造分支时，总是关于以U为左部的规则，从右部第一个选择开始，逐个尝试，试图构造分支；2)构造过程中，发现当前所选取的选择中某符号与相应输入符号不匹配时，立即剪去所作分支，甚至可能发现：先前认为是正确地构造的分支实际上是不正确的，需要把已构造的分支剪去，按规则的下一个选择重新构造分支。按推导生成的语法分析树及其存储表示1E2T3+4E5F6*7T11T8i9F12F10i13i结点序号目标父结点左兄结点右子结点1E0042T1073+1204E13115F2086*2507T2
18、698i5009F701010i90011T401212F1101313i1200(a)语法分析树(b)语法分析树存储表示按分析技术构造所得语法分析树及按推导所得语法分析树对照1E2T9+10E3F5*6T11T4i7F12F8i13i(a)按分析技术构造所得语法树(b)按推导构造所得语法树1E2T3+4E5F6*7T11T8i9F12F10i13i2.问题及其解决从上面的分析过程可见，上述的自顶向下分析技术是：面向目标的、试探的，因而带回溯的，因此称为带回溯的自顶向下分析技术。而且，语法分析树中结点的建立顺序，并不是按重写规则右部顺序生成，结点实际上按深度优先遍历顺
19、序生成。带回溯的自顶向下分析技术主要存在下列两个问题:1)效率问题回溯、查规则效率2)左递归问题左递归的存在使自顶向下分析过程永无止境。EE+TE+TE+T⋮解决方法：·消去回溯性使得对于任何U∈VN,U::=x1
20、x2
21、…
22、xn，如果xi=>*Tiv和xj=>*Tjw,且Ti,Tj∈VT,则Ti≠Tj,i≠j,(1≤i,j≤n)。·消去左递归使得既无规则左递归，也非文法左递归，即，不存在这样的非终结符号U，对于它有U∷=U…或U=>+U…消去了回溯的自顶向下分析技术称为无回溯的自顶向下分析技术。4.1.4消去左递归的文法等价变换概念：文法等价。1)
