第三章 语法分析

1、1第三章第三章 语法分析语法分析词法分析词法分析：字母是元素，组成字符串，记号的集合，线性结构语法分析语法分析：记号是元素，组成句子，句子的集合，树结构语法的双重含义语法的双重含义语法规则：上下文无关文法(子集LL文法、LR文法)语法分析：下推自动机(LL或LR分析器)，自上而下、自下而上分析 主要内容主要内容语法分析的若干问题上下文无关文法自上而下分析自下而上分析上机： DBMS的设计与实现SQL的语法分析器23.1 语法分析的若干问题语法分析的若干问题F语法分析器的作用语法分析器的作用语法分析器是编译器前端的重要组成部分，许多编译器，特别是由自动生成工具构造的编译器，往往其前端的中心部件就

2、是语法分析器。语法分析器在编译器中的位置和作用：33.1 语法分析的若干问题语法分析的若干问题语法分析器的两个重要作用：F根据词法分析器提供的记号流，为语法正确的输入构造分析树（或语法树），这是本章重点本章重点，在以后各节中详细讨论；F检查输入中的语法（可能包括词法）错误，并调用出错处理器进行适当处理，下边简单介绍简单介绍语法错误处理的基本原则，而在以后的讨论中忽略此问题。 43.1 语法分析的若干问题语法分析的若干问题F语法错误的处理原则语法错误的处理原则1.源程序中可能出现的错误 两类：语法错误语法错误和语义错误语义错误词法错误如非法字符或拼写错关键字、标识符等 intege20times

3、语法错误指结构出错，如少分号、begin/end不配对等beginx:=a+by:=x;静态语义错误：如类型不一致、参数不匹配等a,b:integer;x:array1.10 of integer;x:=a+b;动态语义错误(逻辑错误)：如死循环、除数为变量零等while (t) .;a:=a/b;53.1 语法分析的若干问题语法分析的若干问题 大多数错误的诊断和恢复集中在语法分析阶段。一个原因是大多数错误是语法错误，另一个原因是语法分析方法的准确性，它们能以非常有效的方法诊断语法错误。编译时想要准确诊断语义或逻辑错误有时是很困难的。 2.语法错误处理的目标对语法错误的处理，一般希望达到以下基

4、本目标：清楚而准确地报告错误的出现，地点正确、不漏报、不错报也不多报；迅速地从每个错误中恢复过来（以便分析继续进行）；不应使对语法正确的源程序的分析速度降低太多。63.1 语法分析的若干问题语法分析的若干问题3.语法错误的基本恢复策略 紧急方式恢复紧急方式恢复：抛弃若干输入，直到遇到同步记号。短语级恢复短语级恢复：采用串替换的方式对剩余输入进行局部纠正（抛弃插入）。出错产生式出错产生式：用出错产生式捕捉错误（预测错误）。预置型的短语级恢复方式。全局纠正全局纠正：对错误输入序列x，找相近序列y，使得x变换成y所需的修改、插入、删除次数最少。73.1 语法分析的若干问题语法分析的若干问题例3.1

5、下述两条是有语法错误的语句，其中第一条赋值句结束时忘记加分号，采用紧急恢复方式和短语级恢复方式的可能结果分别如下所示。x := a + by := c + d;紧急方式紧急方式： x := a + b + d; - 丢弃b后若干记号，直到遇到+短语级恢复短语级恢复：x := a + b; - 加入分号，使之成为一个赋值句 y := c + d;83.2 上下文无关文法上下文无关文法(CFG)FCFG的定义与表示的定义与表示上下文无关文法，Context Free Grammar，CFG定义定义3.1 CFG是一个四元组：G =（N，T，P，S），其中（1） N是非终结符非终结符（Nonterm

6、inals）的有限集合；（2） T是终结符终结符（Terminals）的有限集合，且NT=；（3） P是产生式产生式（Productions）的有限集合，形如：A，其中AN（左部），(NT)*（右部），若=，则称A为空产生式（也可以记为A ）；（4） S是非终结符，称为文法的开始符号开始符号（Start symbol）。 93.2 上下文无关文法上下文无关文法(CFG)例3.2 简单算术表达式的上下文无关文法可表示如下：N = ET = +，*，(，)，-，idS = EP: E E + E（1） E E * E（2）E （E）（3） (G3.1)E -E（4）E id（5） 1. 产生式的一

7、般读法记号 读作“定义为定义为”或者“可导出可导出”。 “E E + E” 表述为“算术表达式定义为两个算术表达式相加”；或者“一个算术表达式加上另一个算术表达式，仍然是一个算术表达式”。103.2 上下文无关文法上下文无关文法(CFG)2. 由产生式集表示CFG前提前提：若文法正确结论结论：文法开始符号S是第一个产生式的左部；N是可以出现在产生式左边符号的记号集合；T是绝不出现在产生式左边符号的记号集合；P: E E + E（1）E E * E（2）E （E）（3）E -E（4）E id（5）产生式表示也被称为巴克斯范式巴克斯范式（Backus-Naur Form，BNF），其中用:=表示S

8、=EN=ET=+，*，(，)，-，id113.2 上下文无关文法上下文无关文法(CFG)3.终结符与非终结符书写上的区分(a) 用大小写大小写区分： E id(b) 用 区分： E id E E + E(c) 用区分： + 教材约定：大写英文字母A、B、C表示非终结符； 小写英文字母a、b、c表示终结符； 小写希腊字母、表示任意文法符号序列123.2 上下文无关文法上下文无关文法(CFG)4. 产生式的缩写形式当多个产生式的左部非终结符相同时，可合并为一个产生式。新的产生式的左部是此非终结符，右部是所有原来右部的或运算或运算（并集合）。例3.3 G3.1可以重写为如下形式：E E + E （1

9、）| E * E （2）|（E）（3） (G3.2)| -E（4）| id（5）用“|”连接的每个右部称为一个候选项，具有平等的权利。BNF如何表示？如何表示？P: E E + E (1) E E * E (2) E (E)(3) E -E(4) E id(5)133.2 上下文无关文法上下文无关文法(CFG)FCFG产生语言的基本方法推导产生语言的基本方法推导CFG（产生式）通过推导推导的方法产生语言。通俗地讲，产生式产生语言的过程是从开始符号S开始，对产生式左部的非终结符反复地使用产生式：将产生式左部的非终结符替换为右部的文法符号序列（展开产生式，用标记=表示），直到得到一个终结符序列终结

10、符序列。 例3.4 用(G3.2)产生终结符序列-(id+id)可如下：E E + E （1） | E * E （2）|（E）（3） (G3.2)| -E（4）| id（5）E = -E by(4) = -(E) by(3) = -(E+E) by(1) = -(id+E) by(5) = -(id+id) by(5)143.2 上下文无关文法上下文无关文法(CFG)定义定义3.2 利用产生式产生句子的过程中，将产生式A的右部代替文法符号序列A中的A得到的过程，称A直接推直接推导导出，记作：A=。若对于任意文法符号序列1，2，.n，均有1=2=.=n，则称此过程为零步零步或多步推导多步推导，记

11、为：1=*n，其中1=n的情况为零步推导零步推导。若1n，即推导过程中至少使用一次产生式，则称此过程为至少一步推导至少一步推导，记为：1=+n。 两点注意： ，有=*，即推导具有自反性； 若=*，=*，则=*，即推导具有传递性。153.2 上下文无关文法上下文无关文法(CFG)定义定义3.3 由CFG G所产生的语言L(G)被定义为: L(G) = S=+ and T* ， L(G)称为上下文无关语言上下文无关语言(Context Free Language, CFL)，称为句子句子。若S=*，(NT)*，则称为G的一个句型句型。定义定义3.4 在推导过程中，若每次直接推导均替换句型中最左边的

12、非终结符，则称为最左推导最左推导，由最左推导产生的句型被称为左句型左句型。类似可定义最右推导最右推导与右句型右句型，最右推导也被称为规范推导规范推导。E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 12 3 4 5 66是句子，所有i (i=1.6)均是句型。163.2 上下文无关文法上下文无关文法(CFG)F推导、分析树与语法树推导、分析树与语法树E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 推导产生句子的方式不直观。分析树分析树是推导的图形直观表示图形直观表示，同时反映语言结构的实质和推导过程。 定义定义3.

13、5 对CFG G的句型，分析树被定义为具有下述性质的一棵树。（1）根由开始符号所标记；（2）每个叶子由一个终结符、非终结符、或标记；（3）每个内部结点由一个非终结符标记；（4）若A是某内部节点的标记，且X1，X2，.，Xn是该节点从左到右所有孩子的标记，则AX1X2.Xn是一个产生式。若A，则标记为A的结点可以仅有一个标记为的孩子。173.2 上下文无关文法上下文无关文法(CFG)分析树与语言和文法的关系：F每一直接推导(每个产生式)，对应一棵仅有父子关系的子树，即产生式左部非终结符“长出”右部的孩子；F分析树的叶子，从左到右构成G的一个句型。若叶子仅由终结符标记，则构成一个句子。例3.5 再

14、考察-(id+id)的推导过程。E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 最左推导和最右推导的中间过程对应的分分析树可能不同析树可能不同，但最终的分析树相同，因为最终是同一个句子183.2 上下文无关文法上下文无关文法(CFG)分析树既反映了产生句型的推导过程，又反映了句型的结构。在更多的情况下，仅关注句型结构，而忽略推导过程。定义定义3.6 对CFG G的句型，表达式的语法树语法树被定义为具有下述性质的一棵树:（1） 根与内部节点由表达式中的操作符标记；（2） 叶子由表达式中的操作数标记；（3）用于改变运算优先级和结合性的括弧，被隐含在语法树的结

15、构中。语法树与分析树的最根本区别最根本区别在于内部节点（包括根节点）： 分析树的内部节点是非终结符； 语法树的内部节点是操作符（运算符）； 或者说语法树中省略了反映分析过程的非终结符。193.2 上下文无关文法上下文无关文法(CFG)例3.6 句子-(id+id)和句型if C then s1 else s2分析树：左部非终结符“产生”右部文法符号序列；语法树：操作符(运算)作用于操作数(运算对象)；习惯上它们分别被称为具体语法树具体语法树和抽象语法树抽象语法树。 203.2 上下文无关文法上下文无关文法(CFG)F二义性与二义性的消除二义性与二义性的消除二义性问题：一个句子可能对应多于一棵分

16、析树例3.7 文法G3.2为EE+E | E*E |（E）| -E | id句子id+id*id和id+id+id可能的分析树有：213.2 上下文无关文法上下文无关文法(CFG)定义定义3.7 若文法G对同一句子产生不止一棵分析树，则称G是二二义义的。 原因原因：在产生句子的过程中某些直接推导有多于一种选择注意注意：1. 一个句子有多于一棵分析树，仅与文法和句子有关，与采用的推导方法无关；2. 文法中缺少对文法符号优先级和结合性的规定。“悬空（悬空（dangling）else”问题S if C then S(1)| if C then S else S(2)| id := E(3)(G3.3

17、)C E = E | E E(4).(6)E E + E | - E | id | n(7).(10)223.2 上下文无关文法上下文无关文法(CFG)例3.8 条件语句 if x0 then x:=5 else x:=-5if x0 then x:=5 else x:=-5else与离它远的与离它远的then匹配匹配if x0 then x:=5 else x:=-5else与离它近的与离它近的then匹配匹配233.2 上下文无关文法上下文无关文法(CFG)文法二义不能说明它所产生的语言一定是二义的。消除语言二义有两种方法： 改写二义文法为非二义文法； 规定二义文法中符号的优先级和结合性。

18、 改写改写例3.9 与G3.2等价的非二义文法：E E + T | TT T * F | F(G3.4)F （E）| -F | id问题问题：如何改写？EE+E | E*E |（E） (G3.2) | -E | id24上次课总结上次课总结F语法分析器作用F语法错误处理FCFG的定义与表示F推导(最左、最右推导)、句子、句型F分析树F语法树F二义性与二义性的消除原因：文法符号缺乏优先级和结合性消除方法 改写二义文法为非二义文法 为文法符号规定优先级和结合性 改变语言的结构或书写方式253.2 上下文无关文法上下文无关文法(CFG)观察结论观察结论：F新引入的非终结符限制每一步直接推导均有唯一选

19、择；F最终分析树的形状，仅与文法有关，而与推导方法无关；F非终结符的引入，增加了推导步骤(分析树增高)；F越接近S的文法符号的优先级越低。(如EE+T)F对于AA，若A在终结符左边出现(即终结符在中)，则A产生式具有左结合性质。改写二义文法的关键步骤关键步骤：1. 引入新的非终结符，增加一个子结构并提高一级优先级；2. 递归非终结符在终结符左边，运算具有左结合性，否则具有右结合性。263.2 上下文无关文法上下文无关文法(CFG)例3.10 改写二义文法G3.2为G3.4 ： 引入新的非终结符，增加一个子结构并提高一级优先级； 递归非终结符在终结符左边，运算具有左结合性，否则具有右结合性。 1

20、.优先级： +*( ), -, id2.结合性： 左结合+, *右结合-无结合id3.非终结符与运算：E: +（E产生式，左递归）T: *（T产生式，左递归）F: -, ( ), id（F产生式，右递归）E E + E(1) | E * E(2) |（E）(3) | -E(4) | id(5)E E + T | TT T * F | FF (E) | -F | id273.2 上下文无关文法上下文无关文法(CFG)“悬空悬空else”问题：在复合if语句中，可能then多于else，使得else不知与哪个then结合。一般原则是右结合，即else与左边最靠近的then结合。改写文法的根据是将S

21、分为完全匹配完全匹配(MS)和不完全匹配不完全匹配(UMS)两类，并且在UMS中规定else右结合。 S MS(1) | UMS(2)MS if C then MS else MS(3)| id := E(4)UMS if C then S(5)| if C then MS else UMS(6) C E = E | E E(7).(9)E E + T | T(10).(11)T (E) | -T | id | n(12).(15)S if C then S| if C then S else S| id := EC E=E | EEE E+E | -E | id | n283.2 上下文无关

22、文法上下文无关文法(CFG)S MS | UMS(1).(2)MS if C then MS else MS | id := E(3).(4)UMS if C then S | if C then MS else UMS(5).(6)(G3.5)C E = E | E E(7).(9)E E + T | T(10).(11) T （E） | -T | id | n(12).(15)if x0 then x:=5 else x:=-5293.2 上下文无关文法上下文无关文法(CFG)S MS | UMS(1).(2)MS if C then MS else MS | id := E(3).(4)

23、UMS if C then S | if C then MS else UMS(5).(6)(G3.5)C E = E | E E(7).(9)E E + T | T(10).(11) T （E） | -T | id | n(12).(15)if x0 then x:=5 else x:=-5303.2 上下文无关文法上下文无关文法(CFG) 规定优先级和结合性规定优先级和结合性二义文法的优点：1. 比非二义文法容易理解；2. 分析效率高(分析树低，直接推导步骤少)。YACC为二义文法规定优先级和结合性： %left +%left *%right -E E + E| E * E|（E）| -E

24、| idE E + T | TT T * F | FF (E) | -F | id313.2 上下文无关文法上下文无关文法(CFG)修改语言的语法修改语言的语法1. 明确给出结束标志，如Ada中用end if，于是有：if x0 then x:=5; end if; else x:=-5; end if;if x0 then x:=5; else x:=-5; end if; end if;if x0then x:=5;end if;else x:=-5;end if;2. 给表达式加括号，如Pascal中逻辑和算术运算：(a+b)(c*d) if x0then x:=5;else x:=-5

25、;end if;end if;323.3 语言与文法简介语言与文法简介文法的重要作用：1. 给出精确、易于理解的语言结构说明；2. 以文法为基础的语言，便于加入新的、或修改、删除旧的语言结构；3. 有些类别的文法，可以自动生成高效的分析器。本节从理论的角度对文法进行简单地讨论。讨论建立在形式语形式语言与自动机言与自动机的理论之上，且仅引用结论而忽略数学的证明，有兴趣的同学可以参阅相关文献。希望通过本节的讨论，对文法的分类和它们在编译器构造中的作用有一定的了解，同时初步窥探计算机科学的理论基础。333.3 语言与文法简介语言与文法简介F正规式与上下文无关文法正规式与上下文无关文法1.正规式到CF

26、G的转换推论推论3.1 正规式描述的语言结构均可用CFG描述，反之不一定从正规式到CFG的对应关系： 构造正规式的NFA；若0为初态，则A0为开始符号；对于move(i,a)=j，引入产生式AiaAj；对于move(i,)=j，引入产生式 AiAj；若i是终态，则引入产生式Ai 。例3.11 从正规式r=(a|b)*abb的NFA构造CFG： A0 aA0|bA0|aA1A1 bA2A2 bA3A3 经验的方法：A HTH | Ha | HbT abb343.3 语言与文法简介语言与文法简介2.为什么用正规式而不用CFG描述词法？ 词法规则简单，用正规式描述已足够； 正规式的表示比CFG更直观

27、、简洁、易于理解； 有限自动机的构造比下推自动机简单，且分析效率高； 区分词法和语法，为编译器前端的模块划分提供方便。 贯穿词法分析和语法分析始终的思想： 语言的描述和语言的识别是表示一个语言的两个不同侧面，二者缺一不可；（语言、文法、自动机） 用正规式和CFG描述的语言，对应的识别方法（自动机）不同； 正规式适合描述线性结构线性结构，如标识符、关键字、注释等；CFG适合描述具有嵌套（层次）性质的非线性结构非线性结构，如不同结构的句子if-then-else、while-do等。353.3 语言与文法简介语言与文法简介F上下文有关语言上下文有关语言Context Sensitive Langu

28、age, CSL 程序设计语言中除了CFG可以描述的结构之外，还有一些是CFG无法描述的所谓上下文有关的结构。典型的这类语言结构包括：变量的声明与引用、过程调用时形参与实参的一致性检查等。描述它们的文法被称为上下文有关文法（Context Sensitive Grammar, CSG）。363.3 语言与文法简介语言与文法简介例3.12 不能用不能用CFG描述描述的语言： L1=c|(a|b)*(标识符声明与引用一致性的抽象)L2=anbmcndm|n1和m1(形参与实参一致性的抽象)L3=anbncn|n1(计数问题的抽象)相近的相近的CFL：L1=cr|(a|b)*L2=anbmcmdn|

29、n1, m1L2=anbncmdm|n1, m1L3=ambmcn|m, n1SaSa|bSb|cSaSd|aAd AbAc|bcSAB AaAb|ab BcBd|cdAAC AaAb|ab CcC|c373.3 语言与文法简介语言与文法简介计数问题计数问题L3=anbncn|n1CSLL3=ambmcn|m,n1CFLL3=akbmcn|k，m，n1正规集命题命题：L3不是正规集，因为构造不出可以识别L3的DFA。证明：证明：（反证）假设L3是正规集，则可构造n个状态的DFA D，它接受L3； 考察D读完，a，aa，.，an，分别到达S0，S1，.，Sn，共有n+1个状态。根据鸽巢原理鸽巢原

30、理，序列中至少有两个状态相同，设Si=Sj（ji），因为aibickL3，所以存在路径aibick。但是D中也有路径ajbick，矛盾。故L3不是正规集。AAC AaAb|ab CcC|c ?a+b+c+S0SiSkfaibickaj-i383.3 语言与文法简介语言与文法简介F形式语言与自动机简介形式语言与自动机简介 定义定义3.8 若文法G=(N，T，P，S)的每个产生式中，均有(NT)*，且至少含有一个非终结符，(NT)*，则称G为0型文法。对0型文法施加以下第i条限制，即得到i型文法。1. G的任何产生式（S除外）满足|；2. G的任何产生式形如A，其中AN，(NT)*；3. G的任何

31、产生式形如Aa或者AaB(或者ABa)，其中A和BN，aT。 文文 法法语语 言言自自 动动 机机短语文法(0型)短语结构语言图灵机CSG (1型)CSL线性界线自动机CFG (2型)CFL下推自动机正规文法(3型)正规集有限自动机393.3 语言与文法简介语言与文法简介再考察L3：L3=anbncn|n1例3.15 L3可用下述CSG描述：SaSBC(1)SaBC(2)CBBC(3)aBab(4)bBbb(5)bCbc(6)cCcc(7)CSG、CFG、正规式能力递减，但是能力越强的文法，其文法设计和自动机的构造越困难，因此语法分析仅用到CFG（除特别指出，文法即指CFG ）句子句子akbk

32、ck 的推导：的推导：S =.= ak-1S(BC)k-1(by 1)= ak(BC)k (by 2)=.= akBkCk(by 3)= akbBk-1Ck(by 4)=.= akbkCk(by 5)= akbkcCk-1(by 6)=.= akbkck(by 7)403.4 自上而下语法分析自上而下语法分析F二义性与二义性的消除原因：文法符号缺乏优先级和结合性消除方法 改写二义文法为非二义文法 为文法符号规定优先级和结合性 改变语言的结构或书写方式F正规式到CFG的转换F上下文有关语言F形式语言与自动机简介F自上而下分析：自上而下/从左到右413.4 自上而下语法分析自上而下语法分析F自上而

33、下分析的一般方法自上而下分析的一般方法用推导的方法分析输入序列：对输入序列，从S开始进行最左推导最左推导，直到得到一个合法句子或非法结构；从左到右从左到右扫描输入序列，试图用一切可能的方法，自上自上而下而下建立它的分析树；一种试探试探的过程，反复使用不同产生式，谋求与输入序列匹配；例3.16 用下述文法分析输入序列=cad：S cAdA ab| a423.4 自上而下语法分析自上而下语法分析问题：问题： 若有A1|2，公共左因子公共左因子，则会虚假匹配和大量回溯；造成分析效率低、语义动作难以恢复、以及出错位置的报告不确切等。 若有AA，左递归左递归，则死循环使分析无法进行下去。 重写文法：重写

34、文法： 消除左递归，以避免陷入死循环； 提取左因子，以避免回溯。F 消除左递归消除左递归定义定义3.9 若文法G中的非终结符A，对某个文法符号序列存在推导A=+A，则称G是左递归左递归的。若G中有形如AA的产生式，则称该产生式对A直接左递归直接左递归。433.4 自上而下语法分析自上而下语法分析1.消除文法的直接左递归消除文法的直接左递归考虑： AA|产生的语言：*替换为：AA AA|消除了一个直接左递归算法算法3.1 消除直接左递归输入G中所有的A产生式(含直接左递归)输出等价的不含直接左递归的G方法首先，整理A产生式为如下形式：A A1|A2|.|Am|1|2|.|n其中i非空，j均不以A

35、开始。用下述产生式代替A产生式A 1 A |2 A | .|n A A 1 A | 2 A | . | m A |若i为空，则形成一个有环的A产生式443.4 自上而下语法分析自上而下语法分析例3.17 消除算术表达式文法的直接左递归：E E + E | E * E| ( E ) | - E | id(G3.2)E TE(1)E+TE|(2)T FT(3) (G3.4)T*FT|(4)F (E)|-F|id(5).(7)EE+T|TTT*F|F (G3.4)F(E)|-F|id453.4 自上而下语法分析自上而下语法分析2. 消除文法的左递归消除文法的左递归 算法算法3.2 消除左递归输入无回

36、路文法G输出无左递归的等价文法G方法将非终结符合理排序：A1，A2，.，An;for i in 2.n loop for j in 1.i-1loop 用Aj1|2|.|k的右部替换每个形如AiAj产生式中的Aj,得到新产生式：Ai1|2|.|k;消除Ai产生式中的直接左递归; end loop; end loop; 核心思想：核心思想：将不是直接左递归不是直接左递归的非终结符右部展开到其他产生式中注意：注意：若G产生句子的过程中出现A=+A，则无法消除左递归463.4 自上而下语法分析自上而下语法分析核心思想：核心思想：将不是直接左递归的符号右部展开到其他产生式关键步骤：关键步骤：合理排序非

37、终结符：A1，A2，.，An;用Aj1|2|.|k右部替换AiAj中的Aj，得到Ai1|2|.|k；消除Ai产生式中的直接左递归；例3.18 用算法3.2消除文法SAa|b AAc|Sd|中的左递归。 将S的右部展开在A中，得到：AAc|Aad|bd| 消除新产生式中的直接左递归，得到：S Aa | bA bdA | A(G3.8)A cA | adA | 473.4 自上而下语法分析自上而下语法分析3.提取左因子提取左因子 S cAdA ab | a当不确定用A产生式的哪个候选项替换A时，可以重写A产生式来推迟这种决定，直到看见足够的输入，能正确决定所需选择为止。这一过程被称为提取左因子提取

38、左因子，它类似于有限似于有限自动机的确定化自动机的确定化。 将：将：A 1|2替换为：替换为： A AA1|2等价于：等价于： A (1|2 )483.4 自上而下语法分析自上而下语法分析算法算法3.3 提取文法的左因子输入文法G输出等价的无左因子文法G方法重复过程，直到所有A产生式候选项中不再有公共前缀：重排A产生式：A1|2| . |n|；并用 AA| 和 A1|2| .|n取代原A产生式。例3.20 考察悬空else文法：SiCtS | iCtSeS | a Cb 用算法3.3提取左因子，得到如下文法：S iCtSS | aS eS | C b既有左递归又含左因子？既有左递归又含左因子？

39、先消除左递归。先消除左递归。493.4 自上而下语法分析自上而下语法分析4.递归下降分析递归下降分析 直接以程序的方式模拟产生式产生语言的过程； 每个产生式对应一个子程序，产生式右边的非终结符对应子程序调用，终结符则与输入序列匹配； 它对文法的限制是不能有公共左因子和左递归； 它是一种非形式化的方法，只要能写出子程序，用什么样的方法和步骤均可。一种稳妥的方法 构造文法的状态转换图并且化简； 将转换图转化为EBNF表示； 从EBNF构造子程序。 503.4 自上而下语法分析自上而下语法分析1. 构造状态转换图且化简构造状态转换图且化简递归下降分析的文法： L E ; L | E E + T |

40、E - T | T T T * F | T / F | T mod F | F F ( E ) | id | num每个非终结符对应一个状态转换图： 为非终结符A建立一个初态和一个终态； 为AX1X2.Xn构造从初态到终态的路径，边标记为X1，X2，.，Xn。 根据识别同一集合的原则，化简转换图。消除左递归后的等价文法: L E ; L | E T E E + T E | - T E | T F T T * F T | / F T | mod F T | F ( E ) | id | num513.4 自上而下语法分析自上而下语法分析L E ; L | E T EE + T E | - T E

41、 | T F TT * F T | / F T | mod F T | F ( E ) | id | num523.4 自上而下语法分析自上而下语法分析状态图的化简原则 标记为A的边可等价为标记的边转向A转换图的初态； 边连接的两个状态可以合并（FAFA的确定化思想的确定化思想）； 标记相同的路径可以合并； 不可区分的状态可以合并（DFADFA的最小化思想的最小化思想）。533.4 自上而下语法分析自上而下语法分析2.文法的扩展文法的扩展BNF（EBNF）表示）表示 ：重复0或若干次（while） ：可选择（if或while） |：括弧( )之内的或关系（case） ( )：改变运算的优先级和

42、结合性EBNF表示：L E; E T ( + | - ) T T F ( * | / | mod ) F F ( E ) | id | num543.4 自上而下语法分析自上而下语法分析3.递归下降子程序递归下降子程序procedure L isbegin lookahead := lexan; while (lookahead/=eof)loop E; match(;);end loop;end L;procedure E isbegin T; while lookahead(+|-) loop match(lookahead); T; end loop;end E;procedure F

43、isbegin case lookahead is ( : match(); E; match(); id : match(id); num : match(num); others : error(syntax error2); end case;end F;L E; E T ( + | - ) T T F ( * | / | mod ) F F ( E ) | id | num 553.4 自上而下语法分析自上而下语法分析如果不消除左递归不消除左递归：若存在产生式E E + id，则E的递归下降子程序如下：procedure E isbegin E; match(+);-永不执行永不执行

44、match(id);-永不执行永不执行end E;此程序永不停机。同样，文法中的公共左因子公共左因子也会给递归下降分析造成困难。563.4 自上而下语法分析自上而下语法分析F预测分析器预测分析器非递归非递归预测分析器的工作模式预测分析器的核心概念：1. 分析方法：格局与格局变换2. 分析表+驱动器（模拟算法）3. 预测分析表的构造4. LL（文法、语言、分析器）573.4 自上而下语法分析自上而下语法分析1.预测分析表预测分析表L E ; L | E TEE + T E | - T E | T FTT * F T | / F T | mod F T | F (E)|id|num 分析表MA,

45、a的内容：若当前栈顶是非终结符A，下一输入终结符是a，则MA, a指示下一步动作。idnum+-*/mod();#LE;LE;LE;LETETETEE+TE-TETFTFTFTT*FT/FT mod FTFidnum(E)583.4 自上而下语法分析自上而下语法分析2.工作方式工作方式放幻灯的方式：每张“幻灯片”称为一个格局。 从初始格局开始，经过格局变化，最终到达接收格局，表明分析成功；或者到达出错格局，表明发现语法错误。格局格局：三元组，(栈内容top，剩余输入ip，改变格局的动作)改变格局的动作改变格局的动作： 匹配终结符：若top = ip(但#)，则pop且next(ip)； 展开非

46、终结符：若top = X且MX, a = (X)，则pop且push()； 报告分析成功：若top = ip = #，则分析成功并结束； 报告出错：其它情况，调用错误恢复例程。593.驱动器算法驱动器算法算法算法3.4 非递归的预测分析输入输入序列和文法G的预测分析表M输出若L(G)，得到的一个最左推导；否则指出一个错误方法初始格局为: （#S，#，分析器的第一个动作）令ip指向#中的第一个终结符，top指向S;loop x := top; a := ip;ifx Tthenifx = a then pop(x); next(ip);- 匹配终结符else error(1);end if; -

47、 出错：栈顶终结符不是aelseifMx, a = XY1Y2.Ykthen pop(X); push(YkYk-1.Y2Y1);-展开非终结符else error(2);endif;- 出错：产生式不匹配end if;exit when x = #;- 分析成功end loop;604.用预测分析器分析句子用预测分析器分析句子栈栈当前剩余输入当前剩余输入动作动作含义含义#Lid+id*id;#pop(L), push(E;L)(LE;L)#L;Eid+id*id;#pop(E), push(TE)(ETE)#L;ETid+id*id;#pop(T), push(FT)(TFT)#L;ETFi

48、d+id*id;#pop(F), push(id)(Fid)#L;ETidid+id*id;#pop(id), next(ip)id#L;ET+id*id;#pop(T)(T)#L;E+id*id;#pop(E), push(+TE)(E+TE)#L;ET+id*id;#pop(+), next(ip)+#L;ETid*id;#pop(T), push(FT)(TFT)#L;ETFid*id;#pop(F), push(id)(Fid)#L;ETidid*id;#pop(id), next(ip)id#L;ET*id;#pop(T), push(*FT)(T*FT)#L;ETF*id;#pop

49、(*), next(ip)*#L;ETFid;#pop(F), push(id)(Fid)#L;ETidid;#pop(id), next(ip)id#L;ET;#pop(T)(T)#L;E;#pop(E)(E)#L;#pop(;), next(ip);#L#pop(L)(L) #正确结束正确结束61上次课总结上次课总结F自上而下分析：自上而下/从左到右(不能有左递归/左因子)F消除左递归F提取左因子F递归下降分析F预测分析器下推自动机符号栈、分析表、驱动器格局与格局的变换623.4 自上而下语法分析自上而下语法分析F构造预测分析表构造预测分析表1.首先构造FIRST集合与FOLLOW集合；2

50、.然后根据两个集合构造预测分析表。 定义定义3.10 文法符号序列的FIRST集合为:FIRST()= a |=*a.，aT，若=*，则FIRST()定义定义3.11 非终结符A的FOLLOW集合如下:FOLLOW(A) = a |S=*.Aa.，aT，若A是某句型的最右符号，则#FOLLOW(A)。通俗地讲，的FIRST集合就是从开始可导出的文法符号序列中的开头终结符。而A的FOLLOW集合，就是从开始符号可以导出的所有含A的文法符号序列中A之后的终结符。例如：FIRST(E)= (，id, num ，FOLLOW(E)= )，; L E ; L | E TEE + T E | - T E

51、| T FTT*F T|/FT|mod FT|F (E) | id | num 633.4 自上而下语法分析自上而下语法分析算法算法3.5 计算X的FIRST集合输入文法符号X输出X的FIRST集合方法应用下述规则： 若XT，则FIRST(X)=X； 若X是非终结符且有X ，则加入到FIRST(X)； 若X是非终结符且有XY1Y2.Yk，并设Y0=，Yk+1=。那么对所有对所有j(0jk)，若，若aFIRST(Yj+1)且且FIRST(Yj),则加入a到FIRST(X)。FIRST(X1X2.Xn)的计算方法与算法3.5中步骤3类似，即是所有FIRST(Xi) (i=1,2,.,k)的并集，其

52、中k为第一个具有性质不属于FIRST(Xk)或kn的文法符号，若kn，则FIRST(X1X2.Xn) 考虑：考虑：FIRST(E)=FIRST(TE)=FIRST(FTE)= (，id, num L E ; L | E TEE + T E | - T E | T FTT*F T|/FT|mod FT|F (E) | id | num 643.4 自上而下语法分析自上而下语法分析算法算法3.6 计算所有非终结符的FOLLOW集合输入文法G输出G中所有非终结符的FOLLOW集合方法应用下述规则: 加入#到FOLLOW(S)，其中S是开始符号，#是输入结束标记 若有产生式AB，则除外，FIRST()

53、的全体加入到的全体加入到FOLLOW(B)。 若有产生式AB或AB而FIRST()，则FOLLOW(A)的全体加入到的全体加入到FOLLOW(B)。 步骤3的理解：若 S =*Aaa紧跟A之后则 =*Baa也紧跟B之后 因为 FIRST() 使得B成为A产生式右部最右的文法符号 即 对任何aFOLLOW(A)，均有aFOLLOW(B)，反之不然反之不然。653.4 自上而下语法分析自上而下语法分析例3.22 计算非终结符的FIRST与FOLLOW。提示：提示：自下而上计算FIRST，自上而下计算FOLLOWFIRST(F) = ( id numFIRST(T) = * / mod FIRST(

54、T) = FIRST(F) = ( id numFIRST(E) = + - FIRST(E) = FIRST(T) = FIRST(F) = ( id numFIRST(L) = FIRST(E) = ( id num FOLLOW(L) = #FOLLOW(E) = ) ;FOLLOW(E) = ) ;FOLLOW(T) = + - ; )FOLLOW(T) = + - ; )FOLLOW(F) = + - * / mod ) ;L E ; L | E TEE + T E | - T E | T FTT*F T|/FT|mod FT|F (E) | id | num 663.4 自上而下语

55、法分析自上而下语法分析算法算法3.7 构造预测分析表输入文法G输出分析表M方法应用下述规则 对文法的每个产生式A，执行2和3； 对FIRST()的每个终结符a，加入到MA，a； 若FIRST()，则FOLLOW(A)每个终结符b（包括#），加入到MA，b； M中其它没有定义的条目均是error。MA，a 指导下一步动作指导下一步动作：1.若当前栈顶为A，当前输入为a，则规则2表示下一步动作是展开A，因为aFIRST()，展开后下一次正好匹配a。 2.若当前栈顶为A，当前输入为b且bFOLLOW(A)，则规则3表示下一步动作是展开A，即栈顶弹出A，继续分析A之后的部分，因为bFOLLOW(A)，

56、弹出A后下一次正好匹配A的后继b673.4 自上而下语法分析自上而下语法分析FIRST(F/T/E)= ( id numFIRST(T) = * / mod FIRST(E) = + - FIRST(L) = ( id numFOLLOW(L) = #FOLLOW(E/E)= ) ;FOLLOW(T/T)= + - ; )FOLLOW(F) = + - * / mod ) ;idnum+-*/mod();#LEETTF 对FIRST()的每个终结符a，加入到MA，a； 若FIRST()，则FOLLOW(A)每个终结符b(包括#)，加入到MA，b；E;LE;LE;LTETETE+TE-TEFTF

57、TFT*FT /FTmod FTidnum(E)L E ; L | E TEE + T E | - T E | T FTT*F T|/FT|mod FT|F (E) | id | num 683.4 自上而下语法分析自上而下语法分析FLL(1)文法文法MA,a的作用：指导产生式产生句子（指导推导）问题：问题：是否分析表MA,a中都最多有一个条目？例3.23 二义文法的预测分析表： 文法： SiCtSS|aSeS|CbFIRST与FOLLOW集合：FIRST(C) = bFIRST(S) = , eFIRST(S) = i, a FOLLOW(S) = #, eFOLLOW(S) = #, eF

58、OLLOW(C) = tabeit#SSCaiCtSSesb693.4 自上而下语法分析自上而下语法分析定义定义3.12 文法G被称为是LL(1)文法，当且仅当为它构造的预测分析表中不含多重定义的条目不含多重定义的条目。由此分析表所组成的分析器被称为LL(1)分析器，所分析的语言被称为LL(1)语言。第一个L代表从左到右扫描从左到右扫描输入序列，第二个L表示产生最左推导最左推导，1表示在确定每一步动作时向向前看一个终结符前看一个终结符。 判定判定LL(1)文法的方法文法的方法：a)构造分析表； b)无需构造分析表。 推论推论3.2 G是LL(1)的，当且仅当G的任何两个产生式A|满足： 对任何

59、终结符a，和不能同时推导出以a开始的串； 和最多有一个可以推导出； 若=*,则不能导出以FOLLOW(A)中终结符开始的任何串。703.4 自上而下语法分析自上而下语法分析 对FIRST()的每个终结符a，加入到MA，a； 若FIRST()，则FOLLOW(A)每个终结符b(包括#)，加入到MA，b；证明：证明：1.若条件若条件1不满足不满足，即存在终结符a，和同时推导出以a开始的串，则根据算法3.7步骤2，MA，a中有多重定义A和A；2.若条件若条件2不满足不满足，即和均可推出串，则根据算法3.2步骤3，任何属于FOLLOW（A）的终结符b(包括#)，MA，b中有多重定义A和A ；3.若条件

60、若条件3不满足不满足，即存在终结符b，它既在FOLLOW(A)中，又在FIRST()中，则算法3.2步骤2把条目A加入到MA，b中，而步骤3又把条目A加入到MA，b中，即MA，b 中有多重定义A和A 。713.4 自上而下语法分析自上而下语法分析 根据推论3.2，有左递归和左因子的文法不是LL(1)文法，二义文法也不是LL(1)文法。文法(G3.4)不是LL(1)的，因为不满足条件1。文法(G3.4)是LL(1)的，因为三个条件均满足。EE+T|TTT*F|F (G3.4)F(E)|-F|idLL(1)文法的弱点：1. 文法难写、难懂； 2. 适应范围有限，往往写不出有些语言的LL(1)文法。