编译原理第五章自顶向下语法分析方法.doc

第五章 自顶向下语法分析方法 课前索引 【课前思考】　　为了了解自顶向下（自上而下）分析的一般过程和问题，请学员首先回顾在文法和语言一章中介绍的有关基本概念：　　◇ 句子、句型和语言的定义是什么？　　◇ 什么叫最左推导？　　◇ 什么叫最右推导和规范推导？　　◇ 什么叫确定的自顶向下语法分析？　　◇ 自顶向下语法分析是从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的推导。　　◇ 确定的自顶向下语法分析中用的是哪种推导？　　◇ 在确定的自顶向下语法分析过程中，当以同一个非终结符为左部的产生式有多个不同右部时，如何选择用哪个产生式的右部替换当前的非终结符？　　◇ 确定的自顶向下语法分析对文法有何限制？ 【学习目标】　　确定的自顶向下分析方法虽对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。要求学员通过本章的学习后达到以下要求：　　◇ 能够对一个给定的文法判断是否是LL(1)文法；　　◇ 能构造预测分析表；　　◇ 能用预测分析方法判断给定的输入符号串是否是该文法的句子；　　◇ 能对某些非LL(1)文法做等价变换：　　　① 消除左递归　　　② 提取左公共因子　　可能会变成LL(1)文法。这样可扩大自顶向下分析方法的应用。 【学习指南】　　确定的自顶向下分析由于实现方法简单、直观、便于手工构造，因此，仍是目前常用的语法分析方法之一，尤其对小型编译器的实现较为适合。对初学编译技术的学员也较容易入门。确定的自顶向下分析要求文法是LL(1)的，所以，能否用确定的自顶向下分析方法构造语法分析器，首先必须对所给文法进行判断。由此构造 LL(1) 分析器的关键问题是对文法的LL(1)判别。而判断 LL(1)文法时用到文法符号串的开始符号集合（FIRST集）和非终结符的后跟符号集合（FOLLOW集）的计算。本章的学习要求学员对给定的文法能熟练、准确地计算出产生式右部符号串的开始符号集合和每个非终结符的后跟符号集合，只有这两个集合的元素计算准确无误，才能对LL(1)文法的判断得出正确结论，从而正确构造LL(1)分析表。对非LL(1)文法的等价变换特别要注意的是：消除了左递归、提取了左公共因子后不一定就能满足LL(1)文法的条件。 【难 重 点】　　语法分析是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序)，目前语法分析常用的方法有自顶向下（自上而下）分析和自底向上（自下而上）分析两大类。本章将主要介绍确定的自顶向下分析思想和对文法的要求。确定的自顶向下分析要求文法满足LL(1)文法。本章主要介绍内容为：　　◇ LL(1) 文法的定义和判别　　◇ 非LL(1)文法的等价变换　　◇ 确定的自顶向下分析方法　　◇ 递归子程序法（已在第2章应用本章不重复）　　◇ 预测分析方法重点:　　① LL(1)文法的定义和判别　　② 非LL(1)文法的等价变换　　③ 预测分析方法难点:　　对一个文法如何判断是否是LL(1)文法，由于在判断 LL(1)文法时用到文法符号串的开始符号集合（FIRST集）和非终结符后跟符号集合（FOLLOW集）的计算，而一般学员往往因概念不清或不够细心对这两个集合的计算常常出错，导致判断和分析结果的错误。 【知识结构】  语法分析是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序)，目前语法分析常用的方法有自顶向下（自上而下）分析和自底向上（自下而上）分析两大类。而自底向上分析又可分为算符优先分析和LR分析，这三种分析方法各有优缺点。但都是当今编译程序构造的实用方法，我们将在本章和第6、7章着重介绍它们的实现原理和技术。　　自顶向下分析法也称面向目标的分析方法，也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能推出，反之必然出错。自顶向下分析法又可分为确定的和不确定的两种，确定的分析方法需对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。不确定的方法即带回溯的分析方法，这种方法实际上是一种穷举的试探方法，因此效率低，代价高，因而极少使用，本章不做详细介绍。 为了了解自顶向下（自上而下）分析的一般过程和问题我们首先回顾在“文法和语言”一章中介绍的关于句子、句型和语言的定义及什么叫最左推导、最右推导和规范推导的基本概念。在确定的自顶向下语法分析中用的是最左推导。句型、句子、语言的定义句型:　　有文法G [S]， 若S x，且x∈ V*则称x是文法G [S]的句型。　　符号