第三章上下文无关文法及分析

第三章上下文无关文法及分析学习目标:理解:上下文无关文法,推导，归约，分析树，抽象语法树了解:语法的结构，二义性文法分析学习的主要内容语法结构的描述:上下文无关文法语法分析的方法（代码实现语法规则分析）自顶向下的语法分析自底向上的语法分析分析树或语法树，都是递归的线性结构结果的数据结构自顶向下分析自底向上分析表示为DFA算法描述工具确定程序的语法或结构确定单词的结构任务语法分析词法分析上下文无关文法正则表达式3.1分析过程3.2上下文无关文法3.3分析树与抽象语法树3.4二义性3.1分析过程分析的任务从由扫描程序产生的记号中确定程序的语法结构隐式或显式地构造出表示该结构的分析树或语法树记号序列分析程序分析树/语法树分析的接口输入:当分析过程需要下一个记号时，分析程序就调用扫描程序过程以从输入中获得它输出:构造的隐式或显式语法树。语法树的每个节点包括了编译后面过程所需的特性分析的错误处理错误恢复报告有意义的错误信息，并继续进行分析（去找到尽可能多的错误）错误修复从提交给它的非正确版本中推断出一个可能正确的代码版本（这通常在简单情况下才发生的）3.2上下文无关文法作用上下文无关文法说明程序设计语言的语法结构除了上下文无关文法涉及到了递归规则之外，与使用正则表达式说明词法结构很相似例如整型算术表达式的上下文无关文法是exp-expopexp|(exp)|numberop-+|-|*number的正则表达式number=digitdigit*digit=0|1|2|3|4|5|6|7|8|93.2.1上下文无关文法的定义定义上下文无关文法G=(VT,VN,P,S):1.VT是终结符集合2.VN是非终结符集合,VN∩VT=φ3.P是产生式集合,或语法规则,形如A→α,其中A∈VN且α∈(VN∪VT)*4.S是开始符号,S∈VN例如简单的算术表达式的文法G=(VT,VN,P,S)VT={num,+,-,*,/,(,)}VN={exp,op}Exp是开始符号产生式是:exp-expopexpexp-(exp)exp-numop-+op--op-*op-/解释1.VT是组成符号串的基本符号。终结符是单词2.VN是用来表示符号串集合的结构名3.开始符号“S”表示的符号串集合是由语法定义的语言4.产生式定义了一种结构，结构名在箭头的左边。箭头的右边定义了结构的布局。5.产生式的形式(A→α)被称为Backus-Naur范式(或BNF)表示法惯例按照惯例，我们可以只写出一个文法的产生式一般来说，第一个产生式的左边是开始符号使用小写字母表示终结符使用大写字母或用…括起的表示非终结符如果A-α1,A-α2,…,A-αn是所有左边是A的产生式，我们可以写为A-α1|α2|…|αn例如简单算术表达式的文法可写为:E-EOE|(E)|numO-+|-|*|/文法的Chomsky分类有四类文法:1.无限制文法(0型)2.上下文有关文法(1型)3.上下文无关文法(2型)4.正规文法(3型)这四种文法的关系：上下文有关上下文无关正规无限制等同于正则表达式A→aBorA→a，A,B∈VN，a∈VT正规文法(3型)无需考虑A在上下文中的出现情况A→β，A∈VN，β∈V*上下文无关文法(2型)将A替换成时，必须考虑A的上下文，A→,,∈V*A∈VN,β∈V＋上下文有关文法(1型)对产生式没有限制α→βV=VN∪VTα∈V+,β∈V*无限制文法(0型)说明产生式类型3.2.2推导和归约推导和归约的作用上下文无关文法规则确定了为由规则定义的结构的记号符号符合语法的串集例如:对应文法exp-expopexp|(exp)|numberop-+|-|*(34-3)*42是合法的串(34-3*42不是合法的串文法规则通过推导或归约确定记号符号的正规集直接推导and直接归约A-β是文法G的产生式,若有v和w满足:v=αAγ,w=αβγ,其中α,γ∈(VN∪VT)*,则称v直接推导到w,或w直接归约到v，记作v=w直接推导就是用产生式的右部替换产生式的左部（非终结符）的过程直接归约就是用产生式的左部非终结符替换产生式的右部的过程例如文法G：S→0S1，S→01直接推导：0S100S11(S→0S1)00S11000S111(S→0S1)000S11100001111(S→01)S0S1(S→0S1)推导和归约=的闭包,α=*βα=*β当且仅当有0个或多个(n=0)推导序列α1=α2=…=αn-1=αn,α=α1且β=αnS=*w,其中w∈VT*且S是文法G的开始符号，被称为S推导出w或w归约到S例如exp-expopexp|(exp)|numop-+|-|*(34-3)*42的推导是:(1)exp=expopexp(exp-expopexp)(2)=expopnum(exp-num)(3)=exp*num(op-*)(4)=(exp)*num(exp-(exp))(5)=(expopexp)*num(exp-expopexp)(6)=(expopnum)*num(exp-num)(7)=(exp-num)*num(op--)(8)=(num-num)*num(exp-num)3.2.3由文法定义的语言G的句型S是文法G的开始符号，若S=*α,α∈(VN∪VT)*,则α是文法G的一个句型G的句子若w是G的句型,且w仅包含终结符，则w是G的一个句子例如G:S→0S1，S→01S0S100S11000S11100001111S,0S1,00S11,000S111,00001111都是G的句型00001111是G的句子由文法G定义的语言,写作L(G)L(G)={w∈VT*|S=*w，S是文法G的开始符号}即,L(G)是文法G的一切句子的集合例如:G:S→0S1,S→01S=0S1=00S11=03S13=…=0n-1S1n-1=0n1nL(G)={0n1n|n≥1}文法G和L(G)的关系根据文法，可以通过推导得到该文法相应的语言例如G：E→E+T|TT→T×F|FF→(E)|aEE+TT+TF+Ta+Ta+T×Fa+F×Fa+a×Fa+a×aL(G)是包含a,+,×,(和)的算术表达式有了语言的要求，也可以为该语言设计文法例如若语言由0、1符号串组成，串中0和1的个数相同，构造其文法为：A→0B|1CB→1|1A|0BBC→0|0A|1CC3.3分析树和抽象语法树3.3.1分析树分析树的作用分析树是表述记号串结构的一种十分有用的表示法。分析树可视化表示推导例如:E→E+T|TT→T×F|FF→(E)|i“i+i×i”的推导和分析树为：EET+TFT×E=E+TEET+TFT×E=E+T=E+T×F=T+T×F=T+T=T+T×F=…=i+i×iiii…iii…=…=i+i×i解释:一个串的分析树一般对应着串的多个推导。分析树抽取出推导的主要特征，同时却将表面的差别按顺序分解开来。推导不能唯一地表示串的结构，而分析树可以分析树的定义文法G中的一个分析树是一个作了标记的树:1.树的根节点标记为开始符号S2.每个叶子节点标记为终结符或ε3.每个非叶子节点标记为非终结符4.如果一个节点A∈VN有n个孩子，分别标记为X1,X2,..,Xn(可能为终结符或非终结符）,则有A-X1X2…Xn∈P最左和最右推导最左推导最左推导是指推导的每一步中最左的非终结符都要被替换它对应着分析树的前序编号例如exp-expopexp|(exp)|numop-+|-|*“num+num”的最左推导是：exp=expopexp=numopexp=num+exp=num+num1exp2exp4exp3opnum+num最右推导最右推导是指推导的每一步中最右的非终结符都要被替换。它对应着分析树的后序编号“num+num”的最右推导是:exp=expopexp=expopnum=exp+num=num+num1exp4exp2exp3opnum+num最左推导和最右推导对于串的构成是唯一的它们唯一对应一个分析树分析树和推导的关系每个推导产生一个分析树多个推导可能产生同样的分析树最左和最右推导对应唯一地分析树最左或最右推导时，分析树唯一地表示的语法结构，其他推导不一定3.3.2抽象语法树抽象语法树的必要性分析树包含了一些与编译器生成可执行代码无关的信息例如expexpexpopnum(3)+num(4)+34Abstractsyntaxtree表达式(34-3)*42的分析树和抽象语法树是：抽象语法树的定义抽象语法树是实际记号串的抽象表示包含了转换所需要的所有信息(精确地表示了串的语义内容）比分析树更有效的表示形式分析程序将遍历分析树表示的所有步骤，而仅构成一个抽象语法树例如文法描述statement-if-stmt|otherif-stmt-if(exp)statementelse-partelse-part-elsestatement|εexp-0|1串“if(0)otherelseother”的分析树和抽象语法树是：statementif-stmtif(exp)statementelse-part0otherelsestatementotherif0otherother3.4二义性一般来说，记号串有一个分析树，可能对应串的多个推导E=E+T=T+T=T+T×F=…=i+i×iE=E+T=E+T×F=T+T×F=…=i+i×iEET+TFT×iii…串“i+i×i”的分析树有些文法有可能存在串有多个分析树（或最左/最右推导）例如:整型算术表达式文法:E→E+E|E×E|(E)|I串“i×i+i”有两个不同的语法树:对应两个最左推导：1：EE+EE×E+Ei×E+Ei×i+Ei×i+i2：EE×Ei×Ei×E+Ei×i+Ei×i+iiEE+EEE×iiEEE×iEE+ii二义性如果一个文法存在某个串对应两棵不同的语法树（或有两个不同的最左（右）推导），则说这个文法是二义的。如何解决二义性两个解决二义性的基本方法：1.设置一个规则，该规则可在每个二义性情况下指出哪一个语法树是正确的。iEE+EEE×ii消除二义性规则:乘法的优先级高于加法乘法和加法为左结合。整型算术表达式文法:E→E+E|E×E|(E)|i串“i+i+i”有两个不同的语法树:iEE+EEE+iiEEE+iEE+ii基于消除二义性规则，第一个是正确的2.将文法改变成一个强制正确分析树的构造的格式，这样就可以解决二义性了。例如:E-E+E|E×E|(E)|i加入优先权把具有相同优先权的算符归纳为一组中，并为每一种优先权规定不同的规则:E-E+E|TT-T×T|FF-(E)|i“i×i+i”不是二义性的，它的最左推导是:E=E+E=T+E=T×T+E=…=i×i+i但是“i+i+i”还存在二义性，有两个不同的最左推导：E=E+E=E+E+E=…E=E+E=T+E=F+E=i+E=i+E+E=…FEE+ETT×TTFiFii加入结合性:左递归规则使得它的算符在左边结合，而右递归规则使得它们在右边结合E-E+T|TT-T×F|FF-(E)|i“i+i+i”不是二义的，它的最左推导是：E=E+T=E+T+T=T+T+T=…=i+i+iiTET+EET+ii………