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

编译原理 第四章 语法分析—自上而下分析 共 NUMPAGES 28页第 PAGE 2页 DATE \@ yy-M-d 12-2-19 第四章 语法分析—自上而下分析 知识结构： 带回溯分析法 回溯 自上而下分析 面临的问题 左递归 问题的解决 语法分析－ 求FIRST、FOLLOW集合的算法 自上而下分析 LL(1)分析法 证明LL(1)文法 构造LL(1)分析表 递归子程序的构造思想 递归子程序法 递归子程序的特点 递归子程序的设计 第一节 语法分析综述 一、语法分析的任务 按照语言即定的语法规则，对字符串形式的源程序进行语法检查，并识别出相应的语法成分。即语法结构是否符合语法规则。 二、语法分析器在编译程序中的地位（一遍扫描） 语法分析器词法分析器源程序 单词符号 分析树 语法分析器 词法分析器 语义分析中间代码生成 语义分析 中间代码生成 取下一个单词 符号表 符号表 三、语法分析方法 通常把语法分析方法分为两大类，既自上而下分析与自下而上分析。 1、自上而下分析方法 实际上是一种产生的方法，分析过程是一个推导过程。 = 1 \* GB2 ⑴自上而下分析过程 从文法G的开始符号S出发，通过反复使用产生式，逐步推导出与输入的符号串完全相匹配的句子。采用最左推导，以文法开始符号为根结点，逐步为输入串自上而下地构造一棵语法树。 面临的输入符号为a，A所有的产生式： A??1 ??2 ? ? ??n = 1 \* GB3 ①若a?FISRT(?i)，则指派去执行匹配任务。 = 2 \* GB3 ②若a不属于任何一个候选首字符集，则： a、若 ? 属于某个FISRT(?i)且a?FOLLOW(A)，则让A与?自动匹配； b、否则，a的出现是一种错误。 例：设有文法G和输入符号串W：a*a+a G：S ? aA?a A ? BaA?? B ? +? -?*?/ 推导过程： S?aA?aBaA?a*aA?a*aBaA?a*a+aA?a*a+a=W 构造语法树： S a A B a A * B a A + ? = 2 \* GB2 ⑵自上而下分析法 自上而下分析法又可分为确定和不确定的两种。 = 1 \* GB3 ①不确定的分析法（带回溯） 是一种穷举的试探方法，效率低、代价高，极少使用。 = 2 \* GB3 ②确定的分析法（不带回溯） 实现方法简单、直观，便于手工构造或自动生成语法分析器，是目前常用的方法之一。但是对文法有一定的限制。 2、自下而上分析法 = 1 \* GB2 ⑴自下而上分析过程 分析过程是归约过程。从给定的输入串W开始，不断寻找与文法G中某个产生式P的侯选式（右部）进行匹配，并用P代替也称为归约。 = 2 \* GB2 ⑵自下而上分析法 = 1 \* GB3 ①算符优先分析法 定义算符（广义讲是文法的终结符号）之间的某种优先和结合关系，借助这种关系来寻找并确定可归约字符串，并进行归约。 = 2 \* GB3 ②LR分析法 是一类自左向右对输入串进行扫描的自下而上分析方法，分析过程是规范归约的序列。适用于语法分析器的自动构造。