编译原理语法分析.

第四章语法分析学习重点上下文无关文法自顶向下分析方法：递归实现、表驱动自底向上分析方法算符优先分析方法LR分析方法SLR规范LRLALR概述为什么使用上下文无法文法？精确、容易理解的语法描述特定类别语法——编译器自动构造额外好处——发现二义性和难于分析的结构加入特殊结构——翻译、错误检测基于语法的翻译方法描述——程序语言发展变化（新语句，语句变化…）——容易增加新结构，修改已有部分ADAADA9x,C++增加:模板、异常工具4.1语法分析器的角色errorslexicalanalyzerparserrestoffrontendsymboltablesourceprogramparsetreegetnexttokentokenregularexpressions•通常作为语法分析器的一部分实现•包括对单词扩充信息，以进行类型检查、语义分析等工作•利用语法检查单词流的语法结构•构造语法分析树•语法错误和修正•识别正确语法•报告错误intermediaterepresentation三类语法分析器通用分析器，Cocke-Younger-Kasami算法，Early算法，适用任何文法，效率低自顶向下分析器，top-down自底向上分析器，bottom-uptop-down，bottom-up：适用特定类别文法——LL、LR，描述能力足够4.1.1语法错误处理不同层次的错误词法：拼写错误语法：单词漏掉、顺序错误语义：类型错误逻辑：无限循环/递归调用语法错误处理为重点语法错误相对较多编译器容易高效检测错误处理目标三个“简单”的目标清楚、准确地检测、报告错误及其发生位置快速恢复，继续编译，以便发现后续错误不能对“正确”程序的编译速度造成很大影响完全实现困难LL，LR，可最快速度发现错误活前缀特性，viable-prefixproperty一个输入前缀不是语言中任何符号串前缀——发生错误例4.1有关程序错误的统计60%的程序无语法、语义错误错误发生是分散的：错误语句中80%只有一个错误，13%有两个多数错误是简单的：90%的错误是单个单词错误错误分类：60%是标点符号错误，20%是运算符和运算对象错误，15%是关键字错误例4.1（续）#includestdio.hintf1(intv){inti,j=0;for(i=1;i5;i++){j=v+f2(i)}returnj;}intf2(intu){intj;j=u+f1(u*u);returnj;}intmain(){inti,j=0;for(i=1;i10;i++){j=j+i*iprintf(“%d\n”,i);}printf(%d\n,f1(j));return0;}哪些“容易”恢复?哪些“困难”?4.1.2错误恢复策略1.Panic模式丢弃单词，直到发现“同步”单词设计者指定同步单词集，{end,“;”,“}”,…}缺点丢弃输入遗漏定义，造成更多错误遗漏错误优点简单适合每个语句一个错误的情况错误恢复策略（续）2.短语级（phraselevel）局部修正，继续分析“,”“;”，删除“,”，插入“;”同样由设计者指定修正方法避免无限循环有些情况不适用与Panic模式相结合，避免丢弃过多单词错误恢复策略（续）3.错误产生式（errorproduction）理解、描述错误模式文法添加生成错误语句的产生式拓广文法语法分析器程序如，对C语言赋值语句，为“:=”添加规则报告错误，但继续编译错误检测信息＋自动修正错误恢复策略（续）4.全局修正（globalcorrection）错误程序正确程序寻找最少修正步骤，插入、删除、替换不正确输入x，文法G—————y对应的语法分析树过于复杂，时空效率低最少修正xy4.2上下文无关文法定义：四元式(VT,VN,S,P)1.VT：终结符号（单词）集，T2.VN：非终结符（语法变量）集，NT，定义了文法/语言可生成的符号串集合3.S：S∈NT，开始符号，定义语言的所有符号串4.P，产生式集，PR，NT(T|NT)*规则T、NT如何组合，生成语言的合法符号串例4.2：简单表达式exprexpropexprexpr(expr)expr-exprexpridop+op-op*op/op蓝色符号——T，黑色符号——NT4.2.1符号约定1.终结符字母表靠前的小写字母，a、b、c…运算符，+、-…标点符号，(、)、,…数字，0、1、…、9粗体字符串，id、if…蓝色字符串，id、if…符号约定（续）2.非终结符字母表靠前的大写字母，A、B、C…S，通常作为开始符号斜体小写字符串，expr、term、…3.字母表靠后的大写字母X、Y、Z，语法符号——T或NT4.字母表靠后的小写字母u、v…，终结符号串，T*符号约定（续）5.小写希腊字母a、b、g…，语法符号串，(TNT)*6.左部相同的产生式可合并，‘|’——“或”Aa1;Aa2;…;Aak;Aa1|a2|…|a1，候选式7.第一个产生式的左部为开始符号例4.3利用符号约定简化文法例4.2中表达式文法简化后结果EEAE|(E)|-E|idA+|-|*|/|4.2.2推导（derivation）描述文法定义语言的过程自顶向下构造语法分析树的精确描述将产生式用作重写规则由开始符号起始每个步骤将符号串转换为另一个符号串转换规则：利用某个产生式，将符号串中出现的其左部NT替换为其右部符号串推导（续）EE+E|E*E|(E)|-E|idE-E，E可替换为-EE-E，“E直接推出-E”E*E(E)*EE-E-(E)-(id)替换序列，E-(id)的一个推导定义形式化定义aAbagb仅当存在产生式Aga1a2…an——a1an若ab且bg，则ag，“一步推导”，“直接推出”，推导步数=1，“一步或多步推导”，推导步数≥1，“0步或多步推导”，推导步数≥0***+*推导与语言的关系文法G，开始符号S，生成的语言L(G)终结符号串wwL(G)Sww：G的一个句子，sentenceCFG生成上下文无关语言两个CFG生成相同语言，两个CFG等价Sa，a可能包含NTa：G的一个句型，sententialform句子：不包含NT的句型*+例4.4EE*Eid*Eid*id句型句子E-E-(E)-(E+E)-(id+E)-(id+id)另一种推导过程E-E-(E)-(E+E)-(E+id)-(id+id)最左推导和最右推导最左推导：总替换最左边的NTE-E-(E)-(E+E)-(id+E)-(id+id)最右推导：总替换最右边的NTE-E-(E)-(E+E)-(E+id)-(id+id)形式化定义：AwAgwg，w只含TbAwbw，w只含TSa，a：最左句型，left-sententialformlmlmlmlmlmrmrmrmrmrmlmrm*lm4.2.3语法分析树和推导语法树：推导的图示，但不体现推导过程的顺序内部节点：非终结符A内部结点A的孩子节点：左右，对应推导过程中替换A的右部符号串的每个符号叶：由左至右句型，yield，frontier语法树与推导的关系一个推导过程：a1a2…ana1≡A，单节点，标记为Aai-1=X1X2…Xk对应语法树T第i步推导，XjY1Y2…YrT的第j个叶节点，添加r个孩子节点Y1,Y2,…,Yr，特殊情况，r=0，一个孩子e例4.5E-E-(E)-(E+E)-(id+E)-(id+id)例4.5E-E-(E)-(E+E)-(id+E)-(id+id)E-E-(E)-(E+E)-(E+id)-(id+id)一棵语法树可多个推导一棵语法树唯一最左推导，唯一最右推导4.2.4二义性文法（例4.6）句子多个语法树，多个最左（右）推导EE+Eid+Eid+E*Eid+id*Eid+id*idEE*EE+E*Eid+E*Eid+id*Eid+id*id4.3设计CFG4.3.1正规式与CFG正规式词法分析的基础描述正规语言描述能力不够，anbn，n≥1上下文无关文法语法分析的基础描述程序语言结构上下文无关语言正规式与上下文无关文法正规式可描述的语言CFG均可描述，(a|b)*abbA0aA0|aA1|bA0A1bA2A2bA3A3e正规语言上下文无关语言Reg.Lang.CFLsNFACFG1.状态i非终结符Ai：A0，A1，A2，A32.AiaAj3.AiAj4.若i为终态Aie：A3e5.若i为初态，Ai为开始符号：A0正则文法start03b21baabija:A0aA0,A0aA1:A0bA0,A1bA2:A2bA3ijeNFACFGAi的含义是什么？状态i终态路径上的符号串集合Ai取“初态状态i路径上的符号串集合”是否可以？变换规则如何修改？文法变成什么样？AjAiaA0eA0A0a,A1A0aA0A0b,A2bA1A3A2b,A0e为什么还需要正规式？1.词法规则很简单，正规式描述能力足够2.正规式更简洁、更容易理解3.能更自动构造更高效的词法分析器4.使编译器前端更模块化词法、语法规则的划分没有固定准则正规式更适合描述标识符、常量、关键字…的结构CFG更适合描述单词的结构化联系、层次化结构，如括号匹配，if-then-else，…4.3.2CFG的验证证明CFGG生成语言LG生成的每个符号串都在L中L中每个符号串都可由G生成例4.7：验证CFGS(S)S|e生成的语言L={所有括号组成的，且括号匹配的字符串，且只有这些字符串}一、S推导出的句子都L数学归纳法（推导步数）：1.基本情况：一步推导，e，括号匹配2.假定步骤n的推导都生成括号匹配的句子，考虑步骤=n的最左推导，必形如S(S)S(x)S(x)yx、y为步骤n的推导生成的句子——括号匹配的，因此(x)y是括号匹配的综合1、2，一得证**二、L中的符号串S都可推导出数学归纳法（符号串长度）1.基本情况：空串，可由S推导出2.假定L中2n的符号串都可由S推导出。考虑长度=2n的符号串w。它必以‘(’开始，设(x)为w的最短的括号匹配的前缀，则w形如(x)y，x、y长度小于2n，且括号匹配，因此可由S推导出，则存在推导S(S)S(x)S(x)y由1、2，二得证由一、二，原命题得证**设计CFG练习基本的递归L={anbb2n|n≥0}S→b|aSbb不包含子串011的0/1串S→0A|1S|eA→0A|1B|eB→0A|e形如xy(x≠y)的01串长度是什么情况必然不是xx？如何描述？其他情况如何描述？奇数S→B|BSBB→0|1设计CFG的难点手工进行，无形式化方法不同的语法分析方法对CFG有不同的特殊要求如自顶向下分析方法和自底向上分析方法CFG设计完成后可能需要修改CFG的修改两个目的去除“错误”重写，满足特殊要求-二义性-e-moves-回路-左递归-提取左公因子不合要求的问题4.3.3消除二义性例子：条件分支语句stmtifexprthenstmt|ifexprthenstmtelsestmt|other(任何其他形式的语句)无二义性的句子ifE1thenS1elseifE2thenS2elseS3语法树如下stmtstmtstmtexprexprE1E2S3S1S2thenthenelseelseififstmtstmt二义性句子ifE1thenifE2thenS1elseS2有两种意义ifE1thenifE2t