当前位置：文档之家 › 第五章自上而下的语法分析

第五章自上而下的语法分析

  • 格式：ppt
  • 大小：1.08 MB
  • 文档页数：50

下载文档原格式

  / 50

合集下载

《编译原理》第5章自上而下语法分析

《编译原理》第5章自上而下语法分析

编译原理武汉大学计算机学院编译原理课程组第5章自上而下语法分析·基本思想·存在的问题·解决方法·LL(1)方法·递归子程序法5.0 语法分析的功能及基本思想依据语法规则，逐一分析词法分析时得到的单词，把单词串分解成各类语法单位，即确定它们是怎样组成说明和语句，以及说明和语句又是怎样组成程序的。

分析时如发现有不合语法规则的地方，便将出错的位置及出错性质打印报告给程序员；如无语法错误，则用另一种中间形式给出正确的语法结构，供下一阶段分析使用。

1. 语法分析的功能5.0 语法分析的功能及基本思想2．自上而下语法分析的基本思想从识别符号出发，不断建立直接推导，试图构造一个最左推导序列，最终由它推导出与输入符号串相同的符号串。

从语法树的角度看，自顶向下分析过程将以识别符号为根结点，试图向下构造一棵语法树，其末端结点符号串正好与输入符号串相同。

相应于高级语言的编译过程，自上而下语法分析就是从该高级语言文法的开始符号——<程序>出发，试图推导得到该文法的句子——源程序或与其等价的单词串。

3. 自上而下语法分析遇到的问题5.0 语法分析的功能及基本思想在分析的过程中，匹配失败后，必须退回到出错点，选择其它可能的产生式重新推导，这个过程称为回溯。

如果文法中存在如下形式的产生式A →α1|α2|…|αn那么在自上而下的语法分析过程中，当要对A 展开时，应按哪一个后选式展开呢？即如何确定替换A 的αi 。

如果选择错误，将导致回溯。

5.0 语法分析的功能及基本思想3. 自上而下语法分析遇到的问题当文法中出现左递归时（存在非终结符号U，对于它有+⇒U→U…或U U…），会使分析过程陷入无限循环。

例如对文法G[S]：S→ABA→bB|AaB→Sb|a5.0 语法分析的功能及基本思想4.自上而下语法分析中问题的解决方法·避免回溯·消除左递归5.1 消除左递归的方法1．直接左递归的消除•采用扩充BNF表示[x]——x可以出现零次或一次{x}——x可以出现零次到多次x(y|z)——等价于xy或xz5.1 消除左递归的方法1．直接左递归的消除•采用扩充BNF表示•引进新的非终结符号，将左递归改写为右递归。

软件工程 编译原理 第五章 自顶向下的语法分析方法

软件工程 编译原理 第五章 自顶向下的语法分析方法
PROCEDURE T； BEGIN F；T END PROCEDURE T； IF SYM=‘*’ THEN BEGIN ADVANCE； F；T END；
例:文法G(E):
E→TE E→+TE | T→FT PROCEDURE F； T→*FT | IF SYM=‘i’ THEN ADVANCE F→(E) | i ELSE 对应的递归下降子程序为: IF SYM=‘(’ THEN
其中不以P开头。
可以把P的规则等价地改写为如下的非直接左递归 形式： 左递归变 P→P 右递归 P→P|
一般而言，假定P关于的全部产生式是 P→P1 | P2 | … | Pm | 1 | 2|…|n 其中，每个都不等于，每个都不以P开头 那么，消除P的直接左递归性就是把这些规则改写 成：
第5章 自顶向下的语法分析方法
语法分析的作用是识别由词法分析给出 的单词符号序列是否是给定文法的正确句 子(程序)。 目前语法分析常用的方法有: 1、自顶向下（自上而下）分析 2、自底向上（自下而上）分析
5.3非LL(1)文法到LL(1)文法的等价转换
确定的自顶向下分析要求给定语言的文法必
须是 LL(1)形式。然而，不一定每个语言都是 LL(1)文法，对一个语言的非LL(1)文法是否能变
换为等价的LL(1)形式以及如何变换是我们讨论
的主要问题。由LL(1)文法的定义可知若文法中 含有左递归或含有左公共因子，则该文法肯定不 是LL(1)文法，因而，我们设法消除文法中的左 递归，提取左公共因子对文法进行等价变换。
1、提取公共左因子
若文法中含有形如：A→αβ|αγ的产生式，这导 致了对相同左部的产生式其右部的FIRST集相交， 也就是 SELECT(A→αβ)∩SELECT(A→αγ) ≠ φ ，不满足 LL(1)文法的充分必要条件。

第五章自上而下语法分析

第五章自上而下语法分析

第五章⾃上⽽下语法分析第五章⾃上⽽下语法分析1、教学⽬的及要求：本章介绍编译程序的第⼆个阶段语法分析的设计⽅法和实现原理，包括⾃上⽽下分析的⽆回朔的递归下降分析、 LL(1)分析法。

要求理解递归下降分析、LL(1)⽂法的基本概念；掌握⽆回朔的递归下降分析的设计和实现、LL(1)分析表的构造与分析⽅法。

◇能够对⼀个给定的⽂法判断是否是LL(1)⽂法；◇能构造预测分析表；◇能⽤预测分析⽅法判断给定的输⼊符号串是否是该⽂法的句⼦；◇能对某些⾮LL(1)⽂法做等价变换：①消除左递归②提取左公共因⼦可能会变成LL(1)⽂法。

这样可扩⼤⾃顶向下分析⽅法的应⽤。

2、教学内容：语法分析器的功能，⾃上⽽下语法分析（递归下降分析法，预测分析程序），LL（1）分析法，递归下降分析程序构造，预测分析程序。

3、教学重点：递归下降⼦程序，预测分析表构造，LL(1)⽂法。

4、教学难点：对⼀个⽂法如何判断是否是LL(1)⽂法，由于在判断 LL(1)⽂法时⽤到⽂法符号串的开始符号集合（FIRST集）和⾮终结符后跟符号集合（FOLLOW集）的计算，⽽⼀般学⽣往往因概念不清或不够细⼼对这两个集合的计算常常出错，导致判断和分析结果的错误。

5、课前思考为了了解⾃顶向下（⾃上⽽下）分析的⼀般过程和问题，请学⽣⾸先回顾本章之前介绍的有关基本概念：◇句⼦、句型和语⾔的定义是什么？◇什么叫最左推导？◇什么叫最右推导和规范推导？◇什么叫确定的⾃顶向下语法分析？◇⾃顶向下语法分析是从⽂法的开始符号出发，反复使⽤各种产⽣式，寻找与输⼊符号匹配的推导。

◇确定的⾃顶向下语法分析中⽤的是哪种推导？◇在确定的⾃顶向下语法分析过程中，当以同⼀个⾮终结符为左部的产⽣式有多个不同右部时，如何选择⽤哪个产⽣式的右部替换当前的⾮终结符？◇确定的⾃顶向下语法分析对⽂法有何限制？6、章节内容第⼀节概述第⼆节 LL(1)分析⽅法第三节递归下降分析法5.1 概述LL分析法确定的⾃上⽽下分析⾃上⽽下分析递归下降分析法语法分析不确定的⾃上⽽下分析——即带回溯的分析⽅法算符优先分析⾃下⽽上分析LR分析⼀、带回溯的⾃顶向下分析⽅法是⾃顶向下分析的⼀般⽅法，即对任⼀输⼊符号串，试图⽤⼀切可能的办法，从树根结点（识别符号）出发，根据⽂法⾃上⽽下地为输⼊串建⽴⼀棵语法树，或者说，从识别符号开始，根据⽂法为输⼊串建⽴⼀个推导序列，这种分析过程本质上是⼀种试探过程，是反复使⽤不同规则谋求匹配输⼊串的过程。

编译原理-自上而下的语法分析

编译原理-自上而下的语法分析

高效性
由于从文法的最顶端开始分析， 一旦发现不匹配，就可以立即终 止当前分支的搜索，避免不必要 的计算，提高了编译器的效率。
易于处理左递归文
法
自上而下的分析方法可以很方便 地处理含有左递归的文法，而左 递归是许多实际编程语言的重要 特征。
局限性
无法处理左边界问题
自上而下的分析方法在处理某些含有左边界的文法时可能 会遇到问题，因为这种方法会优先匹配最左边的符号，而 左边界问题需要从右往左匹配符号。
案例三
在编译器优化中，自上而下的语法分析被用 于识别和修改源代码中的冗余和低效的语法 成分。例如，在C编译器的实现中，自上而 下的语法分析可以用于优化循环结构，减少 不必要的循环次数，提高程序的执行效率。
自上而下的语法分析还可以用于代码生成和 代码生成器的实现。通过识别和解析源代码 中的语法成分，可以生成更高效、更安全的 机器代码或字节码，提高程序的执行效率和
安全性。
THANKS
感谢观看
详细描述：递归下降分析算法易于理解，每个产生式规 则对应一个函数，函数的实现相对简单明了。
详细描述：对于每个产生式规则，需要编写相应的递归 函数，可能会导致代码冗余。
移入-规约分析算法
总结词
基于栈的算法
详细描述
移入-规约分析算法是一种自上而下的语法分 析算法，它将目标语句从左到右依次读入， 并根据文法的产生式规则进行移入或规约操 作，直到找到目标语句的语法结构。
词法分析
词法分析是编译过程的第一步，也称为扫描或词法扫描。它的任务是从左 到右读取源代码，将其分解成一个个的记号或符号。
词法分析器通常使用正则表达式或有限自动机来识别和生成记号，这些记 号可以是关键字、标识符、运算符、标点符号等。

第五章 语法分析(自上而下分析法)

第五章 语法分析(自上而下分析法)

解： 这里P=exp , α 1=+term , α 2=-term, β =term 改写： exp → term exp' , exp' → +term exp' | - term exp' | ε
(3)间接左递归的消除 例如文法G(S): S→Qc|c Q→Rb|b R→Sa|a
虽没有直接左递归，但S、Q、R都是左递归的
例：简单的表达式文法 exp → exp addop term | term 消除其左递归。 解：属于格式P → Pα | β 这里 P=exp , α =addop term , β =term 改写： exp → term exp' exp' → addop term exp' | ε
例 文法G(E): E→E＋T | T T→T*F | F F→(E) | i 经消去直接左递归后变成： E→TE′ E′→+TE′ | ε T→FT′ T′→*FT′ | ε F→(E) | i 不变
例1 假定有文法G(S): (1) S→xAy (2) A→** | * 分析输入串x*y(记为α)。 ① 按文法的开始符号产生语法树的根节点S,根据规 则，S有三个子孙，于是此时的语法树如图所示； 并把指示器IP指向串α的第一个符号x x*y IP S x*y IP S x A y
把语法树的子节点从左至右对IP所指向的符号进行匹 配。第一符号匹配，于是，IP向后移动一个符号。
是递归下降分析法和预测分析法的基础
LL(1)分析法
构造不带回溯的自上而下分析算法 要消除文法的左递归性 克服回溯
1 左递归的消除
（1）简单直接左递归 直接消除见诸于产生式中的左递归：假定关于非 终结符P的规则为

语法分析最常用的两类方法

语法分析最常用的两类方法

LL分析法和LR分析法。

1、自上而下语法分析方法（LL分析法）
给定文法G和源程序串r。

从G的开始符号S出发，通过反复使用产生式对句型中的非终结符进行替换(推导)，逐步推导出r 。

是一种产生的方法，面向目标的方法。

分析的主旨为选择产生式的合适的侯选式进行推导，逐步使推导结果与r匹配。

2、自下而上语法分析方法（LR分析法）
从给定的输入串r开始，不断寻找子串与文法G中某个产生式P的候选式进行匹配，并用P的左部代替(归约)之，逐步归约到开始符号S。

是一种辨认的方法，基于目标的方法。

分析的主旨为寻找合适的子串与P的侯选式进行匹配，直到归约到G的S为止。

扩展资料
LALR分析器可以对上下无关文法进行语法分析。

LALR即“Look-AheadLR”。

其中，Look-Ahead为“向前看”，L代表对输入进行从左到右的检查，R代表反向构造出最右推导序列。

LALR分析器可以根据一种程序设计语言的正式语法的产生式而对一段文本程序输入进行语法分析，从而在语法层面上判断输入程序是否合法。

实际应用中的LALR分析器并不是由人手工写成的，而是由类似于yacc和GNU Bison之类的LALR语法分析器生成工具构成。

由机器自动生成的代码相比较于程序员手工的代码，拥有更好的运行效率而且减少了程序员的工作量。

第五章自顶而下语法分析方法课外训练

第五章自顶而下语法分析方法（一）内容本章介绍编译程序的第二个阶段语法分析的第一种设计方法和实现原理即自上而下分析的原理及无回朔的递归下降分析、 LL(1)分析法和相应程序构造。

（二）本章重点自上而下分析的思想，LL(1)文法，LL(1)预测分析，递归下降分析程序的构造。

（三）本章难点消除左递归，预测分析表的构造，求First集和Follow集，预测分析中的出错处理。

（四）本章考点LL（1）文法的判定。

递归下降分析程序的构造。

预测分析程序的构造与分析方法。

（五）学习指导理解自上而下分析面临的问题，理解递归下降分析、LL(1)文法，掌握无回朔的递归下降分析方法的设计和程序实现、LL(1)分析表的构造与分析方法。

语法分析是在词法分析的基础上判定程序的语法结构是否符合语法规则的过程。

词法分析器的构造技术是编译器的主要技术。

词法分析分为自上而下的分析（LL（K））和自下而上的分析（算符优先、LR（K））。

本章先学习在逻辑概念上易于接受的自上而下的分析，即从文法开始符号出发，自上而下地为输入串建立一棵语法树，或者说为输入串寻找一个最左推导。

LL（1）分析法是本章的学习重点。

附训练试题：1试构造与下列文法G[S]等价的无左递归文法。

G[S]: S→Sa|Nb|c (1)N →Sd|Ne|f2：文法G的规则集为;P →begin d : X endX →d : X | sYY→: sY | e做出该文法LL(1)分析表。

3 设有以下文法：G[S]: S→eEfGh | gE→FSG | hF→SEc | cG | εG→Sh |ε（1）求出该文法每一个非终结符的FOLLOW集。

（2）它是LL(1)文法吗？为什么？4：给出语言L={1n a0n1m a0m|n>0, m>=0} 的LL(1)文法G[S]并说明其理由。

5 设有文法：G[S]:S→aBc | bABA→aAb | bB→b | e构造其LL(1)分析表，并分析符号串baabbb是否是该文发的句子。

第5章自上而下语法分析


否则 S L(G[Z])
存在主要问题: • 句柄的识别问题
主要方法: • 算法优先分析法 • LR分析法
3 3
1 ．
自上而下分析的一般过程
给定符号串S，若预测是某一语法成分， 那么可根据该语法成分的文法,设法为S构造一棵语法树.
若成功,则S最终被识别为某一语法成分,即 SL(G[Z])其中G[Z]为某语言成分的文法. 若不成功,则 SL(G[Z])
21
5.2 LL(1)分析法
LL(k)文法是一种自上而下语法分析方法.它是从文
法的识别符号出发,生成句子的最左推导.它从左到右 扫描源程序,每次向前查看k(k>1)个字符,便能确定当 前应该选择的产生式,如果每次只向前查看一个字符, 则称为LL(1)文法.
22
5.2 LL(1)分析法
设有文法G[Z]: 定义：α是文法G的一个符号串 FIRST(α) = {a | α * aβ， a Vt ， α,β V*}
消 除 所 有 左 递 归 的 算 法
14
例：文法G[s]为 S →Qc|c Q →Rb|b R →Sa|a
非终结符顺序 重新排列
R→Sa|a Q→Rb|b S→Qc|c
该文法是无直接左递归，但有间接左递归 SQc Rbc Sabc ∴S+ Sabc
1.检查规则R是否存在直接左递归
2.把R代入Q的有关选择，改写规则Q 3.检查Q是否直接左递归
c A d
5
5
S=cad 3. 选用A的右部符号串匹配输入串 A有两个右部,选第一个
G[Z]: Z→cAd A→ab|a
Z ·
c A d a Z · c A d b
完成进一步推导Aab 检查,a-a匹配,b-d不匹配(失败) 但是还不能冒然宣布SL(G[Z]) 4. 回溯 即砍掉A的子树 改选A的第二右部 Aa 检查 a-a匹配 d-d匹配

语法分析--自上而下分析的基本问题

语法分析--⾃上⽽下分析的基本问题语法分析基本概念语法分析的前提：对语⾔的语法结构进⾏描述，采⽤正规式和有限⾃动机描述和识别语⾔的单词符号，⽤上下⽂⽆关⽂法来描述语法规则语法分析的任务：分析⼀个⽂法的句⼦的结构语法分析器的功能：按照⽂法的产⽣式(语⾔的语法规则)，识别输⼊符号串是否为⼀个句⼦(合式程序)⾃下⽽上(Bottom-up)：从输⼊串开始，逐步进⾏归约，直到⽂法的开始符号，归约：根据⽂法的产⽣式规则，把串中出现的产⽣式的右部替换成左部符号，从树叶节点开始，构造语法树，算符优先分析法、LR分析法⾃上⽽下(Top-down)：从⽂法的开始符号出发，反复使⽤各种产⽣式，寻找"匹配"的推导，推导：根据⽂法的产⽣式规则，把串中出现的产⽣式的左部符号替换成右部，从树的根开始，构造语法树，递归下降分析法、预测分析程序⾃上⽽下分析⾯临的问题基本思想：从⽂法的开始符号出发，向下推导，推出句⼦，针对输⼊串，试图⽤⼀切可能的办法，从⽂法开始符号(根结点)出发，⾃上⽽下地为输⼊串建⽴⼀棵语法树多个产⽣式候选带来的问题，回溯问题：分析过程中，当⼀个⾮终结符⽤某⼀个候选匹配成功时，这种匹配可能是暂时的，出错时，不得不“回溯”⽂法左递归问题：⼀个⽂法是含有左递归的，如果存在⾮终结符P⾯临的问题⽂法左递归问题回溯问题构造不带回溯的⾃上⽽下分析算法消除⽂法的左递归性消除回溯消除⽂法的左递归直接左递归的消除间接左递归的消除消除左递归的算法由于对⾮终结符排序的不同，最后所得的⽂法在形式上可能不⼀样。

但不难证明，它们都是等价的消除回溯为了消除回溯必须保证:对⽂法的任何⾮终结符，当要它去匹配输⼊串时，能够根据它所⾯临的输⼊符号准确地指派它的⼀个候选去执⾏任务，并且此候选的⼯作结果应是确信⽆疑的FIRST和FOLLOW集合的构造FIRST集合令G是⼀个不含左递归的⽂法，对G的所有⾮终结符的每个候选α定义它的终结⾸符集FIRST(α)为：提取公共左因⼦FOLLOW集合L: 从左到右扫描输⼊串 L: 最左推导 1:每⼀步只需向前查看⼀个符号FIRST和FOLLOW集合的构造构造每个⽂法符号的FIRST集合构造FOLLOW(A)构造每个⾮终结符的FOLLOW集合对最后的FIRST、FOLLOW集合有点迷，真的有点迷，晚上不该看这个的！！o(╥﹏╥)o。

编译原理第五章语法分析——自下而上分析

第五章语法分析——自下而上分析要紧内容:[1]自下而上分析的大体问题[2]算符优先分析法[3]算符优先分析表和优先函数的构造[4]LR分析器的大体原理大体要求:[1]明白得自下而上分析法的大体思想[2]明白得有关归约、短语、句柄、标准归约等概念[3]把握算符优先分析法[4]了解算符优先表和优先函数的构造技术[5]了解LR 分析器大体原理和工作方式教学要点：本章介绍自下而上语法分析方式。

所谓自下而上分析法确实是从输入串开始，慢慢进行“归约”，直至归约到文法的开始符号；或说，从语法树的结尾开始，步步向上“归约”，直到根结。

讲义摘要：5.1 自下而上分析大体问题自下而上分析法的大体思想：从输入串开始，慢慢进行“归约”，直到文法的开始符号。

即从树结尾开始，构造语法树。

所谓归约，是指依照文法的产生式规那么，把产生式的右部替换成左部符号。

自上而下分析的核心问题是：如何判定符号串的可归约性，和如何归约。

即，识别可归约串的问题。

归约自下而上分析法事实上确实是一种“移进－归约”法，即，采纳“移进－归约”思想进行。

实现思想是：对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，（该句型对应某产生式的右部，即栈顶生成了某产生式的右部的文法符号串），就将栈顶的这一部份替换成 (归约为) 该产生式的左部符号，这称为归约。

重复这一进程直到归约到栈中只剩文法的开始符号时那么为分析成功，也就确认输入串是文法的句子。

现举例说明。

例1：设文法G[S]为：(1) S→aAcBe(2) A→b(3) A→Ab(4) B→d试对abbcde进行“移进－归约”分析。

步骤: 1 2 3 4 5 6 7 8 9 10解：动作: 进a 进b 归(2) 进b 归(3) 进c 进d 归(4) 进e 归(1)表1符合栈的转变进程自下而上语法分析的进程也可看成自底向上构造语法树的进程，每步归约都是构造一棵子树，最后当输入串终止时恰好构造出整个语法树，如图1所示。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

左递归
对文法中一切左递归的消除要求文法中不含回 路即无A+ A的推导。满足这个要求的充分
条件是:文法中不包含形如A A 的有害规则
和 A 的空产生式.
左递归
直接左递归的形式为： A A1 A2 … Am12… n
消除左递归后可改写为：
A1 A 2 A … n A
左公共因子
一般地如有产生式： A 12 … n
当输入符号为从推导出来的非空串时，则不能立即决定 使用产生式 A 1 ，还是2 …，在此情况下，为了避免回 溯，把产生式改写为：
A A A 1 2 … n
其中称为左公因子。于是，对当前非终极符A若输入为 中推导出来的串，则唯一地使用产生式A A。
5.3 非LL(1)文法的等价变换

提取左公共因子 文法中，如果同一非终极符的不同可选 右部包含相同的前缀，则在最左推导过 程中，对同一输入符号不能唯一地确定 应该使用的产生式，于是只能尝试，造 成回溯
结论


产生式中含有左递归的文法不是LL（1） 文法 相同左部的产生式中含有左公共因子的文 法不是LL（1）文法
关于E'的产生式:E'→+TE'∣ε 即E'有两个候选；第一个候选的开头终结符为+，第二 个候选为ε。这就是说，当E'面临输入符号“+”时就令 第一个候选进入工作，而当面临任何其它符号时，E' 就自动认为获得了匹配。递归函数E'就是根据这一原 则设计的。 例如，我们将递归函数的调用以栈的形式模拟来 分析输入串 # i1*(i2+i3)# 的语法分析过程；在此， “#”为输入串i1*( i2+i3)的分隔符。进行语法分析时， 首先将“#”和文法开始符E压入栈中，当语法分析进行 到栈中仅剩“#”而输入串扫描指针已指向输入串尾部 的“#”时，则语法分析成功，分析过程如下图所示。
{ 把一个形如：
A i → A j γ∣ β 1 ∣ β 2 ∣ … ∣ β n A j→ δ 1 ∣ δ 2 ∣ … ∣ δ k
的产生式改写为： Ai→δ1γ∣δ2γ∣…∣δkγ∣β1∣β2∣…∣βn ； 按消除直接左递归的方法消除Ai 的直接左递归； } (3) 化简由(2)所得的文法，即去掉那些从开始符号S 出发，在推导中无法出现的非终结符的产生式(去掉多 余产生式)。
消除文法中一切左递归的算法：
算法步骤：
1)把文法的所有非终结符按某一顺序排列;如A1，A2，…An
2)从A1开始消除左部为A1的产生式的直接左递归，然后把 左部为A1的所有规则的右部逐个替换左部为A2右部以A1开 始的产生式中的A1，并消除左部为A2的产生式中的直接左 递归。继而以同样方式把A1，A2的右部代入左部为A3右部 以A1或A2开始的产生式中，消除左部为A3的产生式之直接 左递归，直到把左部为A1，A2，…A n-1的右部代入左部为 A n的产生式中，从A n中消除直接左递归。

递归子程序法:

递归下降分析法是确定的自上而下分析法.这种分析 法要求文法一定是LL(1)的。 它的基本思想是:对文法中的每个非终结符编写一个 函数(或子程序),每个函数的功能是识别由该非终结 符所表示的语法成分。由于描述语言的文法常常是 递归定义的,因此相应的这组函数必然以相互递归的 方式进行调用，将此种分析法称为递归下降分析法。
特点:1,产生式右部不全由终结符 开始;
2,相同左部的产生式其右部由不同 终结符或非终结符开始;
3,文法无空产生式
产生式右部串的第一个符号
即fristα
需要看后 跟符号即 follow
自顶向下分析总是根据当前句型中的符 号和当前输入的符号决定下一步应执行的分 析动作。如果句型中当前为终结符且与输入 符号匹配，则读下一个输入符号；如果当前 为非终结符号，则根据输入符号选择该非终 结符的一个产生式进行下一步推导，为了分 析方便，能够对输入串确定句型所选择的产 生式需要定义两个集合：即文法符号串的首 符号集First和非终结符的后跟符号集Follow。
select(A )= follow(A)
LL（1）文法的定义

一个上下文无关文法是LL（1）文法的充 要条件是：

对每个非终结符A的两个不同产生式， A
A ，满足 SELECT（A）∩ SELECT（A ）= ，其中、 不能同时 *
即关于任一非终结符的不同产生式其选用集 互不相交，则称G为LL(1)文法。
把first(y2)加入first(X)。
后跟符号集的定义:

设G=（VN、VT、P、S）是上下文无关文法， AVN ，S是开始符号，则文法符号A的后跟符 号集为： FOLLOW（A） ={a|S * A 且 aVT，aFIRST（）， VT*，V+ } * A，且 * ，则# FOLLOW（A） 若S
式，对某一个i若有Y1Y2．．．Yi-1*ε ε 加入first(X)。
且a∈first(Yi)，
则a∈first(X)；如果ε ∈first(Yj)，j=1，2，…k，则把 例如，first(Y1)中的每个元素都属于first(X)；如果Y1
不能推导出ε ，则first(X)=first(Y1)； 如果Y1*ε ，则
5.2 LL(1) 文法的判别
判断某一文法是否是LL(1)文法的步骤
1、求出文法中所有能推出的非终结符号； 2、计算文法中每一个产生式右部符号串的FIRST集； 3、计算文法中每一个非终结符号的FOLLOW集； 4、根据定义计算文法中每一个产生式的SELECT集； 5、计算文法中具有相同左部产生式的SELECT集的交集， 根据LL（1）文法定义确定该文法是否为LL（1）文 法。 补充例：
第五章 自顶向下语法分析




本章内容：从识别符号出发，不断建立直接推导，试图 构造一个推导序列，最终由它推导出与输入符号串相同 的符号串。从语法树的角度看，自顶向下分析过程是以 识别符号为根结点，试图向下构造一棵语法树，使其末 端结点符号串正好与输入符号串相同。 基本知识点：自上而下语法分析的基本思想和面临的问 题，消除左递归的方法，避免回溯对文法的要求，递归 子程序法，LL(1)分析法。 重点：消除左递归的方法，递归子程序的构造方法， LL(1)文法，LL(1)分析表的构造方法。 难点：符号串的FIRST集合的求法，文法非终结符号 FOLLOW集合的求法以及LL(1)分析,表的构造。
对给定的文法，求其非终结符A的集合follow(A)，
应用下列规则，直到follow(A)不能再加入任何终结
符号为止。 (1)若A是开始符号，则输入符号的结束标志 #∈follow(A)。 (2)如果存在产生式B→Aβ，则把first(β)除ε之外
的所有符号加入follow(A)。
(3)如果存在产生式B→A或 B→Aβ，且first(β) 包含ε,即β ε，则把 follow(B) 加入 follow(A)。
3)去掉无用产生式
5.4 不确定的自顶向下分析



由于相同左部的产生式的右部First集 交集不为空而引起回溯 由于相同左部非终结符的右部能* 且该非终结符Follow集中含有其右部 First集的元素。 由于文法含有左递归而引起回溯
5.5 确定的自顶向下分析
递归子程序法 预测分析法
首符号集的定义:

设G=（VN、VT、P、S）是上下文无关文法， 则该文法的符号串的开始符号集为：

FIRST（ ）={a|
若
*
*
a，aVT，、V*}
，则 FIRST（ ）
设α是文法G的任一符号串，定义α的首符号集 first(α)是由α推导出来的串中作为第一个符号的 所有终结符的集合；如果α*ε ，则ε ∈ first(α )。
A1 A 2A … m Aε
回溯：回溯是指否定前面的工作而退回到某环 节重新做起。
消除左递归

消除直接左递归 消除间接左递归 消除文法中所有左递归
如何消除一个文法的一切左递归呢？如果一 个文法不含回路(形如AA的推导)，且产生式的右 部也不含ε的候选式，那么，下述算法将消除文 法的左递归： (1) 将文法G[S]的所有非终结符按一给定的 顺序排列：A1、A2、…、An ； (2) 执行下述循环语句将间接左递归改为直 接左递归： for (i=1;i<=n;i++) for (j=1;j<=i−1;j++)
自顶向下语法分析

文法有0—3型，语法分析方法有两种： 自顶向下和自下而上 自顶向下分析过程: 为输入串从开始符 开始构造语法树从文法开始符出发向 下推导，推出句子。
5.1 确定的自顶向下分析
见例5.1
输入串: W=pccadd
文法：
S→ p A S→ q B
A→ c A d
A →a
特点:1,产生式右部由终 结符开始; 2,相同左部的产生式其 右部由不同终结符开始
求首符号集: 即:为了求出给定文法关于符号X 的首符号集first(X)，应用下列规 则，直到再没有任何终结符号或 ε能加到该首符号集为止。

补充定义:
(1)如果X是终结符，则first(X)={X}。
(2)如果X→ε 是一个产生式，则ε ∈ first(X)。 (3)如果X是非终结符，并且X→Y1Y2．．．YK 是一个产生
过程中达到这一步则表明分析成功，否则表明输入中有语法
错误。递归下降分析对文法的限制是不能有公共左因子和左 递归。
构造递归下降分析程序：
构造递归下降分析程序时,每个函数名是相应的非 终结符,函数体则是根据规则右部符号串的结构编 写。 当遇到终结符a 时,则编写语句 if (当前读来的输入符号==a) 读下一个输入符号; 当遇到非终结符A 时,则编写语句调用A(); 当遇到A →ε规则时,则编写语句 if (当前读来的输入符号 FOLLOW(A) ) error() ; 当某个非终结符的规则有多个候选式时,按LL(1) 文法的条件能唯一地选择一个候选式进行推导。