第五章 自顶向下语法分析方法

《第五章 自顶向下语法分析方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章自顶向下语法分析方法课前思考为了了解自顶向下（自上而下）分析的一般过程和问题，首先回顾在“文法和语言”一章中介绍的有关基本概念：◇句子、句型和语言的定义是什么？◇什么叫最左推导？◇什么叫最右推导和规范推导？◇什么叫确定的自顶向下语法分析？◇自顶向下语法分析是从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的推导。◇确定的自顶向下语法分析中用的是哪种推导？◇在确定的自顶向下语法分析过程中，当以同一个非终结符为左部的产生式有多个不同右部时，如何选择用哪个产生式的右部替换当前的非终结符？◇确定的自顶向下语法分析对文法有何限制？

2、2021/6/112学习目标确定的自顶向下分析方法虽对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。要求通过本章的学习后达到以下要求：◇能够对一个给定的文法判断是否是LL(1)文法；◇能构造预测分析表；◇能用预测分析方法判断给定的输入符号串是否是该文法的句子；◇能对某些非LL(1)文法做等价变换：　①消除左递归　②提取左公共因子可能会变成LL(1)文法。这样可扩大自顶向下分析方法的应用。2021/6/113学习指南确定的自顶向下分析由于实现方法简单、直观、便于手工构造，因此，仍是目

3、前常用的语法分析方法之一，尤其对小型编译器的实现较为适合。对初学编译技术的学员也较容易入门。确定的自顶向下分析要求文法是LL(1)的，所以，能否用确定的自顶向下分析方法构造语法分析器，首先必须对所给文法进行判断。由此构造LL(1)分析器的关键问题是对文法的LL(1)判别。而判断LL(1)文法时用到文法符号串的开始符号集合（FIRST集）和非终结符的后跟符号集合（FOLLOW集）的计算。本章的学习要求学员对给定的文法能熟练、准确地计算出产生式右部符号串的开始符号集合和每个非终结符的后跟符号集合，只有这两个集合的元素计算准确无误，才能对LL(1)文法的判断得

4、出正确结论，从而正确构造LL(1)分析表。对非LL(1)文法的等价变换特别要注意的是：消除了左递归、提取了左公共因子后不一定就能满足LL(1)文法的条件。2021/6/114难重点语法分析是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序)，目前语法分析常用的方法有自顶向下（自上而下）分析和自底向上（自下而上）分析两大类。本章将主要介绍确定的自顶向下分析思想和对文法的要求。确定的自顶向下分析要求文法满足LL(1)文法。本章主要介绍内容为：◇LL(1)文法的定义和判别◇非LL(1)文法的等价变换◇确定

5、的自顶向下分析方法◇递归子程序法◇预测分析方法2021/6/1152021/6/116重点:①LL(1)文法的定义和判别　　②非LL(1)文法的等价变换　　③预测分析方法难点:对一个文法如何判断是否是LL(1)文法，由于在判断LL(1)文法时用到文法符号串的开始符号集合（FIRST集）和非终结符后跟符号集合（FOLLOW集）的计算，而往往因概念不清或不够细心对这两个集合的计算常常出错，导致判断和分析结果的错误。知识结构2021/6/117句型、句子、语言的定义句型:有文法G[S]，若Sx，且x∈V*则称x是文法G[S]的句型。符号表示经过0步或

6、若干步的推导。句子:有文法G[S]，若Sx，且x∈VT*，则称x是文法G[S]的句子。例：G[S]：S→0S1，S→01可有推导S0S100S11000S11100001111说明00001111是G[S]的句子。最左（最右）推导：在推导的任何一步(其中、是句型)，都是对中的最左（右）非终结符进行替换。最右推导被称为规范推导。由规范推导所得的句型称为规范句型。句型的分析句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。从左到右的分析算法，

7、即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号。分析算法分类：自上而下分析法：从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的最左推导。自下而上分析法：从输入符号串开始，逐步进行归约（最右推导的逆过程），直至归约到文法的开始符号。2021/6/119自上而下的语法分析自下而上的语法分析句型分析的有关问题①如何选择使用哪个产生式进行推导？假定要被替换的最左非终结符号是V，且左部为V的规则有n条：V→A1

8、A2

9、…

10、An，那么如何确定用哪个右部去替换V呢？②如何识别可归约的串？在自下而上的分析方法中

11、，在分析程序工作的每一步，都是从当前串中寻找一个子串，看它是否能归约到文法的某个