南开大学编译原理第二章课件.ppt

南开大学编译原理第二章课件.ppt*第二章一个简单的编译器*学****内容构造一个以语法分析器为核心的编译器——将中缀表达式转换为后缀表示形式利用上下文无关文法描述源语言的语法结构利用语法制导翻译方法进行表达式转换构造预测分析器,进行语法分析,并同时进行语法制导翻译*学****内容(续)构造更复杂的词法分析器——消除单字符单词的限制,支持变量符号表的简单实现方法*上下文无关文法,context-freegrammar巴科斯-瑙尔范式,Backus-NaurForm,BNF语义描述:非形式化描述辅助代码生成:语法制导翻译,syntax-directedtranslation*构造一个简单的编译器目标:表达式中缀表示后缀表示9-5+295-2+过程:语法制导翻译器:语法分析+中间代码生成*:描述语言的语法结构if(expression)statementelsestatement 对应的文法规则stmtif(expr)stmtelsestmt产生式,productionif,else——单词,终结符号,terminalexpr,stmt——单词序列,非终结符号,nonterminal具有形式为…可*上下文无关文法四个部分组成一组终结符号,单词,基本符号一组非终结符号(语法变量),语法范畴,语法概念一组产生式,定义语法范畴产生式:AαA—一个非终结符,左部α—终结符或/与非终结符串,右部一个特定的非终结符——开始符号,startsymbol*形式化定义几个概念Σ:有穷字母表,元素——符号符号串:Σ中符号构成的有穷序列空字:不含任何符号的序列,εΣ*:符号串全体,包括空字φ:空集{},区分ε,{},{ε}Σ*的子集U、V的积(连接)*几个概念(续)UV≠VU,(UV)W=U(VW)V自身的n次积(连接)记为VnV0={ε}V的闭包(closure)每个符号串,都是V中符号串有限次连接正则闭包,V+=VV**四元式定义上下文无法文法(VT,VN,S,P)VT:非空有限集,终结符号集合VN:非空有限集,非终结符号集合S:开始符号P:产生式集合(有限集)每个产生式形式Aa,其中关于A的产生式S至少在某个产生式左部出现一次