Chapter04_SyntaxAnalysis语法分析.

北京化工大学信息科学与技术学院计算机系史晟辉[e-mail]@mail.buct.edu.cn2020/1/11北京化工大学信息科学与技术学院计算机系2Chapter4SyntaxAnalysis语法分析4.1语法分析器的作用4.2上下文无关文法4.3自顶向下语法分析4.4自底向上语法分析2020/1/11北京化工大学信息科学与技术学院计算机系34.1语法分析器的作用词法分析源程序目标程序语法分析语义分析文字表、符号表处理错误处理中间代码优化中间代码生成前端后端●Thephaseofacompiler编译程序的结构目标代码生成2020/1/11北京化工大学信息科学与技术学院计算机系44.1语法分析器的作用词法分析源程序目标程序语法分析语义分析文字表、符号表处理错误处理中间代码优化中间代码生成前端后端●Thephaseofacompiler编译程序的结构目标代码生成2020/1/11北京化工大学信息科学与技术学院计算机系54.1语法分析器的作用语法分析器词法分析器记号流源程序前端其他部分分析树中间表示符号表管理器出错处理器parser分析程序sequenceoftokens记号序列(input)syntaxtree语法树(output)syntaxTree=parse();2020/1/11北京化工大学信息科学与技术学院计算机系64.1.1语法错误的处理●源程序中可能出现的错误①词法错误如非法字符或拼写错关键字、标识符等；@intege20times②语法错误是指语法结构出错，如少分号、begin/end不配对等。beginx:=a+by:=x;③静态语义错误：如类型不一致、参数不匹配等；a,b:integer;x:array[1..10]ofinteger;x:=a+b;④动态语义错误（逻辑错误）：如无穷递归、变量为零时作除数等。while(t){...};a:=a/b;2020/1/11北京化工大学信息科学与技术学院计算机系74.1.1语法错误的处理●语法错误处理的目标•清楚而准确地报告错误的出现，地点正确、不漏报、不错报也不多报；•迅速地从每个错误中恢复过来（以便分析继续进行）；•不应使对语法正确源程序的分析速度降低太多。2020/1/11北京化工大学信息科学与技术学院计算机系84.1.1错误恢复策略●语法错误的基本恢复策略•紧急方式恢复：抛弃若干输入，直到遇到同步记号。•短语级恢复：采用串替换的方式对剩余输入进行局部纠正（抛弃＋插入）。•出错产生式：用出错产生式捕捉错误（预测错误）。预置型的短语级恢复方式。•全局纠正：对错误输入序列x，找相近序列y，使得x变换成y所需的修改、插入、删除次数最少。最近似正确的纠错程序最小代价纠错2020/1/11北京化工大学信息科学与技术学院计算机系94.2Context-freegrammars上下文无关文法●Thesyntaxofaprogramminglanguageisusuallygivenbythegrammarrulesofacontext-freegrammar.程序设计语言的语法通常是由上下文无关文法规则给出。●Therulesofacontext-freegrammararerecursive.上下文无关文法的规则是递归的。2020/1/11北京化工大学信息科学与技术学院计算机系104.2.1上下文无关文法概述4.2.1.1Comparisontoregularexpressionnotation与正则表达式比较thecontext-freegrammar:numbernumberdigit|digit；digit0|1|2|3|……|9theregularexpression:number=digitdigit*digit=0|l|2|3|4|5l6|7|8|9*•|()=无不出现|含义变化(=,:,::=)thecontext-freegrammar:expexpopexp|(exp)|numberop+|–|*Backus-Naur范式(BNF文法)2020/1/11北京化工大学信息科学与技术学院计算机系114.2.2.1Specificationofcontext-freegrammarrules上下文无关文法规则的说明●什么是文法？文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或称“语法”）。例:请判断英语句子Thebigelephantatethepeanut.语法上是否正确？2020/1/11北京化工大学信息科学与技术学院计算机系12句子主语谓语主语冠词形容词名词冠词the形容词big名词elephant|peanut谓语动词宾语动词ate宾语冠词名词解：(1)已知语法规则(2)由规则推导句子推导方法：从一个要识别的符号开始推导，即用相应规则的右部来替代规则的左部，每次仅用一条规则去进行推导。句子=主语谓语主语谓语=代词谓语……直到所有带的符号都由终结符号替代为止。2020/1/11北京化工大学信息科学与技术学院计算机系13句子=主语谓语=冠词形容词名词谓语=the形容词名词谓语=thebig名词谓语=thebigelephant谓语=thebigelephant动词宾语=thebigelephantate宾语=thebigelephantate冠词名词=thebigelephantatethe名词=thebigelephantatethepeanut句子::=主语谓语主语::=冠词形容词名词冠词::=the形容词::=big名词::=elephant|peanut谓语::=动词宾语动词::=ate宾语::=冠词名词上述推导可写成句子=thebigelephantatethepeanut+2020/1/11北京化工大学信息科学与技术学院计算机系14(1)有若干语法成分同时存在时，总是从最左的语法成分进行推导，这称之为最左推导，类似的有最右推导（一般推导）。(2)从一组规则可推出不同的句子，如以上规则还可推出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子，它们在语法上都正确，但在语义上都不正确。所谓文法是在形式上对句子结构的定义与描述，而未涉及语义问题。Note2020/1/11北京化工大学信息科学与技术学院计算机系154.2.2.2Derivationsandthelanguagedefinedbyagrammar推导及由文法定义的语言1.相应的正则式：2.derivation推导例：根据文法，请判断程序(34-3)*42语法上是否正确？expexpopexp|(exp)|numberop+|–|*(1)exp=expopexp[expexpopexp](2)=expopnumber[expnumber](3)=exp*number[op*](4)=(exp)*number[exp(exp)](5)=(expopexp)*number[expexpopexp](6)=(expopnumber)*number[expnumber](7)=(exp-number)*number[op-](8)=(number-number)*number[expnumber](number-number)*number2020/1/11北京化工大学信息科学与技术学院计算机系16L(G)={s|exp=*s}●文法定义的（产生的）语言exp：开始符号thestartsymbol=*：星推导(=+：正推导)s：句子expexpopexp|(exp)|numberop+|–|*exp：开始符号thestartsymbolexpnumber：产生式Nonterminals(非终结符)Terminals(终结符)●文法2020/1/11北京化工大学信息科学与技术学院计算机系17●Example1)已知文法G：E(E)|a，请问文法定义的语言是什么？L(G)={a,(a),((a)),(((a))),…}={(na)n|naninteger=0}2)已知文法G：E(E)，请问文法定义的语言是什么？空3)已知文法G：EE+a|a，请问文法定义的语言是什么？L(G)={a,a+a,a+a+a,a+a+a+a,...}4)已知正则式为a+，请问相应的文法及定义的语言是什么？G:AAa|aorAaA|aL(a*)={an|naninteger=0}leftrecursiverightrecursive5)已知正则式为a*，请问相应的文法是什么？G:AAa|orAaA|Recursive递归Grammar文法AA|AA|2020/1/11北京化工大学信息科学与技术学院计算机系18●Example6)已知文法定义的语言如下(C的嵌套if语句)，请写出该文法？otherif(0)otherif(1)otherif(0)otherelseotherif(1)otherelseotherif(0)if(0)otherif(0)if(1)otherelseotherif(1)otherelseif(0)otherelseotherG:Statementif-stmt|otherif-stmtif(exp)statement|if(exp)statementelsestatementexp0|1statementif-stmt|otherif-stmtif(exp)statementelse-partelse-partelsestatement|exp0|1OR2020/1/11北京化工大学信息科学与技术学院计算机系19●Example7)已知文法A(A)A|，请问(()(()))()语法正确吗？A=(A)A[A(A)A]=(A)(A)A[A(A)A]=(A)(A)[A]=(A)()[A]=((A)A)()[A(A)A]=(()A)()[A]=(()(A)A)()[A(A)A]=(()(A))()[A]=(()((A)A))()[A(A)A]=(()(()A))()[A]=(()(()))()[A]∴(()(()))()语法正确2020/1/11北京化工大学信息科学与技术学院计算机系20●Example8)已知文法G如下，请问文法定义的语言是什么？stmt-sequencestmt;stmt-sequence|stmtstmtsL(G)={s,s;s,s;s;s,...)若例8中允许语句序列为空，即定义的语言为L(G‘)={,s;,s;s;,s;s;s;,...)，则相应的文法是什么？stmt-sequencestmt;stmt-sequence|stmts若例8中允许语句序列为空，但要求分号作为语句分隔符，即定义的语言为L(G‘)={,s,s;s,s;s;s,...)，则相应的文法是什么？stmt-sequencenonempty-stmt-sequence|nonempty-stmt-sequencestmt；nonempty-stmt-sequence|stmtstmts2020/1/11北京化工大学信息科学与技术学院计算机系21●Example若例8中允许语句序列为空，但要求分号作为语句结束符，即定义的语言为L(G‘)={;,s;,;s;,s;s;,;s;s;,s;s;s;,...)，则相应的文法是什么？stmt-sequencestmt-other1stmt-other2stmt-other1stmt|stmt-other2;