《编译技术：第02章 简单编译器》由会员分享，可在线阅读，更多相关《编译技术：第02章 简单编译器（64页珍藏版）》请在金锄头文库上搜索。
1、第二章实现一个简单编译器Zhou, Erqiang实现一个简单编译器a = 1; a = 1; b = 10;b = 10;while (a b)while (a b) a = a + 1; a = a + 1;b = a + b;b = a + b;2School of Information and Software Engineering词法分析词法分析中间代码生成中间代码生成语法分析语法分析语义分析语义分析中间代码优化中间代码优化目标代码优化目标代码优化目标代码生成目标代码生成100: a = 1100: a = 1101: b = 10101: b = 10102: if a b g
2、oto 104102: if a b goto 104103: goto 107103: goto 107104: t1 = a + 1104: t1 = a + 1105: a = t1105: a = t1106: goto 102106: goto 102107: t2 = a + b107: t2 = a + b108: b = t2108: b = t2Zhou, Erqiang语言定义代码考查代码考查 “C C语言语言”代码片段代码片段 表达式种类？表达式种类？ 语句种类？语句种类？赋值表达式构成赋值表达式构成 变量变量 赋值号赋值号 表达式（整数表达式（整数/ /求和运算）求和运
3、算）布尔表达式构成布尔表达式构成 变量变量 比较符号比较符号 变量变量3School of Information and Software Engineeringa = 1; a = 1; b = 10;b = 10;while (a b)while (a b) a = a + 1; a = a + 1;b = a + b;b = a + b;Zhou, Erqiang语言定义赋值语句构成赋值语句构成 赋值表达式赋值表达式 分号分号whilewhile语句构成语句构成 while ( while ( 布尔表达式布尔表达式 ）赋值语句）赋值语句进一步考查表达式进一步考查表达式 变量：以字母开头
4、，后由字母、数字下划线构成的字符串变量：以字母开头，后由字母、数字下划线构成的字符串 常量：整数常量：整数 运算：运算符运算：运算符 变量变量 常量常量4School of Information and Software Engineeringa = 1; a = 1; b = 10;b = 10;while (a b)while (a b) a = a + 1; a = a + 1;b = a + b;b = a + b;关键字？函数名？结构名？关键字？函数名？结构名？浮点数？字符串常量？浮点数？字符串常量？函数调用？数组元素？函数调用？数组元素？标识符标识符Zhou, Erqiang语言
5、定义语言定义总结语言定义总结 语言语言 = = 语法语法 + + 语义语义 语法规则语法规则 较高级较高级( (抽象抽象) )的语法成份的语法成份 whilewhile语句语句 while(while(布尔表达式布尔表达式) )语句语句 较低级较低级( (具体具体) )的语法成份的语法成份 标识符标识符 _a-zA-Z+_a-zA-Z0-9*_a-zA-Z+_a-zA-Z0-9* 标识符、关键字、符号、常量等标识符、关键字、符号、常量等5School of Information and Software Engineering语法规则语法规则降格为词法规则降格为词法规则Zhou, Erqia
6、ng语言定义词法分析器词法分析器 处理词法规则，即降格的语法规则处理词法规则，即降格的语法规则 需识别：标识符、关键字、符号、常量等需识别：标识符、关键字、符号、常量等 对于语法规则，这些符号已终结，不可再分对于语法规则，这些符号已终结，不可再分 统称为统称为“终结符终结符” 非终结符非终结符：语法规则中可再分的语法成分：语法规则中可再分的语法成分 如：如：“语句语句”、“表达式表达式”等等6School of Information and Software EngineeringZhou, Erqiang语言定义语法定义语法定义 关于关于 while while 语句语句 whilewhi
7、le语句语句 while ( while ( 布尔表达式布尔表达式 ) ) 语句语句 while_stmt while ( bool_expr ) stmtwhile_stmt while ( bool_expr ) stmt WHILE_STMT WHILE_STMT while (while ( BOOL_EXPR BOOL_EXPR ) ) STMT STMT或或 while_stmt while_stmt WHILE (WHILE ( bool_expr bool_expr ) ) stmt stmt7School of Information and Software Enginee
8、ringa = 1; a = 1; b = 10;b = 10;while (a b)while (a expr bool_expr expr expr | expr expr | expr expr | expr = expr | expr = expr 8School of Information and Software Engineeringa = 1; a = 1; b = 10;b = 10;while (a b)while (a b) a = a + 1; a = a + 1;b = a + b;b = a + b;Zhou, Erqiang语言定义表达式表达式 primary_
9、expr primary_expr IDID | | NUMBERNUMBER expr primary_expr expr primary_expr | primary_expr | primary_expr + + expr expr | primary_expr | primary_expr - - expr expr程序及语句程序及语句 program stmt | program stmtprogram stmt | program stmt stmt while_stmt | assign_stmt stmt while_stmt | assign_stmt9School of I
10、nformation and Software Engineeringa = 1; a = 1; b = 10;b = 10;while (a b)while (a expr expr | expr | expr = 图中的图中的“边边” 跳转到的类别跳转到的类别 = = 图中的图中的“结点结点” 12School of Information and Software EngineeringZhou, Erqiang词法分析13School of Information and Software Engineering整数整数开始开始取一个字符取一个字符当前字符为当前字符为0、1、2、9取一
11、个字符取一个字符当前字符为当前字符为0、1、2、9结束结束非数字非数字返回返回“整数整数”标识符标识符当前字符为字母当前字符为字母取一个字符取一个字符当前字符为字母或数字当前字符为字母或数字结束结束非字母非字母/数字数字返回返回“标识符标识符”或或“关键字关键字”其它其它字符字符关键字检查关键字检查如何识别整数及标识符？如何识别整数及标识符？ Zhou, Erqiang词法分析词法分析器所需函数词法分析器所需函数 取一个字符取一个字符 getChargetChar 将当前字符加到当前已识别子串将当前字符加到当前已识别子串 addCharaddChar 跳过多余空格跳过多余空格/ /注释注释 g
12、etNonBlankgetNonBlank 关键字检查关键字检查 checkKeywordscheckKeywords 符号检查符号检查 checkSymbolcheckSymbol词法分析的实现词法分析的实现 参教材参教材 图图2-32-3及相关代码及相关代码14School of Information and Software EngineeringZhou, Erqiang语法分析语法分析的目的语法分析的目的 确定输入程序在语法是否正确确定输入程序在语法是否正确 生成完整的语法分析树，供后续分析使用生成完整的语法分析树，供后续分析使用语法分析方法语法分析方法 已定义语法规则已定义语法规
13、则 已有符合该规则的源代码已有符合该规则的源代码 语法规则语法规则 和和 源程序源程序 如何建立联系？如何建立联系？15School of Information and Software EngineeringZhou, Erqiang语法分析语法规则语法规则 和和 源程序源程序 如何建立联系？如何建立联系？源程序是否符合语法规则？源程序是否符合语法规则？由语法规则出发由语法规则出发检查语法规则是否能推导出源程序检查语法规则是否能推导出源程序由源程序出发由源程序出发检查源程序是否符合语法规则检查源程序是否符合语法规则16School of Information and Software E
14、ngineering标识符的定义标识符的定义 iden nondigit nondigit _ | A | B | | Z | a | b | | z iden iden nondigit iden iden digit digit 0 | 1 | 2 | | 9 Zhou, Erqiang17语法分析School of Information and Software Engineering从从语法规则语法规则出发检验标识符出发检验标识符 func1iden iden digit iden 1 iden nondigit 1 iden c1 iden nondigit c1 iden nc1
15、 iden nondigit nc1 iden unc1 nondigit unc1 func1Zhou, Erqiang18语法分析School of Information and Software Engineeringiden nondigit iden iden nondigit iden iden digit digit 0 | 1 | 2 | | 9 nondigit _ | A | B | | Z | a | b | | zSchool of Information and Software EngineeringZhou, Erqiang19语法分析f u n c 1u n
16、c 1f u n c 1nondigit u n c 1ideniden nondigit iden iden nondigit iden iden digit digit 0 | 1 | 2 | | 9 nondigit _ | A | B | | Z | a | b | | z n c 1iden u n c 1iden nondigit n c 1iden c 1iden n c 1iden nondigit c 1iden 1iden c 1iden nondigit 1iden iden 1 iden 从从源程序源程序出发检验标识符出发检验标识符 func1func1School o
17、f Computer Science and Engineering School of Information and Software EngineeringZhou, Erqiang20递归下降分析法递归下降分析法 每个每个 非终结符非终结符 对应一个解析函数对应一个解析函数 语法语法规则右侧为规则右侧为其左侧非终结符所其左侧非终结符所对应的对应的“函数体函数体”关于关于“函数体函数体” 右侧终结符右侧终结符 对应对应 从输入串中消耗该终结符从输入串中消耗该终结符 右侧非终结符右侧非终结符 对应对应 函数调用函数调用 语法上规则中的语法上规则中的| | 对应对应“if-elseif-el
18、se”语句语句语法分析School of Information and Software Engineering21Zhou, Erqiang根据右侧定义函数体根据右侧定义函数体 当遇到终结符时，编写语句当遇到终结符时，编写语句 if ( if (当前符号当前符号 与与 该终结符该终结符 匹配匹配) ) 读入下一个字符读入下一个字符 源程序中的符号源程序中的符号 与与 规则中的符号规则中的符号 当遇到非终结符时当遇到非终结符时 编写调用该非终结符对应的函数编写调用该非终结符对应的函数语法分析School of Information and Software Engineering22Zho
19、u, Erqiang赋值语句规则：赋值语句规则：assign_stmt assign_stmt ID =ID = expr expr ; ;左侧非终结符左侧非终结符 assign_stmt assign_stmt 定义函数定义函数 void analyse_assign_stmt()void analyse_assign_stmt()右侧开始为终结符右侧开始为终结符IDID，则编写，则编写 if ( match(ID) ) if ( match(ID) ) advance(); advance();IDID之后是终结符之后是终结符 = =，编写，编写 if ( match(=) ) if (
20、match(=) ) advance(); advance();语法分析School of Information and Software Engineering23Zhou, Erqiangmatch函数检查函数检查当前单词当前单词 与与 参数参数 是否匹配是否匹配advance函数函数 读入下一个单词读入下一个单词赋值语句规则：赋值语句规则：assign_stmt assign_stmt ID =ID = expr expr ; ;= = 之后是非终结符之后是非终结符 exprexpr，编写，编写 analyse_expr(); /analyse_expr(); /表达式分析函数表达式分
21、析函数最后是终结符最后是终结符 ；编写；编写 if ( match(;) ) if ( match(;) ) advance(); advance();语法分析School of Information and Software Engineering24Zhou, Erqiang赋值语句规则：赋值语句规则：assign_stmt assign_stmt ID =ID = expr expr ; ;语法分析School of Information and Software Engineering25Zhou, Erqiang void void analyse_assign_stmt()an
22、alyse_assign_stmt() ifif ( ! match( ID ) ) ( ! match( ID ) ) /匹配标识符匹配标识符 printf(printf(“ERROR: Expect an ID.nERROR: Expect an ID.n”);); returnreturn; ; advance(); advance(); /将下一个待分析字符设为当前分析字符将下一个待分析字符设为当前分析字符 ifif ( ! match( ( ! match( = = ) ) ) ) /匹配赋值符号匹配赋值符号 printf(printf(“ERROR: Expect ERROR: E
23、xpect = = .n .n”);); returnreturn; ; advance(); advance(); /将下一个待分析字符设为当前分析字符将下一个待分析字符设为当前分析字符 analyse_expr(); analyse_expr(); /匹配表达式匹配表达式 if if ( ! match( ( ! match( ; ; ) ) ) ) /匹配分号匹配分号 printf(printf(“ERROR: Expect ERROR: Expect ; ;.n.n”);); returnreturn; ; Zhou, Erqiang语法分析program stmt | program
24、 stmtprogram stmt | program stmtstmt while_stmt | assign_stmtstmt while_stmt | assign_stmtwhile_stmt while_stmt WHILE (WHILE ( bool_expr bool_expr ) ) stmt stmtassign_stmt assign_stmt ID =ID = expr expr ; ;bool_expr expr bool_expr expr expr expr | expr | expr expr expr | expr | expr expr expr | expr
25、 | expr = expr exprexpr primary_expr expr primary_expr + + expr | primary_expr expr | primary_expr - - expr exprprimary_expr ID | NUMBERprimary_expr ID | NUMBER31School of Information and Software Engineering方法类似，参考教材方法类似，参考教材抽象语法树抽象语法树 是源代码的是源代码的抽象语法结构抽象语法结构的的树状表现树状表现 不保留仅语法用的符号不保留仅语法用的符号 与具体语法树相对应
26、与具体语法树相对应 包括语法规则中的各种符号包括语法规则中的各种符号建立抽象语法树School of Information and Software Engineering32Zhou, Erqiangwhile顺序yz=x+ab建立抽象语法树School of Information and Software Engineering33Zhou, ErqiangETint+(int+int+int)ETEEETTTint+()+intint+intE TE E + TT intT (E)抽象语法树抽象语法树 结点类型结点类型 设计设计 建立抽象语法树School of Informatio
27、n and Software Engineering34Zhou, Erqiangtypedef structtypedef struct _ast ast; _ast ast;typedef structtypedef struct _ast *past; _ast *past;struct struct _ast_astint int ivalue;ivalue;charchar* svalue;* svalue;charchar* nodeType;* nodeType;past left;past left;past right;past right;结点类型结点类型结点指针类型结点指
28、针类型保存整数信息保存整数信息保存字符串信息保存字符串信息结点类型结点类型指向左子树指向左子树指向右子树指向右子树与与 结点结点 相关函数设计相关函数设计 past newAstNode()past newAstNode() 创建抽象语法树结点创建抽象语法树结点 past newNum(int value)past newNum(int value) 创建数值结点创建数值结点 结点中的结点中的ivalueivalue被设置为被设置为valuevalue past newVarRef(char* name) past newVarRef(char* name) 创建标识符结点创建标识符结点 结点
29、中的结点中的svaluesvalue被设置为被设置为namename past newExpr(int oper, past left, past right)past newExpr(int oper, past left, past right) 创建一个表达式结点创建一个表达式结点:ivalue:ivalue表示运算符表示运算符 leftleft、rightright分别指向表达式的两个操作数分别指向表达式的两个操作数 建立抽象语法树School of Information and Software Engineering35Zhou, Erqiang建立了表达式建立了表达式a-4+c
30、a-4+c的抽象语法树的抽象语法树 p1 = newVarRef( pa );p1 = newVarRef( pa ); p2 = newNum( 4 ); p2 = newNum( 4 ); p3 = newExpr( p3 = newExpr( - -, p1, p2);, p1, p2); p4 = newVarRef( pc ); p4 = newVarRef( pc ); p5 = newExpr( p5 = newExpr( + +, p3, p4); , p3, p4); 建立抽象语法树School of Information and Software Engineering3
31、6Zhou, Erqiangpapa是指向标识符是指向标识符a a的指针的指针pcpc是指向标识符是指向标识符c c的指针的指针a或或c是什么类型？是什么类型？局部变量？全局变量？局部变量？全局变量？建立语法树时需要填表建立语法树时需要填表符号表的作用符号表的作用 登记符号属性值登记符号属性值 查找符号的属性、检查其合法性查找符号的属性、检查其合法性 作为目标代码生成阶段地址分配的依据作为目标代码生成阶段地址分配的依据符号（标识符）有哪些属性符号（标识符）有哪些属性 变量：变量名、变量：变量名、类型类型、值、值 函数：函数名、参数个数、参数函数：函数名、参数个数、参数类型类型，返回，返回类型类
32、型 “数据类型数据类型”对程序设计语言至关重要对程序设计语言至关重要语义分析School of Information and Software Engineering37Zhou, Erqiang“int a;int a;” 意味着什么？意味着什么？数据类型数据类型 是是“数据数据”的抽象的抽象 定义了一组定义了一组值值和一组和一组操作操作为什么需要为什么需要“数据类型数据类型” 实现实现“数据抽象数据抽象” 不用关心存储单元中二进制位串的意义不用关心存储单元中二进制位串的意义School of Information and Software EngineeringZhou, Erqian
33、g38语义分析 之 数据类型C C语言实现语言实现“分数分数”运算？运算？假如语言只支持位运算假如语言只支持位运算 “整数整数”运算如何进行？运算如何进行？语义分析 之 基本类型School of Information and Software EngineeringZhou, Erqiang39基本数据类型基本数据类型 不用其它类型来定义的数据类型不用其它类型来定义的数据类型 int, float, char, int, float, char, string, boolstring, bool整数整数 支持支持不同长度不同长度的整数类型的整数类型 java java中中4 4种种有符号有
34、符号整数整数 byte, short, int, long byte, short, int, long大多数计算机中大多数计算机中 负整数是如何表示的？负整数是如何表示的？二进制补码，为什么？二进制补码，为什么？0 0的二进制反码有几种？的二进制反码有几种？语义分析 之 基本类型School of Information and Software EngineeringZhou, Erqiang40浮点数浮点数 实数的模拟，保持实数的模拟，保持“近似值近似值”语言支持语言支持 两种浮点类型两种浮点类型:float :float 和和 doubledouble float float：四个字节
35、：四个字节 doubledouble：八个字节：八个字节 表示为小数和指数表示为小数和指数大多数计算机中大多数计算机中 浮点数是如何表示的？浮点数是如何表示的？IEEE IEEE 浮点标准浮点标准754754格式格式语义分析 之 基本类型School of Information and Software EngineeringZhou, Erqiang41布尔类型布尔类型 只有只有“真真”和和“假假”两个值两个值 C, Java, C#, C+ C, Java, C#, C+ 中的布尔类型？中的布尔类型？ 数值表达式是否可以当作布尔类型？数值表达式是否可以当作布尔类型？ 布尔类型如何表示？（
36、占几位？）布尔类型如何表示？（占几位？）C99C99，C+C+允许允许Java, C#Java, C#不允许不允许通常为一个字节。为什么？通常为一个字节。为什么？因为很多计算机因为很多计算机 不能有效访问单个二进制位不能有效访问单个二进制位语义分析 之 基本类型School of Information and Software EngineeringZhou, Erqiang42总结：内部类型有以下优点总结：内部类型有以下优点 基本表示（二进制表示）的不可见基本表示（二进制表示）的不可见 编译时类型检查编译时类型检查 运算无二义检查运算无二义检查 精度控制精度控制对数据对象对数据对象 类型类
37、型和使用的和使用的操作操作 是否匹配的是否匹配的一致性检查一致性检查静态检查和动态检查静态检查和动态检查 静态：编译时；使程序正确、有效静态：编译时；使程序正确、有效 动态：运行时；影响可靠性、效率低动态：运行时；影响可靠性、效率低 编程方便编程方便School of Information and Software EngineeringZhou, Erqiang43语义分析 之 类型检查语言按类型分类语言按类型分类 无类型无类型 没有类型定义没有类型定义 弱类型弱类型 所有类型检查在所有类型检查在编译时完成编译时完成 强类型强类型 全部或部分类型检查在运行时完成全部或部分类型检查在运行时完
38、成School of Information and Software EngineeringZhou, Erqiang44语义分析 之 类型检查某种类型的值某种类型的值转换为转换为另一种类型的值另一种类型的值语言应该提供类型转换机制语言应该提供类型转换机制 隐式隐式( (自动自动) )转换转换 显式显式( (强制强制) )转换转换School of Information and Software EngineeringZhou, Erqiang45语义分析 之 类型转换混合运算混合运算表达式给变量值赋表达式给变量值赋实参向函数形参传值实参向函数形参传值函数返回值函数返回值语义分析 之 类型
39、转换FORTRAN 类型转换的要求和规则类型转换的要求和规则都是隐式的都是隐式的ADA 类型转换的要求和规则类型转换的要求和规则都是显式的都是显式的C 类型转换的要求和规则类型转换的要求和规则有隐式、显式有隐式、显式School of Information and Software EngineeringZhou, Erqiang46两种转换方式两种转换方式拓拓展展（扩扩大大）: :转转换换之之后后的的类类型型值值集集合合包包含含转换之前类型值集合（整型转换之前类型值集合（整型实型）实型）收收缩缩（缩缩小小）: :若若转转换换之之前前类类型型值值集集合合包包含含转换之后类型值集合（实型转换之
40、后类型值集合（实型整型）整型） School of Information and Software EngineeringZhou, Erqiang47语义分析 之 类型转换中间代码（三地址码）Zhou, Erqiang48School of Information and Software Engineering三地址代码三地址代码 一般形式为一般形式为 x = y op z 操作码操作码: : op 三个地址三个地址: : x, y和和z对运算类操作对运算类操作 地址地址 y 和和 z 指出两个运算对象指出两个运算对象 地址地址 x 用来存放运算结果用来存放运算结果三地址码的常见形式Zh
41、ou, Erqiang49School of Information and Software Engineering二元二元运算类赋值语句运算类赋值语句 x = y op z 其中其中opop为二元运算符或逻辑运算符为二元运算符或逻辑运算符一元一元运算类赋值语句运算类赋值语句 x = op z 其中其中opop为一元运算符为一元运算符 如一元减如一元减uminusuminus 逻辑否定逻辑否定notnot 移位符，类型转换符等移位符，类型转换符等三地址码的常见形式Zhou, Erqiang50School of Information and Software Engineering复制类赋
42、值语句复制类赋值语句 x = y无条件转移语句无条件转移语句 goto L 转到标号为转到标号为L L的语句的语句三地址码的常见形式Zhou, Erqiang51School of Information and Software Engineering条件转移语句条件转移语句 if x rop y goto L 或或 if a goto L rop rop为关系运算符为关系运算符 、=、若若 x 和和 y 满足关系满足关系rop，或，或 a 为为true时时 则执行标号为则执行标号为L的语句的语句 否则顺序执行下一语句否则顺序执行下一语句三地址码的常见形式Zhou, Erqiang52Sch
43、ool of Information and Software Engineering翻译翻译 A := -B*(C+D) 地址地址 代码代码 n n t1 := -B n+1 n+1 t2 := C+D n+2 n+2 t3 := t1* t2 n+3 n+3 A := t3 教材中的三地址代码中的地址教材中的三地址代码中的地址既代表既代表地址地址，又表示其对应的，又表示其对应的值值，类似于，类似于高级语言高级语言三地址码的常见形式Zhou, Erqiang53School of Computer Science and Engineering School of Information a
44、nd Software Engineeringvoid void func()func() intint A = 1, B = 2, C = 3, D = 4; A = 1, B = 2, C = 3, D = 4; A = -B*(C+D);A = -B*(C+D); define define i32 func() #0 i32 func() #0 %A = %A = alloca alloca i32, align 4i32, align 4 %B = %B = alloca alloca i32, align 4i32, align 4 %C = %C = alloca alloca
45、i32, align 4i32, align 4 %D = %D = alloca alloca i32, align 4i32, align 4 store store i32 1, i32* %A, align 4i32 1, i32* %A, align 4 store store i32 2, i32* %B, align 4i32 2, i32* %B, align 4 store store i32 3, i32* %C, align 4i32 3, i32* %C, align 4 store store i32 4, i32* %D, align 4i32 4, i32* %D
46、, align 4 %1 = %1 = load load i32* %B, align 4i32* %B, align 4 %2 = %2 = subsub nsw i32 0, %1 nsw i32 0, %1 %3 = %3 = load load i32* %C, align 4i32* %C, align 4 %4 = %4 = load load i32* %D, align 4i32* %D, align 4 %5 = %5 = add add nsw i32 %3, %4nsw i32 %3, %4 %6 = %6 = mul mul nsw i32 %2, %5nsw i32
47、 %2, %5 store store i32 %6, i32* %A, align 4i32 %6, i32* %A, align 4 ret ret voidvoid clang -emit-llvm -S ./llvm_example.c实际编译器的三地址代码类似于汇编语言实际编译器的三地址代码类似于汇编语言即：把即：把地址地址 与与 值值 分开分开保存保存 要么是值，要么是地址要么是值，要么是地址三地址码的生成Zhou, Erqiang54School of Information and Software Engineering语法树的遍历语法树的遍历void void visit(
48、past N)visit(past N) forfor( ( 从左到右遍历从左到右遍历 N 的每个子结点的每个子结点 C C ) ) visit( visit( C ); ); 按照按照 N 的语义规则生成三地址代码；的语义规则生成三地址代码； 三地址码的生成Zhou, Erqiang55School of Information and Software Engineering基本表达式结点翻译方案基本表达式结点翻译方案 primary_expr primary_expr IDID | | NUMBERNUMBER 基本表达式如果是基本表达式如果是“变量变量” 结点中结点中nodeTypen
49、odeType为为“varRefvarRef” 三地址代码中需要变量名，即三地址代码中需要变量名，即“sValuesValue” 基本表达式如果是基本表达式如果是“整数整数” 结点中结点中nodeTypenodeType为为“intValueintValue” 三地址代码中需要常数的值，即三地址代码中需要常数的值，即“iValueiValue”三地址码的生成Zhou, Erqiang56School of Information and Software Engineering基本表达式结点翻译方案基本表达式结点翻译方案 primary_expr primary_expr IDID | | N
50、UMBERNUMBER 设计函数设计函数 int int genPrimaryExpr(past node, genPrimaryExpr(past node, charchar* operand)* operand) 其中输入参数其中输入参数nodenode指向要翻译的结点指向要翻译的结点 输出参数输出参数operandoperand指向该结点的指向该结点的 变量名变量名 或或 整数值对应的字符串整数值对应的字符串三地址码的生成Zhou, Erqiang57School of Information and Software Engineering基本表达式结点翻译方案基本表达式结点翻译方案
51、int int genPrimaryExpr(past node, genPrimaryExpr(past node, charchar* operand)* operand) ifif(strcmp(node-nodeType, intValue) = 0)(strcmp(node-nodeType, intValue) = 0)ifif(operand != NULL)(operand != NULL)sprintf(operand, %d, node-ivalue);sprintf(operand, %d, node-ivalue); else ifelse if(strcmp(node
52、-nodeType, varRef) = 0)(strcmp(node-nodeType, varRef) = 0)ifif(operand != NULL)(operand != NULL)sprintf(operand, %s, node-svalue);sprintf(operand, %s, node-svalue); elseelse printf(ERROR: printf(ERROR: 发现不支持的运算类型发现不支持的运算类型);); return return -1;-1; return return 1;1; 三地址码的生成Zhou, Erqiang58School of I
53、nformation and Software Engineering表达式结点翻译方案表达式结点翻译方案 left left指向左子树，指向左子树，rightright指向右子树指向右子树 子树可能是基本表达式子树可能是基本表达式 也可能是表达式也可能是表达式如果是基本表达式如果是基本表达式 调用调用genPrimaryExprgenPrimaryExpr得到操作数得到操作数如果是表达式如果是表达式 递归调用自己生成子树对应的代码递归调用自己生成子树对应的代码约定：该子树的结果保存在当前的临时变量中约定：该子树的结果保存在当前的临时变量中如何获取该子树的结果？如何获取该子树的结果？对对gen
54、PrimaryExprgenPrimaryExpr行调整：行调整： 加入对表达式的处理加入对表达式的处理 使其可处理表达式的子树使其可处理表达式的子树 参教材参教材 genPrimaryExpr()genPrimaryExpr()三地址码的生成Zhou, Erqiang59School of Information and Software Engineering基本表达式结点翻译方案基本表达式结点翻译方案int int genExpr(past node)genExpr(past node)ifif(node = NULL) (node = NULL) return return -1;-1
55、;ifif( strcmp(node-nodeType, expr) = 0)( strcmp(node-nodeType, expr) = 0)char char loperand50; loperand50; char char roperand50;roperand50;char char oper5;oper5;ltype = genPrimaryExpr(node-left, loperand);ltype = genPrimaryExpr(node-left, loperand);rtype = genPrimaryExpr(node-right, roperand);rtype
56、= genPrimaryExpr(node-right, roperand);ifif( ltype = rtype & ltype != -1)( ltype = rtype & ltype != -1) sprintf(oper, %c, node-ivalue); sprintf(oper, %c, node-ivalue); printf( %d = %s %s %sn,printf( %d = %s %s %sn,getTemVarNum(), loperand, oper, roperand);getTemVarNum(), loperand, oper, roperand); r
57、eturn return 1;1;return return -1;-1; 作业练习：练习：2-1、2-5实验：实验：2-2、2-3、2-4 Zhou, Erqiang60School of Information and Software Engineering作业1. 为下列语法规则构造递归下降语法分析器: 1) S + S S | - S S | a 2) S S ( S ) S | 3) S 0 S 1 | 0 12. 扩展2.3节中的词法分析器以消除注释。注释的定义如下: 1) 以/开始的注释，包括从它开始到这一行的结尾的所有字符。 2) 以/*开始的注释，包括从它到后面第一次出现的
58、字符序列*/之间的所有字符。3. 扩展2.3节中的词法分析器，使它能够识别浮点数，比如“2.” , “3.14”和“.5”等。4. 扩展2.4节所给语法规则G1，使其支持一元运算-及含有括号的四则混合运算；根据本节实例，完成扩展语法规则的语法分析程序及翻译方案。5. 请将表达式 - ( a + b )*( c + d ) - ( a + b + c)表示成三地址代码序列。Zhou, Erqiang61School of Information and Software EngineeringZhou, ErqiangTHE ENDQUESTIONS62School of Information and Software Engineering实验1词法分析地点：信软楼3楼 实验中心时间：9月20日 上午9:00至12:002014220301001-312014220302001-31 2014220303001-19时间：9月20日 下午14:30至17:30所有其他同学 实验1词法分析自学：正则表达式， Lexical Analysis with Flex
