编译原理实验报告5-语法分析程序的设计(2).doc

.实验5 语法分析程序的设计（2）一、实验目的通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析中算法优先分析方法。二、实验内容设计一个文法的算法优先分析程序，判断特定表达式的正确性。三、实验要求1、给出文法如下： GE E-T|E+T; T-F|T*F; F-i|(E);可以构造算符优先表如下：+*()i+*() i 2、计算机中表示上述优先关系，优先关系的机内存放方式有两种1）直接存放，2）为优先关系建立优先函数，这里由学生自己选择一种方式；1、 给出算符优先分析算法如下：k:=1; Sk:=#;REPEAT 把下一个输入符号读进a中； IF SkVT THEN j:=k ELSE j:=k-1; WHILE Sj a DO BEGIN REPEAT Q:=Sj; IF Sj-1VT THEN j:=j-1 ELSE j:=j-2 UNTIL Sj Q 把Sj+1Sk归约为某个N； k:=j+1; Sk:=N; END OF WHILE; IF Sj a OR Sj a THEN BEGIN k:=k+1;Sk:=a END ELSE ERROR UNTIL a=# 1、 根据给出算法，利用适当的数据结构实现算符优先分析程序；2、 利用算符优先分析程序完成下列功能：1） 手工将测试的表达式写入文本文件，每个表达式写一行，用“；”表示结束；2） 读入文本文件中的表达式；3） 调用实验2中的词法分析程序搜索单词；4） 把单词送入算法优先分析程序，判断表达式是否正确（是否是给出文法的语言），若错误，应给出错误信息；5） 完成上述功能，有余力的同学可以对正确的表达式计算出结果。四、实验环境PC微机DOS操作系统或 Windows 操作系统Turbo C 程序集成环境或 Visual C+ 程序集成环境五、实验步骤1、 分析文法中终结符号的优先关系；2、 存放优先关系或构造优先函数；3、利用算符优先分析的算法编写分析程序；4、写测试程序，包括表达式的读入和结果的输出；5、程序运行效果，测试数据可以参考下列给出的数据。六、测试数据 输入数据：编辑一个文本文文件expression.txt，在文件中输入如下内容：10;1+2;(1+2)*3+(5+6*7);(1+2)*3+4;1+2+3+(*4+5);(a+b)*(c+d);(ab3+de4)*5)+1;正确结果：（1）10;输出：正确（2）1+2;输出：正确（3）(1+2)*3+(5+6*7); 输出：正确（4）(1+2)*3+4输出：错误（5）1+2+3+(*4+5)输出：错误（6）(a+b)*(c+d)输出：正确（7）(ab3+de4)*5)+1输出：错误七、实验报告要求实验报告应包括以下几个部分：1、 给定文法优先关系和存放方式；+*()i#+ *(e1)e2e2 ie2e2#e3e4引入“#”，将句型包含起来并填入出错标记。使用二维数组将其存放。2、 算符优先分析程序的算法和结构；程序从文本文件中逐行读取表达式，每行以“；”做标记。调用词法分析程序将这行数据分析出由一个个的单词组成的表达式，再逐个分析单词。另外，由于文法中没写入关于标识符和常数的产生式，所以在对单词符号进行语法分析时，会将标识符和常数自动规约为“i”。数据结构：优先关系表R：二维数组，存储了终结符+、*、（、）、i、#的优先关系。符号W：结构体，有四个成员，包括：ch：char类型，非终结符与终结符的字符标记；po：int类型，只对终结符有效，与在R中的位置有关，有词法分析器提供；对于非终结符，其po无效；val：string类型，综合属性；对终结符i，其值由词法分析器提供；对非终结符，其值由规约时对应的产生式的规则计算得到；对界符或运算符，val无效；type：int类型，标记属性值类型，0为标识符，不可计算；1为可计算的数值；由词法分析器提供；注意：程序内部数值的计算和标记一律使用十进制，文本中的表达式必须为十进制整数，即如果在文本中使用八进制或十六进制，词法分析器分析后不会添加至缓冲区，在表达式语法正确且其中不含标志符时，计算得到的结果一律使用十进制。例：对于文本中十进制数字10，其对应的初始结构体成员的值ch=i，po=5，val=”10”，type=1。符号栈S：符号结构体的一维数组。算法：说明 ：GE E-T|E+T; T-F|T*F; F-i|(E);算符优先文法并未对非终结符定义优先关系，无法对单非产生式进行规约，所以实际上在规约时，上面的E-T，T-F基本没有使用，而且规约时并不严格按照产生式的右部规约，只要待规约项符合句型#N1a1N2a2NnanNn+1#（每个ai都是终结符，Ni是可有可无的非终结符），并且相对产生式，在相同位置有相同的非终结符即可规约，这样算符优先文法规约很快，但有些语法错误将无法识别，在本实验中，只要在要规约的地方准确的判断可规约的项，即符合句型，在不严格要求非终结符相同而终结符位置符号相同时，存在可匹配文法的产生式，即可规约，例如：F * F 可以匹配T*F继而规约为T。定义用Wch表示字符名为ch的符号；实际程序中关于终结符优先关系的比较是利用R获取优先关系标志的，算法中为了可读性，直接将结构体进行比较了。从文本文件读入一行数据，反复调用scanP()得到符号集合，用符号结构体数组E存储；k = 1; i = 0;Sk = W#;Do A = Ei+;if（Sk 是终结符）j = k;elsej = k 1;while(Sj A) Do Q = Sj;If(Sj - 1 是终结符)j = j 1;elsej = j 2;while(Sj Q);N = Statute(S,j + 1,k);k = j + 1；Sk = N；If(Sj A | Sj = A) k+;Sk = A;else error(Sj.po,A.po);while(A = W#);程序功能说明： 程序从文本文件读入表达式，判断语法是否正确，正确则输出结果，其中有标识符的话，结果还是含有标识符的原表达式，语法错误的话，则输出错误信息。源程序：程序中文本文件在桌面文件名为expression.txt#include#include#includeusing namespace std;#define NULL 0#define MAXSIZE 30/单行表达式的符号总数最大值typedef struct grammar_symbol/文法符号char ch;int po;string val;int type;W;char pre66 = /优先关系表 , , , , , , , , , , , =, , , 2, , 2, , , , 2, , 2, , , , , 3, = a & ch = 0 & ch = 9)flag = 1;return flag;int Reserve(char strToken) /整型函数，对strToken中的字符串查找保留字表，若它是一个保留字则返回它的编码，否则返回0int code = 0, i;char keyWord66 = if, then, else, while, do ;for (i = 0; i 5; i+) if (strcmp(strToken, keyWordi) = 0) code = i + 1;break;return code;int SearchOP(char ch) /整型函数，对strToken中的字符串查找运算符和界符，若它是一个运算符或界符，则返回它的编码，否则返回0int code = 0, i;char OP10 = +, *, (, ), -, /, , =, ; ;for (i = 0; i 10; i+) if (ch = OPi) code = i + 1;break;return code;char Retract(FILE* fp, char ch) /子函数，将搜索指示器回调一个字符位置，将ch置为空白字符ch = ;fseek(fp, -1L, 1);return ch;void ProError() /错误处理函数printf(输入错误！n);return;int scan(FILE* fp,W* E,int num) W w;char ch;char strToken10;strToken0 = 0;/置strToken为空串ch = GetBC(fp); /先读取一个非空白的字符if (feof(fp)return 0;if (ch = ;)printf(;);return 0;/判断表达式尾，是则返回调用程序if (IsLetter(ch) /判断标识符while (IsLetter(ch) | IsDigit(ch) Concat(ch, strToken);ch = GetChar(fp);ch = Retract(fp, ch);if (Reserve(strToken) /判断关键字printf(n, strToken);else /判断标识符printf(%s, strToken);w.ch = i;w.po = 4;w.val = strToken;w.type = 0;Enum = w;else if (ch = 1 & ch = 1 & ch = 0 & ch = 7) Concat(ch, strToken);ch = GetChar(fp);ch = Retract(fp, ch);printf(n, strToken);else if (ch = x) /判断十六进制整数ch = GetChar(fp);while (IsDigit(ch) | ch = a & ch = f) Concat(ch, strToken);ch = GetChar(fp);ch = Retract(fp, ch);printf(n, strToken);else /判断十进制的0ch = Retract(fp, ch);printf(0);w.ch = i;w.po = 4;w.val = 0;w.type = 0;Enum = w;else if (SearchOP(ch) != 0) /判断运算符和界符printf(%c, ch);int po = SearchOP(ch) - 1;w.ch = ch;w.po = po;Enum = w;else /出错ProError();return 1;bool checkVt(char ch) bool flag = false;int i;char Vt6 = +, *, (, ), i, # ;for (i = 0; i ) do Q = Sj;if (checkVt(Sj - 1.ch)j = j - 1;elsej = j - 2; while (preSj.poQ.po != );W N = Statute(S, j + 1, k);if (N.ch = #) error(4);return 0;k = j + 1;Sk = N;if (preSj.poA.po = | preSj.poA.po = =) k+;Sk = A;else error(preSj.poA.po);return 0; while (A.ch != #);if (A.ch = #) printf(正确，结果为：%snn, Sk - 1.val.data();return 0;int main() FILE* fp;errno_t err;if (err = fopen_s(&fp,C:UsersAdministratorDesktopexpression.txt, r) != NULL) /以只读方式打开文件，失败则退出程序printf(file can not open!);exit(0);int n = 0;printf(语法分析结果如下：nn);while (!feof(fp) /若不是文件尾则执行循环int num = 0;W EMAXSIZE;/存储一行表达式GetBC(fp);if (!feof(fp) n+;fseek(fp, -1L, 1);printf(%d), n);else break;while (1) /只读一行，行末标志为“；”int flag = scan(fp, E,num);if (flag = 0)break;num+;printf(n输出：);syntax(E,num);fclose(fp); /关闭文件fp = NULL;/避免指向非法内存 3、 程序运行流程；输入表达式到文本程序开始是否是文件尾读取一行文本否调用syntax()判断语法是否正确输出结果是否输出错误返回退出程序是4、 程序的测试结果和问题；实验报告源数据： 其它数据： 问题：实验时是根据实验报告提供的算法编程的，但是原算法使用了类似Pascal的语言，而我用的是C，算法实现时具体的语法不同，例如Pascal的repeatuntil与C语言的dowhile并一样，实验时不注意会使程序出错，二者的循环条件是相反的。编程时，误将终结符数组的左右括号输入成了中文的括号，导致在判断是否为终结符时，英文的左右括号无法与中文的括号匹配，程序出现了错误，虽然调试时很容易就发现了，但这样的细节问题不应该费时间要调试才解决，这提醒我编程时更应该认真仔细，效率才能得到保证。另外，语法错误时，这一行表达式的分析就可以直接终止但此时程序是在两层循环里面，只有跳出这两层循环才会终止，而break则只能跳出一层，若在最后一层使用标志，再跳出一层，这就导致之后的每一行都会多做一次判断，而我又不想使用goto，所以最后我决定使用子函数，将语法分析的主要程序段放在子函数中，有语法错误，直接return就可以了。5、 实验总结。 本次实验有之前的词法分析程序和已经提供的算法作基础，编写起来并不难，就是要注意算符优先文法本身的优缺点，它忽略右部只有一个非终结符的产生式，而且规约的时候主要还是匹配终结符，由于这个原因，规约很快，但有些语法错误的表达式会误认为句子，所以在在原本算法的第十一步，规约的具体步骤要按具体的文法来完成，其中要包括没有匹配时对应的错误处理。实验的最主要部分的算法很容易实现，主要是如何正确的完成规约，并将正确的句子的结果计算出来，此处是借助于结构体，在每个规约步骤中，加上对应的计算规则，即可完成。通过这个，再次让我明白，编程时，设计好算法和数据结构事半功倍。部分内容来源于网络，有侵权请联系删除！