编译原理-语法分析-规约
课程名称 编译原理 设计题目 语法分析规约 目 录一 .问题描述.(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-> >|=|< (id1，id2代表标识符)2.3 属性文法的描述: 属性文法的定义形式: 每个文法符号有一组属性,每个文法产生式A->有一组产生式b:=f(c1,c2,，ck)的语义规则，其中f式函数，b和c1,c2,，ck式该产生式文法符号的属性。3语法分析方法及中间代码形式的描述； 3.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->id1>id2| id1=id2| id1<id2，F-> id1= id2(E->aFb F->>|=|<)对F只有一种产生式而在输入串中的终结符a，b等在程序中用id代替了，正好做到了输入串和符号栈的匹配抵消，因此简化了预测分析表的构造，对于E来说有3个侯选式，在本程序中通过函数firstset（）来判断应该选哪个产生式，但是firstset（）是依赖Token2数组来判断的，没有完全摆脱掉数组的限制，因此也是本程序的不足之处。3.2 中间代码的描述:中间代码概述：中间代码采用四元式输出，一个四元式是一个带有四个域的记录结构，这四个域分别称为oparg1arg2及result。域op包含一个代表运算符的内部码。语句while a<b do a=a+b的四元式输出形式如下： 100 ( <, a , b , 102 ) 101 ( j , _ , _ , 105 ) 102 ( + , a , b , n ) 103 ( = , n , _ , a ) 104 ( j , _ , _ , 100)本次设计的中间代码：本次程序的中间代码是根据一定的语义规则写出的： T while A do E F 代码结构： Sbegin ： Ecode to E.tureE.ture ： Acode to E.falsegoto S.beginto E.false ： 4简要分析与概要设计4.1词法分析词法分析程序的任务是：从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号的中间程序。词法分析检查的错误主要是挑出源程序中出现的非法符号。所谓非法符号是指不是程序设计语言中允许出现的符号，就像自然语句中的错字。4.2递归下降翻译器的设计1.：对每个非终结符F构造一个函数过程，对F的每个继承属性设置一个形式参数，函数的返回值为F的综合属性，F对应的函数过程中，为出现在F的产生式中的每一个文法符号的每一个属性都设置一个局部变量。非终结符F对应的函数过程中，根据当前的输入符号决定使用哪个产生式候选。2：每个产生式对应的程序代码中，按照从左到右的次序，对于单词符号，非3：终结符和语义动作分别做以下工作。（1）对于带有综合属性x的终结符X，把x的值存入为X，x设置的变量中。然后产生一个匹配X的调用，并继续读入一个输入符号。（2）对于每个非终结符号R，产生一个右边带有函数调用的赋值语句c=R(r1,r2,，rk)（3）对于语义动作，把动作的代码抄进分析器中，用代表属性的变量来代替对应属性的每一次引用。4.3语法制导翻译在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译。属性文法的每个符号有属性，所以每个符号入栈时，必须连属性一起入栈，这样，栈符号就由文法符号及存放该符号属性的域所组成。由于属性类型不同，属性域存放的内容就要根据属性的类型来定。有的可能直接存放属性值，也有的存放的是指向属性值的指针。对于综合属性，其属性域不存放其属性值，而是存放一个指针，指向存贮该属性值的单元。对于继承属性，其属性域直接保存其属性值。继承属性的属性域刚入栈时为空，但是在该栈符号变成栈顶符号之前的某一时刻，它们必须接受相应的属性值，即在成为栈顶时，继承属性的属性域必须有值。5详细算法描述5.1 文法/* 文法G(s) s->WEDG G->c=R R->dTe|d T -> +|-|*|/|%E->aFb F-> >|=|< */ 5.2 查错：按照递归下降法求Wa<bDa=a+b，程序的执行顺序是S()àW()àEàF()àD()àG()àR()àT()1) S()void S() printf("%dtS->WEDGn",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();
