网站后台改网页底色,网站建设的系统流程图,做类似58同城的网站,网站建设维护要加班吗1#xff0c;语法分析的若干问题
1.1 语法分析器的作用 编译器前端的重要组成部分#xff1a; (1) 根据词法分析器提供的记号流#xff0c;为语法正确的输入构造分析树(或语法树)。 (2) 检查输入中的语法(可能包括词法)错误#xff0c;并调用出错处理器进…1语法分析的若干问题
1.1 语法分析器的作用 编译器前端的重要组成部分 (1) 根据词法分析器提供的记号流为语法正确的输入构造分析树(或语法树)。 (2) 检查输入中的语法(可能包括词法)错误并调用出错处理器进行适当处理。 语法分析器 1、通用的语法分析方法 Cocke-Younger-Kasami算法和Earley算法 2、自上而下 对任何输入串试图用一切可能的办法从文法开始符号根结点出发自上而下地为输入串建立一棵语法树或者说为输入串寻找一个最左推导。 3、自下而上 自上而下的一般方法 消除左递归 提取左因子 递归下降分析 预测分析器 语法分析器在编译器中的位置与作用 1.2 语法错误的处理原则
1.2.1源程序中可能出现的错误 语法错误 词法错误非法字符或关键字、标识符拼写错误等 语法错误语法结构出错如少分号、{/}不配对等 语义错误 静态语义错误涉及的是编译时可检查出来的错误如类型不一致、参数不匹配等 动态语义错误一般是指程序运行时的逻辑错误如无穷递归、变量为零时作除数等。 大多数错误的诊断和恢复集中在语法分析阶段一个原因是大多数错误是语法错误另一个原因是语法分析方法的准确性它们能以非常有效的方法诊断语法错误。在编译的时候想要准确地诊断语义或逻辑错误有时是很困难的。 1.2.2语法错误处理的目标 ① 清楚而准确地报告错误的出现地点正确、不漏报、不错报也不多报 ② 迅速地从每个错误中恢复过来以便分析继续进行 ③ 对语法正确源程序的分析速度不应降低太多。 1.2.3语法错误的基本恢复策略 希望编译器的语法分析方式不是遇到一个语法错误就停止就需要采取某种恢复策略使得分析在遇到错误时还能够继续进行。 紧急方式恢复这是最简单的方法适用于大多数分析方法。 短语级恢复建立在产生式(CFG)的基础上以短语为基本分析单元同时也便于进行语法制导翻译恢复得比紧急方式要精确因此被认为是一种较为理想的恢复方式。 出错产生式 全局纠正 例题 下述两条是有语法错误的语句其中第一条赋值句结束时忘记加分号x a b y c d; 紧急方式 x a b d; -- 丢弃b之后的若干记号直到遇到同步记号 短语级恢复x a b; -- 加入分号使之成为一个赋值句 2上下文无关文法(CFG)
2.1 CFG的定义与表示
2.1.1 定义 定义3.1 上下文无关文法是一个四元组G (NTPS) ① N是非终结符的有限集合(Nonterminals) ② T是终结符的有限集合(Terminals)且N∩TΦ ③P是产生式的有限集合(Productions)每个产生式形如: A→α其中A∈N被称为产生式的左部α∈(N∪T)*被称为产生式的右部若αε则称A→ε为空产生式(也可以记为A →) ④ S是非终结符被称为文法的开始符号(Start symbol)。 2.2.2 例题 定义简单算术表达式的上下文无关文法G3.1(N,T,P,S)如下所示。 N{E} T{,*,(,),–,id} SE P: E → E E (1) E → E * E (2) E → (E) (3) E → –E (4) E → id (5) 2.2.3 表示 1由产生式集表示CFG 文法可以由其产生式集P代替而不写四元组。CFG的产生式表示也被称为巴克斯范式(BNF)值得注意的是规范的BNF中“→”用“::”表示。 2产生式的一般读法 一般情况下可以将产生式中的记号“→”读作“定义为”或者“可导出”。 3终结符与非终结符书写上的区分 本教材默认采用区分大小写的方法来区分终结符与非终结符若不作特殊说明一般用大写英文字母A、B、C表示非终结符小写英文字母a、b、c表示终结符小写希腊字母α、β、δ表示任意的文法符号序列即大小写混合的英文字母串。 4产生式的缩写形式 2.2.2的例题 G3.1可以重写为如下形式E → E E | E * E | (E) | –E | id 2.2 CFG产生语言的基本方法 —— 推导
2.2.1 推导定义以及性质 通过推导可以产生CFG所描述的语言。 推导就是从文法的开始符号S开始反复使用产生式将产生式左部的非终结符替换为右部的文法符号序列直到得到一个终结符序列 2.2.2 例题 文法G(E): E → E E (1) E→ E * E (2) E → (E) (3) E → –E (4) E → id (5) 根据文法G使用最左推导得出终结符序列 ”–(idid)” 。 2.2.3 上下文无关语言(CFL)最左推导 定义3.3 由CFG G所产生的语言L(G)被定义为: L(G)称为上下文无关语言(CFL)ω称为句子。若Sαα∈(N∪T)*则称α为G的一个句型。 定义3.4 在推导过程中若每次直接推导均替换句型中最左边的非终结符则称为最左推导由最左推导产生的句型被称为左句型。 类似地可以定义最右推导与右句型最右推导也被称为规范推导。 2.3 推导、分析树与语法树 定义3.5 对CFG G的句型分析树被定义为具有下述性质的一棵树。 ① 根由开始符号所标记 ② 每个叶子由一个终结符、非终结符或ε标记 ③ 每个内部结点由一个非终结符标记 ④ 若A→X1X2...Xn是一个产生式则X1X2...Xn是标记为A的内部结点从左到右所有孩子的标记。若A→ε则标记为A的结点可以仅有一个标记为ε的孩子。 分析树与文法和语言存在下述关系 ① 每一直接推导(或者每个产生式)对应一棵仅有父子关系的子树即产生式左部非终结符“长出”右部的孩子 ② 分析树的叶子从左到右构成G的一个句型。若叶子仅由终结符标记则构成一个句子。 分析树与推导的关系 ① 分析树是推导的图形表示但不能显示推导的顺序 ② 每棵分析树都可以对应惟一的最左推导或最右推导但每个句子产生式不一定只有一棵分析树也就是说每个句子不一定只有一个最左推导或者最右推导。 例句子id id * id 例题 用文法G采用最左推导产生句子idid*id. 一个句子两棵分析树 (a) 先进行运算(b) 先进行*运算(c) 左结合(d) 右结合 2.4 二义性与二义性的消除
2.4.1 二义性(Ambiguity) 定义3.7 若文法G对同一个句子产生不止一棵分析树则称G是二义的。 ① 一个句型有多于一棵分析树仅与文法和句型有关与采用的推导方法无关 ② 造成二义性的原因是文法中缺少对文法符号优先级和结合性的规定。 在任何一个程序设计语言中如果出现了二义性则表示同一段程序在确定的、相同的环境下反复执行会得到不同的结果而这种情况在程序设计中是不允许的。也就是说任何一个程序设计语言不应该有二义性。 2.4.2 为文法符号规定优先级和结合性 改写文法可以解决二义性问题但不是唯一的解决方法。比较上述讨论过的二义文法和非二义文法发现二义文法至少有两个优点 ① 比非二义文法容易理解 ② 分析效率高(分析树低直接推导步骤少)。
3语言与文法简介 到目前为止我们在两个层面上讨论了程序设计语言的结构从词法分析的层面上看语言是由字母组成的记号的集合从语法分析的层面上看语言是由记号组成的句子的集合。记号可以用正规式描述句子可以用CFG描述。 程序设计语言的结构均可以用文法来描述。文法无论对程序设计语言的设计还是对编译器的编写至少在以下三个方面起着重要作用 ① 文法给出了精确的、易于理解的语言结构的说明 ② 以文法为基础的语言便于加入新的或修改、删除旧的语言结构 ③ 有些类别的文法可以自动生成高效的分析器。 3.1为什么用正规式而不用CFG描述程序设计语言的词法 根据推论3.1CFG既描述程序设计语言的语法又描述词法而基于下述几个原因往往采用正规式而不是CFG描述词法 ① 词法规则简单用正规式描述已足够 ② 正规式的表示比CFG更直观、简洁、易于理解 ③ 有限自动机的构造比下推自动机简单且分析效率高 ④ 区分词法和语法为编译器前端的模块划分提供方便。
3.2 正规式和CFG的适用条件 一般情况下正规式适合描述线性结构如标识符、关键字、注释等。而CFG适合描述具有嵌套(层次)性质的非线性结构如不同结构的句子if-then-else、begin-end等。
3.3 形式语言与自动机简介 乔姆斯基(Chomsky)把文法分为四种类型: 0型、1型、2型和3型。文法之间的差异在于对产生式施加不同的限制。 定义3.8 若文法G(NTPS)的每个产生式α→β中均有α∈(N∪T)*且至少含有一个非终结符β∈(N∪T)*则称G为0型文法。 对0型文法施加以下第i条限制即可得到i型文法。 1G的任何产生式α→β(S→ε除外) 均满足|α|≤|β| (|x|表示x中文法符号的个数) 2G的任何产生式形如A→β其中A∈Nβ∈(N∪T)* 3G的任何产生式形如A→a 或者A→aB(或者A→Ba)其中AB∈Na∈T。 0型文法也被称为短语文法任何0型语言都是递归可枚举的反之递归可枚举集也必定是一个0型语言。 1型文法就是上下文有关文法这种文法意味着对非终结符的替换必须考虑上下文并且一般不允许换成ε串。例如若αAβ→αγβ是1型文法的产生式α和β不全为空则非终结符A只有在左边是α右边是β这样的上下文中才可能替换成γ。 2型文法就是上下文无关文法非终结符的替换无需考虑上下文。 3型文法等价于正规式因而也被称为正规文法或线性文法。 四种类型的文法和它们所描述的语言以及识别对应语言的自动机分别列举在表中。 4 自上而下分析的一般方法
4.1 基本思想 自上而下分析的基本思想是对于任何一个输入序列从文法的开始符号开始进行最左推导直到得到一个合法句子或者发现一个非法结构。在推导的过程中试图用一切可能的方法自上而下、从左到右为输入序列建立分析树。整个分析是一种试探的过程是反复使用不同产生式谋求与输入序列匹配的过程。
4.2 例题 已知如下文法G(S)给出输入序列ωcad自上而下试探建立分析树的过程。 G(S): S → cAd A → ab | a 试探性质的自上而下分析 (a) 匹配失败回溯(b) 匹配成功接收 (1) 若存在形如A → αβ1|αβ2的产生式即A产生式中有多于一个候选项的前缀相同(称为公共左因子或简称左因子)则可能会造成虚假匹配使得在分析过程中可能需要进行大量回溯从而造成分析效率低、语义动作难以恢复以及出错位置的报告不确切等。 (2) 若存在形如A → Aα的产生式则分析过程中一旦采用了该产生式去替换就会陷入死循环而使分析无法进行下去。产生式的这种形式被称为左递归。 为了避免上述弱点需要对文法进行重写。消除左递归以避免陷入死循环提取左因子以避免回溯。 4.3 消除左递归 分类直接左递归 间接左递归 规则1 直接左递归的产生式A→Aα|β β不以A开头 A→βA A→αA|ε 规则2 直接左递归的产生式 A→ Aα1 | Aα2 | ... | Aαm |β1 |β2 | ...|βn所有βi均不以A直接开头或间接开头 A→β1A|β2A|...|βnA A→α1A|α2A|...αmA|ε 并不是所有的文法都能消除左递归 4.4 提取左因子 对于有左因子的文法推导过程中会出现无法确定用A产生式的哪个候选项替换A的情况这时可以重写A产生式来推迟这种决定直到看见足够的输入能正确决定所需选择为止。这一过程类似于有限自动机的确定化被称为提取左因子。 算法3.3 提取文法的左因子 输入 文法G 输出 等价的无左因子文法G 方法 为每个产生式A找出其候选项中最长公共前缀α重排A产生式如下其中γ是不以α为前缀的其他候选项。 A→ αβ1|αβ2| ...|αβn|γ 并用下述产生式替代之。 A→ αA|γ A→ β1|β2| ...|βn 重复此过程直到所有A产生式的候选项中均不再有公共前缀。 练习 1、文法G(A):A→aABj | a B→Bb | d 2、文法G(M):M→MaH | H H→b(M) | (M) | b 3、文法G(S):S→AdD | ε A→aAd | ε D→DdA | b | ε 5FIRST集和FOLLOW集 5.1 FIRST集 算法3.5 计算X的FIRST集合 输入 文法符号X 输出 X的FIRST集合 方法 应用下述规则 ① 若X是终结符则FIRST(X){X} ② 若X 是非终结符且有X→ε则加入ε到FIRST(X) ③ 若X 是非终结符且有X→Y1Y2...Yk并令Y0εYk1ε则对所有j(0≤j≤k)若a∈FIRST(Yj1)且ε∈FIRST(Yj)加入a到FIRST(X)。 5.2 FOLLOW 算法3.6 计算所有非终结符的FOLLOW集合 输入 文法G 输出 G中所有非终结符的FOLLOW集合 方法 应用下述规则: ① 加入#到FOLLOW(S)其中S是开始符号#是输入结束标记 ② 若有产生式A→αBβ则除ε外FIRST(β)的全体加入到FOLLOW(B) ③ 若有产生式A→αB或A→αBβ而ε∈FIRST(β)则FOLLOW(A)的全体加入FOLLOW(B)。 6预测分析表 算法3.7 构造预测分析表 输入 文法G 输出 分析表M 方法 应用下述规则 ① 对文法的每个产生式A→α执行②和③ ② 对FIRST(α)的每个终结符a加入α到M[Aa] ③ 若ε在FIRST(α)中则对FOLLOW(A)的每个终结符b(包括#)加入α到M[Ab] ④ M中其他没有定义的条目均是error。 预测分析表是一个二维数组M[A, a] 所有的非终结符构成分析表的行下标 所有的终结符构成分析表的列下标其中包括特殊的结束标志#。 M[A, a]中的内容表示当前栈顶为非终结符A且当前输入为终结符a时分析器要进行的动作。 3.4.5.3 LL(1)文法 定义3.12 一个文法G被称为是LL(1)文法当且仅当为它构造的预测分析表中不含多重定义的条目。由此分析表所组成的分析器被称为LL(1)分析器它所分析的语言被称为LL(1)语言。第一个L表示从左到右扫描输入序列第二个L表示产生最左推导1表示在确定分析器的每一步动作时向前看一个终结符。 推论3.2 一个文法G是LL(1)的当且仅当G的任何两个产生式A→α|β满足下面条件: ① 对任何终结符aα和β不能同时推导出以a开始的文法符号序列 ② α和β最多有一个可以推导出ε ③ 若β ε则α不能推导出以在FOLLOW(A)中的终结符开始的任何文法符号序列。 推论3.2实际上等价于当且仅当G的任何两个产生式A→α|β满足上述三个条件时为文法G构造的预测分析表中不含多重定义的条目。反之若不满足三个条件之一则分析表中有多重定义条目。 若条件①不满足即存在终结符aα和β同时推导出以a开始的文法符号序列则根据算法3.7规则②M[Aa]中就会有多重定义条目A→α和A→β 若条件②不满足即α和β均可推出ε则根据算法3.7规则③任何属于FOLLOW(A)的终结符b(包括#)M[Ab]中就会有多重定义条目A→α和A→β 若条件③不满足即存在终结符b它既在FOLLOW(A)中又在FIRST(α)中则 算法3.7规则②把条目A→α加入到M[Ab]中而规则③又把条目A→β加入到M[Ab]中。 LL(1)文法的弱点 (1) 文法比较难写。因为按照人们习惯写出的文法往往含有左递归和左因子。虽然有成熟的算法可以消除左递归和提取左因子但改写之后的文法很难读也很难使用。同时对比分析树可以看出改写后文法构造的分析树不直观且推导步骤增加。 (2) LL(1)文法适应范围有限对于有些语言往往写不出它的LL(1)文法。
