WHILE循环语句的翻译程序设计(递归下降法,输出四元式).doc

《WHILE循环语句的翻译程序设计(递归下降法,输出四元式).doc》由会员分享，可在线阅读，更多相关《WHILE循环语句的翻译程序设计(递归下降法,输出四元式).doc（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、武汉理工大学数据结构课内实践报告学 号： 0121210340314课内实践报告课程名称 编译原理设计题目WHILE循环语句的翻译程序设计(递归下降法，输出四元式)学 院 计算机科学与技术专业班级计算机1203班姓 名 闵丹枫指导教师林 泓2014年12月 8日2据年 课践名报签指及不以 分0） 0中）-0、分 优记分成语等/ 验 范范 确正 造、性性案 理理 纪遵认得满项序 00 0：枫：姓 机定绩计等琴 学华 文果的确直错的源分即，果性验检统进结运对情编过成序个成来的块的再最算块，几成将然思己清，的分做前程在因行输误对情种考充次的合加编便分分进况及，目研应们程。会也合善性健逻程编的算序的编

2、不路晰比果前序在要思的程编白，间四地，下递，识了理编程运译语算体和用用易单运序误错法确能程然人出将四能，翻 现分下递上序不、价计。结翻间，法分。解有,后相在了很理递,文 之次过过等会与不特评计程制为果 + 为果 ;)如结 ;* ) 下下; ） 结结和 - ) ( - = (运赋处) 0 + ) - + ) - | 运减/+ ; = ; + ( ( - ) + /= | 运除/)+ = 0 ( +)( - ) - - = 运运处) + + ) )( - + )- + /= | 运除理) = + = (+ ; ( + ; = ( 出式行语 “ ”缺 = ) + + ( - - )( =) , 括括

3、号从; ( )= + = ( + )/ * |-= |+= | = =) 号符) ) ( )= &= + + + , - ) & + + ( ) ( + )= & ( + + _ , , + ( = = _ ( _ / _ | ！非） ) ( + ( ) & ()/ ) (_ ） ！输关 ) = )+ = * ）) + )( ) = ) ( +) ) 元出语赋处/ ) 元四处句语/ ; 式元输除行句/ ) , ( 的中后计用 ) ( / _ / ; / ; (_ 判 * ( 分分语 ) 达取/ ( 键查 , 0= 标号/ = 达值赋/ ; = 个个中入标 个符运 0= 0 0 定的()( (

4、描算值须性的继，成即性相接它，某号顶号该但为栈域性承。存直域，属对元值贮指指存而值放域，性对指性向放有值性接的。类属要内存属不类由组的号该及符号，入一必时号个，号个文。行作义述则或程的所产据展步析随程翻制用次的性替来属表中进代动，动 , 句值的有带一 结非号入一读，的配一然中置，为存，符终合作工做动和终：，于序次左按代的应选式生使号输当，程数应结量变置性属号文个式产现，程的 性合值回，式形性承的，过函造符设的译递字错中自号现允言序不号法所法现中出挑误检法。程号单改序串字号单个一扫序程地逐从是的分词误法示时的序有没下执的以序时的足满件有是子用套，程归递以虑就递文个用归始 开的句 分可下个到可序支

5、型该做就类前果；导文不字输是果，的需是判，结得根中分在。是符，符运标，关限包型类类单回进结据字否是比和词的到析词。词符入包中析的字现来的过然操它程一写非对通技降递设概程全设概 , , ( _ , , ( _ ,( ) = /) . = .( = : : ) ( : ) . = +) . : )= . =: = =: = )= =) . = )= ) : ( : ）) ) | , | ), | . = ; : : = = ( 规义生) 哪应无则的互 每然集符个出所表) ， )( ： 右个的环循会，递不 结描法属 . | - . |- +- . | | | . ( - 为法到，归消 |) / -

6、| +- 下示法语 的写达识:字符标|式表=:式 式达 表=式 |式表 式式表 达 式表符件( = ） 尔斯充扩描文描法性码代示代四用分行合，的句 符是入识则若要词否入查可程该的为语析法分个写下递。) 法使归除的语 别任主式式间输导法采法递选法程义法句循值表 描描描式式出法（序程句循 月 名教责 0 师点0一星周设时书收验行验到 期的计排告计程试及序成周计及统成 周周排）书规开（考）等体足点特的本制（果果和方的）代图流描的计设统计设的代间述形中目题计设分及描法述的性法）描域（括包的文报程写要按告序序分过并测例计设析计序程和法成思方析的述描四码的法性法法方的给求体写明以求其及设括（任要计计上在计

7、有。环机供验机用的言算一掌译完件式式、降归设程句 院院与算位作 林师 机 ：班 闵 务计 务 ： 林 位院 设、式掌言用供。上计括其求求给性的四的法程设例过序写文包描性法及计中代的计描）的（的足）考）排成周及计排 验收时0师 0责 句（式描 循义程采法式别语除 )写法为程入要则符，分代代性扩尔）=( 句:表 达式=式符:( | + -/ ) 到为 - .- 结不会个 )， 出符每 的无)义 = = .| ) ) ): : = = = )= = . += : ) . ) ). . . 描描下直的足文中编过别的某式按一择导，法调率程组程, 理此式定这个程序执用继程开符入器过 来的递分步程，出的所词

8、个降一 (表符 ( 种, ,归子中列形式四个域分 及个符 =的 , 全概降非程操过字包符析词和据进类限关，是中根是，是字果类该可下分的开归递递，子是足以下有时误的地扫单串改。误中法法言现中的造函性式值 ，个号变结，号生的按于：做合，然的一号一有 ,，进属替的程步展所述行个个时，符及由属内类接放性，放指贮对域承性该顶它接即性须 (的 0= 个=; 赋 / 0 查 /达 分 * ( )用中 句行 句四 处元 ) ( )= ) () * ) 关 ( / | _ ( _ , + ) - + + ( 号 值 ( ! | /+ =+ = ( 括 ) )- (+ ) “ 行 = + ; ( += ) |=

9、) +- ) )运 ) ( ( =+除 + (+; ;减 - )+ 处运 为程特等过 ,了相,法间。价上下 ，出人能错易用语程编递地四程要前比不算编健合会应及进编的考情行程前，然几算的的成编运统性果的直果琴绩定 00序认遵 性、正 /成优 -00不指年 教丹 班技学机 式四输降(计翻的循题原译 名报践 0 ：号课程设计任务书学生姓名： 闵丹枫 专业班级： 计算机1203班 指导教师： 林 泓 工作单位：计算机科学与技术学院 题目: WHILE循环语句的翻译程序设计（递归下降法、输出四元式）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。实践：计算机实验室提供计算机及软件环境。如果自

10、己有计算机可以在其上进行设计。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1） 写出符合给定的语法分析方法的文法及属性文法。（2） 完成题目要求的中间代码四元式的描述。（3） 写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。（4） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（5） 设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：1 系统描述（问题域描述）；2 文法及属性文法的描述；3 语法分析方法描述及语法分析表设计；4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5 编译系统的概要设计；6

11、 详细的算法描述（流程图或伪代码）；7 软件的测试方法和测试结果；8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；9 参考文献（按公开发表的规范书写）。时间安排：设计安排一周：周1、周2：完成系统分析及设计。周3、周4：完成程序调试及测试。周5：撰写课程设计报告。设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。设计报告书收取时间：设计周的次周星期一上午10点。指导教师签名： 2014年 9月 1日系主任（或责任教师）签名： 2014年 月 日 WHILE循环语句的翻译程序设计（递归下降法、输出四元式）一 系统描述1.1问题描述设计一个WHILE布尔表达式DO赋值

12、语句循环语句的词法语法及语义分析程序，语法分析选择递归下降法，采用用语法制导翻译输出中间代码四元式。1.2主要任务设计一个能识别while循环语句的文法，消除左递归，使文法符合LL(1)文法。利用递归下降法编写一个集词法分析，语法分析和语义分析为一体的程序。该程序首先可以检查输入语句是否符合词法要求，若符合则继续识别输入的语句是否符合while语句的文法，若符合则进行语义分析，输出用四地址代码表示的中间代码。二 文法及属性文法的描述2.1 文法的描述 扩充巴科斯-瑙尔范式（EBNF）： := while () do := := + | - | := * | / | :=() | |:=；根据以

13、上写出来的While循环语句的文法表示如下：1. S - while (A) do B2. A - CDC3. D - | = | = | C+E | C-E | E5. E - E*F | E/F | E6. F - (C) | i | n对以上文法消除左递归，最后得到的文法为：1. S-while (A) do B 2. A-CDC3. D- | = | = | EG 5. G-+EG | -EG | 6. E-FH 7. H-*FH | / FH | 8. F-(C) | i | n 9. B-i=C；2.1 属性文法的描述(1)任一非终结符B都不是左递归的，否则会产生死循环。(2)对A

14、的任意两个右部i , j ,有：first(i)first(j)=， First(i)表i所能导出串的第一个符号的集合。显然，每个i的first(i)是互不相同的，否则则无法判断应执行哪个(i )。产生式 语义规则S-while (A) do B S.first:=newtemp; S.second:=newtemp;A.true:=newtemp;emit（A.false:=S.second;S1.second:=S.first; S.place:=(S.begin, :) | B.place |printf(S.true, :) |S1.place | printf(goto,S.begi

15、n) | printf(B.false, :) | printf(goto Lnext);）A-CDCA.place:=newpemt;emit(A.place:=C1.place D.place C2.place).D- D.place:=newtemp ;Emit(D.Place:=).D- D.place:=newtemp ;Emit(D.Place:= =D.place:=newtemp ;Emit(D.Place:=).D- =D.place:=newtemp ;Emit(D.Place:=).D- =D.place:=newtemp ;Emit(D.Place:=EG C.Plac

16、e:=newtemp;Emit(C.Place:=E.Place G.place)G-+EG G.Place:=newtemp;Emit(G1.Place:=+E.Place G2.place)G-EG G.Place:=newtemp;Emit(G1.Place:=-E.Place G2.place)G-G.Place:=newtemp;Emit(G.Place:=H-*FH H.Place:=newtemp;Emit(H1.Place:=*F.Place H2.place)H- /FHH.Place:=newtemp;Emit(H1.Place:=+F.Place H2.place)H-G

17、.Place:=newtemp;Emit(H1.Place:=+E.Place H2.place)F-(C) F.Place:=C.PlaceB-i=C;p:=lookup(i.name)If p!=nil thenEmit(p:=C.PlaceElse error)三 语法分析方法描述31 语法分析方法描述 递归下降法是一种比较简单直观，易于构造的语法分析方法。他要求文法满足LL（1）文法，他的设计思想是对应文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的单词（或串），当某非终结符的产生式有多个候选时，能够按LL（1）形式可唯一地确定选择某个候选进行推导。它的优点是

18、简单直观，易于构造，很多编译系统所实现缺点是对文法要求很高，由于递归调用多，影响分析器的效率。递归下降程序是由一组子程序组成，每个子程序对应于一个非终结(S,A,B,C,D,E,F,G,H)。每个子程序处理相应句型中相对于此非终结符号的产生式。在定义文法时，是递归定义的，所以这些子程序也是递归的。当一个子程序调用另一个子程序时，原子程序顺序执行语句，即总是先执行被调用的子程序，然后再执行后继的程序。程序中9个子程序，其中S 是开始符号，也是递归下降分析的入口，通过调用词法分析器进行单词分析，并通过word=l.Yufa_Queue.front()来得到当前所分析到的单词，然后在递归语法分析中根

19、据这个单词分析下一步要执行的子程序。其中要注意的是，当子程序G()和H()中出现匹配的是空字符串时，不做单词处理，该所取得的单词，应该为下一个匹配产生做准备。32 递归下降法实现的原理设A是一个非终结符：A1 A2 An则写 (A) if charfirst(1 ) then(1 ) else if charfirst(2 ) then (2 ) else if charfirst(n ) then (n) else ERROR其中(i)表示调用处理符号串i的子程序。对A的任一右部i 设为： i = y1 y2 yn则定义( i) begin(y1);(y2);(yn) end其中yj可分为下

20、列两种情况（j=1,n):1) yjVT,则 ( yj) if char yj then ERROR else READ(char)2) yjVN,则(yj)表示调用关于yj的递归子程序。四中间代码形式的描述及中间代码序列的结构设计4.1四元式形式 中间代码为四元式，按照要求，要输出四元式一个四元式是一个带有四个域的记录结构，这四个域分别称为oparg1arg2及result。域op包含一个代表运算符的内部码。语句while ab do a=a+b的四元式输出:1 ( , a , b , 3 ) 2 ( j , _ , _ ,6 ) 3 ( + , a , b , n ) 4 ( = , n

21、, _ , a ) 5 ( j , _ , _ , 1) 6五 编译系统的概要设计5.1全局程序的概要设计 递归下降分析技术就是通过对每个非终结符编写一个子程序来实现它的操作，然后通过递归的调用来实现对输入字符串的分析，这其中还包括对输入字符串的词法分析。在词法分析的时，得到的字符单词要和关键字比较，看是否是关键字，根据比较结果进行返回相应的单词类型。单词类型主要包括界限符，关键字，常量，标识符，运算符等，每种符号都是一种类型。在语法分析程序中，根据词法得到的结果，进行判断是否是当前需要的单词类型，如果不是就说明输入字符串不能由该文法推导出来；如果是当前需要的类型，就相应得做该单词类型分支程序

22、。根据文法可以得到这个递归下降程序可以分析while语句，在文法的开始符号S开始进行递归调用，因此这个文法的递归中就要考虑到调用以及递归。在递归子程序中，在嵌套调用其他子程序时都是有一定条件的，当满足这个条件的时候该程序可以按照满足的条件执行下去，当没有满足程序中的条件时就会显示语法错误。5.2词法分析词法分析程序的任务是：从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号的中间程序。词法分析检查的错误主要是挑出源程序中出现的非法符号。所谓非法符号是指不是程序设计语言中允许出现的符号，就像自然语句中的错字。5.3递归下降翻译器的设计对每个非终结符A构

23、造一个函数过程，对A的每个继承属性设置一个形式参数，函数的返回值为A的综合属性，A对应的函数过程中，为出现在A的产生式中的每一个文法符号的每一个属性都设置一个局部变量。非终结符A对应的函数过程中，根据当前的输入符号决定使用哪个产生式候选。每个产生式对应的程序代码中，按照从左到右的次序，对于单词符号，非3：终结符和语义动作分别做以下工作。1. 对于带有综合属性x的终结符X，把x的值存入为X，x设置的变量中。然后产生一个匹配X的调用，并继续读入一个输入符号。2. 对于每个非终结符号B，产生一个右边带有函数调用的赋值语句c=B(b1,b2,，bk)3. 对于语义动作，把动作的代码抄进分析器中，用代表

24、属性的变量来代替对应属性的每一次引用。5.4语法制导翻译在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译。属性文法的每个符号有属性，所以每个符号入栈时，必须连属性一起入栈，这样，栈符号就由文法符号及存放该符号属性的域所组成。由于属性类型不同，属性域存放的内容就要根据属性的类型来定。有的可能直接存放属性值，也有的存放的是指向属性值的指针。对于综合属性，其属性域不存放其属性值，而是存放一个指针，指向存贮该属性值的单元。对于继承属性，其属性域直接保存其属性值。继承属性的属性域刚入栈时为空，但是在该栈符号变成栈顶符号之前的某一时刻，它们必须接受

25、相应的属性值，即在成为栈顶时，继承属性的属性域必须有值。六 详细的算法描述S()W()EF()D()G()R()T()方法和变量的定义#define MAX 100int m = 0, sum = 0;/sum用于计算运算符的个数 m用于标记输入表达式中字符的个数char JG = A;char strMAX; /用于存赋值表达式int token = 0; /左括号的标志int sign = 0;char whi5 = w, h, i, l, e ; /检查关键字whilestring getsentence(); /获取表达式void anlyse(string temp); /while

26、语句递归分析bool Judge_W(char *ch); /判断whilevoid Do_E(string temp); /Evoid Do_F(string temp); /F void Do_G(string temp); / Gvoid change(int e); /用于更改计算后数组中的值void chengchuchuli(int i, int m); /对赋值语句进行乘除处理便于输出四元式 void jiajianchuli(int j, int m); /对赋值语句进行加减处理四元式void siyuanshi(); /用于处理赋值语句输出四元式void anlyse(str

27、ing temp)char *wh = new char5;int s_length = temp.size() + 1;char *str = new chars_length;for (; sign 5; sign+)whsign = tempsign;if (Judge_W(wh)if (tempsign = ()sign+;Do_E(temp);做W（）：bool Judge_W(char *ch) bool flag = true;for (int i = 0; i 5; i+)if (chi != whii)flag = false;cout while关键字输入错误！ aFbif

28、 (tempsign = a & tempsign A & tempsign = Z)cout ( ;sign+;Do_F(temp);elsecout （）中含有非法字符！ | =void Do_F(string temp) /F - | =int f_sign = sign;if (tempf_sign = )if (tempf_sign + 1 = =)cout tempf_sign + 1= a & tempf_sign + 2 A & tempf_sign + 2 = Z)cout tempf_sign tempf_sign + 1 , tempf_sign - 1 , tempf_

29、sign + 2 ,sign) = a & tempf_sign + 1 A & tempf_sign + 1 = Z)cout tempf_sign , tempf_sign - 1 , tempf_sign + 1 ,sign) endl;sign+;sign+;if (tempsign = ) & tempsign + 1 = )sign = sign + 2;Do_G(temp);elsecout ()中存在符号错误 c=Rvoid Do_G(string temp) /G- c=R 赋值表达式int pMAX;int len = temp.size() + 1;char ch = a

30、;int c = -1, q = 0;while (tempsign != ; & sign len)ch = tempsign;strm+ = ch;if (ch = = | ch = + | ch = - | ch = * | ch = /) sum+;else if (ch = ()p+c = m - 1;else if (ch = )q = m - 1;chengchuchuli(pc, q);/从左括号处理到又括号jiajianchuli(pc, q);JG = (char)(int)JG-;strpc = strm - 1 = JG;c-;JG = (char)(int)JG+;s

31、ign+;cout str endl;siyuanshi();if (tempsign != ;) cout 前缺少 “;” endl;if (temptemp.size()-1 != ) cout 缺少“” = A&ch = Z)for (int l = 0; l= A&stre = Z)for (int i = 0; im; i+)if (stri = stre)stri = JG;void chengchuchuli(int i, int m)i+;for (; i = m - 1; i+)/处理乘除运算if (stri = * | stri = /)cout ( stri stri - 1