《编译原理课程设计(if-else条件语句翻译_三地址_简单优先法)》由会员分享，可在线阅读，更多相关《编译原理课程设计(if-else条件语句翻译_三地址_简单优先法)（37页珍藏版）》请在金锄头文库上搜索。
1、课程设计任务书题目: IF-ELSE 条件语句的翻译程序设计（简单优先法、输出三地址表示）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1） 写出符合给定的语法分析方法的文法及属性文法。（2） 完成题目要求的中间代码三地址表示的描述。（3） 写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。（4） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（5） 设计报告格式按附件要求书写。课程设计报告书
2、正文的内容应包括：1 系统描述（问题域描述） ；2 文法及属性文法的描述；3 语法分析方法描述及语法分析表设计；4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5 编译系统的概要设计；6 详细的算法描述（流程图或伪代码） ；7 软件的测试方法和测试结果；8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等） ；9 参考文献（按公开发表的规范书写） 。时间安排：设计安排一周：周 1、周 2：完成系统分析及设计。周 3、周 4：完成程序调试及测试。周 5：撰写课程设计报告。设计验收安排：设计周的星期五第 1 节课开始到实验室进行上机验收。设计报告书收取时间：设计周的次周星
3、期一上午 10 点。指导教师签名： 2013 年 月 日系主任（或责任教师）签名： 2013 年 月 日IF-ELSE 条件语句的翻译程序设计（简单优先法、输出三地址表示）1 系统描述 1.1 题目IF-ELSE 条件语句的翻译程序设计（简单优先法、输出三地址表示）1.2目的通过设计、编制、调试一个条件语句的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。1.3设计内容及步骤对条件语句： IF 布尔表达式 THEN 赋值语句 ELSE 赋值语句（1） 按给定的题目写出符合语法分析方法要求的文法和属性文法描述。（2） 按给定的题目给出语法分析方法
4、的思想及分析表设计。（3） 按给定的题目给出中间代码序列的结构设计。（4） 完成相应的词法分析、语法分析和语义分析程序设计。（5） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。2 文法及属性文法的描述2.1 文法文法是用于描述语言的语法结构的形式规则（即语法规则）。这些规则必须是准确的、易于理解的以及有相当强的描述能力。由这种规则所产生的程序语言应有利于句子分析和翻译，而且，最好能通过这些规则自动产生有效的语法分析程序。IF-ELSE 条件语句的文法 GS如下所示：(1) S - CM(2) S - TM(3) M - begin L end(4) C - if B the
5、n(5) T - C M else其中非终结符 B 为布尔表达式，其文法 GB如下：(1) B - B1 or B2(2) B - B1 and B2(3) B - not B1(4) B - ( B1 )(5) B - id1 rop id2(6) B - true(7) B - false而在文法 GS中非终结符 L 表示赋值语句块，其文法 GL如下：(1) L - L1 A ;(2) L - A;(3) A - id = M(4) M - E(5) E - E1 + E2(6) E - E1 * E2(7) E - -E1(8) E - ( E1 )(9) E - id 2.2 属性文法
6、属性文法是在上下文无关文法的基础上，为每个文法符号（终结符或者非终结符）配备若干相关的“值”（与文法符号相关的属性）。在一个属性文法中，对应于每个产生式 Aa 都有一套与之相关联的语义规则，每规则的形式为：b:=f(c 1,c2,，c k)其中 f 是一个函数，而且或者b 是 A 的一个综合属性并且 c1,c2,，c k是产生式右边文法符号的属性或者非终结符既可有综合属性也可有继属性，文法开始符号的所有继承属性作为属性计算前的初始值 1。2.2.1 语义变量和语义动作说明对于文法 GL,首先对 id 表示的单词定义一属性 id.name，用做语义变量，用Lookup（id.name）语义函数审
7、查 id.name 是否出现在符号表中，如在，则返回一指向该登陆项的指针，否则返回 nil。语义过程 emit 表示输出四元是到输出文件上。语义过程 newtmp 表示生产一临时变量，每调用一次，生成一新的临时变量。语义变量E.place，表示存放 E 值的变量名在符号表的登陆项或一整数码（若此变量时一个临时变量） 2，2.2.1 给出了翻译赋值语句块到三地址的语义描述。2.2.1 GS的属性文法为：(1) S - CM S.chain := merge(C.chain,M.chain) (2) S - TM S.chain := merge(T.chain,M.chain) (3) M -
8、begin L end M.chain := L.chain(4) C - if B then bakpatch(B.true,nextstat)C.chain := B.false(5) T - C M else q := nextstatemit(GOTO-)backpatch(C.chain,nextstat)T.chain := merge(M.chain,q)2.2.2 GB的属性文法为：(1) B - B1 or B2 backpatch(B1.false,B2.codebgin); B.codebegin := B1.codebegin;B.true := merge(B1.tr
9、ue,B2.true);B.false := B2.false(2) B - B1 and B2 backpatch(B1.true,B2.codebegin);B.codebegin := B1.codebegin;B.true := B2.true;B.false := merge(B1.false,B2.false);(3) B - not B1 B.true := B1.false;B.codebegin := B1.codebegin;B.false := B1.true;(4) B - ( B1 ) B.true := B1.true;B.codebegin := B1.codeb
10、egin;B.false := B1.false;(5) B - id1 rop id2 B.true := nextstat;B.codebegin := nextstat;B.false := nextstat+1;emit(ifid1.placeropid2.placegoto-);emit(goto-) (6) B - true B.true := nextstat;B.codebegin := nextstat;emit(goto-)(7) B - false B.false := nextstat;B.codebegin := nextstat;emit(goto-)其中 next
11、stat 给出在输出序列中下一三地址式子的序号。emit 过程没调用一次，nextstat 增加 12.2.3 GL的属性文法为：(1) L - L1 A ; L.chain := A.chain(2) L - A; L.chain := A.chain(3) A - id := M p := lookup(id.name);if p nil thenemit(p := E.place);else error(4) M - E (5) E - E1 + E2 E.place := newtemp；emit(E.place :=E1.place + E2.place)(6) E - E1 * E
12、2 E.place := newtemp;emit(E.place := E1.place * E2.palce)(7) E - -E1 E.palce := newtemp;emit(E.place := minusE1.place)(8) E - ( E1 ) E.place := E1.place (9) E - id (6)A-num p := lookup(id.name);if p nil thenE.palce := p else error3 语法分析方法描述及语法分析表设计3.1 简单优先法的定义构造及优缺点3.1.1 简单优先法定义构造一个文法 G，若它不含产生式，也不含任
13、何右部相同的不同产生式，并且它的任何符号对(X,Y)，或者没有关系，或者存在下述三种关系：=、之一，则称该文法是一个简单优先文法。A)X=Y 当且仅当 G 中含有形如 PXY的产生式B)XY 当且仅当 Y 为 G 的终结符，G 中含有形如 PQR的产生式，其中 Q，R 为非终结符，且 Q X， YFirst(R)D)对任何 X，若文法开始符号 SX，则#。 33.1.2 简单优先法的优缺点优点：准确、规范，技术简单。缺点：适用的范围小，构造的分析表太大，分析效率较低。3.2 语法分析为实现简单优先算法,可以使用工作栈.用以寄存操作数或运算结果.算法的基本思想是: (1) 置初始状态：S(1):
14、=#, i:=1, j:=1(2) 若 S(i)与 T(j)无任何关系，则出错停机(3) 若 S(i)= T(j)或 S(i)T(j)，则把 T(j)送入 S 栈中，读下一符，转（2）。(4) 若 S(i)T(j)，则从 S 栈顶开始往前栈串 Sj1 ,Sj1+1,Si其中 Sj1 为第一个使 Sj1-1Sj1 ,然后用 Sj1,Sj1+1,Si 去查生产式表，若查到有相同右部的产生式即 USj1,Sj1+1,Si，则从栈中退掉子串Sj1,Sj1+1,Si，并把 U 进栈；然后转(2)。若查不到转出错处理。(5) 若 T(j)=#,并且 S 栈的内容为# Z(Z 为文法开始符号)则正确停机。否则，出错停机。3.3 语法分析表设计3.3.1 GS的优先关系表如表 1：表 1 GS 的优先关系矩阵S C T M begin L end if B then else #S C = begin if =B =then else # or () id = rop =true false # A = ; := = + E b and c b goto 3002: goto -003: if c , f then begin x = y*z*a;d= -h;p= q+r+s;c =w;end#$其中“#”为文法结束标志， “$”为文件结束标志，下同。
