李元金 计算机与信息工程学院 E-mail: liyuanjin10@126.com 第9讲 语法分析—自上而下分析（1） 李元金 计算机与信息工程学院 E-mail: liyuanjin10@126.com.

Presentation on theme: "李元金 计算机与信息工程学院 E-mail: liyuanjin10@126.com 第9讲 语法分析—自上而下分析（1） 李元金 计算机与信息工程学院 E-mail: liyuanjin10@126.com."— Presentation transcript:

1 李元金 计算机与信息工程学院 E-mail: liyuanjin10@126.com
第9讲 语法分析—自上而下分析（1） 李元金 计算机与信息工程学院

2 内容与目标 内容 a.语法分析器的功能 b.自上而下分析面临的问题 c. LL(1)分析法 目标 a.掌握语法分析器的功能

3 源程序 表 词法分析器 出 单词符号 格 错 语法分析器 管 处 语法单位 理 理 四元式 优化段 四元式 目标代码生成器 目标代码
语义分析与中间代码生成器 四元式 优化段 四元式 目标代码生成器 目标代码

4 4.1 语法分析器的功能 语法分析的任务:在词法分析识别出单词符号的基础上，分析判定程序的语法结构是否符合语法规则。
即对于任一给定w∈VT*,判断L(G) 语言的语法结构是用上下文无关文法描述的，因此语法分析器的工作本质上就是按文法的产生式识别输入串是否为一个句子。这里所说的输入串是指单词符号组成的有限序列。

5 语法分析器的功能：它是一个程序，该程序按照文法的产生式P(语言的语法规则)，识别输入符号串w是否为一个句子(合式程序)。
语法分析器在编译程序中的地位 如下图所示。

6 单词符号 语法分 析树 源程序 词法分 析器 语法分 符号表 编译程序 后续部分 取下一单词 ... 图1 语法分析器在编译程序中的地位

7 语法分析的两种方法： 自下而上分析法(Bottom-up)
基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。 算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。 LR分析法：规范归约

8 E E + E E * E i i i G(E)： E  i| E+E | E-E | E*E | E/E | (E) i*i+i

9 自上而下分析法(Top-down) 基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找"匹配"的推导。
递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。 预测分析程序 优点：直观、简单和宜于手工实现。

10 4.2 自上而下分析面临的问题 自上而下就是从文法的开始符号出发，向下推导， 推出句子。 带“回溯”的
4.2 自上而下分析面临的问题 自上而下就是从文法的开始符号出发，向下推导， 推出句子。 带“回溯”的 不带“回溯”的递归子程序(递归下降)分析方法。 自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号(根结点)出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。其本质上是一个试探的过程，是反复使用不同产生式谋求匹配输入串的过程。

11 例3.4.1 假定有文法G(S): (1) S→xAy (2) A→**|* 分析输入串 =x*y。
按文法的开始符号产生根结S，并让IP指向指示器输 入串的第一个符号x。然后，把语法分析树的子结点从 左至右对IP所指向的符号进行匹配。第一个符号匹配 ，于是IP向后移动一个符号。 S x*y IP A x y

12 由于S的第二个子结点是非终符，它有两个候选. 和
由于S的第二个子结点是非终符，它有两个候选**和*。先试着拿出第一个，此时语法树发展如上所示。把子树A的最左子结点与IP所指向的符号进行匹配，结果一致，故IP移向下一个符号。 S x*y IP A x y *

13 再拿A的第二个子结点与IP所指的符号进行匹配，
结果不一致。 S x*y IP A x y *

14 回朔，注销掉A子树，并把IP回退到进入A前的位置，然后取出A的第二个候选。此时匹配获得成功。IP向前移动到下一个符号。
S x*y IP A x y * S x*y IP A x y * S x*y IP A x y

15 下面对S的第三个子结点y进行匹配。由于这个结点与最后一个输入字符相符，所以就完成了对构造语法分析树的任务。

16 当某个非终结符有多个产生式候选时，可能带来如下问题:
1.回溯：分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时，不得不“回溯”。 2.左递归：一个文法是含有左递归的，如果存在非终结符P

17 含有左递归的文法将使自上而下的分析陷入无限
循环，所以首先要消除左递归。 虚假匹配：当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。 当最终报告匹配不成功时，难以知道输入串中出错的位置。 效率低、代价高、只有理论意义

18 4.3 LL(1)分析法 LL(1)的意思：第一个L表示从左到右扫 描输入串，第二个L表示最左推导，1表 示分析时只需向前看一个符号。它是递 归下降分析法与预测分析法的基础。

19 4.3.1 左递归的消除 左递归变右递归 简单直接左递归：（规则左递归） 假定关于非终结符P的规则为
左递归的消除 简单直接左递归：（规则左递归） 假定关于非终结符P的规则为 P→P |  其中不以P开头。 我们可以把P的规则等价地改写为如下的非直接左递归形式： P→P P→P| 左递归变右递归 改写前后是等价的。

20 例：文法G(E): E→E＋T | T T→T*F | F F→(E) | i 经消去直接左递归后变成： E→TE E→+TE |  T→FT T→*FT | 

21 P→P1 | P2 | … | Pm | 1 | 2|…|n
普遍的直接左递归（规则左递归） 一般而言，假定P关于的全部产生式是 P→P1 | P2 | … | Pm | 1 | 2|…|n 其中，每个都不等于，每个都不以P开头 那么，消除P的直接左递归性就是把这些规则 改写成： P→1P | 2P | … | nP P→1P | 2P |… | mP |  左递归变右递归

22 例：已知简单表达式文法 exp→exp+term|exp-term|term 解：这里P=exp, 1= +term, 2= -term, =term 改写： exp →term exp’, exp’→+term exp’|-term exp’| 

23 一般的左递归：（文法左递归） 一个文法消除左递归的条件： 不含以为右部的产生式 不含回路。 P Þ +

24 例如文法G(S): S→Qc|c Q→Rb|b R→Sa|a (4.3) SQcRbcSabc
虽没有直接左递归，但S、Q、R都是左递归的 SQcRbcSabc

25 消除左递归的算法: 1. 把文法G的所有非终结符按任一种顺序排列成P1，P2，…，Pn；按此顺序执行；
2. for (i=1;i<=n; i++)//文法有n个非终结符 { for ( j=1;j<=i-1;j++)//第i个每个非终结符Pi可能有i-1个产生式 把形如Pi→Pj的规则改写成 Pi→1|2|…|k ; (其中Pj→1|2|…|k是关于Pj的所有规则) } 消除关于Pi规则的直接左递归性 3. 化简由2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。

26 例：已知文法： S→Sa|Tbc|Td T→Se|gh 试消除其左递归 解：①把非终结符排序P1=S，P2=T(n=2) ②执行循环 i=1,j=1 不执行关于i的内循环，但关于P1=S存在规则左递归，对它进行改写： S→(Tbc|Td)S’ S’→aS’|

27 ∴T→T((bc|d) S’ e|gh i=2,j=1 先执行内循环： 形如关于P2→P1的规则，即T→Se且S→ (Tbc|Td)S’
呈递归，对它进行改写： P1→1|2形，故写成： P2→1 |2形，连同T→gh，有： ∴T→T((bc|d) S’ e|gh

28 消去关于P2=T规则的左递归如下： T→ghT’ T’→(bc|d) S’ e T’| ③最后得到的整个文法为： S→(Tbc|Td)S’ S’→aS’| T’→(bc|d)S’eT’| 

29 现在的Q不含直接左递归，把它代入到S的有关候选后，S变成 S→Sabc | abc | bc | c
例：考虑文法G(S) S→Qc|c Q→Rb|b R→Sa|a 令它的非终结符的排序为R、Q、S。 Q的规则变为 Q→Sab | ab | b 现在的Q不含直接左递归，把它代入到S的有关候选后，S变成 S→Sabc | abc | bc | c

30 消除S的直接左递归后： S→abcS | bcS | cS S→abcS |  Q→Sab |ab | b R→Sa|a 关于Q和R的规则已是多余的，化简为： S→abcS |  (4.4)

31 注意，由于对非终结符排序的不同，最后所得的文法在形式上可能不一样。但不难证明，它们都是等价的。
例如，若对文法(4.3)的非终结符排序选为S、Q、R，那么，最后所得的无左递归文法是： S→Qc | c Q→Rb | b R→bcaR | caR |a R (4.5) R→ bca R |  文法(4.4)和(4.5)的等价性是显然的。

32 消除回溯、提左因子 为了消除回溯就必须保证：对文法的任 何非终结符，当要它去匹配输入串时， 能够根据它所面临的输入符号准确地指 派它的一个候选去执行任务，并且此候 选的工作结果应是确信无疑的。 A→ 1 |  2 | … |  n S a…. IP A ...

33 1.令G是一个不含左递归的文法，对G的所有非终结符的每一个候选，定义它的终结首符集FIRST()为：
特别是，若 ，则规定FIRST()。即， FIRST()是的所有可能推导的开头终结符或可能的。

34 例：文法G(S): S→Ap|Bq; A→a|cA; B→b|dB 有： FIRST(Ap)={a,c}, FIRST(Bq)={b,d},

35 2.文法符号的FIRST集计算(P78) 对每一文法符号XVT∪VN构造FIRST(X) 连续使用下面的规则，直至每个集合FIRST不再增大为止： a.若XVT，则FIRST(X)＝{X}。 b.若XVN，且有产生式X→a…，则把a加入到FIRST(X)中。 c.若X→也是一条产生式，则把也加到FIRST(X)中。

36 d.若X→Y…是一个产生式且YVN，则把FIRST(Y)中的所有非-元素都加到FIRST(X)中；
e.若X→Y1Y2…Yk是一个产生式，Y1，…，Yi-1都是非终结符，而且，对于任何j，1ji-1，FIRST(Yj)都含有(即Y1…Yi-1)， 则把FIRST(Yi)中的所有非-元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有，j＝1，2，…，k，则把加到FIRST(X)中。

37 3.求符号串的FIRST集合（P79） 对文法G的任何符号串=X1X2…Xn构造集合FIRST()。 a.置FIRST()＝FIRST(X1)\{}； b. 若对任何1ji-1，FIRST(Xj)，则把FIRST(Xi)\{}加至FIRST()中；特别是，若所有的FIRST(Xj)均含有，1jn，则把也加至FIRST()中。显然，若＝则FIRST()＝{}。

38 ∴First(E)= First(T)= First(F )={(,i} First(E)={+, } First(T)={*, }
例：文法 E→TE E→+TE |  T→FT T→*FT |  F→(E) | i First(E)={(,i} First(E)={+, } First(T)={(,i} First(T)={*, } First(F)={(,i} ∴First(E)= First(T)= First(F )={(,i} First(E)={+, } First(T)={*, }

39 作业 1.作业 P81-1，2，3 2.实验 实验二 3.课后要求 复习本节内容,预习下节。