第2章-一个简单的语法制导翻译器

1第二章一个简单的语法制导翻译器2本章主要内容用C语言开发一个把中缀表达式转换为后缀表达式的翻译程序，展示基本的编译技术主要描述编译器的前端词法分析、语法分析和语义分析通过本章对编译的过程有所了解9*5+x95*x+中缀表达式expropexpr后缀表达式exprexprop32.1概述程序设计语言由语法(syntax)和语义(semantics)两个方面定义。程序设计语言的语法通常用上下文无关文法来表示。if_stmtif(expr)stmtelsestmtAbDcDeFgH|e中文：S-主语谓语宾语日语：S-主语宾语谓词阿拉伯语：S-谓词主语宾语语义的描述则比语法的描述难得多，采用非形式化的自然语言描述牛吃草。语义错误：汽车吃草。4如何描述语法上下文无关文法ContextFreeGrammar(CFG)Bakus-Naur范式(BNF)语法图SyntaxGraphIPNP-SBJVPNP-SBJDNPNPNN贷款|本息|回收|中国语法分析树ParseTree5Bakus-Naur范式(BNF)约翰·巴科斯巴科斯-诺尔范式Form6BNF例子标识符的定义：identifier::=letter{letter|digit}letter::=“A”|“B”|“C”|...|“Z”|“a”|“b”|...|“z”digit::=“0”|“1”|“2”|...|“9”整数的定义：integer::=[symbol]unsignedunsigned::=digit{digit}symbol::=+|-digit::=0|1|2|...|9BNF范式的内容：(1)在双引号中的字(word)代表着这些字符本身。而double_quote用来代表双引号。(2)在双引号外的字（有可能有下划线）代表着语法部分。(3)尖括号()内包含的为必选项。(4)方括号([])内包含的为可选项。(5)大括号({})内包含的为可重复0至无数次的项。(6)竖线(|)表示在其左右两边任选一项，相当于OR的意思。(7)::=是“被定义为”的意思。非终结符终结符省略了尖括号7语法图SyntaxGraph尼古拉斯·沃斯提出了“结构化程序设计”的概念,算法+数据结构=程序,设计了Pascal语言。8上下文无关文法Context-FreeGrammar,CFG上下文无关文法CFG是一个四元组(Vt,Vn,S,P)，其中：1.Vt是一个非空有穷集合，称作终结符号集合TerminalSymbols2.Vn是一个非空有穷集合，称作非终结符号集合Non-terminals，且VtVn=。3.SVn，称作开始符号StartSymbol。4.P是一个非空有穷集合，称为产生式集合ProductionRules，每条产生式形为A，其中AVn，(VtVn)*。9例2.1简单的算术表达式listlist+digitlistlist-digitlistdigitdigit0|1|2|3|4|5|6|7|8|9终结符号：+-0123456789Vt非终结符号：listdigitVn开始符号：list“”：推导，左部是非终结符，右部是(VtVn)*“|”表示“或者”listlist+digitlist－digitdigit9529-5+210例2.1简单的算术表达式listlist+digit|list–digit|digitdigit0|1|2|3|4|5|6|7|8|9上述文法定义的是由加号和减号分隔的数字序列构成的列表。11例2.2数字序列9-5+2的推导（derive）listlist+digitlist-digit+digitdigit-digit+digit9-digit+digit9-5+digit9-5+2P1:listlist+digitP2:listlist-digitP3:listdigitP4:digit9P4:digit5P4:digit2从开始符号推导得到的所有的终结符号串的集合称为该文法定义的语言(language)。12例2.3函数调用中的参数列表callid(opt_params)opt_paramsparams|paramsparams,param|parammain()square(n)max(m,n)132.2.1分析树(ParseTree)分析树描述如何从文法的开始符号推导出它的语言中的一个语句。如果非终结符A有产生式AXYZ，则A的一棵分析树为：AXYZ14句法分析树ParseTree分析树具有如下性质：根结点是开始符号StartSymbol叶子结点是终结符或内部结点是一个非终结符Non-TerminalIfAx1x2…xn,ThenA是一个非终结符;x1x2…xn是A的孩子，是终结符或非终结符一个文法生成的语言是它的某个分析树生成的串的集合。为给定的符号串找到一棵分析树的过程称为串的语法分析(parsing)。15listdigitdigitlistdigitlist952-+listlist+digitlist-digit+digitdigit-digit+digit9-digit+digit9-5+digit9-5+2推导过程可以用分析树（ParseTree）表示token文法Grammar:stringstring+string|string–string|0|1|…|9162.2.2二义性Ambiguity对某个文法，如一个句子有两棵以上的分析树，称为二义（歧义）文法。stringstringstringstringstring+2-59stringstringstringstringstring-+2599-5+2listlist+digit|list–digit|digit172.2.3运算符的结合性AssociativityofOperators可以用括号来表明计算顺序，如9-5+2=(9-5)+2如果对某个运算符op，x1,x2,x3为运算对象，且x1opx2opx3表示(x1opx2)opx3，则称op是左结合的；如果x1opx2opx3表示x1op(x2opx3)，则称op是右结合的。左结合例子：a=3-4-5;a=3-4+5；右结合例子：a=b=c+1;a=**p；q=&*p；18rightletter=right|letterlettera|b|c|…|zlistdigitdigitlistdigitlist952-+listlist+digit|list-digit|digitdigit0|1|…|9rightletterletterrightletterrightcba==Leftvs.Right9-5+2a=b=c192.2.4算符优先级OperatorPrecedence9+5*2是什么含义?(9+2)*5或9+(5*2)？不同的运算符号有不同的优先级，如9+5*2表示9+(5*2)，所以*的优先级比+高。()*/+-优先级20通过适当改写文法规则，可以描述不同的结合律和优先级：factordigit|(expr)termterm*factor|term/factor|factorexprexpr+term|expr–term|termfactor(因子)：不能被任何运算符分开的表达式term(项)：可以被高优先级的运算符*和/分开，但不能被低优先级运算符分开的表达式expr(表达式)：expression对于处理n层优先级的情况，我们需要n+1个非终结符号。21Java语句的语法stmtid=expr;|if(expr)thenstmt|if(expr)stmtelsestmt|while(expr)stmt|dostmtwhile(expr);|{stmts}stmtsstmtsstmt|注意:“;”的设置假设改为：if(expr)thenstmt；又假设stmt为赋值语句，那么语句就会多出现一个分号，例如：if(a0)b++;;222.3语法制导翻译Syntax-DirectedTranslation语法是掌握语义的钥匙语法制导定义每个文法符号有属性的集合每个产生式有语义计算规则的集合语法制导翻译方案描述翻译过程一个例子：将中缀表达式翻译成后缀表达式SSubjVerbObj奶牛吃草exprexpr1+term翻译expr1;匹配+；翻译term；处理加法表达式；232.3.1后缀表示PostfixNotation翻译的归纳定义：如果E一个变量或常数,那么Postfix(E)=E如果EE1opE2,那么Postfix(E)=Postfix(E1opE2)=Postfix(E1)Postfix(E2)op如果E(E1)，那么Postfix(E)=Postfix(E1)Examples:(9–5)+295–2+9–(5+2)952+-242.3.2语法制导定义Syntax-DirectedDefinition每个文法符号有属性的集合(aSetofAttributes)每个产生式有语义计算规则的集合(aSetofSemanticRules)252.3.3中缀到后缀翻译的语法制导定义例2.6为每个非终结符定义属性“t”，表示其对应的表达式的后缀表示，每条产生式带有语义规则ProductionSemanticRuleexprexpr1+termexpr.t:=expr1.t||term.t||‘+’exprexpr1–termexpr.t:=expr1.t||term.t||’-’exprtermexpr.t:=term.tterm0term.t:=‘0’term1term.t:=‘1’….….term9term.t:=‘9’expr1的解释26注释分析树综合属性：属性值是由子节点的属性确定的通过遍历分析树可以求得结果计算顺序：深度优先遍历是一种常用的方法expr.t=95-expr.t=9expr.t=95-2+term.t=5term.t=2term.t=92+5-9继承属性：属性值是父结点以及兄弟结点上的属性值决定的。272.3.4语法树的遍历voidvisit(nodeN){for(从左到右遍历N的每个子结点C){visit(C);}按照结点N上的语义规则求值；(例如：打印结点N的内容)}//后序遍历，后根遍历procedurevisit(nodeN){按照结点N上的语义规则求值；(例如：打印结点N的内容)for(从左到右遍历N的每个子结点C){visit(C);}}//先序遍历，先根遍历//访问以结点N为根的树282.3.5语法制导翻译方案也可以把上下文无关文法扩展成翻译模式（也叫翻译文法），不生成分析树来进行属性计算。特点是在产生式的右部中插入语义动作rest+term{print(‘+’)}rest1翻译模式类似于语法制导定义，只是语义规则的计算顺序是显式给出的。rest+term{print(‘+’)}rest129语法制导翻译方案exprexpr1+term{print(‘+’)}expr1-term{print(‘-’)}termterm0{print(‘0’)}term1{print(‘1’)}…term9{print(‘9’)}9-5+2产生式右部30termtermtermexprexprexpr952-+{print(‘-’)}{print(‘9’)}{print(‘5’)}{print(‘2’)}{print(‘+’)}可以把语义动作看作是特殊的终结符，不匹配输入，语法分析的时候直接执行312.4语法分析(Parsing)两类方法（指构造分析树结点的顺序）自顶向下(top-down)自底向上(bottom-up)自顶向下方法从开始符号开始构造分析树对终结符，看是否与输入匹配（否则回溯）对非终结符，选择一个