编译原理-语法分析
1,第三章 语法分析,词法分析:字母是元素,组成字符串,记号的集合,线性结构 语法分析:记号是元素,组成句子, 句子的集合,树结构 语法的双重含意: 语法规则:上下文无关文法(子集LL文法或LR文法) 语法分析:下推自动机(LL或LR分析器),自上而下和自下而上分析,本章主要内容: 与语法分析有关的基本概念和相关问题 上下文无关文法 自上而下分析 自下而上分析 上机作业第二部分:函数绘图语言的语法分析器,结束(2010年3月25日),2,3.1 语法分析的若干问题 3.1.1 语法分析器的作用,语法分析器是编译器前端的重要组成部分,许多编译器,特别是由自动生成工具构造的编译器,往往其前端的中心部件就是语法分析器。语法分析器在编译器中的位置和作用:,3,3.1.1 语法分析器的作用(续),根据词法分析器提供的记号流,为语法正确的输入构造分析树(或语法树),这是本章的重点,在以后各节中详细讨论; 检查输入中的语法(可能包括词法)错误,并调用出错处理器进行适当处理,下边简单介绍语法错误处理的基本原则,而在以后的讨论中忽略此问题。,语法分析器的两个重要作用:,4,3.1.2 语法错误的处理原则,词法错误如非法字符或拼写错关键字、标识符等 intege 20times 语法错误是指语法结构出错,如少分号、begin/end不配对等begin x:=a+b y:=x; 静态语义错误:如类型不一致、参数不匹配等a,b:integer; x:array110 of integer;x:=a+b; 动态语义错误(逻辑错误):如死循环、变量为零时作除数等while (t) .; a:=a/b;, 源程序中可能出现的错误 两类:语法(包括词法)错误和语义错误,5,3.1.2 语法错误的处理原则(续1),大多数错误的诊断和恢复集中在语法分析阶段。一个原因是大多数错误是语法错误,另一个原因是语法分析方法的准确性,它们能以非常有效的方法诊断语法错误。编译时想要准确诊断语义或逻辑错误有时是很困难的。,对语法错误的处理,一般希望达到以下基本目标: 清楚而准确地报告错误的出现,地点正确、不漏报、不错报也不多报; 迅速从每个错误中恢复过来(以便分析继续进行); 不应使对语法正确源程序的分析速度降低太多。, 语法错误处理的目标,6,3.1.2 语法错误的处理原则(续2),紧急方式恢复:抛弃若干输入,直到遇到同步记号。 短语级恢复:采用串替换的方式对剩余输入进行局部纠正(抛弃插入)。 出错产生式:用出错产生式捕捉错误(预测错误)。预置型的短语级恢复方式。 全局纠正:对错误输入序列x,找相近序列y,使得x变换成y所需的修改、插入、删除次数最少。, 语法错误的基本恢复策略,7,3.1.2 语法错误的处理原则(续3),紧急方式: x := a + b + d; - 丢弃b后若干记号,直到遇到+ 短语级恢复:x := a + b; - 加入分号,使之成为一个赋值句y := c + d;,例3.1 下述两条是有语法错误的语句,其中第一条赋值句结束时忘记加分号,采用紧急恢复方式和短语级恢复方式的可能结果分别如下所示。,x := a + b y := c + d;,8,3.2 上下文无关文法(Context Free Grammar,CFG) 3.2.1 CFG的定义与表示,定义3.1 CFG是一个四元组G =(N,T,P,S),其中 (1) N是非终结符(Nonterminals)的有限集合; (2) T是终结符(Terminals)的有限集合,且NT=; (3) P是产生式(Productions)的有限集合,A,其中AN(左部),(NT)*(右部),若=,则称A为空产生式(也可以记为A ); (4) S是非终结符,称为文法的开始符号(Start symbol)。,9,3.2.1 CFG的定义与表示(续1),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),例3.2 简单算术表达式的上下文无关文法可表示如下:, 产生式的一般读法可以将产生式中的记号读作“定义为”或者“可导出”。更一般的,“E E + E”可用自然语言表述为“算术表达式定义为两个算术表达式相加”。或者“一个算术表达式加上另一个算术表达式,仍然是一个算术表达式”。,10,3.2.1 CFG的定义与表示(续2),前提:若文法正确,第一个产生式的左部是文法开始符号S 则: N是可以出现在产生式左边符号的集合,T是绝不出现在产生式左边符号的集合(记号),P: E E + E (1)E E * E (2)E (E) (3)E -E (4)E id (5),S=E N=E T=+,*,(,),-,id, 由产生式集表示CFG,11,3.2.1 CFG的定义与表示(续3),(a) 用大小写区分: E id (b) 用“区分: E “id“ E E “+“ E (c) 用区分: + 约定:大写英文字母A、B、C表示非终结符;小写英文字母a、b、c表示终结符;小写希腊字母、表示任意文法符号序列。, 终结符与非终结符书写上的区分,12,3.2.1 CFG的定义与表示(续4),当若干个产生式具有相同的左部非终结符时,可以将它们合并为一个产生式。该产生式的左部是此非终结符,右部是所有原来右部的或运算(并集合),产生式以该非终结符命名。 例3.3 G3.1可以重写为如下形式:,E E + E (1)| E * E (2)|(E) (3) (G3.2)| -E (4)| id (5),P: E E + E (1)E E * E (2)E (E) (3)E -E (4)E id (5), 产生式的缩写形式,称其为E产生式。 用“|”连接的每个右部称为一个候选项,具有平等的权利。 即id是一个表达式,-E也是一个表达式。,13,3.2.2 CFG产生语言的基本方法推导,CFG(产生式)通过推导的方法产生语言。通俗地讲,产生式产生语言的过程是从开始符号S开始,对产生式左部的非终结符反复地使用产生式:将产生式左部的非终结符替换为右部的文法符号序列(展开产生式,用标记=>表示),直到得到一个终结符序列。,E => -E by(4)=> -(E) by(3)=> -(E+E) by(1)=> -(id+E) by(5)=> -(id+id) by(5),E E + E (1)| E * E (2)|(E) (3) (G3.2)| -E (4)| id (5),例3.4 用(G3.2)产生终结符序列-(id+id)可如下:,14,3.2.2 CFG产生语言的基本方法推导(续1),若对于任意文法符号序列1,2,.n,均有1=>2=>.=>n,则称此过程为零步或多步推导,记为: 1=*>n,其中1=n的情况为零步推导。若1n,即推导过程中至少使用一次产生式,则称此过程为至少一步推导,记为:1=+>n。 ,定义3.2强调了两点:,有=*>,即推导具有自反性;若=*>,=*>,则=*>,即推导具有传递性。,定义3.2 利用产生式产生句子的过程中,将产生式A的右部代替文法符号序列A中的A得到的过程,称A直接推导出,记作:A=>。,15,3.2.2 CFG产生语言的基本方法推导(续2),定义3.3 由CFG G所产生的语言L(G)被定义为:L(G) = S=+> and T* , L(G)称为上下文无关语言(Context Free Language, CFL),称为句子。若S=*>,(NT)*,则称为G的一个句型。 ,定义3.4 在推导过程中,若每次直接推导均替换句型中最左边的非终结符,则称为最左推导,由最左推导产生的句型被称为左句型。 ,类似的可以定义最右推导与右句型,最右推导也被称为规范推导。,16,3.2.2 CFG产生语言的基本方法推导(续3),E => -E => -(E) => -(E+E) => -(id+E) => -(id+id) 1 2 3 4 5 6,E E + E (1)| E * E (2)|(E) (3) (G3.2)| -E (4)| id (5),再考察-(id+id)的推导过程(这是一个最左推导):,其中,1是文法开始符号,6是句子,其他i (i=2、3、4、5)均是句型。句型是一个相当广泛的概念,根据定义3.3可知,1和6同样也是句型。,17,3.2.3 推导、分析树与语法树,推导:E => -E => -(E) => -(E+E) => -(id+E) => -(id+id) 产生句子的方式很不直观,看起来十分困难。分析树是推导的图形表示,它的表示很直观,并且同时反映语言结构的实质和推导过程。,定义3.5 对CFG G的句型,分析树被定义为具有下述性质的一棵树。(1) 根由开始符号所标记;(2) 每个叶子由一个终结符、非终结符、或标记;(3) 每个内部结点由一个非终结符标记;(4) 若A是某内部节点的标记,且X1,X2,.,Xn是该节点从左到右所有孩子的标记,则AX1X2.Xn是一个产生式。若A,则标记为A的结点可以仅有一个标记为的孩子。 ,18,3.2.3 推导、分析树与语法树(续1),每一直接推导(每个产生式),对应一棵仅有父子关系的子树,即产生式左部非终结符“长出”右部的孩子; 分析树的叶子,从左到右构成G的一个句型。若叶子仅由终结符标记,则构成一个句子。,分析树与语言和文法的关系:,19,3.2.3 推导、分析树与语法树(续2),E => -E => -(E) => -(E+E) => -(id+E) => -(id+id) 用分析树的方式如下:,最左推导和最右推导的中间过程对应的分析树可能不同,因为句型不同: -(id+E) 或 -(E+id) 但是最终的分析树相同,因为最终是同一个句子: -(id+id),例3.5 再考察-(id+id)的推导过程。,分析树既反映了产生句型的推导过程,又反映了句型的结构。,20,3.2.3 推导、分析树与语法树(续3),更多的情况下,仅关注句型结构,而忽略推导过程。,定义3.6 对CFG G的句型,表达式的语法树被定义为具有下述性质的一棵树:(1) 根与内部节点由表达式中的操作符标记;(2) 叶子由表达式中的操作数标记;(3)用于改变运算优先级和结合性的括弧,被隐含在语法树的结构中。 ,实质上,语法树与分析树的最根本区别在于它们的内部节点(包括根节点):分析树的内部节点是非终结符;语法树的内部节点是操作符(运算符);或者说语法树中省略了反映分析过程的非终结符。,21,3.2.3 推导、分析树与语法树(续4),例3.6 句子-(id+id)和句型if C then s1 else s2 :,分析树:左部非终结符“产生出”右部文法符号序列; 语法树:操作符(运算)“作用于”操作数(运算对象); 习惯上:它们分别被称为具体语法树和抽象语法树。,22,结束(2010年3月30日),定义3.1 CFG 定义3.2 直接推导、零或多步推导、至少一步推导 定义3.3 CFL、句子、句型 定义3.4 最左推导、左句型(最右推导、右句型) 定义3.5 分析树 定义3.6 语法树,