编译原理实验报告5-语法分析程序的设计

1、实验 5语法分析程序的设计 （2）一、实验目的通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分 析，进一步掌握常用的语法分析中算法优先分析方法。？二、实验内容设计一个文法的算法优先分析程序，判断特定表达式的正确性。三、实验要求1、给岀文法如下：GEE->T|E+T;T->F|T*F;F->i|（E）;可以构造算符优先表如下：+*()i+/ /lj*()ii2、计算机中表示上述优先关系，优先关系的机内存放方式有两种1）直接存放，2）为优先关系建立优先函数,这里由学生自己选择一种方式；1、给岀算符优先分析算法如下：k:=1;Sk:

2、=' #'；REPEAT把下一个输入符号读进a中；IF Sk VT THEN j:=k ELSE j:=k-1;WHILE Sj a > DOBEGINREPEATQ:=Sj;IF Sj-1 VT THEN j:=j-1 ELSE j:=j-2UNTIL Sj Q <把Sj+1S归约为某个 N;k:=j+1;Sk:=N;END OF WHILE;IF Sj V a OR Sj 三 a THENBEGINk:=k+1;Sk:=aENDELSE ERRORUNTIL a= #'1、根据给岀算法，利用适当的数据结构实现算符优先分析程序;2、利用算符优先分析程序完成

3、下列功能:1）手工将测试的表达式写入文本文件，每个表达式写一行，用“；”表示结束；2）读入文本文件中的表达式；3）调用实验2中的词法分析程序搜索单词；4）把单词送入算法优先分析程序，判断表达式是否正确（是否是给岀文法的语言），若错误，应给岀错误 信息；5）完成上述功能，有余力的同学可以对正确的表达式计算岀结果。?四、实验环境PC微机DOS操作系统或 Windows操作系统Turbo C程序集成环境或Visual C+程序集成环境?五、实验步骤1、分析文法中终结符号的优先关系；2、存放优先关系或构造优先函数；3、利用算符优先分析的算法编写分析程序；4、写测试程序，包括表达式的读入和结果的输岀；5

4、、程序运行效果，测试数据可以参考下列给出的数据。?六、测试数据输入数据：编辑一个文本文文件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输岀：错误七、实验报告要求实验报告应包括以下几个部分

5、：1、给定文法优先关系和存放方式;+*()i#+*(e1)e2e2ie2e2#e3e4引入“ # ”，将句型包含起来并填入岀错标记。使用二维数组将其存放。2、算符优先分析程序的算法和结构；程序从文本文件中逐行读取表达式，每行以“；”做标记。调用词法分析程序将这行数据分析岀由一个个的单词组成的表达式，再逐个分析单词。另外，由于文法中没写入关于标识符和常数的产生式，所以在对* I I I >1单词符号进行语法分析时，会将标识符和常数自动规约为“i”。数据结构：优先关系表 R:二维数组，存储了终结符+、*、（、）、 i、#的优先关系。$ t符号W :结构体，有四个成员，包括：ch : char

6、类型，非终结符与终结符的字符标记；po : int类型，只对终结符有效，与在R中的位置有关，有词法分析器提供；对于非终结符，其po无效；val: string类型，综合属性；对终结符i，其值由词法分析器提供；对非终结符，其值由规约时对应的产生式的规则计算得到；对界符或运算符，val无效；type : int类型，标记属性值类型，0为标识符，不可计算；1为可计算的数值；由词法分析器提供；注意：程序内部数值的计算和标记一律使用十进制，文本中的表达式必须为十进制整数，即如果在文本中使用八进制或十六进制，词法分析器分析后不会添加至缓冲区，在表达式语法正确且其中不含标志符 时，计算得到的结果一律使用十进

7、制。例：对于文本中十进制数字10，其对应的初始结构体成员的值ch='po=5，va匸"10”，type=1。符号栈S:符号结构体的一维数组。算法：说明：GEE->T|E+T;T->F|T*F;F->i|（E）;算符优先文法并未对非终结符定义优先关系，无法对单非产生式进行规约，所以实际上在规约时，上面的E->T，T->F基本没有使用，而且规约时并不严格按照产生式的右部规约，只要待规约项符合句型#N1a1N2a2 NnanNn+1# （每个ai都是终结符，Ni是可有可无的非终结符），并且相对产生式，在相同位置有相同的非终结符即可规约，这样算符优先文法

8、规约很快，但有些语法错误将无法识别，在本实验中，只要在要规约的地方准确的判断可规约的项，即符合句型，在不严格要求非终结符相同而终结符位置符号相同时，存在可匹配文法的产生式，即可规约，例如：F * F可以匹配T*F继而规约为R获取优先关系标定义用Wch表示字符名为ch的符号；实际程序中关于终结符优先关系的比较是利用志的，算法中为了可读性，直接将结构体进行比较了。从文本文件读入一行数据，反复调用sca nP()得到符号集合，用符号结构体数组E存储；k = 1; i = 0;Sk = W#;Do A = Ei+;if( Sk是终结符)j = k;elsej = k -1;while(Sj >

9、A) Do Q = Sj;If(Sj - 1是终结符)j = j -1;elsej = j -2while(Sj < Q);N = Statute(S,j + 1,k);k = j + 1;Sk = N ；If(Sj < A | Sj = A) k+;Sk=代else error(Sj.po,A.po);while(A = W#);程序功能说明：程序从文本文件读入表达式，判断语法是否正确，正确则输岀结果，其中有标识符的话，结果还是含有 标识符的原表达式，语法错误的话，则输出错误信息。源程序：程序中文本文件在桌面文件名为expression.txt#include<iostre

10、am>#include<string> #include<stdlib.h> using namespace std;#define NULL 0#define MAXSIZE 30/单行表达式的符号总数最大值typedef struct grammar_symbol文法符号char ch;int po;string val;int type;W;char pre66 = ;char GetChar(FILE* fp) char ch;ch = fgetc(fp); return ch;char GetBC(FILE* fp) char ch;do ch = Ge

11、tChar(fp); while (ch = ' ' | ch = 't' | ch = 'n'); return ch;void Concat(char ch, char strToken|) char str2;int len = strlen(strToken); strTokenlen = ch;strTokenlen + 1 = '0'int IsLetter(char ch) 回0'>','<','<','>','<&

12、#39;,'>','>','>','<','>','<','>','<','<','<',=,'<','1','>','>','2','>','2','>','>','>',&#

13、39;2','>','2','>','<','<','<','3','<',/优先关系表读取文件中的一个字符读取文件的字符直至ch不是空白/将ch中的字符连接到strToken之后布尔函数，判断ch中的字符是否为字母，是返回1,否则返int flag = 0;if (ch >= 'a' && ch <= 'z')flag = 1;return flag;int Is

14、Digit(char ch) int flag = 0;if (ch >= '0' && ch <= '9')flag = 1;return flag;int Reserve(char strToken) / 整型函数,的编码，否则返回0布尔函数，判断ch中的字符是否为数字，是返回1,否则返回0对strToken中的字符串查找保留字表，若它是一个保留字则返回它int code = 0, i;char keyWord66 = "if", "then", "else", &quo

15、t;while", "do" ; for (i = 0; i < 5; i+) if (strcmp(strToken, keyWordi) = 0) code = i + 1;break;return code;个运算符或界符,int SearchOP(char ch) /整型函数，对strToken中的字符串查找运算符和界符，若它是则返回它的编码，否则返回 0 int code = 0, i;char OP10 = '+', '*',' (', ')', '-', '

16、/', '<', '>', '=', '' ;for (i = 0; i < 10; i+) if (ch = OPi) code = i + 1; break;return code;char Retract(FILE* fp, char ch) ch =''fseek(fp, -1L, 1);return ch;void ProError() printf(” 输入错误！ n");return;int scan(FILE* fp,W* E,int num) W w;char

17、ch;char strToken10;strToken0 = '0'ch = GetBC(fp);if (feof(fp)return 0;if (ch = '')printf("");I,子函数，将搜索指示器回调一个字符位置，将/错误处理函数/置strToken为空串先读取一个非空白的字符ch置为空白字符return 0;/判断表达式尾，是则返回调用程序if (IsLetter(ch) / 判断标识符while (IsLetter(ch) | IsDigit(ch) Concat(ch, strToken); ch = GetChar(fp

18、);/判断关键字ch = Retract(fp, ch);if (Reserve(strToken) printf("<%s,->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 <= '9') while (IsDigit(ch) Concat(ch, str

19、Token); ch = GetChar(fp);ch = Retract(fp, ch); printf("%s", strToken); w.ch = 'i'w.po = 4;/判断十进制整数w.val = strToken;w.type = 1;Enum = w;else if (ch = '0') ch = GetChar(fp);if (ch >= '1' && ch <= '7') while (ch >= '0' && ch <

20、;= '7') Concat(ch, strToken); ch = GetChar(fp); ；ch = Retract(fp, ch); printf("<2,%s>n", strToken);else if (ch = 'x') /判断八进制整数判断十六进制整数ch = GetChar(fp);while (IsDigit(ch) | ch >= 'a' && ch <= 'f') Concat(ch, strToken); ch = GetChar(fp);ch

21、= Retract(fp, ch); printf("<3,%s>n", strToken); else ch = Retract(fp, ch);判断十进制的0printf("O");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;e

22、lse ProError();return 1;bool checkVt(char ch) bool flag = false;int i;char Vt6 = '+', '*', '(', ')', 'i', '#' ;for (i = 0; i < 6; i+) if (ch = Vti) flag = true;return flag;W Statute(W* S, int s, int e) W N;判断运算符和界符/出错规约子函数，将S中j+1到k的符号规约为Nif (Ss.ch =

23、 'i' && s = e) N.ch = 'F'N.val = Ss.val;N.type = Ss.type;else if (Ss.ch = '(' && !(checkVt(Ss + 1.ch) && Se.ch = ')') if (Ss + 1.type = 1) N.ch = 'F'N.val = Ss + 1.val;N.type = Ss + 1.type;else N.ch = 'F'N.val = '('+ Ss

24、+ 1.val + ')'N.type = Ss + 1.type;else if (!(checkVt(Ss.ch) && Ss + 1.ch = '+' && !(checkVt(Se.ch) N.ch = 'E'if (Ss.type = 1 && Se.type = 1) N.type = 1;int v = atoi(Ss.val.data() + atoi(Se.val.data();char l30;sprintf_s(l,30,%d", v);N.val = l;else

25、N.type = 0;N.val = Ss.val + Ss + 1.ch + Se.val;else if (s != e) && !(checkVt(Ss.ch) && Ss + 1.ch = '*' && !(checkVt(Se.ch) N.ch = 'T'if (Ss.type = 1 && Se.type = 1) N.type = 1;int v = atoi(Ss.val.data() * atoi(Se.val.data();char l30;sprintf_s(l, 30,&qu

26、ot;%d", v);N.val = l;else N.type = 0;N.val = Ss.val + Ss + 1.ch + Se.val;else if(Ss.ch = 'T' && s = e)N.ch = 'E'N.val = Ss.val;N.type = Ss.type;else N.ch = '#'N.po = 4;return N;void error(char errnum) / 错误处理子函数if (errnum = '1') printf(”错误，非法左括号nn");e

27、lse if(errnum = '2')printf（”错误，缺少运算符nn"）;else if (errnum = '3')printf(”错误，非法右括号nn");else if (errnum = '4')printf("错误，缺少表达式nn");int synta x(W* E,int num) /算法对应的主要实现程序W SMAXSIZE;int k = 1, i = 0, j;W border, A, Q;二border.ch = '#'border.po = 5;Enum =

28、border;Sk = border;do A = Ei+;if (checkVt(Sk.ch)/ 判断 Sk是终结符j = k;else.1j = k - 1;while (preSj.poA.po = '>') 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 +

29、 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:UsersAdminis|ratorDesktopexpression.txt", "r") != NULL) 读方式打开文件，失败则退岀程序程序开始、printf("file can not open!"); exit(0);是否是文件尾int n = 0; printf（"语法分析结果如下：nn"）W EMAXSIZE; GetBC(fp);否/若不是文件尾则执行循环读取一行文本/存储一行表达式while (!feof(fp) int num = 0;否调用syntax（判断语法是否正确n+