语法分析器(含完整源码)

1、语法分析实验报告一、实验目的： 1. 了解单词(内部编码)符号串中的短语句型结构形成规律。 2. 理解和掌握语法分析过程中语法分析思想(LL，LR)的智能算法化方法。二、实验内容：构造自己设计的小语言的语法分析器： 1. 小语言的语法描述(语法规则)的设计即文法的设计； 2. 把文法形式符号中所隐含的信息内容挖掘出来并用LL或LR的资料形式(分析表)表示出来； 3. 语法分析的数据输入形式和输出形式的确定；4. 语法分析程序各个模块的设计与调试。主要设备和材料：电脑、win7操作系统、VC语言系统三、实验步骤：1、语法规则 <程序> := <变量定义语句> | <

2、赋值语句> | <条件语句> | <循环语句> <变量定义语句> := var 变量，变量； <赋值语句> := 变量 ：= <表达式>； <表达式> := 标识符运算符 标识符 ； <标识符> := 变量 |常量 <运算符 > := + | - | * | / | >= | <= <条件语句> := <if语句><else语句> <if语句> := if(表达式) thenbegin 赋值语句 |条件语句 | 循环语句end <

3、;else语句> := begin 赋值语句 | 条件语句 | 循环语句 end <循环语句> := while(表达式) begin 赋值语句 | 条件语句 | 循环语句 end <输出语句> := prn 表达式-注1：若if语句、else语句、循环语句中出现begin，后面的end必须出现，即begin与end同对出现-注2：if、while后的"（"，"）"表示终结符，而不是定义成分优先的说明符号2、分析表： : =变量常量 ， ；运算符 （ )变 量定 义-> -> -> -> 赋 值语 句

4、->->->-> ->条 件语 句->-> -> -> -> -> -> 循 环语 句-> -> -> -> -> -> -> 输 出语 句->->->分析表(续)：whilevarbeginendifthenprn变 量 定 义-> 赋 值 语 句条 件 语 句->->-> -> 循 环 语 句-> -> -> 输 出 语 句->3、 调试和测试四、源代码（见附录）：五、实验总结：本实验在词法分析的基础上，对

5、提取出的标识符进行语法判断。对已有的语法规则运用LL(1)文法判别并进行构造分析表时，遇到的最大困难是：当发生规约冲突时，该如何处理。如对于产生式s->aAb，当对a进行规约时，满足语法规则的（用户输入串中当前要进行规约的标识符）只有有限种，而不满足的却有无限种情况。当发生规约冲突时，如何在这无限种情况中，确定冲突的具体信息，以便用户查找。在反复的尝试和验证中，我们发现发生冲突的用户输入串满足一定的规律，且按这种规律可以把这无限种情况化归为有限类，于是我们找出其中规律并进行划分，然后再对这些有限类冲突进行处理。六、实验心得:通过这次实验有以下几点收获:1 LR(1)的构造使得对理论的知识

6、理解的更加透彻。其中LR（1）分析表构造了很多遍，一直无法得到正确结果，这是恒心的考验。2 在写程序中用类数组来存放单词属性使得对单词各项值的调用更加方便，特别是对出错信息的检测有很大的作用。3 本实验是在词法基础上的更进一步，在词法程序上添加语法程序，更加理解二者之间的关系。词法分析为语法分析提供了词法单元，方便分析，使程序模块化，易于读懂。附录：#include <iostream>#include <fstream>#include <string>#include <math.h>#include <ctype.h>#incl

7、ude <cstdlib> using namespace std;#define Max 655 /最大代码长度#define WordMaxNum 256 /变量最大个数#define DigitNum 256/常量最大个数#define MaxKeyWord33/关键字数量#define MaxOptANum 8/运算符最大个数#define MaxOptBNum 4/运算符最大个数#define MaxEndNum 11/界符最大个数typedef struct DisplayTableint Index; /标识符所在表的下标int type;/标识符的类型int lin

8、e;/标识符所在表的行数char symbol20;/标识符所在表的名称Table;int TableNum = 0; /display表的表项总数char WordWordMaxNum20; /标识符表char DigitWordMaxNum20; /数字表int WordNum = 0; /变量表的下标int DigNum = 0; /常量表的下标bool errorFlag = 0; /错误标志 int TableIndex = -1; /display 表的下标索引int beginCount = 0;/遇到begin加1，遇到end减1int ifCount = 0; /遇到if加1

9、Table *table = new TableMax;/关键字const char* const KeyWordMaxKeyWord = "and","array", "begin","case","char","constant","do","else","end","false","for","if","input","i

10、nteger","not","of","or","output","packed","procedure","program","read","real","repeat","set", "then", "to", "type", "until", "var",&quo

11、t;while", "with","prn" / 单目运算const char OptA = '+','-','*','/','=','#','<','>'/双目运算符const char *OptB = "<=",">=",":=","<>"/ 界符const char End = '('

12、;, ')' , ',' , '' , '.' , '' , '' , ':' , '' , '' , '"' void error(char str20,int nLine, int errorType) errorFlag = 1; cout <<" nError : " switch(errorType) case 1:cout << "第" <<

13、; nLine-1 <<"行" << str << " 变量的长度超过限制！n" break; case 2:cout << "第" << nLine-1 <<"行" << str << " 小数点错误！n" break;case 3:cout << "第" << nLine-1 <<"行" << str <

14、< " 常量的长度超过限制！n"break;/switch/errorvoid Scanner(char ch,int chLen,int nLine)int chIndex = 0; while(chIndex < chLen) /对输入的字符扫描/*处理空格和tab*/忽略空格和tabwhile(chchIndex = ' ' | chchIndex = 9 ) chIndex +; /*处理换行符*/ /遇到换行符，行数加1while(chchIndex = 10) nLine+;chIndex +;/*标识符*/if( isalpha(c

15、hchIndex) /以字母、下划线开头 char str256; int strLen = 0;/是字母、下划线while(isalpha(chchIndex) | chchIndex = '_' ) strstrLen + = chchIndex; chIndex +;while(isdigit(chchIndex)/不是第一位，可以为数字strstrLen + = chchIndex;chIndex +;strstrLen = 0; /字符串结束符if(strlen(str) > 20) /标识符超过规定长度，报错处理error(str,nLine,1); else

16、int i; for(i = 0;i < MaxKeyWord; i+) /与关键字匹配/是关键字，写入table表中 if(strcmp(str, KeyWordi) = 0) strcpy(tableTableNum.symbol,str);tableTableNum.type = 1; /关键字tableTableNum.line = nLine;tableTableNum.Index = i;TableNum +;break; if(i >= MaxKeyWord) /不是关键字tableTableNum.Index = WordNum;strcpy(WordWordNum

17、+,str);tableTableNum.type = 2; /变量标识符strcpy(tableTableNum.symbol,str);tableTableNum.line = nLine;TableNum +;/*常数*/else if(isdigit(chchIndex) /遇到数字int flag = 0;char str256;int strLen = 0;/数字和小数点while(isdigit(chchIndex) | chchIndex = '.')/flag表记小数点的个数，0时为整数，1时为小数，2时出错if(chchIndex = '.'

18、) flag +;strstrLen + = chchIndex;chIndex +; strstrLen = 0;if(strlen(str) > 20) /常量标识符超过规定长度20，报错处理error(str,nLine,3);if(flag = 0)tableTableNum.type = 3; /整数if(flag = 1)tableTableNum.type = 4; /小数if(flag > 1)error(str,nLine,2);tableTableNum.Index = DigNum;strcpy(DigitDigNum +,str);strcpy(tableT

19、ableNum.symbol,str);tableTableNum.line = nLine;TableNum +;/*运算符*/else/用来区分是不是无法识别的标识符，0为运算符，1为界符int errorFlag;char str3;str0 = chchIndex;str1 = chchIndex + 1;str2 = '0'int i;for( i = 0;i < MaxOptBNum;i+)/MaxOptBNum)if(strcmp(str,OptBi) = 0) errorFlag = 0; tableTableNum.type = 6; strcpy(ta

20、bleTableNum.symbol,str); tableTableNum.line = nLine; tableTableNum.Index = i; TableNum +; chIndex = chIndex + 2; break;if(i >= MaxOptBNum)for( int k = 0;k < MaxOptANum; k+)if(OptAk = chchIndex)errorFlag = 0;tableTableNum.type = 5;tableTableNum.symbol0 = chchIndex;tableTableNum.symbol1 = 0;tabl

21、eTableNum.line = nLine;tableTableNum.Index = k;TableNum +;chIndex +;break;/*界符*/for(int j = 0;j < MaxEndNum;j +)if(Endj =chchIndex)errorFlag = 1;tableTableNum.line = nLine;tableTableNum.symbol0 = chchIndex;tableTableNum.symbol1 = 0;tableTableNum.Index = j;tableTableNum.type = 7;TableNum +;chIndex

22、 +;/*其他无法识别字符*/开头的不是字母、数字、运算符、界符if(errorFlag != 0 && errorFlag != 1) char str256;int strLen = -1;strstrLen + = chchIndex;chIndex +;while(*ch != ' ' | *ch != 9 | chchIndex != 10)strstrLen + = chchIndex;chIndex +;strstrLen = 0;tableTableNum.type = 8;strcpy(tableTableNum.symbol,str);tab

23、leTableNum.line = nLine;tableTableNum.Index = -2;TableNum +; /*把十进制小数转为16进制*/void Trans(double x,int p) /把十进制小数转为16进制int i=0; /控制保留的有效位数while(i<p) if(x=0) /如果小数部分是0 break; /则退出循环 else int k=int(x*16); /取整数部分 x=x*16-int(k); /得到小数部分 if(k<=9) cout<<k; else cout<<char(k+55); ; i+; ;/*语

24、法错误*/void Gerror(int errorType,int nIndex)errorFlag = 1;switch(errorType)case 1:cout << "第" << tablenIndex.line <<"行：" << tablenIndex.symbol <<" 应该为赋值号：= n"break; case 2:cout << "第" << tablenIndex.line <<"行：

25、" << tablenIndex.symbol <<" 应为变量 n"break;case 3:cout << "第" << tablenIndex.line <<"行：" << tablenIndex.symbol <<" 应为逗号 n"break; case 4:cout << "第" << tablenIndex.line <<"行：" &l

26、t;< tablenIndex.symbol <<" 应为分号 n"break;case 5:cout << "第" << tablenIndex.line <<"行：" << tablenIndex.symbol <<" 应为运算符 n"break;case 6:cout << "第" << tablenIndex.line <<"行：" << ta

27、blenIndex.symbol <<" 应为变量或常量 n"break;case 7:cout << "第" <<tableTableIndex.line <<"行 " << tablenIndex.symbol << "与"<<tableTableIndex + 1.symbol <<"之间缺少运算符 n"break;case 8:cout << "第" <&

28、lt; tablenIndex.line <<"行：" << tablenIndex + 1 .symbol <<" 应为'(' n"break;case 9:cout << "第" <<tableTableIndex.line <<"行 " << tableTableIndex.symbol << "与" <<tablenIndex + 1.symbol <<

29、"之间缺少'(' n"break;case 10:cout << "第" << tableTableIndex - 1.line << " 行: 缺少'then'" << endl;break;case 11: cout << "第" << tableTableIndex.line << " 行:"<<tablenIndex.symbol << "

30、应为then n" break;case 12:cout << "第" << tableTableIndex.line << " 行: end 后不能接 " <<tableTableIndex.symbol << endl; break;case 13:cout << "第" << tablenIndex.line <<"行： " << tablenIndex - 1.symbol <<

31、"与 " <<tableTableIndex.symbol <<"之间缺少变量 n"break;case 14:cout << "第" <<tablenIndex .line <<"行 " << tablenIndex .symbol << "后缺少'' n"break;case 15:cout << "第" << tableTableIndex.lin

32、e << " 行:"<<tablenIndex.symbol << "应为')' n"break;case 16:cout << "第" << tableTableIndex.line << " 行,begin 后不能接 " <<tableTableIndex.symbol << endl;break;/*表达式判断*/bool express()while(1 ) if(tableTableIndex.

33、type=2|tableTableIndex.type = 3 ) if(tableTableIndex.type=3&&tableTableIndex+ 1.type = 2 && tableTableIndex.line = tableTableIndex + 1.line) Gerror(7,TableIndex); /出错信息：该处缺少运算符/TableIndex = TableIndex + 2;TableIndex +;if(tableTableIndex.line != tableTableIndex + 1.line)/Gerror(14,Tab

34、leIndex); /出错信息：该语句缺少分号return 1; TableIndex +;else if(tableTableIndex.type = 5|tableTableIndex.type = 6)Gerror(13,TableIndex);TableIndex +;else Gerror(6,TableIndex); /出错信息：该处应为变量或常量TableIndex +;if(tableTableIndex.type =5| tableTableIndex.type = 6 )TableIndex +;else if(tableTableIndex.type = 7)return

35、 1;else if(TableIndex >= TableNum) /| ) Gerror(14,TableIndex); /出错信息：该语句缺少分号 return 1;else Gerror(5,TableIndex); /出错信息：此处应为运算符 TableIndex +;/*赋值语句判断*/bool Assign() /赋值语句的判断TableIndex +;if(strcmp( ":=" , tableTableIndex.symbol) = 0)TableIndex +; else Gerror(1,TableIndex); /出错信息：赋值号应该为&qu

36、ot;:=" TableIndex +;if(express() /":="后可以为变量或常量if(strcmp("",tableTableIndex.symbol) = 0)return 1;else if(TableIndex >= TableNum) Gerror(14,TableIndex); /出错信息：该语句缺少分号 return 1;else if(tableTableIndex.line != tableTableIndex + 1.line)Gerror(14,TableIndex); /出错信息：该语句缺少分号retu

37、rn 1;/TableIndex +;else Gerror(6,TableIndex); /出错信息：":="后应为变量或常量 TableIndex +;return 0;/*语句判断*/bool judge() /条件、循环、初始化语句的判断/*begin*/if(strcmp("begin",tableTableIndex.symbol)=0) /匹配begin beginCount +; if(tableTableIndex + 1.type = 7)TableIndex +;cout << "第" <<

38、; tableTableIndex.line << " 行,begin 后不能接 " <<tableTableIndex.symbol << endl;return 1;/*end*/if(strcmp("end",tableTableIndex.symbol) = 0) /匹配endbeginCount -;if(TableIndex < TableNum)if(tableTableIndex+1.type=7|tableTableIndex+ 1.type = 8)TableIndex +;Gerror(12

39、,TableIndex);return 1; /*else*/if(strcmp("else",tableTableIndex.symbol) = 0) /匹配else ifCount -; return 1;if(strcmp("prn",tableTableIndex.symbol) = 0)/匹配prn TableIndex +; if(tableTableIndex.type = 2 | tableTableIndex.type = 3) / prn 后为变量或常量TableIndex +; /语句结束，“；”if(strcmp("&q

40、uot;,tableTableIndex.symbol) = 0)return 1; else Gerror(4,TableIndex);/出错信息：此处应为"" /ifelse Gerror(2,TableIndex);/出错信息：此处应为变量 TableIndex +; /if_prn/*var变量定义*/if(strcmp("var",tableTableIndex.symbol) = 0)/ var a,b,c;TableIndex +;if(tableTableIndex.type != 2)if(strcmp(",",ta

41、bleTableIndex.symbol) = 0)Gerror(13,TableIndex);else Gerror(2,TableIndex);/出错信息：此处应为变量TableIndex +;if(strcmp(",",tableTableIndex.symbol) !=0)Gerror(3,TableIndex); /出错信息：此处应为","TableIndex +;while(1)while(strcmp(",",tableTableIndex.symbol)=0)TableIndex = TableIndex + 1;if

42、(tableTableIndex.type !=2)Gerror(2,TableIndex);/出错信息：此处应为变量TableIndex +; TableIndex +;if(strcmp("",tableTableIndex.symbol)=0)return 1;else Gerror(4,TableIndex);/出错信息：此处应为分号""return 0;/*if语句判断*/if语句else if(strcmp("if",tableTableIndex.symbol) = 0) ifCount +; /if个数加1 if(tableTableIndex +1.type = 2 | tableTableIndex + 1.type = 3)Gerror(9,TableIndex); /出错信息：此处缺少')'TableIndex +; else if(strcmp("(",tableTableIndex + 1.symbol) !=