《编译原理西电社－刘坚第3章》由会员分享，可在线阅读，更多相关《编译原理西电社－刘坚第3章（226页珍藏版）》请在金锄头文库上搜索。
1、,第3章 80x86微处理器,3.1 语法分析的若干问题 3.2 上下文无关文法(Context Free Grammar, CFG) 3.3 语言与文法简介 3.4 自上而下语法分析 3.5 自下而上语法分析 3.6 本章小结,3.1 80x86微处理器简介,3.1.1 语法分析器的作用 语法分析器是编译器前端的重要组成部分，许多编译器，特别是由自动生成工具构造的编译器，往往其前端的中心部件就是语法分析器。语法分析器在编译器中的位置和作用如图3.1所示，它的主要作用有两点： (1) 根据词法分析器提供的记号流，为语法正确的输入构造分析树(或语法树)。这是本章的重点，在以后各节中详细讨论； (
2、2) 检查输入中的语法(可能包括词法)错误，并调用出错处理器进行适当处理。下边简单介绍语法错误处理的基本原则，而在以后的讨论中忽略此问题。,图3.1 语法分析器在编译器中的位置与作用,3.1.2 语法错误的处理原则 1源程序中可能出现的错误 源程序中可能出现的错误可以分为两类：语法错误和语义错误。其中，语法错误又包括词法错误和语法错误。词法错误指出现非法字符或关键字、标识符拼写错误等；语法错误是指语法结构出错，如少分号、begin/end不配对等。语义错误包括静态语义错误和动态语义错误。静态语义错误涉及的是编译时可检查出来的错误，如类型不一致、参数不匹配等；动态语义错误一般是指程序运行时的逻辑
3、错误，如无穷递归、变量为零时作除数等。 大多数错误的诊断和恢复集中在语法分析阶段，一个原因是大多数错误是语法错误，另一个原因是语法分析方法的准确性，它们能以非常有效的方法诊断语法错误。在编译的时候，想要准确地诊断语义或逻辑错误有时是很困难的。,2语法错误处理的目标 对语法错误的处理，一般希望达到以下基本目标： 清楚而准确地报告错误的出现，地点正确、不漏报、不错报也不多报； 迅速地从每个错误中恢复过来，以便分析继续进行； 对语法正确源程序的分析速度不应降低太多。,这些目标看起来容易，但是实现起来并不简单。幸好常见的错误是简单的，直接了当的出错处理机制一般就足以应付。但有些时候，错误的实际位置远远
4、前于发现它的位置，并且这种错误的准确性也难以推断。在某些场合，出错处理程序可能需要猜测程序员的本意。 有些分析方法，如LL和LR方法，可以尽可能快地检测语法错误。更准确地说，它们具有“活前缀” (viable-prefix property)性质，这指的是，它们一看见输入的前缀不是该语言任何串的前缀时，就能报告错误。出错处理的关键是如何从错误中恢复，使分析可以进行下去，而不是遇到第一个错误就停止分析。,3语法错误的基本恢复策略 若希望编译器的语法分析方式是每次对输入源程序完整地扫描一遍，而不是遇到第一个语法错误就停止的话，就需要采取某种恢复策略，使得分析在遇到错误时还能够继续进行。以下是一些可
5、能的恢复策略。 (1) 紧急方式恢复(Panic-mode recovery)：这是最简单的方法，适用于大多数分析方法。发现错误时，分析器每次抛弃一个输入记号，一直向前搜索，直到输入记号属于某个指定的合法记号(称为同步记号)集合为止。同步记号一般是定界符，如分号或end等，它们在源程序中的作用很清楚。当然，设计编译器时必须选择适当的同步记号。这种处理方法最简单，但是也最容易造成错报，特别是漏报和多报语法错误的现象。,(2) 短语级恢复(Phrase-level recovery)：发现错误时，分析器采用串替换的方式对剩余输入进行局部纠正，它用可以使分析器继续的输入串来代替剩余输入的前缀。典型的
6、局部纠正是用分号代替逗号，删除多余的分号，或插入遗漏的分号等。设计编译器时必须仔细选择替换的串，以免引起死循环，例如，若总是在当前输入符号的前面插入一些东西就会造成死循环。这种方式建立在产生式(用于规定上下文无关文法的一种形式化描述)的基础之上，以短语为基本分析单元，同时也便于进行语法制导翻译，恢复得比紧急方式要精确，因此被认为是一种较为理想的恢复方式。,(3) 出错产生式(Error-productions)：预测被分析语言可能出现的错误，用出错产生式捕捉错误。这是语法分析器生成器YACC采用的方式，它基本上可以被认为是一种预置型的短语级恢复方式。 (4) 全局纠正(Global corre
7、ction)：对有语法错误的输入序列x，根据文法G构造相近序列y的语法树，使得x变换成y所需的修改、插入、删除次数最少。由于这种方法的代价太大，因此目前只具有理论价值。,例3.1 下述两条是有语法错误的语句，其中第一条赋值句结束时忘记加分号，采用紧急恢复方式和短语级恢复方式的可能结果分别如下所示。 x := a + b y := c + d; 紧急方式： x := a + b + d; - 丢弃b之后的若干记号，直到遇到同步记号+ 短语级恢复：x := a + b; - 加入分号，使之成为一个赋值句 y := c + d;,3.2 上下文无关文法(Context Free Grammar, C
8、FG),3.2.1 CFG的定义与表示 定义3.1 上下文无关文法是一个四元组G =(N，T，P，S)，其中 N是非终结符的有限集合(Nonterminals)； T是终结符的有限集合(Terminals)，且NT=； P是产生式的有限集合(Productions)，每个产生式形如: A，其中AN，被称为产生式的左部，(NT)*，被称为产生式的右部，若=，则称A为空产生式(也可以记为A )； S是非终结符，被称为文法的开始符号(Start symbol)。,例3.2 定义简单算术表达式的上下文无关文法G3.1=(N,T,P,S)如下所示。 N=E T=+,*,(,),id S=E P: E E
9、 + E (1) E E * E (2) E (E) (3) E E (4) E id (5),1由产生式集表示CFG 由于每个产生式中均有AN且(NT)*，所以，对于一个没有错误的CFG，可以这样区分N和T集合：N是仅出现在产生式左边符号的集合，T是词法分析器返回的记号的集合(某些约定的特殊终结符除外)，根据NT=可以推断出T是所有不出现在产生式左边符号的集合。如果再约定S是第一个产生式的左部，则文法可以由其产生式集P代替，即不写四元组，而仅给出P。CFG的产生式表示也被称为巴克斯范式(Backus-Naur Form，BNF)，值得注意的是，规范的BNF中，“”用“:=”表示。,2产生式的
10、一般读法 一般情况下，可以将产生式中的记号“”读作“定义为”或者“可导出”。例如，EE+E可读作“E定义为E+E”，或者“E可导出E+E”。更一般的，可用自然语言表述为“算术表达式定义为两个算术表达式相加”，或者“一个算术表达式加上另一个算术表达式，仍然是一个算术表达式”。,3终结符与非终结符书写上的区分 对于一个仅有几个产生式的简单文法，其中的终结符和非终结符很容易区分，没有必要在书写上明确区分终结符和非终结符。但是对于一个实用的文法，产生式可能有几百个或者更多，这时如果终结符和非终结符之间在书写上没有明确区分，则很难辨别它们，给理解产生式造成困难。区分终结符和非终结符的方法有很多，原则是容
11、易辨别即可，例如， 用大小写区分： E id 用“ “区分： E “id“ E E “+“ E 用区分： + ,本教材默认采用区分大小写的方法来区分终结符与非终结符，若不作特殊说明，一般用大写英文字母A、B、C表示非终结符，小写英文字母a、b、c表示终结符，小写希腊字母、表示任意的文法符号序列，即大小写混合的英文字母串。,4产生式的缩写形式 考察文法G3.1，多个产生式左部的非终结符均是E。对于这种情况，可以把左部非终结符相同的产生式合并成一个产生式，并以此非终结符为该产生式命名，而所有的产生式右部由或符号(|)连接，每个右部现在被称为该产生式的一个候选项，各候选项具有平等的权利。,例3.3
12、G3.1可以重写为如下形式： E E + E (1) | E * E (2) |(E) (3) | E (4) | id (5),该产生式被称为E产生式，它一共有5个候选项，分别表示：两个算术表达式相加结果是一个算术表达式，两个算术表达式相乘结果是一个算术表达式，加上括弧的算术表达式还是一个算术表达式，对算术表达式取负的结果是一个算术表达式，标识符是一个算术表达式。,3.2.2 CFG产生语言的基本方法 推导 可以通过推导的方法产生CFG所描述的语言。非正式地讲，推导就是从文法的开始符号S开始，反复使用产生式，将产生式左部的非终结符替换为右部的文法符号序列(展开产生式，用标记=表示)，直到得到
13、一个终结符序列。 例3.4 终结符序列(id+id)可以由文法G3.2产生，因此它是文法G3.2所产生的语言中的一个元素。标记=上方的序号指出每次使用的产生式序号。 (4) (3) (1) (5) (5) E = E = (E) = (E+E) = (id+E) = (id+id),定义3.4 在推导过程中，若每次直接推导均替换句型中最左边的非终结符，则称为最左推导，由最左推导产生的句型被称为左句型。 类似地，可以定义最右推导与右句型，最右推导也被称为规范推导。 再考察例3.4的推导过程，1=E，2= E，3= (E)，4= (E+E)，5= (id+E)，6= (id+id)。其中，1是文法
14、开始符号，6是句子，其他i(i=2,3,4,5)均是句型。由于从4到5替换的是最左边的非终结符，所以此推导是一个最左推导，所有的句型是左句型。句型是一个相当广泛的概念，根据定义3.3可知，1和6同样也是句型。,3.2.3 推导、分析树与语法树 定义3.5 对CFG G的句型，分析树被定义为具有下述性质的一棵树。 根由开始符号所标记； 每个叶子由一个终结符、非终结符或标记； 每个内部结点由一个非终结符标记； 若AX1X2.Xn是一个产生式，则X1，X2，.，Xn是标记为A的内部结点从左到右所有孩子的标记。若A，则标记为A的结点可以仅有一个标记为的孩子。,分析树与文法和语言存在下述关系： 每一直接
15、推导(或者每个产生式)，对应一棵仅有父子关系的子树，即产生式左部非终结符“长出”右部的孩子； 分析树的叶子从左到右，构成G的一个句型。若叶子仅由终结符标记，则构成一个句子。,例3.5 考虑例3.4的最左推导E = E = (E) = (E+E) = (id+E) = (id+id)，和最右推导E = E = (E) = (E+E) = (E+id) = (id+id)，它们所对应的分析树序列分别如图3.2(a)、(b)所示。可以看出，最左推导和最右推导的中间过程对应的分析树可能不同(因为句型不同)，但是最终的分析树相同，因为最终是同一个句子。 更多的情况下，往往仅希望用树来反映句型的结构实质，而忽略句型的推导过程，从而引出语法树的概念。语法树是表示表达式结构的最好形式。,定义3.6 对CFG G的句型，表达式的语法树被定义为具有下述性质的一棵树: 根与内部节点由表达式中的操作符标记； 叶子由表达式中的操作数标记； 用于改变运算优先级和结合性的括弧，被隐含在语法树的结构中。,例3.6 根据定义3.6，例3.5最终的分析树所对应的语法树如图3.3(a)所示。 定义3.6是针对表达式的，若将一般句子的结构看作是操作符与操作数的组合，则可以利用定义3.6得到对应的语法树。例如条件语句if condition then s1 else s2，可以看作
