编译原理--语法分析——规约.docx

课程名称 编译原理 设计题目 语法分析规约 目 录一 .问题描述.(2）二文法及属性文法的描述.（2） 2.1文法描述.（2） 2.2 while-do循环语句的文法.(2)2.3属性文法描述.（2）3语法分析方法及中间代码形式的描述.（3） 3.1 语法分析方法.（3） 3.2 中间代码形式描述.（3）4简要的分析与概要设计.（4） 4.1词法分析.(4）4.2递归下降翻译器的设计.（4）4.3语法制导翻译.（5）5 详细的算法描述.（5） 5.1 文法.（6） 5.2 查错.（6）三 测试方法和测试结果.（9） 3.1测试方法.（9） 3.2测试结果.（9）四 设计心得.（10） 一、 问题描述1.1 能够写出一个while-do语句，此语句符合LL（1）的文法。1.2 构造词法分析程序对while-do语句进行词法分析。 1.3构造语法分析程序对while-do语句进行语法分析，判断语法正确性。1.4 运行程序，要求有正确的语义输出（4地址码）。二、 文法及属性文法的描述： 2.1 文法描述： 基本概念：文法是对语言结构的定义与描述。即从形式上用于描述和规定语言构的称为“文法”。定义：文法G=（VN，VT，P，Z） VN ：非终结符号集 VT ：终结符号集 P：产生式或规则的集合 Z：开始符号（识别符号） ZVN 其中:2.2 while-do循环语句的文法 文法G(s)如下： S-WEDG （意思是while E do G） G-c=R R-dTe|d T-+|-|*|/ E-aFb F- |=|有一组产生式b:=f(c1,c2,，ck)的语义规则，其中f式函数，b和c1,c2,，ck式该产生式文法符号的属性。3语法分析方法及中间代码形式的描述； 3.1 语法分析方法: 3.1.1本次设计采用LL（1）分析 ：预测分析方法概述：分析钜阵的元素MA，a中的下标A为非终结符，a为终结符或句子的结束标记“#”，钜阵元素MA，a的内容为一条关于A的产生式。它表明当用非终结符A向下推而当输入符a时，所应该采用的后选式。当钜阵元素为空时，则表示用A往下推导时遇到了不应该出现的符号，即A与a不能匹配，因此应该出错处理。在构造预测分析表时，对每个终结符或“#”号用a表示，则若aSELECT（A-a)。令MA，a= A-a(一般为了简化,取MA，a= a)把所有的无定义的MA，a标上ERROR(一般在表中用空白表示)。3.1.2 此程序预测分析方法： 此设计为非左递归while-do文法,应采用自上而下的预测分析方法。在此设计中，产生式只到E-id1id2| id1=id2| id1 id1= id2(E-aFb F-|=|)对F只有一种产生式而在输入串中的终结符a，b等在程序中用id代替了，正好做到了输入串和符号栈的匹配抵消，因此简化了预测分析表的构造，对于E来说有3个侯选式，在本程序中通过函数firstset（）来判断应该选哪个产生式，但是firstset（）是依赖Token2数组来判断的，没有完全摆脱掉数组的限制，因此也是本程序的不足之处。3.2 中间代码的描述:3.2.1中间代码概述：中间代码采用四元式输出，一个四元式是一个带有四个域的记录结构，这四个域分别称为oparg1arg2及result。域op包含一个代表运算符的内部码。语句while ab do a=a+b的四元式输出形式如下： 100 ( WEDG G-c=R R-dTe|d T - +|-|*|/|%E-aFb F- |=| */ 5.2 查错：按照递归下降法求WaWEDGn,total);total+; W(); E();2) W()void W() if(ch!=W) printf(有非法字符%c请按回车返回!,ch); getchar(); getchar(); exit(1); 3) E()void E() ch=a+i1; if(ch!=a) printf(有非法字符%c %c请按回车返回!,ch); getchar(); getchar(); exit(1); printf(%dtE-aFbn,total);total+; F();4) F()void F() int i; ch=a+i1; i=i1+1; if(ai!=b) printf(有非法字符%c请按回车返回!,ai); getchar(); getchar(); exit(1); switch(ch) case : printf(%dtF-n,total);total+; break; case =: printf(%dtF-=n,total);total+; break; default: printf(%dtF-c=Rn,total);total+; R();7) R()void R() int i; i=i1+1; i1=i1+2; ch=ai1; if(ai!=&ch!=d) printf(有非法字符%c %c请按回车返回!,ai,ch); getchar(); getchar(); exit(1); else if(ai1+1=+)|(ai1+1=-)|(ai1+1=*)|(ai1+1=/) printf(%dtR-dTen,total);total+; T(); else printf(%dtR-dn,total);total+; W(); E(); 8) T()void T() ch=a+i1; switch(ch) case +: printf(%dtT-+n,total);total+; break; case -: printf(%dtT-n,total);total+; break; case *: printf(%dtT-*n,total);total+; break; default: printf(%dtT-/n,total);total+; break; ch=#;三、测试方法和测试结果3.1测试方法在C+环境下，设计几个有代表的用例，进行测试，例如：输入语句W(while)abD(do)a=a+b#(其中d表示do ,w表示while)。本次课程设计在运行时，按照while语句的语法要求输入符合条件的语法，最后语句应以#结束若得出的不是预期的结果，那么程序就出现问题。如果有问题的话就进行单步调试找到程序中出现的逻辑问题。词法部分：因为本此输入的单词符号都是符合词法分析程序定义所以能够得到正确的词法分析结果。语法部分：因为次此的输入aaFb f- dFb G-c=R),符合本程序定义的while-do语法规则,所以语法正确。语义输出：在识别非终结符号的时候将与其相对应的产生式输出（相应的语义动作），实现了语法制导翻译，最后将其以4地址的形式输出。3.2测试结果测试结果如下：四、设计心得本次设计是采用递归下降的方法对输入的while-do 循环语句进行语法，语义分析，并输出四元式。因此程序中充分体现了递归下降的思想。通过对语法分析的实践操作，对它在实践中的应用有了更深刻的理解，通过上机实践，提高了从错误中分析问题，解决问题的能力。在实践的基础上，把所学的知识得到了实际应用，通过本次的编译原理课程设计，让我对用C+编程的大致思路又进行了一次回顾，设计一个可运行的程序代码的思路规范，声明变量，定义各大需要调用的函数及其调用。此程序只能实现对WabDa=a+b#的分析与四元式输出，由于我所设计的栈中只能