第三章 语法分析

1第三章语法分析词法分析：字母是元素，组成字符串，记号的集合，线性结构语法分析：记号是元素，组成句子，句子的集合，树结构语法的双重含义语法规则：上下文无关文法(子集－LL文法、LR文法)语法分析：下推自动机(LL或LR分析器)，自上而下、自下而上分析主要内容语法分析的若干问题上下文无关文法自上而下分析自下而上分析上机：DBMS的设计与实现—SQL的语法分析器23.1语法分析的若干问题语法分析器的作用语法分析器是编译器前端的重要组成部分，许多编译器，特别是由自动生成工具构造的编译器，往往其前端的中心部件就是语法分析器。语法分析器在编译器中的位置和作用：33.1语法分析的若干问题语法分析器的两个重要作用：根据词法分析器提供的记号流，为语法正确的输入构造分析树（或语法树），这是本章重点，在以后各节中详细讨论；检查输入中的语法（可能包括词法）错误，并调用出错处理器进行适当处理，下边简单介绍语法错误处理的基本原则，而在以后的讨论中忽略此问题。43.1语法分析的若干问题语法错误的处理原则源程序中可能出现的错误

两类：语法错误和语义错误词法错误如非法字符或拼写错关键字、标识符等

@ intege 20times语法错误指结构出错，如少分号、begin/end不配对等

begin x:=a+b y:=x;静态语义错误：如类型不一致、参数不匹配等

a,b:integer; x:array[1..10]ofinteger; x:=a+b;动态语义错误(逻辑错误)：如死循环、除数为变量零等

while(t){...}; a:=a/b;53.1语法分析的若干问题

大多数错误的诊断和恢复集中在语法分析阶段。一个原因是大多数错误是语法错误，另一个原因是语法分析方法的准确性，它们能以非常有效的方法诊断语法错误。编译时想要准确诊断语义或逻辑错误有时是很困难的。语法错误处理的目标对语法错误的处理，一般希望达到以下基本目标：清楚而准确地报告错误的出现，地点正确、不漏报、不错报也不多报；迅速地从每个错误中恢复过来（以便分析继续进行）；不应使对语法正确的源程序的分析速度降低太多。63.1语法分析的若干问题语法错误的基本恢复策略紧急方式恢复：抛弃若干输入，直到遇到同步记号。短语级恢复：采用串替换的方式对剩余输入进行局部纠正（抛弃＋插入）。出错产生式：用出错产生式捕捉错误（预测错误）。预置型的短语级恢复方式。全局纠正：对错误输入序列x，找相近序列y，使得x变换成y所需的修改、插入、删除次数最少。73.1语法分析的若干问题[例3.1]下述两条是有语法错误的语句，其中第一条赋值句结束时忘记加分号，采用紧急恢复方式和短语级恢复方式的可能结果分别如下所示。

x:=a+b y:=c+d;

紧急方式：x:=a+b+d; --丢弃b后若干记号，直到遇到+

短语级恢复：x:=a+b; --加入分号，使之成为一个赋值句

y:=c+d;83.2上下文无关文法(CFG)CFG的定义与表示

上下文无关文法，ContextFreeGrammar，CFG定义3.1CFG是一个四元组：

G=（N，T，P，S），其中 （1）N是非终结符（Nonterminals）的有限集合； （2）T是终结符（Terminals）的有限集合，且N∩T=Φ； （3）P是产生式（Productions）的有限集合，形如：

A→α，其中A∈N（左部），α∈(N∪T)*（右部）， 若α=ε，则称A→ε为空产生式（也可以记为A→）； （4）S是非终结符，称为文法的开始符号（Start symbol）。93.2上下文无关文法(CFG)[例3.2]简单算术表达式的上下文无关文法可表示如下：

N={E} T={+，*，(，)，-，id} S=E

P: E→E+E （1）

E→E*E （2）

E→（E） （3）(G3.1) E→-E （4）

E→id （5）产生式的一般读法 记号→读作“定义为”或者“可导出”。 “E→E+E”表述为“算术表达式定义为两个算术表达式相加”；或者“一个算术表达式加上另一个算术表达式，仍然是一个算术表达式”。103.2上下文无关文法(CFG)由产生式集表示CFG

前提： 若文法正确

结论： 文法开始符号S是第一个产生式的左部；

N是可以出现在产生式左边符号的记号集合；

T是绝不出现在产生式左边符号的记号集合；

P: E→E+E （1）

E→E*E （2）

E→（E） （3）

E→-E （4）

E→id （5） 产生式表示也被称为巴克斯范式（Backus-NaurForm，BNF），其中→用::=表示S=E N={E}T={+，*，(，)，-，id}113.2上下文无关文法(CFG)终结符与非终结符书写上的区分

(a)

用大小写区分：E→id (b)

用""区分：E→"id"E→E"+"E (c)

用<>区分：<E>→<E>+<E>

教材约定：大写英文字母A、B、C表示非终结符； 小写英文字母a、b、c表示终结符； 小写希腊字母α、β、δ表示任意文法符号序列123.2上下文无关文法(CFG)产生式的缩写形式当多个产生式的左部非终结符相同时，可合并为一个产生式。新的产生式的左部是此非终结符，右部是所有原来右部的或运算（并集合）。[例3.3]G3.1可以重写为如下形式：

E→ E+E （1）

|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)13上次课总结语法分析器作用语法错误处理CFG的定义与表示143.2上下文无关文法(CFG)CFG产生语言的基本方法－推导CFG（产生式）通过推导的方法产生语言。通俗地讲，产生式产生语言的过程是从开始符号S开始，对产生式左部的非终结符反复地使用产生式：将产生式左部的非终结符替换为右部的文法符号序列（展开产生式，用标记=>表示），直到得到一个终结符序列。[例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)153.2上下文无关文法(CFG)定义3.2

利用产生式产生句子的过程中，将产生式A→γ的右部代替文法符号序列αAβ中的A得到αγβ的过程，称αAβ直接推导出αγβ，记作：αAβ=>αγβ。若对于任意文法符号序列α1，α2，...αn，均有α1=>α2=>...=>αn，则称此过程为零步或多步推导，记为：

α1=*>αn，其中α1=αn的情况为零步推导。若α1≠αn，即推导过程中至少使用一次产生式，则称此过程为至少一步推导，记为：α1=+>αn。 两点注意：

α，有α=*>α，即推导具有自反性；若α=*>β，β=*>γ，则α=*>γ，即推导具有传递性。163.2上下文无关文法(CFG)定义3.3

由CFGG所产生的语言L(G)被定义为:L(G)={ω┃S=+>ωandω∈T*}，

L(G)称为上下文无关语言(ContextFreeLanguage,CFL)，ω称为句子。 若S=*>α，α∈(N∪T)*，则称α为G的一个句型。定义3.4

在推导过程中，若每次直接推导均替换句型中最左边的非终结符，则称为最左推导，由最左推导产生的句型被称为左句型。类似可定义最右推导与右句型，最右推导也被称为规范推导。

E=>-E=>-(E)=>-(E+E)=>-(id+E)=>-(id+id) α1 α2 α3 α4 α5 α6 α6是句子，所有αi(i=1...6)均是句型。173.2上下文无关文法(CFG)推导、分析树与语法树

E=>-E=>-(E)=>-(E+E)=>-(id+E)=>-(id+id)推导产生句子的方式不直观。分析树是推导的图形直观表示，同时反映语言结构的实质和推导过程。定义3.5

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

E=>-E=>-(E)=>-(E+E)=>-(id+E)=>-(id+id)

最左推导和最右推导的中间过程对应的分析树可能不同，但最终的分析树相同，因为最终是同一个句子193.2上下文无关文法(CFG)分析树既反映了产生句型的推导过程，又反映了句型的结构。在更多的情况下，仅关注句型结构，而忽略推导过程。定义3.6

对CFGG的句型，表达式的语法树被定义为具有下述性质的一棵树:

（1）根与内部节点由表达式中的操作符标记； （2）叶子由表达式中的操作数标记； （3）用于改变运算优先级和结合性的括弧，被隐含在语法树的结构中。 语法树与分析树的最根本区别在于内部节点（包括根节点）：分析树的内部节点是非终结符；语法树的内部节点是操作符（运算符）；或者说语法树中省略了反映分析过程的非终结符。203.2上下文无关文法(CFG)[例3.6]句子-(id+id)和句型ifCthens1elses2分析树：左部非终结符“产生”右部文法符号序列；语法树：操作符(运算)作用于操作数(运算对象)；习惯上它们分别被称为具体语法树和抽象语法树。213.2上下文无关文法(CFG)二义性与二义性的消除 二义性问题：一个句子可能对应多于一棵分析树[例3.7]文法G3.2为 E→E+E|E*E|（E）|-E|id

句子id+id*id和id+id+id可能的分析树有：223.2上下文无关文法(CFG)定义3.7

若文法G对同一句子产生不止一棵分析树，则称G是二义的。

原因：在产生句子的过程中某些直接推导有多于一种选择注意：一个句子有多于一棵分析树，仅与文法和句子有关，与采用的推导方法无关；文法中缺少对文法符号优先级和结合性的规定。“悬空（dangling）else”问题S→ ifCthenS (1) |ifCthenSelseS (2) |id:=E (3) (G3.3)C→ E=E|E<E|E>E (4)...(6)E→ E+E|-E|id|n (7)...(10)233.2上下文无关文法(CFG)[例3.8]条件语句ifx<3thenifx>0thenx:=5elsex:=-5if x<3then ifx>0thenx:=5else x:=-5else与离它远的then匹配if x<3then if x>0 then x:=5 else x:=-5else与离它近的then匹配243.2上下文无关文法(CFG)文法二义不能说明它所产生的语言一定是二义的。消除语言二义有两种方法：①改写二义文法为非二义文法；②规定二义文法中符号的优先级和结合性。改写[例3.9]与G3.2等价的非二义文法：

E→E+T|T T→T*F |F (G3.4) F→（E） |-F|id问题：如何改写？E→E+E|E*E|（E）(G3.2)|-E|id25上次课总结语法分析器作用语法错误处理CFG的定义与表示推导(最左、最右推导)、句子、句型分析树语法树二义性与二义性的消除原因：文法符号缺乏优先级和结合性263.2上下文无关文法(CFG)观察结论：新引入的非终结符限制每一步直接推导均有唯一选择；最终分析树的形状，仅与文法有关，而与推导方法无关；非终结符的引入，增加了推导步骤(分析树增高)；越接近S的文法符号的优先级越低。(如E→E+T)对于A→αAβ，若A在终结符左边出现(即终结符在β中)，则A产生式具有左结合性质。改写二义文法的关键步骤：引入新的非终结符，增加一个子结构并提高一级优先级；递归非终结符在终结符左边，运算具有左结合性，否则具有右结合性。273.2上下文无关文法(CFG)[例3.10]改写二义文法G3.2为G3.4：引入新的非终结符，增加一个子结构并提高一级优先级；递归非终结符在终结符左边，运算具有左结合性，否则具有右结合性。优先级： [+] [*] [(),-,id]结合性： 左结合 [+,*]

右结合 [-]

无结合 [id]非终结符与运算：

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|id283.2上下文无关文法(CFG)“悬空else”问题：在复合if语句中，可能then多于else，使得else不知与哪个then结合。一般原则是右结合，即else与左边最靠近的then结合。改写文法的根据是将S分为完全匹配(MS)和不完全匹配(UMS)两类，并且在UMS中规定else右结合。

S→MS (1) |UMS (2) MS→ifCthenMSelseMS (3) |id:=E (4) UMS→ifCthenS (5) |ifCthenMSelseUMS (6) C→E=E|E<E|E>E (7)...(9) E→E+T|T (10)...(11) T→(E)|-T|id|n (12)...(15)S→ifCthenS |ifCthenSelseS |id:=EC→E=E|E<E|E>EE→E+E|-E|id|n293.2上下文无关文法(CFG)S→MS|UMS (1)...(2)MS→ifCthenMSelseMS|id:=E (3)...(4)UMS→ifCthenS|ifCthenMSelseUMS (5)...(6) (G3.5)C→E=E|E<E|E>E (7)...(9)E→E+T|T (10)...(11)T→（E）|-T|id|n (12)...(15)if x<3then if x>0 then x:=5 else x:=-5303.2上下文无关文法(CFG)S→MS|UMS (1)...(2)MS→ifCthenMSelseMS|id:=E (3)...(4)UMS→ifCthenS|ifCthenMSelseUMS (5)...(6) (G3.5)C→E=E|E<E|E>E (7)...(9)E→E+T|T (10)...(11)T→（E）|-T|id|n (12)...(15)if x<3then ifx>0thenx:=5else x:=-5313.2上下文无关文法(CFG)规定优先级和结合性 二义文法的优点：比非二义文法容易理解；分析效率高(分析树低，直接推导步骤少)。

YACC为二义文法规定优先级和结合性：

%left'+' %left'*' %right'-'

E→E+E |E*E |（E）

|-E |idE→E+T|TT→T*F|FF→(E)|-F|id323.2上下文无关文法(CFG)修改语言的语法明确给出结束标志，如Ada中用endif，于是有：

ifx<3thenifx>0thenx:=5;endif;elsex:=-5;endif; ifx<3thenifx>0thenx:=5;elsex:=-5;endif;endif; if x<3 then ifx>0 thenx:=5; endif; elsex:=-5; endif;给表达式加括号，如Pascal中逻辑和算术运算：

(a+b)>(c*d)if x<3then ifx>0 thenx:=5; elsex:=-5; endif;endif;333.3语言与文法简介文法的重要作用：给出精确、易于理解的语言结构说明；以文法为基础的语言，便于加入新的、或修改、删除旧的语言结构；有些类别的文法，可以自动生成高效的分析器。本节从理论的角度对文法进行简单地讨论。讨论建立在形式语言与自动机的理论之上，且仅引用结论而忽略数学的证明，有兴趣的同学可以参阅相关文献。希望通过本节的讨论，对文法的分类和它们在编译器构造中的作用有一定的了解，同时初步窥探计算机科学的理论基础。343.3语言与文法简介正规式与上下文无关文法正规式到CFG的转换推论3.1

正规式描述的语言结构均可用CFG描述，反之不一定从正规式到CFG的对应关系：构造正规式的NFA；若0为初态，则A0为开始符号；对于move(i,a)=j，引入产生式Ai→aAj；对于move(i,ε)=j，引入产生式Ai→Aj；若i是终态，则引入产生式Ai→ε。[例3.11]从正规式r=(a|b)*abb的NFA构造CFG：A0→aA0|bA0|aA1A1→bA2A2→bA3A3→ε经验的方法：A→HTH→ε|Ha|HbT→abb353.3语言与文法简介为什么用正规式而不用CFG描述词法？词法规则简单，用正规式描述已足够；正规式的表示比CFG更直观、简洁、易于理解；有限自动机的构造比下推自动机简单，且分析效率高；区分词法和语法，为编译器前端的模块划分提供方便。贯穿词法分析和语法分析始终的思想：语言的描述和语言的识别是表示一个语言的两个不同侧面，二者缺一不可；（语言、文法、自动机）用正规式和CFG描述的语言，对应的识别方法（自动机）不同；正规式适合描述线性结构，如标识符、关键字、注释等；CFG适合描述具有嵌套（层次）性质的非线性结构，如不同结构的句子if-then-else、while-do等。363.3语言与文法简介上下文有关语言

ContextSensitiveLanguage,CSL

程序设计语言中除了CFG可以描述的结构之外，还有一些是CFG无法描述的所谓上下文有关的结构。典型的这类语言结构包括：变量的声明与引用、过程调用时形参与实参的一致性检查等。描述它们的文法被称为上下文有关文法（ContextSensitiveGrammar,CSG）。373.3语言与文法简介[例3.12]不能用CFG描述的语言：L1={ωcω|ω∈(a|b)*} (标识符声明与引用一致性的抽象)L2={anbmcndm|n≥1和m≥1} (形参与实参一致性的抽象)L3={anbncn|n≥1} (计数问题的抽象)相近的CFL：L1'={ωcωr|ω∈(a|b)*}L2'={anbmcmdn|n≥1,m≥1}L2''={anbncmdm|n≥1,m≥1}L3'={ambmcn|m,n≥1}S→aSa|bSb|cS→aSd|aAdA→bAc|bcS→ABA→aAb|abB→cBd|cdA→ACA→aAb|abC→cC|c383.3语言与文法简介计数问题L3={anbncn|n≥1} CSLL3'={ambmcn|m,n≥1} CFLL3''={akbmcn|k，m，n≥1} 正规集命题：L3'不是正规集，因为构造不出可以识别L3'的DFA。证明：（反证）假设L3'是正规集，则可构造n个状态的DFAD，它接受L3'；考察D读完ε，a，aa，...，an，分别到达S0，S1，...，Sn，共有n+1个状态。根据鸽巢原理，序列中至少有两个状态相同，设Si=Sj（j>i），因为aibick∈L3'，所以存在路径aibick。但是D中也有路径ajbick，矛盾。故L3'不是正规集。A→ACA→aAb|abC→cC|c?a+b+c+S0SiSkfaibickaj-i39上次课总结二义性与二义性的消除原因：文法符号缺乏优先级和结合性消除方法改写二义文法为非二义文法为文法符号规定优先级和结合性改变语言的结构或书写方式正规式到CFG的转换上下文有关语言形式语言与自动机简介403.3语言与文法简介形式语言与自动机简介

定义3.8

若文法G=(N，T，P，S)的每个产生式α→β中，均有α∈(N∪T)*，且至少含有一个非终结符，β∈(N∪T)*，则称G为0型文法。对0型文法施加以下第i条限制，即得到i型文法。G的任何产生式α→β（S→ε除外）满足|α|≤|β|；G的任何产生式形如A→β，其中A∈N，β∈(N∪T)*；G的任何产生式形如A→a或者A→aB(或者A→Ba)，其中A和B∈N，a∈T。文法语言自动机短语文法(0型)短语结构语言图灵机CSG(1型)CSL线性界线自动机CFG(2型)CFL下推自动机正规文法(3型)正规集有限自动机413.3语言与文法简介再考察L3：L3={anbncn|n≥1}[例3.15]L3可用下述CSG描述：

S→aSBC (1) S→aBC (2) CB→BC (3) aB→ab (4) bB→bb (5) bC→bc (6) cC→cc (7)CSG、CFG、正规式能力递减，但是能力越强的文法，其文法设计和自动机的构造越困难，因此语法分析仅用到CFG（除特别指出，文法即指CFG）句子akbkck

的推导：S=>...=>ak-1S(BC)k-1 (by1) =>ak(BC)k (by2) =>...=>akBkCk (by3) =>akbBk-1Ck (by4) =>...=>akbkCk (by5) =>akbkcCk-1 (by6) =>...=>akbkck (by7)423.4自上而下语法分析自上而下分析的一般方法用推导的方法分析输入序列：对输入序列ω，从S开始进行最左推导，直到得到一个合法句子或非法结构；从左到右扫描输入序列，试图用一切可能的方法，自上而下建立它的分析树；一种试探的过程，反复使用不同产生式，谋求与输入序列匹配；[例3.16]用下述文法分析输入序列ω=cad：S →cAdA →ab |a433.4自上而下语法分析问题：

若有A→αβ1|αβ2，公共左因子，则会虚假匹配和大量回溯；造成分析效率低、语义动作难以恢复、以及出错位置的报告不确切等。若有A→Aα，左递归，则死循环使分析无法进行下去。重写文法：消除左递归，以避免陷入死循环；提取左因子，以避免回溯。消除左递归定义3.9

若文法G中的非终结符A，对某个文法符号序列α存在推导A=+>Aα，则称G是左递归的。若G中有形如A→Aα的产生式，则称该产生式对A直接左递归。443.4自上而下语法分析消除文法的直接左递归考虑：A→Aα|β 产生的语言：βα*替换为：A→βA' A'→αA'|ε 消除了一个直接左递归算法3.1

消除直接左递归输入 G中所有的A产生式(含直接左递归)输出 等价的不含直接左递归的G'方法 首先，整理A产生式为如下形式：

A→Aα1|Aα2|...|Aαm|β1|β2|...|βn

其中αi非空，βj均不以A开始。用下述产生式代替A产生式

A→β1A'|β2A'|...|βnA' A'→α1A'|α2A'|...|αmA'|ε

若αi为空，则形成一个有环的A产生式453.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)E→E+T|TT→T*F|F(G3.4)F→(E)|-F|id463.4自上而下语法分析消除文法的左递归算法3.2

消除左递归输入 无回路文法G输出 无左递归的等价文法G'方法 将非终结符合理排序：A1，A2，...，An; for iin2..n loopforjin1..i-1 loop

用Aj→δ1|δ2|...|δk的右部替换每个形如Ai→Ajγ产生式中的Aj,

得到新产生式：Ai→δ1γ|δ2γ|...|δkγ;

消除Ai产生式中的直接左递归; endloop; endloop;核心思想：将不是直接左递归的非终结符右部展开到其他产生式中注意：若G产生句子的过程中出现A=+>A，则无法消除左递归473.4自上而下语法分析核心思想：将不是直接左递归的符号右部展开到其他产生式关键步骤：合理排序非终结符：A1，A2，...，An;

用Aj→δ1|δ2|...|δk右部替换Ai→Ajγ中的Aj，得到Ai→δ1γ|δ2γ|...|δkγ； 消除Ai产生式中的直接左递归；[例3.18]用算法3.2消除文法S→Aa|bA→Ac|Sd|ε中的左递归。①将S的右部展开在A中，得到：

A→Ac|Aad|bd|ε②消除新产生式中的直接左递归，得到：

S→Aa|b A→bdA'|A' (G3.8') A'→cA'|adA'|ε483.4自上而下语法分析提取左因子S→cAdA→ab|a当不确定用A产生式的哪个候选项替换A时，可以重写A产生式来推迟这种决定，直到看见足够的输入，能正确决定所需选择为止。这一过程被称为提取左因子，它类似于有限自动机的确定化。将： A→αβ1|αβ2替换为： A→αA' A'→β1|β2等价于： A→α(β1|β2)493.4自上而下语法分析算法3.3

提取文法的左因子输入 文法G输出 等价的无左因子文法G'方法 重复过程，直到所有A产生式候选项中不再有公共前缀：重排A产生式：A→αβ1|αβ2|...|αβn|γ；并用A→αA'|γ和A'→β1|β2|...|βn取代原A产生式。[例3.20]考察悬空else文法：S→iCtS|iCtSeS|aC→b

用算法3.3提取左因子，得到如下文法：

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

L→E;L|εE→E+T|E-T|TT→T*F|T/F|TmodF|FF→(E)|id|num每个非终结符对应一个状态转换图：为非终结符A建立一个初态和一个终态；为A→X1X2...Xn构造从初态到终态的路径，边标记为X1，X2，...，Xn。根据识别同一集合的原则，化简转换图。消除左递归后的等价文法:L→E;L|εE→TE'E'→+TE'|-TE'|εT→FT'T'→*FT'|/FT'|modFT'|εF→(E)|id|num523.4自上而下语法分析L→E;L|εE→TE'E'→+TE'|-TE'|εT→FT'T'→*FT'|/FT'|modFT'|εF→(E)|id|num533.4自上而下语法分析状态图的化简原则①标记为A的边可等价为标记ε的边转向A转换图的初态；②ε边连接的两个状态可以合并（FA的确定化思想）；③标记相同的路径可以合并；④不可区分的状态可以合并（DFA的最小化思想）。543.4自上而下语法分析文法的扩展BNF（EBNF）表示{}：重复0或若干次（while）[]：可选择（if或while）|：括弧()之内的或关系（case）()：改变运算的优先级和结合性EBNF表示：L→{E;}E→T{(+|-)T}T→F{(*|/|mod)F}F→(E)|id|num55上次课总结形式语言与自动机简介自上而下分析：自上而下/从左到右(不能有左递归/左因子)消除左递归提取左因子递归下降分析563.4自上而下语法分析递归下降子程序procedureLisbeginlookahead:=lexan;while(lookahead/=eof) loopE;match(';'); endloop;endL;procedureEisbegin

T;whilelookahead∈(+|-)loopmatch(lookahead);T;endloop;endE;procedureFisbegin

caselookaheadis'(':match('(');E;match(')');id:match(id);num:match(num);others:error("syntaxerror2");endcase;endF;L→{E;}E→T{(+|-)T}T→F{(*|/|mod)F}F→(E)|id|num573.4自上而下语法分析如果不消除左递归： 若存在产生式E→E+id，则E的递归下降子程序如下：

procedureEis begin E; match('+'); --永不执行

match(id); --永不执行

endE;

此程序永不停机。 同样，文法中的公共左因子也会给递归下降分析造成困难。583.4自上而下语法分析预测分析器非递归预测分析器的工作模式预测分析器的核心概念：分析方法：格局与格局变换分析表+驱动器（模拟算法）预测分析表的构造LL（文法、语言、分析器）593.4自上而下语法分析预测分析表

L→E;L|ε E→TE' E'→+TE'|-TE'|ε T→FT' T'→*FT'|/FT'|modFT'|ε F→(E)|id|num分析表M[A,a]的内容：若当前栈顶是非终结符A，下一输入终结符是a，则M[A,a]指示下一步动作。idnum+-*/mod();#LE;LE;LE;LεETE'TE'TE'E'+TE'-TE'εεTFT'FT'FT'T'εε*FT'/FT'modFT'εεFidnum(E)603.4自上而下语法分析工作方式放幻灯的方式：每张“幻灯片”称为一个格局。从初始格局开始，经过格局变化， 最终到达接收格局，表明分析成功；或者到达出错格局，表明发现语法错误。格局：三元组，(栈内容^top，剩余输入^ip，改变格局的动作)改变格局的动作：匹配终结符：若^top=^ip(但≠#)，则pop且next(ip)；展开非终结符：若^top=X且M[X,a]=α(X→α)，则pop且push(α)；报告分析成功：若^top=^ip=#，则分析成功并结束；报告出错：其它情况，调用错误恢复例程。61上次课总结递归下降分析预测分析器下推自动机符号栈、分析表、驱动器格局与格局的变换62驱动器算法算法3.4

非递归的预测分析输入 输入序列ω和文法G的预测分析表M输出 若ω∈L(G)，得到ω的一个最左推导；否则指出一个错误方法 初始格局为:（#S，ω#，分析器的第一个动作） 令ip指向ω#中的第一个终结符，top指向S; loopx:=top^;a:=ip^; if x∈T then if x=a

thenpop(x);next(ip); --匹配终结符

elseerror(1); endif; --出错：栈顶终结符不是a else if M[x,a]=X→Y1Y2...Yk thenpop(X);push(YkYk-1...Y2Y1); --展开非终结符

elseerror(2); endif; --出错：产生式不匹配

endif; exitwhenx=#; --分析成功

endloop;63用预测分析器分析句子栈 当前剩余输入 动作 含义#L id+id*id;# pop(L),push(E;L) (L→E;L)#L;E id+id*id;# pop(E),push(TE') (E→TE')#L;E'T id+id*id;# pop(T),push(FT') (T→FT')#L;E'T'F id+id*id;# pop(F),push(id) (F→id)#L;E'T'id id+id*id;# pop(id),next(ip) id#L;E'T' +id*id;# pop(T') (T'→ε)#L;E' +id*id;# pop(E'),push(+TE') (E'→+TE')#L;E'T+ +id*id;# pop(+),next(ip) +#L;E'T id*id;# pop(T),push(FT') (T→FT')#L;E'T'F id*id;# pop(F),push(id) (F→id)#L;E'T'id id*id;# pop(id),next(ip) id#L;E'T' *id;# pop(T'),push(*FT') (T'→*FT')#L;E'T'F* *id;# pop(*),next(ip) *#L;E'T'F id;# pop(F),push(id) (F→id)#L;E'T'id id;# pop(id),next(ip) id#L;E'T' ;# pop(T') (T'→ε)#L;E' ;# pop(E') (E'→ε)#L; ;# pop(;),next(ip) ;#L # pop(L) (L→ε)# # 正确结束643.4自上而下语法分析构造预测分析表首先构造FIRST集合与FOLLOW集合；然后根据两个集合构造预测分析表。定义3.10

文法符号序列α的FIRST集合为: FIRST(α)={a|α=*>a...，a∈T}，若α=*>ε，则ε∈FIRST(α)定义3.11

非终结符A的FOLLOW集合如下: FOLLOW(A)={a|S=*>...Aa...，a∈T}， 若A是某句型的最右符号，则#∈FOLLOW(A)。通俗地讲，α的FIRST集合就是从α开始可导出的文法符号序列中的开头终结符。而A的FOLLOW集合，就是从开始符号可以导出的所有含A的文法符号序列中A之后的终结符。例如：FIRST(E)={(，id,num}，FOLLOW(E)={)，;}L→E;L|εE→TE' E'→+TE'|-TE'|εT→FT'T'→*FT'|/FT'|modFT'|εF→(E)|id|num653.4自上而下语法分析算法3.5

计算X的FIRST集合输入 文法符号X输出 X的FIRST集合方法 应用下述规则：若X∈T，则FIRST(X)={X}；若X是非终结符且有X→ε，则加入ε到FIRST(X)；若X是非终结符且有X→Y1Y2...Yk，并设Y0=ε，Yk+1=ε。那么对所有j(0≤j≤k)，若a∈FIRST(Yj+1)且ε∈FIRST(Yj),则加入a到FIRST(X)。FIRST(X1X2...Xn)的计算方法与算法3.5中步骤3类似，即是所有FIRST(Xi)(i=1,2,..,k)的并集，其中k为第一个具有性质ε不属于FIRST(Xk)或k>n的文法符号，若k>n，则ε∈FIRST(X1X2...Xn)考虑：FIRST(E)=FIRST(TE')=FIRST(FT'E')={(，id,num}L→E;L|εE→TE' E'→+TE'|-TE'|εT→FT'T'→*FT'|/FT'|modFT'|εF→(E)|id|num663.4自上而下语法分析算法3.6

计算所有非终结符的FOLLOW集合输入 文法G输出 G中所有非终结符的FOLLOW集合方法 应用下述规则:加入#到FOLLOW(S)，其中S是开始符号，#是输入结束标记若有产生式A→αBβ，则除ε外，FIRST(β)的全体加入到FOLLOW(B)。若有产生式A→αB或A→αBβ而ε∈FIRST(β)，则FOLLOW(A)的全体加入到FOLLOW(B)。

步骤3的理解： 若 S=*>δAa a紧跟A之后 则 =*>δαBa a也紧跟B之后因为ε∈FIRST(β)使得B成为A产生式右部最右的文法符号即对任何a∈FOLLOW(A)，均有a∈FOLLOW(B)，反之不然。673.4自上而下语法分析[例3.22]计算非终结符的FIRST与FOLLOW。提示：自下而上计算FIRST，自上而下计算FOLLOW FIRST(F)={(idnum} FIRST(T')={*/modε} FIRST(T)=FIRST(F)={(idnum} FIRST(E')= {+-ε} FIRST(E)=FIRST(T)=FIRST(F)={(idnum} FIRST(L)={ε}∪FIRST(E)={ε(idnum} FOLLOW(L)={#} FOLLOW(E)={);} FOLLOW(E')={);} FOLLOW(T)={+-;)} FOLLOW(T')={+-;)} FOLLOW(F)={+-*/mod);}L→E;L|εE→TE' E'→+TE'|-TE'|εT→FT'T'→*FT'|/FT'|modFT'|εF→(E)|id|num683.4自上而下语法分析算法3.7

构造预测分析表输入 文法G输出 分析表M方法 应用下述规则对文法的每个产生式A→α，执行2和3；对FIRST(α)的每个终结符a，加入α到M[A，a]；若ε∈FIRST(α)，则FOLLOW(A)每个终结符b（包括#），加入α到M[A，b]；M中其它没有定义的条目均是error。M[A，a]指导下一步动作：若当前栈顶为A，当前输入为a，则规则2表示下一步动作是展开A→α，因为a∈FIRST(α)，展开后下一次正好匹配a。若当前栈顶为A，当前输入为b且b∈FOLLOW(A)，则规则3表示下一步动作是展开A→ε，即栈顶弹出A，继续分析A之后的部分，因为b∈FOLLOW(A)，弹出A后下一次正好匹配A的后继b693.4自上而下语法分析FIRST(F/T/E)={(idnum}FIRST(T')={*/modε}FIRST(E')={+-ε}FIRST(L)={ε(idnum}FOLLOW(L)={#}FOLLOW(E/E')={);}FOLLOW(T/T')={+-;)}FOLLOW(F)={+-*/mod);}idnum+-*/mod();#LEE'TT'F对FIRST(α)的每个终结符a，加入α到M[A，a]；若ε∈FIRST(α)，则FOLLOW(A)每个终结符b(包括#)，加入α到M[A，b]；E;LE;LE;LTE'TE'TE'+TE'-TE'FT'FT'FT'*FT'/FT'modFT'idnum(E)εεεεεεεL→E;L|εE→TE' E'→+TE'|-TE'|εT→FT' T'→*FT'|/FT'|modFT'|εF→(E)|id|num70上次课总结预测分析器下推自动机符号栈、分析表、驱动器格局与格局的变换预测分析表的构造FIRSTFOLLOW构造分析表LL(1)文法及判定713.4自上而下语法分析LL(1)文法M[A,a]的作用：指导产生式产生句子（指导推导）问题：是否分析表M[A,a]中都最多有一个条目？[例3.23]二义文法的预测分析表： 文法：S→iCtSS'|a S'→eS|ε C→b FIRST与FOLLOW集合：

FIRST(C)={b} FIRST(S')={ε,e} FIRST(S)={i,a}FOLLOW(S)={#,e}FOLLOW(S')={#,e}FOLLOW(C)={t}abeit#SS'CaiCtSSesεbε723.4自上而下语法分析定义3.12

文法G被称为是LL(1)文法，当且仅当为它构造的预测分析表中不含多重定义的条目。由此分析表所组成的分析器被称为LL(1)分析器，所分析的语言被称为LL(1)语言。第一个L代表从左到右扫描输入序列，第二个L表示产生最左推导，1表示在确定每一步动作时向前看一个终结符。判定LL(1)文法的方法：a)构造分析表；b)无需构造分析表。推论3.2G是LL(1)的，当且仅当G的任何两个产生式A→α|β满足：对任何终结符a，α和β不能同时推导出以a开始的串；α和β最多有一个可以推导出ε；若β=*>ε,则α不能导出以FOLLOW(A)中终结符开始的任何串。733.4自上而下语法分析对FIRST(α)的每个终结符a，加入α到M[A，a]；若ε∈FIRST(α)，则FOLLOW(A)每个终结符b(包括#)，加入α到M[A，b]；证明：若条件1不满足，即存在终结符a，α和β同时推导出以a开始的串，则根据算法3.7步骤2，M[A，a]中有多重定义A→α和A→β；若条件2不满足，即α和β均可推出ε串，则根据算法3.2步骤3，任何属于FOLLOW（A）的终结符b(包括#)，M[A，b]中有多重定义A→α和A→β；若条件3不满足，即存在终结符b，它既在FOLLOW(A)中，又在FIRST(α)中，则算法3.2步骤2把条目A→α加入到M[A，b]中，而步骤3又把条目A→β加入到M[A，b]中，即M[A，b]中有多重定义A→α和A→β。743.4自上而下语法分析

根据推论3.2，有左递归和左因子的文法不是LL(1)文法，二义文法也不是LL(1)文法。文法(G3.4)不是LL(1)的，因为不满足条件1。文法(G3.4')是LL(1)的，因为三个条件均满足。E→E+T|TT→T*F|F(G3.4)F→(E)|-F|idLL(1)文法的弱点：文法难写、难懂；适应范围有限，往往写不出有些语言的LL(1)文法。实际编译器中使用更多的是一类LL(1)文法的真超集，即LR(1)文法。E→TE' (1)E'→+TE'|ε (2)T→FT' (3)(G3.4')T'→*FT'|ε (4)F→(E)|-F|id (5)..(7)753.5自下而上语法分析自上而下分析的方法是产生语言的自然过程。对于分析语言来讲，自下而上分析的方法更自然，因为语法分析处理的对象一开始都是终结符组成的串，而不是文法的开始符号。同时，自下而上分析中最一般的方法，LR方法的能力比自上而下分析的LL方法要强，从而使得LR分析成为最为实用的语法分析方法。两种主要的自下而上分析方法：算符优先分析(不讨论)LR分析763.5自下而上语法分析自下而上分析的基本方法思路：从句子ω开始，从左到右扫描ω，反复用产生式的左部替换产生式的右部、谋求对ω的匹配，最终得到文法的开始符号，或者发现一个错误。规范规约与“剪句柄”定义3.13

设αβδ是文法G的一个句型，若存在S=*>αAδ，A=+>β，则称β是句型αβδ相对于A的短语，特别的，若有A→β，则称β是句型αβδ相对于产生式A→β的直接短语。一个句型的最左直接短语被称为句柄。直观上，句型是一个完整结构，短语是句型中针对某非终结符的局部。因此，开始符号S是句型而不是短语。短语形成的两个要素：从S可以推导出A，即S=*>αAδ；从A至少一次推导出β，即A=+>β。773.5自下而上语法分析[例3.25]文法、分析树与短语文法： E→E+T|T T→T*F|F F→id句型：id1+id2*id3分析树：短语： id1+id2*id3 (E1) id2*id3 (T1) id1 (E2,T2,F1) id2 (T3,F3) id3 (F2)直接短语：id1 (F1) id2 (F3) id3 (F2)句柄： id1 (F1)短语：以非终结符为根子树中所有从左到右的叶子直接短语：只有父子关系的树中所有从左到右排列的叶子(树高为2)句柄：最左边父子关系树中所有从左到右排列的叶子(句柄是唯一的)问题：id1+id2是句型id1+id2*id3的短语吗？783.5自下而上语法分析定义3.14

若α是文法G的句子且满足下述条件，则称序列αn，αn-1，...，α0是α的一个最左归约。αn=αα0=S（S是G的开始符号）对任何i(0<i<=n)，αi-1是将αi中句柄替换为相应产生式左部非终结符得到的。[例3.26]文法(1)S→aABe(2)A→b(3)A→Abc(4)B→d

对句子abbcde的最左归约： （2） （3）（4）（1）

abbcde<=aAbcde<=aAde<=aABe<=S提醒：最左归约的逆过程是一个最右推导，分别称最右推导和最左归约为规范推导和规范归约。问题：如何直观地看出句柄并进行归约？793.5自下而上语法分析剪句柄文法(1)S→aABe(2)A→b(3)A→Abc (4)B→d句子：abbcde假设已经有了句子的分析树，则：需要解决的问题：确定右句型中将要归约的子串（确定句柄）；确定如何选择正确的产生式进行归约。移进-归约：用一个栈“记住”将要归约句柄的前缀，句柄未形成前移进，形成后归约。(2)A→b(3)A→Abc(4)B→d(1)S→aABe80上次课总结LL(1)文法及判定自下而上分析：归约、短语、直接短语、句柄、规范(最左)归约规范归约的直观表示：剪句柄移进－归约分析工作模式：格局与格局变换813.5自下而上语法分析移进-归约分析器工作模式预测分析器：分析方法：格局与格局变换分析表驱动器（模拟算法）预测分析表的构造LL（文法、语言、分析器）移进-归约分析器：分析方法：格局与格局变换分析表驱动器（模拟算法）LR（文法、语言、分析器）SLR分析表的构造823.5自下而上语法分析工作方法：放幻灯，每个幻灯片是一个格局。格局：（#栈，当前剩余输入#，改变格局的动作）改变格局的动作：移进(shift)：输入序列中的终结符进栈。(匹配终结符)归约(reduce)：将栈顶句柄替换为对应非终结符(最左归约)。接受(accept)：宣告分析成功。报错(error)：发现语法错误，调用错误恢复例程。对照预测分析：匹配终结符（弹出）最左推导（展开非终结符）833.5自下而上语法分析[例3.27]用移进-归约方法分析abbcde：

abbcde<=aAbcde<=aAde<=aABe<=S栈 剩余输入 改变格局的动作# abbcde# 移进#a bbcde# 移进#ab bcde# 归约，(2)A→b#aA bcde# 移进#aAb cde# 移进#aAbc de# 归约，(3)A→Abc#aA de# 移进#aAd e# 归约，(4)B→d#aAB e# 移进#aABe # 归约，(1)S→aABe#S # 接受需要解决的问题：（由分析表确定）如何保证栈中总是活前缀(指导移进)如何确定栈顶已经形成句柄并选择正确的产生式进行归约(指导归约)(1)S→aABe(2)A→b(3)A→Abc(4)B→d结论：句柄总是在栈顶形成(最左归约)。栈中保留的总是一个右句型的前缀(加上若干终结符形成句型)，称为活前缀；最左归约是逻辑上从下到上构造一棵分析树，或从下到上为分析树剪句柄。843.5自下而上语法分析LR分析LR分析的特点：采用最一般的无回溯移进－归约方法可分析的文法是LL文法的真超集能及时发现错误，快到从左到右扫描输入序列的最大可能分析表较复杂，难以手工构造LR分析的核心：移进－归约分析表＋驱动器内容：工作原理(分析表的组成、分析算法)－>分析表的构造讨论依据的文法：

E→E-T|T （1）（2）

T→T*F|F （3）（4）

F→-F|id （5）（6）853.5自下而上语法分析LR分析与LR文法id-*#ETF0s4s51231s6acc2r2s7r23r4r4r44r6r6r65s4s586s4s5937s4s5108r5r5r59r1s7r110r3r3r3动作表(action)转移表(goto)action[s,a]确定改变格局的动作(与输入有关)goto[s,A]指示非终结符的状态转移分析表格局与动作：开始格局：(#0，ω#，移进)结束格局：(#0S，#，接受)出错格局：(#δ，ω'#，报错)改变格局的动作：action[s,a]=si：移进

=rj：用第j个产生式的左 部替换栈中的句柄

=acc：接收

=blank：报错goto[s,A]=s'：s状态下遇到A转移到状态s'提示：②和⑤共同完成归约。E→E-T|T T→T*F|F F→-F|id86算法3.8LR分析输入 输入序列ω和文法G的LR分析表（action与goto）输出 若ω属于L(G)，得到ω的规范归约，否则指出一个错误方法 初始格局为：（#0，ω#，移进），其中0是初态

ip指向ω#中的第一个终结符，top指向栈顶初始状态；

loops:=top^;a:=ip^; caseaction[s，a]is shifts':push(a);push(s');next(ip);--移进

reducebyA→β: pop(2*|β|); --弹出句柄和相应状态

s':=top^; --暴露出当前栈顶状态s' push(A); --产生式左部符号进栈

push(goto(s'，A));--新栈顶状态进栈

write(A→β);--完成归约，跟踪分析轨迹

accept:return; --成功返回

others:error; --出错处理

endcase; endloop;实际的算法中仅存放状态，而在分析的格局中，仅显示文法符号。873.5自下而上语法分析栈 剩余输入 动作#0 id--id*id# s4#0id4 --id*id# r6(F→id)#0F3 --id*id# r4(T→F)#0T2 --id*id# r2(E→T)#0E1 --id*id# s5#0E1-6 -id*id# s5#0E1-6-5 id*id# s4#0E1-6-5id4 *id# r6(F→id)#0E1-6-5F8 *id# r5(F→-F)#0E1-6F3 *id# r4(T→F)#0E1-6T9 *id# s7#0E1-6T9*7 id# s4#0E1-6T9*7id4 # r6(F→id)#0E1-6T9*7F10 #r3(T→T*F)#0E1-6T9 #r1(E→E-T)#0E1 # accid-*#ETF0s4s51231s6acc2r2s7r23r4r4r44r6r6r65s4s586s4s5937s4s5108r5r5r59r1s7r110r3r3r3shifts':push(a);push(s');next(ip);reducebyA→β:pop(2*|β|);s':=top^;push(A);push(goto(s'，A));write(A→β);883.5自下而上语法分析定义3.15若为文法G构造的移进－归约分析表中不含多重定义的条目，则称G为LR(k)文法，分析器被称为是LR(k)分析器，它所识别的语言被称为LR(k)语言。L表示从左到右扫描