编译原理课件：第二章 一个简单的语法制导翻译器.ppt
78页
计算机科学与技术学院计算机科学与技术学院编译原理编译原理第一章第一章 编译原理简介编译原理简介 回顾回顾 第一章 编译原理简介 回顾v编译器：编译器：编译器是一种翻译器，它的特点是目标语言比源语言低级 编程语言机器语言编译器编译器 词法分析器词法分析器语法分析器语法分析器语义分析器语义分析器源程序源程序中间代码生成器中间代码生成器独立于机器的代码优化器独立于机器的代码优化器代码生成器代码生成器依赖于机器的代码优化器依赖于机器的代码优化器目标机器代码目标机器代码符号表符号表第一章 编译原理简介 回顾 符符 号号 表表 positioninitialrate. . .. . .. . .123词法分析器词法分析器 id, 1 = id, 2 + id, 3 60 position = initial + rate 60 记号流记号流 字符流字符流第一章 编译原理简介 回顾 表达式的语法特征表达式的语法特征v任任何何一一个个标标识识符符都都是表达式是表达式v任任何何一一个个数数都都是是表表达式达式v如如果果e1和和e2都都是是表表达式，那么达式，那么 e1 + e2 e1 * * e2 (e1)也都是表达式也都是表达式表达式表达式表达式表达式表达式表达式标识符标识符表达式表达式表达式表达式(initial)标识符标识符(rate)数数(60)*+initial + rate * * 60的的分析树分析树第一章 编译原理简介 回顾 符符 号号 表表 positioninitialrate. . .. . .. . .123语法分析器语法分析器 id, 1 = id, 2 + id, 3 60 = + 60 id, 1 id, 2 id, 3 语法树语法树 记号流记号流第一章 编译原理简介 回顾 符符 号号 表表 positioninitialrate. . .. . .. . .123语义分析器语义分析器 = + 60 id, 1 id, 2 id, 3 = + inttofloat id, 1 id, 2 id, 3 60 语法树语法树 语法树语法树第一章 编译原理简介 回顾 符符 号号 表表 positioninitialrate. . .. . .. . .123中间代码生成器中间代码生成器t1 = inttofloat(60)t2 = id3 t1t3 = id2 + t2id1 = t3 = + inttofloat id, 1 id, 2 id, 3 60 三地址三地址中间代码中间代码 语法树语法树第一章 编译原理简介 回顾 符符 号号 表表 positioninitialrate. . .. . .. . .123代码优化器代码优化器t1 = inttofloat(60)t2 = id3 t1t3 = id2 + t2id1 = t3t1 = id3 * * 60.0id1 = id2 + t1 三地址三地址中间代码中间代码 三地址三地址中间代码中间代码第一章 编译原理简介 回顾 符符 号号 表表 positioninitialrate. . .. . .. . .123代码生成器代码生成器MOVF id3, R2MULF #60.0, R2MOVF id2, R1ADDF R2, R1MOVF R1, id1t1 = id3 * * 60.0id1 = id2 + t1 三地址三地址中间代码中间代码 汇编汇编代码代码第一章 编译原理简介 回顾 11/34 第一章 编译原理简介 回顾v编译器的工作可以分成若干阶段，每个阶段把源程序从一种表示变换成另一种表示。
前端前端后端后端 第一章 编译原理简介 回顾v编译系统除了编译器外，还需要一些其他工具的帮助，才能得到可执行的目标程序，这些工具包括预处理器、汇编器和连接器等vC语言的编译系统vJava语言的编译系统 第一章 编译原理简介 回顾vC语言的产生The Development of the C Language：C history – Written by Dennis RitchieBCPL B语言 New B语言 C语言Ken Thompson (left) with Dennis RitchieDEC PDP-7, as used for initial work on C and Unix 第一章 编译原理简介 回顾v编译性语言、解释性语言和脚本语言高级语言翻译成机器语言，计算机才能执行高级语言编写的程序翻译有两种方式：v编译：一次性编译成机器语言文件，不用重新编译，效率高v解释：每个语句都是执行的时候才翻译，每执行一次就翻译一次，效率比较低脚本语言是一种解释性的语言vJavaScript，ASP,PHP,PERLJava语言v既要编译，又要解释；编译只有一次，程序执行时解释执行；通过编译器，把java程序翻译成一种中间代码——字节码，然后通过JVM解释成相应平台的语言 计算机科学与技术学院计算机科学与技术学院编译原理编译原理第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v以简单实现编译器前端示例：以简单实现编译器前端示例：词法分析语法分析中间代码生成 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法制导翻译器语法（syntax）：程序的正确形式语义（semantics）：程序的含义，即程序在运行时做什么事情 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v中间代码抽象语法树（abstract syntax tree），常简称为语法树（syntax tree） 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v中间代码三地址码：x = y op zv最多只执行一个运算，通常是计算、比较或者分支跳转 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法定义if (expression) statement else statementstmt if ( expr ) stmt else stmtv产生式终结符：if else非终结符：expr stmt 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v文法定义上下文无关文法（context-free grammar）list list + digitlist list - digitlist digitdigit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9v以计算表达式 9 – 5 + 2 为例 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v推导（derivation）从开始符号出发，不断替换产生式左端的非终结符可以从开始符号推导得到的所有终结符号串的集合称为该文法定义的语言（language）v例：9 – 5 + 2list list + digitlist list - digitlist digitdigit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9v{1, 2, 1 + 1, 2 – 1, ….}是该文法定义的语言 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v推导（derivation）从开始符号出发，不断替换产生式左端的非终结符可以从开始符号推导得到的所有终结符号串的集合称为该文法定义的语言（language）v另例：Java函数调用max(x, y) 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v推导（derivation）从开始符号出发，不断替换产生式左端的非终结符可以从开始符号推导得到的所有终结符号串的集合称为该文法定义的语言（language）v另例：Java函数调用max(x, y)设计一个文法如下vcall id ( opt_params )vopt_params params | εvparams params, param | param 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法分析：接受一个终结符号串作为输入，找出从文法的开始符号推导出这个串的方法v语法分析树：用图形（树）的方式展现语法分析的过程上下文无关文法的语法分析树：v根节点的标号为文法的开始符号v每个叶子节点的标号为一个终结符号或εv每个内部节点的标号为一个非终结符号v内部节点Ａ，子节点X1, X2, …Xn, 那么必然存在产生式：Ａ X1 X2 … Xn. X1, X2, …Xn可以是终结符，也可以是非终结符。
第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法分析树list list + digitlist list - digitlist digitdigit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法分析：为一个给定的终结符号串构建一棵句法树的过程称为对该符号串进行语法分析一些术语：v语言（language）v结果（yield）v叶子节点/终结节点v内部节点/非终结节点 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v文法的二义性一个文法可能有多棵语法分析树能够生成同一个给定的终结符号串v例： string string + string string string – string string 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9给定符号串9 – 5 + 2其两棵语法树： 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v运算符的结合性v运算符的左（右）结合性：当一个运算分量左右两侧都有该运算符时，该运算分量属于其左（右）边的运算符v左结合文法list list + digitlist list - digitlist digitdigit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9例：9 – 5 - 2 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v运算符的结合性v运算符的左（右）结合性：当一个运算分量左右两侧都有该运算符时，该运算分量属于其左（右）边的运算符v右结合文法right letter = right | letterletter a | b | … | z例：a = b = c 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v运算符的优先级v例：+ - * /具有相同结合性与优先级的运算符放一类v+ -v* /为表达式创建基本单元：数位和带括号的表达式vfactor digit | ( expr )高优先级次之，且考虑左结合性vterm term * factor | term / factor | factor 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v运算符的优先级v例：+ - * /高优先级次之，且考虑左结合性vexpr expr + term | expr - term | term 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v运算符的优先级v例：+ - * /vfactor digit | ( expr )vterm term * factor | term / factor | factorvexpr expr + term | expr - term | term 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法制导翻译：对语法树进行语义分析语义分析例如：将中缀表达式转化成为后缀v9 - 5 + 2 9 5 – 2 +v ？？ 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法制导翻译：对语法树进行语义分析语义分析语法制导定义语法制导翻译方案 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法制导翻译语法制导定义(syntax-directed definition)v每个文法符号和一个属性集合相关联例树中”.t”是属性v每个产生式和一组语义规则相关联 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法制导翻译语法制导定义(syntax-directed definition)v每个文法符号和一个属性集合相关联例树中”.t”是属性v每个产生式和一组语义规则相关联后缀表达式后缀表达式 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法制导翻译语法制导定义(syntax-directed definition)v每个文法符号和一个属性集合相关联例树中”.t”是属性v每个产生式和一组语义规则相关联简单语法制导定义 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法制导翻译属性v综合属性如果某个属性在语法分析树节点N上的值由N的子节点和N本身的属性值确定，则该属性为综合属性v继承属性如果某个属性由语法分析树中该节点本身、父节点以及兄弟节点上的属性值决定，则该属性为继承属性 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v后缀表达式（postfix notation）：E如何E是一个变量或常量，则E的后缀是本身如果E是一个形如E1 op E2的表达式，op是二目运算符，那么E的后缀表示是：E1’ E2’ op，这里E1’ 和E2’分别是E1和E2的后缀表示如果E是一个形如（E1）的表达式，则E的后缀表示就是E1的后缀表示 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法制导翻译语法制导定义(syntax-directed definition)深度优先遍历 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法制导翻译：对语法树进行语义分析语义分析语法制导定义语法制导翻译方案语法制导翻译方案v将程序片段附加到一个文法的各个产生式上的表示法 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法制导翻译：对语法树进行语义分析语义分析语法制导定义语法制导翻译方案语法制导翻译方案v将程序片段附加到一个文法的各个产生式上的表示法v被嵌入到产生式体中的程序片段成为语义动作（semantic action）。
语义动作用花括号括起来 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法制导翻译：对语法树进行语义分析语义分析语法制导定义语法制导翻译方案语法制导翻译方案v将程序片段附加到一个文法的各个产生式上的表示法如何E是一个变量或常量，则E的后缀是本身如果E是一个形如E1 op E2的表达式，op是二目运算符，那么E的后缀表示是：E1’ E2’ op，这里E1’ 和E2’分别是E1和E2的后缀表示如果E是一个形如（E1）的表达式，则E的后缀表示就是E1的后缀表示 ( 9 – 5 ) + 2 9 5 – 2 + ? 9 5 2 + - 3 * 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法制导翻译：对语法树进行语义分语义分析析语法制导定义语法制导翻译方案 计算机科学与技术学院计算机科学与技术学院编译原理编译原理第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器 上周课回顾上周课回顾 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v一个编译器的前端 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v中间代码三地址码：x = y op zv最多只执行一个运算，通常是计算、比较或者分支跳转 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v文法定义上下文无关文法（context-free grammar）list list + digitlist list - digitlist digitdigit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9v以计算表达式 9 – 5 + 2 为例 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法制导翻译：对语法树进行语义分析语义分析语法制导定义语法制导翻译方案 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法制导翻译语法制导定义(syntax-directed definition)v每个文法符号和一个属性集合相关联例树中”.t”是属性v每个产生式和一组语义规则相关联 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法制导翻译：对语法树进行语义分语义分析析语法制导定义语法制导翻译方案 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法分析决定如何使用一个文法生成一个终结符号串的过程v给定输入：终结符号串：9 – 5 + 2文法：vlist list + digitvlist list - digitvlist digitvdigit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9v输出：？ 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法分析决定如何使用一个文法生成一个终结符号串的过程v给定输入：终结符号串：9 – 5 + ２文法：vlist list + digitvlist list - digitvlist digitvdigit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9v输出：？ 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法分析决定如何使用一个文法生成一个终结符号串的过程v上下文无关文法通常Parsing的时间复杂度是O(n3)对于程序设计语言，时间复杂度是O(n)v自顶向下方法自顶向下方法v自底向上方法 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法分析自顶向下分析方法v例：给定文法：stmt expr | if ( expr ) stmt | for ( optexpr ; optexpr ; optexpr ) stmt | otheroptexpr ε | expr 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法分析自顶向下分析方法stmt expr | if ( expr ) stmt | for ( optexpr ; optexpr ; optexpr ) stmt | otheroptexpr ε | expr输入是：for ( ; expr ; expr ) other 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法分析自顶向下分析方法stmt expr | if ( expr ) stmt | for ( optexpr ; optexpr ; optexpr ) stmt | otheroptexpr ε | expr输入是：for ( ; expr ; expr ) other 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法分析自顶向下分析方法v一般来说，为一个非终结符号选择产生式是一个“尝试并犯错”的过程 —— 回溯v预测语法分析法：不需要回溯要求设计的文法满足：当考虑到一个输入符号（终结符）的时候，只有一种非终结符可以生成这个输入符号，是确定性的。
FIRST集合v令α是一个文法符号（终结符号或非终结符号）串， FIRST(α)是由α生成的一个或多个终结符号串的第一个符号的集合v如果α是ε或者可以生成ε ，那么ε也在FIRST(α)中 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法分析自顶向下分析方法v一般来说，为一个非终结符号选择产生式是一个“尝试并犯错”的过程 —— 回溯v预测语法分析法：不需要回溯要求设计的文法满足：当考虑到一个输入符号（终结符）的时候，只有一种非终结符可以生成这个输入符号，是确定性的v有两个产生式A α和Aβ，预测分析法要求FIRST(α)和FIRST(β)不相交v如果输入符号在FIRST(α)中，就用A α，如果输入符号在FIRST(β)中，就用A β 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法分析自顶向下分析方法v预测分析法stmt expr | if ( expr ) stmt | for ( optexpr ; optexpr ; optexpr ) stmt | otheroptexpr ε | exprvFIRST(stmt) = {expr, if, for, other}vFIRST(expr ;) = { expr } stmt expr | if ( expr ) stmt | for ( optexpr ; optexpr ; optexpr ) stmt | other 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器optexpr ε | expr 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器optexpr ε | expr何时使用ε产生式输入：for ( ; expr ; expr ) other 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v设计一个预测分析器对应于非终结符A：v检查向前看符号，决定使用A的哪个产生式。
如果一个产生式的体为α(α不是空串ε)，且向前看符号在FIRST(α)中，那么就选择这个产生式v然后，模拟被选中的产生式的体，也就是，从左向右逐个执行此产生式体的符号执行”就是调用相应非终结符的过程v嵌入翻译方案翻译动作作为一个非终结符 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法分析左递归v可能使递归下降语法分析器进入无限循环例： expr expr + termexprexprexprexprtermtermterm…… 第二章第二章 一个简单的语法制导翻译器一个简单的语法制导翻译器v语法分析消除左递归A A α | βA β RR α R | ε 。
