1、编译原理第 5章自顶向下语法分析方法 5.1 确定的自顶向下分析思想 5.2 LL(1)文法的判别 5.3 某些非 LL(1)文法到 LL(1)文法的等价变换 5.4 不确定的自顶向下分析思想 5.5 确定的自顶向下分析方法编译原理引言1、语法分析的地位 是编译程序的核心部分。2、语法分析的任务 识别由词法分析得出的单词序列是否是给定文法的句子。3、语法分析方法 自顶向下分析和自底向上分析 自顶向下分析包括确定分析和不确定分析 自底向上分析包括算符优先分析和 LR分析编译原理引言4、语法分析的方式1）自上而下语法分析 反复使用不同产生式进行推导以谋求与输入符号串相匹配。2）自下而上语法分析 对
2、输入符号串寻找不同产生式进行归约直到文法开始符号。注：这里所说的输入符号指词法分析所识别的单词编译原理引言 自顶向下分析法 ： 也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能推出，反之必然出错。 自顶向下分析法又可分为确定的和不确定的两种。 确定的分析方法需对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器。 不确定的方法即带回溯的分析方法，这种方法实际上是一种穷举的试探方法，因此效率低，代价高，因而极少使用。编译原理引言 回顾在 “文法和语言 ”一章中介绍的关于句子、句型和语言的定义及什么叫最左推导、最右推导和
3、规范推导的基本概念。 有文法 GS，若 S x，且 x V*则称 x是文法 G S的句型 。符号 表示经过 0步或若干步的推导。 有文法 GS，若 S x，且 x VT*， 则称 x是文法 G S的 句子 。例： GS： S0S1， S01可有推导 S 0S100S11000S111 00001111说明 00001111是 GS的句子。*编译原理引言 最左（最右）推导：在推导的任何一步 (其中 、 是句型 )，都是对 中的最左（右）非终结符进行替换。 最右推导被称为规范推导。 由规范推导所得的句型称为规范句型。 句型的分析 句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。
4、编译原理引言 句型分析的有关问题 如何选择使用哪个产生式进行推导？假定要被替换的最左非终结符号是 V， 且左部为 V的规则有 n条： VA1|A2|An， 那么如何确定用哪个右部去替换 V呢？ 如何识别可归约的串？在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中寻找一个子串，看它是否能归约到文法的某个非终结符号，该子串称为 “可归约串 ”。编译原理5.1 确定的自顶向下分析思想 例：若有文法 G1S:S pA |qB A cAd|a B d B |b 识别输入串 w= pccadd是否是 G1S的句子试探推导过程：S pA pcAd pccAdd pccadd编译原理5.1 确定的自顶向下分析思想 G1S: S pA |qB A cAd|a B d B |b 这个文法有以下两个特点： 每个产生式的右部都由终结符号开始。 如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。 对于这样的文法显然在推导过程中完全可以根据当前的输入符号决定选择哪个产生式往下推导，因此分析过程是唯一确定的。编译原理5.1 确定的自顶向下分析思想 若有文法 G2S:S Ap |Bq A a|cA B b|dB识别输入串 w=ccap是否是 G2S的句子，那么试探推出输入串的推导过程为 ：S Ap cAp ccAp ccap
