当前位置: 首页 > >

编译方法实验指导书(8学时)

发布时间:

E->TG->FSG->iSG->i/FSG->i/iSG->i/iG->i/i-TG->i/i-FSG->i/i-iSG->i/i-iG->i/i-i

《编译原理》实验课程教学大纲
1.实验课程名称: 《编译原理实验》 2.实验课程名称(英文) : Compiling Method 3.课程代码:130016 4.实验课程性质:非独立设课 5.学 时:8 6.学 分:3 7.适用专业:计算机科学与技术 8.先修或同修课程:离散数学,数据结构,高级语言程序设计等 9.开课单位:信息与计算机工程学院 10.制定实验教学大纲的依据: 东北林业大学《编译方法》教学大纲。 11.本实验课在培养实验能力中的地位及作用 通过本实验课程培养学生以下几方面的能力: 加深学生对编译方法所涉及的概念、算法、理论的理解; 体验编译方法所涉及的抽象思维的具体实现; 激励学生在编译方法设计方面的创新精神; 培养正规系统程序设计的能力; 12.应达到的实验能力标准 本课程的实验主要培养学生的抽象思维能力和正规的程序设计能力,加强对编译方法 基本原理、基本概念的理解,使学生初步具备将算法或理论转化为正确程序的能力。

13.实验内容 (1) 实验一 词法分析 实验目的: 编制一个类 c 语言的词法分析程序。 实验要求:画好类c语言的有穷状态自动机。在进行本实验之前,应熟练课程内容,在 上机之前做好实验计划,编写好相应的代码 . 实验内容:根据有穷状态自动机编制一个类 c 语言的扫描程序。 (2)实验二 语法分析 实验目的:编写一个类 c 语言的语法分析程序 实验要求: 阅读课本有关章节, 花一周时间确定语法部分的文法, 设计出LL(1)分析表; 考虑好设计方案;设计出模块结构、测试数据,初步编制好程序。 实验内容:根据 LL(1)分析表和文法编制类 c 语言的语法分析程序

实验指导书 (1) 实验一 词法分析

实验目的:编制一个类 c 语言的词法分析程序。 一、 实验内容 实验目的:建立一个词法分析器,其功能是输入一段源程序,经过处理后,按程序顺 序并以二元式输出单词符号(即程序语言的语法单位) ,并且,如果该单词是关键字或符 号(包括界符和运算符) ,则在相应的关键字表或符号表中找出其位置;如果该单词是关 键字或常数,则直接输出。 二、 程序设计原理与方法 程序设计原理: 根据各个单词的状态转换图,可以进行合成,给出能够识别 Simple-C 语言中各类单词的 DFA,如图 2-8 所示。

字母/_ s A

字母/数字/_ 行结束/其它 字符 B 在表中,是关键字 不在表中,是标识符 D 无符号整数 出错 . e 数字 数字 实常数 其它字符 单界限符 O / 注释 行结束 出错 数字 F G 数字 实常数 出错

数字 C 数字

e

H

+/数字

I

J

SPACE

*、%、(、)、;、:、[、]、{、}、,、&、、.、 L 其它字符

/

M

*

N 其它字符

*

+ Q

其它字符

+

除号 自加运算符

其它字符 加法运算符 R 自减运算符 其它字符 =/</> T 关系双界限符 其它字符 ! U 其它字符 ' V 其它字符 " X " 行结束 其它字符 W 关系双界限符 出错 字符常数 出错 字符串 出错 其它字符 出错 E = 关系单界限符 = 减法/取负运算符 -

' 行结束

三、 示例程序
#include "stdio.h" #include "string.h" //状态名表 typedef enum { S_state, A_state, B_state, C_state, D_state, E_state, F_state, G_state, H_state, I_state, J_state, K_state, L_state, M_state, N_state, O_state, P_state, Q_state, R_state, T_state, U_state, V_state, W_state, X_state, Y_state, Z_state, END_state } STATE; //单词类别标识 typedef enum { KEY_WORD = 0, COMMENT, IDENTIFIER, UNSINED_INT, REAL_CONST, SINGLE_DELIMITER, DIVISION_SIGN, SUBTRACTIONSELF_OPERATOR, SUBTRACTION_OPERATOR,

ADDSELF_OPERATOR, ADD_OPERATOR, ERROR, CHAR_CONST,

DOUBLERELATIONAL_OPERATOR, SINGLERELATIONAL_OPERATOR, STRING_CONST , NONE

} WORDTYPE; //单词类别名称 char WordTypeExplanation[][30] = { "关键字", "标识符", "无符号整数" ,"实型常量" ,"单界限符 ", "注释", 或取负运算符", 无可处理字符" }; #define KEYWORD_COUNT 18 #define KEYWORD_MAXLENGTH 20 //关键字表 编号由位置隐含 char KeyWordTable[KEYWORD_COUNT][KEYWORD_MAXLENGTH] = { "break", "case", "char" ,"continue" ,"default", "do", "double", "else" , "float", "除号", "自增运算符" , "双界限关系运算符" , "单界限关系运算符", "出错", "字符常量", "字符串常量" , " "加法运算符", "自减运算符", "减法运算符

"for" , "return", "struct" , "switch" ,"unsigned" ,"void", "while" }; /* GetWordType判断是关键字还是自定义标识符 参数:char* str 待判断标识符 返回值:KEY_WORD 关键字 */ WORDTYPE GetWordType(char* str) { int i=0; for(i = 0;i < KEYWORD_COUNT ; i++) { if(strcmp(str, KeyWordTable[i]) ==0 ) break; /*查找关键字表,此处可用折半查找提高效率*/ } if(i < KEYWORD_COUNT) return KEY_WORD; else return IDENTIFIER; } /* GetCharactorType() 取得当前字符类别 返回值: 0:未知字符 星号 大于号 */ int GetCharactorType(char ch) { 7:百分号 18:小于号 8:斜线 19:叹号 10:左方括号 20:单引号 1:字母 9:冒号 12:逗号 2:数字 IDENTIFIER 自定义标识符

"if",

"int",

3:下划线 4:e或E(科学记数法) 5:小数点 13:空格 14:加号 15:减号

6:

11:右方括号

16:等号 17:

21:双引号 22:左括号 23:右括号 24:左大括号 25:右大括号

if(ch == 'e' || ch == 'E') /* 对字母e 和E 单独处理 因其可能用于实数的科学记数法 */ return 4; else else if( ch >= 'A' && ch<= 'Z' || ch >= 'a' && ch<= 'z') return 1; if( ch >= '0' && ch<= '9') return 2; else if(ch == '_')

return 3; else if(ch == '.') return 5; else if(ch == '*') return 6; else if(ch == '%') return 7; else if(ch == '/') return 8; else if(ch == ':') return 9; else if(ch == '[') return 10; else if(ch == ']') return 11; else if(ch == ',') return 12; else if(ch == 32 ) return 13; else if(ch == '+') return 14; else if(ch == '-') return 15; else if(ch == '=') return 16; else if(ch == '>') return 17; else if(ch == '<') return 18; else if(ch == '!') return 19; else if(ch == '\'')/* 单引号*/ return 20; else if(ch == '\"')/* 双引号*/ return 21; else if(ch == '(') return 22; else if(ch == ')') return 23; /* 空格 ASCII码值为32*/

else if(ch == '{') return 24; else if(ch == '}') return 25;

return 0; }

/*RecogniteWordByDFA() 直接转向法识别单词类别by DFA; 每次可处理一行 参数: char *straddr 待识别字符串首地址 int strlen 待识别字符串总长度 int* pcurpos 当前处理字符在字符串中的位置游标变量地址 返回值:WORDTYPE 规定的类别码 */ WORDTYPE RecogniteWordByDFA(char *straddr,int strlength, int* pcurpos ) { STATE state = S_state; /* 初始化当前状态值为 S_state */ WORDTYPE wordtype = ERROR; /* 单词类别判定结果码,初始为ERROR */ int cur_pos = *pcurpos; int ch_type = 0; char tmpstr[256] = {0}; while(state != END_state) { switch(state) { case S_state: if(cur_pos >= strlength ) { state = Z_state; break; } ch_type = GetCharactorType(straddr[cur_pos]); /*取得当前字符类别*/

switch(ch_type) { case 1: /*字母*/ case 3: /*下划线*/ case 4: /*字母e或E*/ state = A_state; tmpstr[cur_pos- *pcurpos] = straddr[cur_pos]; /*记录当前字符,用以在B状态 判断是标识符还是关键字*/ break; case 2: /*数字*/ state = C_state; break; case 6:/*星号*/ case 7:/*百分号*/ case 9:/*分号*/ case 10:/*左方括号*/ case 11:/*右方括号*/ case 12:/*逗号*/ case 13:/*空格*/ case 22:/*左括号*/ case 23:/*右括号*/ case 24: /*左大括号*/ case 25: /*右大括号*/ state = L_state; break; case 8: /*斜线*/ state = M_state; break; case 14: /*加号*/ state = Q_state; break; case 15: /*减号*/ state = R_state; break;

case 16: /*等号*/ case 17: /*大于号*/ case 18: /*小于号*/ state = T_state; break; case 19: /*叹号*/ state = U_state; break; case 20: /*单引号*/ state = V_state; break; case 21: /*双引号*/ state = X_state; break; default: /* 其它字符 */ state = Z_state; break; } cur_pos ++; break; case A_state: if(cur_pos >= strlength ) { state = B_state; break; } ch_type = GetCharactorType(straddr[cur_pos]); if(ch_type == 1 || ch_type == 2 || ch_type == 3 || ch_type == 4) { state = A_state; tmpstr[cur_pos- *pcurpos] = straddr[cur_pos]; /*记录当前字符,用以在B状态判 断是标识符还是关键字*/ cur_pos ++;

} else { state = B_state; } break; case B_state: wordtype = GetWordType(tmpstr); /*判断是关键字还是标识符*/ state = END_state; break; /*A_state -- B_state 处理关键字和标识符 */ case C_state: if(cur_pos >= strlength ) { state = D_state; break; } ch_type = GetCharactorType(straddr[cur_pos]); if(ch_type == 2) /*数字*/ { cur_pos ++; state = C_state; } else if(ch_type == 4) /* e或E */ { cur_pos ++; state = H_state; } else { state = D_state; break; } break;

case D_state: if(cur_pos >= strlength ) /*所有字符处理完毕*/ { wordtype = UNSINED_INT; state = END_state; break; } ch_type = GetCharactorType(straddr[cur_pos]);/*此句可以省略*/ if(ch_type == 5)/*小数点*/ { cur_pos ++; state = F_state; } else /*其它字符*/ { wordtype = UNSINED_INT; state = END_state; } break; case F_state: if(cur_pos >= strlength ) /*所有字符处理完毕*/ { wordtype = ERROR; state = END_state; break; } ch_type = GetCharactorType(straddr[cur_pos]); if(ch_type == 2)/*数字*/ { cur_pos ++; state = G_state; } else /*其它字符*/ { wordtype = ERROR;

state = END_state; } break; case G_state: if(cur_pos >= strlength ) /*所有字符处理完毕*/ { wordtype = REAL_CONST ; state = END_state; break; } ch_type = GetCharactorType(straddr[cur_pos]); if(ch_type == 2 ) /*数字*/ { cur_pos ++; state = G_state; } else if(ch_type == 4) /*E 或 e*/ { cur_pos ++; state = H_state; } else { wordtype = REAL_CONST ; state = END_state; } break; case H_state: /*处理科学记数法表示的实数中 e或E后面的部分 */ if(cur_pos >= strlength ) /*所有字符处理完毕, e后面没有字符*/ { wordtype = ERROR; state = END_state; break; }

ch_type = GetCharactorType(straddr[cur_pos]); if(ch_type == 2 ) /*数字*/ { cur_pos ++; state = J_state; } else if(ch_type == 14 || ch_type == 15 ) /* + 或 - */ { cur_pos ++; state = I_state; } else /* 3.4e 或 3e 后面不是数字也不是正负号 */ { wordtype = ERROR; state = END_state; } break; case I_state: if(cur_pos >= strlength ) /*所有字符处理完毕, e+-后面没有字符*/ { wordtype = ERROR; state = END_state; break; } ch_type = GetCharactorType(straddr[cur_pos]); if(ch_type == 2 ) /*数字*/ { cur_pos ++; state = J_state; } else /* e+-后面不是数字*/ { wordtype = ERROR; state = END_state; }

break; case J_state: if(cur_pos >= strlength ) /*所有字符处理完毕,是实常数*/ { wordtype = REAL_CONST; state = END_state; break; } ch_type = GetCharactorType(straddr[cur_pos]); if(ch_type == 2 ) /*数字*/ { cur_pos ++; state = J_state; } else /* 是实常数*/ { wordtype = REAL_CONST; state = END_state; } break; /*C_state - J_state 数字(包括 正整数 实数 科学记数的实数)*/ case L_state: wordtype = SINGLE_DELIMITER; state = END_state; break; case M_state: if(cur_pos >= strlength ) /*所有字符处理完毕,是除号*/ { wordtype = DIVISION_SIGN; state = END_state; break; }

ch_type = GetCharactorType(straddr[cur_pos]); if(ch_type == 6 ) /*星号*/ { cur_pos ++; state = N_state; } else /*是除号 */ { wordtype = DIVISION_SIGN; state = END_state; } break; case N_state: if(cur_pos >= strlength ) /*所有字符处理完毕, ,注释不完整*/ { wordtype = ERROR; state = END_state; break; } ch_type = GetCharactorType(straddr[cur_pos]); if(ch_type != 6 ) /*不是星号*/ { cur_pos ++; state = N_state; } else /*是星号 */ { cur_pos ++; state =O_state; } break; case O_state: if(cur_pos >= strlength ) /*所有字符处理完毕,注释不完整*/ {

wordtype = ERROR; state = END_state; break; } ch_type = GetCharactorType(straddr[cur_pos]); if(ch_type != 8 ) /*不是斜线*/ { cur_pos ++; state = N_state; } else /*是斜线 */ { cur_pos ++; wordtype = COMMENT; state = END_state; } break; /* 注释和除号处理完毕*/ case Q_state: if(cur_pos >= strlength ) /*所有字符处理完毕,是加号 */ { wordtype = ADD_OPERATOR; state = END_state; break; } ch_type = GetCharactorType(straddr[cur_pos]); if(ch_type == 14 ) /* 自增++ */ { cur_pos ++; wordtype = ADDSELF_OPERATOR; state = END_state; } else /*是加号 */

{ wordtype = ADD_OPERATOR; state = END_state; } break; /*加号和自增处理完毕*/ case R_state: if(cur_pos >= strlength ) /*所有字符处理完毕,是减号 */ { wordtype = SUBTRACTION_OPERATOR; state = END_state; break; } ch_type = GetCharactorType(straddr[cur_pos]); if(ch_type == 15 ) /* 自减-- */ { cur_pos ++; wordtype = SUBTRACTIONSELF_OPERATOR; state = END_state; } else /*是减号 */ { wordtype = SUBTRACTION_OPERATOR; state = END_state; } break; /*减号和自减处理完毕*/ case T_state: if(cur_pos >= strlength ) /*所有字符处理完毕,是 关系单界运算符 { wordtype = SINGLERELATIONAL_OPERATOR; */

state = END_state; break; } ch_type = GetCharactorType(straddr[cur_pos]); if(ch_type == 16 ) /* 关系双界运算符 == >= { cur_pos ++; wordtype = DOUBLERELATIONAL_OPERATOR ; state = END_state; } else /*是 关系单界运算符 */ { wordtype = SINGLERELATIONAL_OPERATOR; state = END_state; } break; case U_state: if(cur_pos >= strlength ) /*所有字符处理完毕,出错 { wordtype = ERROR; state = END_state; break; } ch_type = GetCharactorType(straddr[cur_pos]); if(ch_type == 16 ) /* 关系双界运算符 != */ { cur_pos ++; wordtype = DOUBLERELATIONAL_OPERATOR ; state = END_state; } else /* 出错 */ { */ <= */

wordtype = ERROR; state = END_state; } break; /* 关系 单\双 界运算符处理完毕*/ case V_state: if(cur_pos >= strlength ) /*所有字符处理完毕,字符常量缺少右边的单引号 { wordtype = ERROR; state = END_state; break; } ch_type = GetCharactorType(straddr[cur_pos]); if(ch_type == 20 ) /* 两个单引号中间没有字符,出错 */ { cur_pos ++; wordtype = ERROR; state = END_state; } else /* 其它字符 */ { cur_pos ++; state = W_state; } break; case W_state: if(cur_pos >= strlength ) /*所有字符处理完毕,字符常量缺少右边的单引号 { wordtype = ERROR; state = END_state; break; */ */

} ch_type = GetCharactorType(straddr[cur_pos]); if(ch_type == 20 ) /* 字符型常量 { cur_pos ++; wordtype = CHAR_CONST; state = END_state; } else /* 出错,字符型常量中只能有一个字符 */ { wordtype = ERROR; state = END_state; } break; /* 字符型常量 处理完毕*/ case X_state: if(cur_pos >= strlength ) /*所有字符处理完毕,字符串常量缺少右边的双引号 { wordtype = ERROR; state = END_state; break; } ch_type = GetCharactorType(straddr[cur_pos]); if(ch_type == 21 ) /* 字符串型常量 { cur_pos ++; wordtype = STRING_CONST; state = END_state; } else /* 其它字符 */ { */ */ */

cur_pos ++; state = X_state; } break; /* 字符串型常量 处理完毕*/ case Z_state: default: wordtype = ERROR; state = END_state; break; } } *pcurpos = cur_pos ; /* 修改当前行待处理位置游标变量的值 */ return wordtype; } int main() { char teststr[80] = {0}; char outstr[256] = {0}; int i=0; int curpos = 0 , start = 0; WORDTYPE wordtype; int strlength = 0; puts("Input a program line to test please: "); gets(teststr); strlength = (int)strlen(teststr); while(curpos < strlength) { start = curpos; memset(outstr, 0 , sizeof(char)*256);

wordtype = RecogniteWordByDFA(teststr ,strlength for(i = start;i<curpos; i++) outstr[i-start] = teststr[i];

, &curpos );

printf("(%s: %s)\n", outstr , WordTypeExplanation[wordtype]); } getchar(); return 0; }

四、总结
在上述程序中,主要是实现了把源文件的关键字、标识符、常数、符号分离开的功能。 并附带了简单的错误处理过程。

(2)

实验二 语法分析

1、实验目的:对 Simple-C 语言进行 LL(1)分析的实现过程及方法。 2、实验内容:编能够根据文法及LL(1)分析表生成语法分析程序。 1)文法:Program: :=ProgramHead FunctionDeclare VarDifine FunctionGroup (2) | FunctionDeclare VarDifine FunctionGroup (3) | ProgramHead VarDifine FunctionGroup (4) | ProgramHead FunctionDeclare FunctionGroup (5) | ProgramHead FunctionGroup (6) | FunctionDeclare FunctionGroup (7) | VarDifine FunctionGroup (8) | FunctionGroup 程序头: (9)ProgramHead : := # include"LibFileName.h" ProgramHead (10)LibFileName : :=stdio (11) |math (12) |string (13) |ctype 函数声明与全局变量定义: (14)FunctionDeclare : := BaseType FunctionName(ForParList) FunctionDeclareMore (15) | struct StrTypeName

FunctionName(ForParList) FunctionDeclareMore (16) | void StrTypeName FunctionName(ForParList) FunctionDeclareMore (17)FunctionDeclareMore : :=; FunctionDeclare (18) |ε (19)VarDifine : := ExpSentence (20)FunctionName : := Id 函数组: (21)FunctionGroup : := UnMainFunction MainFunction UnMainFunction (22)UnMainFunction : :=FunctionHead FunctionBody (23) |ε (24)FunctionHead : := BaseType FunctionName(ForParList) (25) | void FunctionName(ForParList) (26) | struct StrTypeName FunctionName(ForParList) (27)FunctionBody : :={ExpSentence ExecSentence} (28)MainFunction : := MainFunctionHead FunctionBody (29)MainFunctionHead : := void main() 类型: (30)BaseType : :=int (31) |char (32) |float (33) |double (34)OneArrayType ::= BaseType ArrayName[Dimlong ]

(35)TwoArrayType : := BaseType ArrayName[Dimlong][ Dimlong] (36)ArrayName : :=Id (37)Dimlong : :=Intc (38)StructureType : :=struct StrTypeName StructureBody (39)StrTypeName : := Id (40)StructureBody : :={ MembersList } (41)MembersList : :=BaseType IdList; MembersListMore (42) |OneArrayType; MembersListMore (43) |TwoArrayType; MembersListMore (44) | struct StrTypeName StrVarName; MembersListMore (45)StrVarName : := IdList (46)MembersListMore : := MembersList (47) |ε

(48)IdList : :=Id IdMore (49)IdMore : :=,IdList (50) |ε 声明语句: (51)DecSentence : := BaseType IdList; DecSentence (52) | BaseType IdList=Intc; DecSentence (53) | BaseType IdList='Charc' ; DecSentence (54) | BaseType IdList=Floatc; DecSentence (55) | OneArrayType; DecSentence (56) | TwoArrayType; DecSentence (57) | OneArrayType= {ArrayIntc }; DecSentence (58) | OneArrayType= {ArrayCharc }; DecSentence (59) | OneArrayType= {ArrayFloatc }; DecSentence (60) | OneArrayType= "String"; DecSentence (61) | OneArrayType= {"String" }; DecSentence (62) | TwoArrayType= { ArrayIntc }; DecSentence (63) | TwoArrayType= { ArrayCharc }; DecSentence (64) | TwoArrayType= {ArrayFloatc }; DecSentence (65) | TwoArrayType= {ArrayString };DecSentence (66) | StructureType StrVarName ;DecSentence (67)ArrayIntc : :=Intc IntcMore (68)IntcMore : :=, ArrayIntc (69) |ε (70)ArrayCharc : :='Charc' CharcMore (71)CharcMore : :=, ArrayCharc (72) |ε (73)ArrayFloatc : :=Floatc FloatcMore (74)FloatcMore : :=, ArrayFloatc (75) |ε (76)ArrayString : :="String" StringMore (77)StringMore : :=, ArrayString (78) |ε 可执行语句: (79)ExecSentence : :=Sen SenMore (80)SenMore : := ExecSentence (81) |ε (82)Sen : :=ConditionalSen (83) |LoopSen (84) |InputSen

(85) |OutputSen (86) |ReturnSen (87) |FunCallSen (88) |AssignmentSen (89) | Expression; (90) |continue; (91) | break; (92) |ε 赋值语句: (93)AssignmentSen : :=Id=Expression; (94) | ArrayName[Index ] =Expression; (95) | ArrayName[Index] [Index ] = Expression; (96) | StrVarName.StrVar= Expression; (97)Index : :=Intc 函数调用语句: (98)FunCallSen : := FunctionName(ActParList); 注:Simple-C 语言的输入输出是通过调用库函数来实现,在后面的文法中单独说明。 实参表: (99)ActParList : := Expression ActParListMore (100) |ε (101)ActParListMore : :=, ActParList (102) |ε 形参表: (103)ForParList : := BaseType Id FormListMore (104) |ε (105)FormListMore : :=, ForParList (106) |ε 条件语句: (107)ConditionalSen : :=if (Expression ) {ExecSentence} else{ExecSentence} (108) |if (Expression ) {ExecSentence} (109) |if (Expression ) Sen; else {ExecSentence} (110) |if (Expression ) Sen;else Sen; (111) |if (Expression ) {ExecSentence}else Sen; (112) |if (Expression ) Sen; (113) |switch(Expression){SwitchBody} (114)SwitchBody : := case ConsExpression: CaseBody SwiBodyMore (115)ConsExpression : :=ConsCountExpression ConsConExpressionMore

(116)ConsConExpressionMore: := CmpOp ConsCountExpression ConsConExpressionMore (117) |ε (118)ConsCountExpression : := ConsTerm ConsTermMore (119)ConsTermMore : := AddOp ConsTerm ConsTermMore (120) |ε (121)ConsTerm : :=ConsFactor ConsFactorMore (122)ConsFactorMore : := MultOp ConsFactor ConsFactorMore (123) |ε (124)ConsFactor : := SingleOp ConsLost (125) | ConsLost (126)ConsLost : := Intc (127) | 'Charc' (128) | (ConsExpression) (129)SwiBodyMore : := SwitchBody (130) | default: ExecSentence (131) |ε (132)CaseBody : := ExecSentence (133) | ExecSentence break; 循环语句: (134)LoopSen : :=while (Expression ) Sen; (135) | while (Expression ) {ExecSentence} (136) |do{ExecSentence}while (Expression ) ; (137) | for (ForExpression ) {ExecSentence} (138) | for (ForExpression ) Sen; (139)ForExpression: :=Expression; Expression; Expression 输入语句: (140)InputSen : :=scanf("String",AddrList); (141) |getchar(); (142) | gets(ArrayName); (143)AddrList : :=&ID AddrListMore (144) | ArrayName AddrListMore (145)AddrListMore : :=, AddrList (146) |ε 输出语句: (147)OutputSen : :=printf("String ",OutList); (148) |putchar('Charc'); (149) |putchar(ID); (150) | puts(ArrayName);

(151) | puts("String"); (152)OutList : := Expression OutListMore (153)OutListMore : :=, OutList (154) |ε 返回语句: (155)ReturnSen : :=return(Expression); (156) | return Expression; (157) | return; (158)Expression : :=ConExpression 条件表达式: (159)ConExpression : := CountExpression ConExpressionMore (160) ConExpressionMore : : = CmpOp CountExpression ConExpressionMore (161) |ε 算术表达式: (162)CountExpression : := Term RemainTerm (163)RemainTerm : := AddOp Term RemainTerm (164) |ε 项: (165)Term : :=Factor RemainFactor (166)RemainFactor : := MultOp Factor RemainFactor (167) |ε (168)Factor : := SingleOp Lost (169) | Lost 因子: (170)Lost : :=( Expression) (171) | Intc (172) | Variable (173) | Floatc (174) | 'Charc' (175)Variable : :=Id (176) | ArrayName[Index] (177) | ArrayName[Index ] [Index ] (178) | StrVarName.StrVar (179) |FunctionName(ActParList) (180)StrVar : :=Id StrVarMore (181)StrVarMore : :=.StrVar (182) |ε (183)CmpOp : :=< (184) |< =

(185) (186) (187) (188) (189)AddOp (190) (191)MultOp (192) (193) (194)SingleOp (195) (196) 2)LL(1)分析表

|> |> = |= = |!= : := + |: := * |/ |% : := | ++ |-表 3-5 LL(1)分析表

break

case

char (1) (3) (4)

continue

default

do

double (1) (3) (4)

else

float (1) (3) (4)

for

(8) (11)

(10) (11)

(9) (11)

(15) (25)

(15) (17) (26)

(15) (24)

(15) (19)

(15) (17) (26)

(15) (17) (26)

(15) (19)

(38)

续表 1 int (1) 1 (3) 2 (4) 3 4 (7) 5 (11) 6 7 (15) 8 (17) 9 (26) 10 (27) 11 12 (30) 13 (31) 14 (32) 15 16 (37) 17 18 (32) (32) (20) (18) (19) (21)/ (22)/ (23) (23) (23) (15) (15) (15) (15) (15) (15) (5) (3) return switch void (1) while ID Intc Floatc Charc +

(39) 19 20 (42) 21 (43) 22 (45) 23 (47) 24 (49) 25 (50) 26 27 (56) 28 (57) 29 (60) 30 (61) 31 (62) 32 (63) 33 34 (66) 35 (67) 36 (69) 37 (71) 38 (73) 39 (73) (73) (69) (69) (66) (66) (63) (63) (62) (62) (60) (60) (56) (56) (56) (56) (56) (56)

(76) 40 (79) 41 42

(75)

(77)

(86) 43 44 45 (94) 46 47 48 49 (102) 50 (94) (94)

续表 2 * / % = > < == != >= <=

1 2 3 4 5 6 7 8

9 10 11 12 13 14 15 16 17 18 19 (40) 20 21 (44) 22 23 (46) 24 25 26 27 28 29 (46) (46) (47) (47) (47) (47) (47) (47) (44) (44) (44) (44) (44) (40) (40) (40) (40) (40)

30 31 32 33 (64) 34 35 (68) 36 37 (70) 38 39 40 41 (82) 42 43 (88) 44 45 46 47 48 49 50 (89) (90) (80) (84) (85) (83) (81) (70) (70) (71) (71) (71) (71) (71) (71) (68) (68) (68) (68) (68) (64) (64) (64) (64) (64)

续表 3 -( ) ; , ' { } : # (2) 1 2 3 (6) 4 5 (12) 6 (14) 7 (15) 8 (23) 9 10 11 (29) 12 13 14 (32) 15 (35) 16 17 18 (39) 19 20 (39) (39) (41) (34) (32) (33) (32) (28) (23) (23) (15) (15) (16) (13)



(42) 21

(42)

(42) (44)

22 (45) 23 (47) 24 (48) 25 (52) 26 (55) 27 (56) 28 29 (60) 30 31 (62) 32 (63) 33 (65) 34 (66) 35 (68) 36 (69) 37 (71) 38 (72) 39 (74) 40 41 (78) (73) (73) (71) (71) (69) (69) (68) (68) (66) (66) (65) (65) (63) (63) (62) (62) (60) (60) (56) (56) (51) (49) (49) (45) (45)

42 43 44 (93) 45 (94) 46 47 48 (101) 49 50 3、示例程序
#include "stdio.h" #include "stdlib.h" #include "string.h" #define MAX_LINE_LENGTH 1024 /*****非终结符表 (1)FunctionGroup (2) Function (3) FunctionHead (4)FunctionBody (5)BaseType (6)ForParList (7)FormListMore (8)Sentence (9)Sen (10)DecSentence (11)IdList (12)IdMore (13)AssignmentSen (14)FunCallSen (15)ActParList 0x0100 0x0200 0x0300 0x0400 0x0500 0x0600 0x0700 0x0800 0x0900 0x0a00 0x0b00 0x0c00 0x0d00 0x0e00 0x0f00

(94)

(94) (96)/ (97) (99) (96)/ (97) (98) (100)

(94)

(9

(16)ActParListMore (17)ConditionalSen (18)SwitchBody (19)ConsExpression

0x1000 0x1100 0x1200 0x1300 0x1500

(20)ConsConExpressionMore 0x1400 (21)ConsCountExpression (22)ConsTermMore (23)ConsTerm (24)ConsFactorMore (25)ConsFactor (26)ConsLost (27)SwiBodyMore (28)CaseBody (29)LoopSen (30)ForExpression (31)ReturnSen (32)Expression (33)ConExpression (35)CountExpression (36)RemainTerm (37)Term (38)RemainFactor (39)Factor (40)Lost (41)Variable (42)CmpOp (43)AddOp (44)MultOp (45)SingleOp (46)FunCallSenMore (47)ActParListen (49)ActParLisScanf (50)FunctionName */ /*******种别码表(终结符列表) break 1 0x0001 0x1600 0x1700 0x1800 0x1900 0x1a00 0x1b00 0x1c00 0x1d00 0x1e00 0x1f00 0x2000 0x2100 0x2300 0x2400 0x2500 0x2600 0x2700 0x2800 0x2900 0x2a00 0x2b00 0x2c00 0x2d00 0x2e00 0x2f00 0x3100 0x3200

(34)ConExpressionMore 0x2200

(48)ActParLisPrintf 0x3000

case char default do double else float for if int return struct switch unsigned void while ID Intc Floatc Charc Stringc + * / % = > < == != >= <= ++ -( ) [

2 3

0x0002 0x0003 0x0004 5 6 7 0x0005 0x0006 0x0007 0x0009 0x000a 0x000b 0x000c 0x000d 0x000e 0x000f 0x0010 0x0012 0x0014 0x0015 0x0017 0x0018 0x0019 0x001a 0x001b 0x001c 0x001d 0x001e 0x001f 0x0020 0x0021 0x0022 0x0023 0x0024 0x0025 0x0026 0x0027 0x0028

continue 4

8

0x0008 9 10 11 12 13 14 15 16

17 19

0x0011 18 20 21 0x0013

22

0x0016 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

] ; , . & ' " _ { } : # */

41 42 43 44 45 46 47 48 49 50 51 52

0x0029 0x002a 0x002b 0x002c 0x002d 0x002e 0x002f 0x0030 0x0031 0x0032 0x0033 0x0034 ****************

/******************文法列表102条文法,每条文法长度 < 32 文法表示:

非终结符形为0x0100--0x2C(十进制 1-45) 终结符形为0x0001--0x0033(十进制 1-51) ε 为0x0034 (十进制 52 ) ************************************************************************/ unsigned short int grammar[103][32] = { {0x0100}, /*(0) FunctionGroup {0x0200, 0x0100}, /*(1) FunctionGroup ::= {0xFFFF}, /*(2) FunctionGroup ::= {0x0300, 0x0400}, /*(3) Function /*(4) FunctionHead /*(5) FunctionHead /*(6)FunctionBody {0x000c}, /*(7) BaseType {0x0003}, /*(8) BaseType ::= char */ ::= int */ ::= ::= ::= ::= FunctionHead FunctionBody BaseType ID(ForParList) void ID(ForParList) {Sentence } */ */ */ */ {0x0500, 0x0013, 0x0026, 0x0600, 0x0027}, {0x0011, 0x0013, 0x0026, 0x0600, 0x0027}, {0x0031, 0x0800, 0x0032}, ε */ Function FunctionGroup */ */

{0x0009}, /*(9) BaseType {0x0007}, /*(10)BaseType /*(11)ForParList {0xFFFF}, /*(12)ForParList {0x002b, 0x0600}, /*(13)FormListMore {0xFFFF}, /*(14)FormListMore {0x0900, 0x0800}, /*(15)Sentence {0xFFFF}, /*(16)Sentence {0x0a00}, /*(17)Sen {0x1100}, /*(18)Sen {0x1d00}, /*(19)Sen {0x1f00}, /*(20)Sen {0x0e00}, /*(21)Sen {0x0d00}, /*(22)Sen {0x2000}, /*(23)Sen {0x0004, 0x002a}, /*(24)Sen {0x0001, 0x002a}, /*(25)Sen /*(26)DecSentence {0x0013, 0x0c00}, /*(27)IdList {0x002b, 0x0b00}, ::= Id IdMore */ ::= ::= break; BaseType IdList; DecSentence */ */ {0x0500, 0x0b00, 0x002a}, ::= continue; */ ::= Expression; */ ::= AssignmentSen */ ::= FunCallSen */ ::= ReturnSen */ ::= LoopSen */ ::= ConditionalSen */ ::= DecSentence */ ::= ε */ ::= Sen Sentence */ ::= ε */ ::=, ForParList */ ::= ε */ ::= ::= double BaseType ID FormListMore */ */ {0x0500, 0x0013, 0x0700}, ::= float */

/*(28)IdMore {0xFFFF}, /*(29)IdMore

::=

,IdList

*/ */ */ */ */ */ */ */ */ */

::= ε Id=Expression; FunctionName(FunCallSenMore Expression ActParListMore ε , ActParList ε if (Expression ) {Sentence} switch(Expression){SwitchBody}

{0x0013, 0x001d, 0x2000, 0x002a}, /*(30)AssignmentSen ::= {0x3200, 0x0026, 0x2e00 }, /*(31)FunCallSen {0x2000, 0x1000}, /*(32)ActParList {0xFFFF}, /*(33)ActParList {0x002b, 0x0f00}, /*(34)ActParListMore ::= {0xFFFF}, /*(35)ActParListMore ::= /*(36)ConditionalSen ::= /*(37)ConditionalSen ::= /*(38)SwitchBody {0x1500, 0x1400}, /*(39)ConsExpression ::= {0x2a00, 0x1500, 0x1400}, /*(40)ConsConExpressionMore::= CmpOp ConsCountExpression ConsConExpressionMore*/ {0xFFFF}, /*(41)ConsConExpressionMore::= ε {0x1700, 0x1600}, /*(42)ConsCountExpression {0x2b00, 0x1700, 0x1600}, /*(43)ConsTermMore {0xFFFF}, /*(44)ConsTermMore {0x1900, 0x1800}, /*(45)ConsTerm ::= ConsFactor ConsFactorMore MultOp ConsFactor ConsFactorMore */ */ */ {0x2c00, 0x1900, 0x1800}, /*(46)ConsFactorMore ::= {0xFFFF}, /*(47)ConsFactorMore ::= ε ::= ε */ ::= AddOp ConsTerm ConsTermMore */ ::= ConsTerm ConsTermMore */ */ ConsCountExpression ConsConExpressionMore */ ::= {0x000b, 0x0026, 0x2000, 0x0027, 0x0031, 0x0800, 0x0032}, {0x000f, 0x0026, 0x2000, 0x0027, 0x0031, 0x1200, 0x0032}, {0x0002, 0x1300, 0x0033, 0x1c00, 0x1b00}, case ConsExpression: CaseBody SwiBodyMore */ ::= ::= ::=

{0x2d00, 0x1a00}, /*(48)ConsFactor {0x1a00}, /*(49)ConsFactor {0x0014}, /*(50)ConsLost /*(51)ConsLost /*(52)ConsLost {0x1200}, /*(53)SwiBodyMore /*(54)SwiBodyMore {0xFFFF}, /*(55)SwiBodyMore {0x0800}, /*(56)CaseBody /*(57)LoopSen /*(58)LoopSen /*(59)LoopSen ::= ::= ::= ::= Sentence while (Expression ) {Sentence} */ */ */ */ */ */ */ */ {0x0012, 0x0026, 0x2000, 0x0027, 0x0031, 0x0800, 0x0032}, {0x0006, 0x0031, 0x0800, 0x0032, 0x0012, 0x0026, 0x2000, 0x0027, 0x002a}, do{Sentence}while (Expression ); for (ForExpression ) {Sentence} {0x000a, 0x0026, 0x2000, 0x2700, 0x0031, 0x0800, 0x0032}, {0x2000, 0x002a, 0x2000, 0x002a, 0x2000}, /*(60)ForExpression ::=Expression; Expression; Expression {0x000d, 0x0026, 0x2000, 0x0027, 0x002a}, /*(61)ReturnSen {0x2100}, /*(62)Expression {0x2300, 0x2200}, /*(63)ConExpression ::= CountExpression ConExpressionMore {0x2a00, 0x2300, 0x2200}, /*(64)ConExpressionMore {0xFFFF}, /*(65)ConExpressionMore {0x2500, 0x2400}, /*(66)CountExpression {0x2b00, 0x2500, 0x2400}, ::= Term RemainTerm */ ::= ε */ ::= CmpOp CountExpression ConExpressionMore */ ::=ConExpression ::=return(Expression); ::= ε */ ::= ::= SwitchBody default: Sentence */ */ {0x0005, 0x0033, 0x0800}, ::= ::= Intc 'Charc' */ */ */ {0x002e, 0x0016, 0x002e}, {0x0026, 0x1300, 0x0027}, ::= (ConsExpression) ::= ConsLost */ ::= SingleOp ConsLost */

/*(67)RemainTerm {0xFFFF}, /*(68)RemainTerm {0x2700, 0x2600}, /*(69)Term /*(70)RemainFactor {0xFFFF}, /*(71)RemainFactor {0x2d00, 0x2800}, /*(72)Factor {0x2800}, /*(73)Factor /*(74)Lost {0x0014}, /*(75)Lost {0x2900}, /*(76)Lost {0x0015}, /*(77)Lost /*(78)Lost {0x0013}, /*(79)Variable {0x001f}, /*(80)CmpOp {0x0023}, /*(81)CmpOp {0x001e}, /*(82)CmpOp {0x0022}, /*(83)CmpOp {0x0020}, /*(84)CmpOp {0x0021}, /*(85)CmpOp {0x0018}, /*(86)AddOp

::= AddOp Term RemainTerm ::= ε ::= Factor RemainFactor ::= MultOp Factor RemainFactor ::= ε ::= SingleOp Lost ::= Lost ::= ( Expression) ::= Intc ::= Variable ::= Floatc ::= 'Charc' ::= Id ::= < ::= <= ::= > ::= >= ::= == ::= != ::= +

*/ */ */ */ */ */ */ */ */ */ */ */ */ */ */ */ */ */ */ */

{0x2c00, 0x2700, 0x2600},

{0x0026, 0x2000, 0x0027},

{0x002e, 0x0016, 0x002e},

{0x0019}, /*(87)AddOp {0x001a}, /*(88)MultOp {0x001b}, /*(89)MultOp {0x001c}, /*(90)MultOp {0x0019}, /*(91)SingleOp {0x0024}, /*(92)SingleOp {0x0025}, /*(93)SingleOp ::= -*/ */ */ */ */ */ */ */ */ */ {0x0f00, 0x0027,0x002a}, /*(94)FunCallSenMore ::= ActParList); {0x002f, 0x0017 , 0x002f, 0x2f00, 0x0027, 0x002a }, /*(95)FunCallSenMore ::= "String" ActParListen); {0x3000}, /*(96)ActParListen {0x3100}, /*(97)ActParListen ::= ActParLisScanf {0x002b, 0x2000, 0x3000}, /*(98)ActParLisPrintf::=, Expression ActParLisPrintf {0xFFFF}, /*(99)ActParLisPrintf::=ε {0x002b,0x002d, 0x2900, 0x3100 }, /*(100)ActParLisScanf::=, & Variable ActParLisScanf {0xFFFF}, /*(101)ActParLisScanf::= {0x0013}, /*(102)FunctionName }; ::= Id ε ::= ActParLisPrintf ::= ++ */ ::= */ ::= % */ ::= / */ ::= * */ ::= */

/************************************************ 函数名:SearchLL1Table 功能: 查找LL1分析表 参数: int uterm 非终结符编号

int term 返回值:>0 成功 0 查找失败 <0 错误码

终结符编号

*************************************************/ int SearchLL1Table(int uterm, int term) { switch(uterm) { case 1: switch(term) { case 3: case 7: case 9: case 12: case 17: return 1; case 52: return 2; default: return -uterm; } break; case 2: switch(term) { case 3: case 7: case 9: case 12: case 17: return 3; default: return -uterm; } break;

case 3: switch(term) { case 3: case 7: case 9: case 12: return 4; case 17: return 5; default: return -uterm; } break; case 4: switch(term) { case 49: return 6; default: return -uterm; } break; case 5: switch(term) { case 3: return 8; case 7: return 10; case 9: return 9; case 12: return 7; default: return -uterm;

} break; case 6: switch(term) { case 3: case 7: case 9: case 12: return 11; case 39: return 12; default: return -uterm; } break; case 7: switch(term) { case 39: return 14; case 43: return 13; default: return -uterm; } break; case 8: switch(term) { case 1: case 3:

case 4: case 6: case 7: case 9: case 10: case 11: case 12: case 13: case 15: case 18: case 19: case 20: case 21: case 25: case 36: case 37: case 38: case 46: return 15; case 50: return 16; default: return -uterm; } break; case 9: switch(term) { case 1: return 25; case 3: case 7: case 9: case 12: return 17; case 4: return 24; case 6:

case 10: case 18: return 19; case 11: case 15: return 18; case 13: return 20; case 19: return 21; /*返回21时 应判断是否 22 23 的情况*/ case 20: case 21: case 25: case 36: case 37: case 38: case 46: return 23; default: return -uterm; } break; case 10: switch(term) { case 3: case 7: case 9: case 12: return 26; default: return -uterm; } break; case 11:

switch(term) { case 19: return 27; default: return -uterm; } break; case 12: switch(term) { case 42: return 29; case 43: return 28; default: return -uterm; } break; case 13: switch(term) { case 19: return 30; default: return -uterm; } break; case 14: switch(term) { case 19: return 31; default: return -uterm;

} break; case 15: switch(term) { case 19: case 20: case 21: case 25: case 36: case 37: case 38: case 46: return 32; case 39: return 33; default: return -uterm; } break; case 16: switch(term) { case 39: return 35; case 43: return 34; default: return -uterm; } break; case 17: switch(term) { case 11: return 36;

case 15: return 37; default: return -uterm; } break; case 18: switch(term) { case 2: return 38; default: return -uterm; } break; case 19: switch(term) { case 20: case 25: case 36: case 37: case 38: case 46: return 39; case 51: return 41; default: return -uterm; } break; case 20: switch(term) { case 30:

case 31: case 32: case 33: case 34: case 35: return 40; default: return -uterm; } break; case 21: switch(term) { case 20: case 25: case 36: case 37: case 38: case 46: return 42; default: return -uterm; } break; case 22: switch(term) { case 24: case 25: return 43; case 30: case 31: case 32: case 33: case 34: case 35: case 51:

return 44; default: return -uterm; } break; case 23: switch(term) { case 20: case 25: case 36: case 37: case 38: case 46: return 45; default: return -uterm; } break; case 24: switch(term) { case 24: case 25: case 30: case 31: case 32: case 33: case 34: case 35: case 51: return 47; case 26: case 27: case 28: return 46; default:

return -uterm; } break; case 25: switch(term) { case 20: case 38: case 46: return 49; case 25: case 36: case 37: return 48; default: return -uterm; } break; case 26: switch(term) { case 20: return 50; case 38: return 52; case 46: return 51; default: return -uterm; } break; case 27: switch(term) { case 2: return 53;

case 5: return 54; case 50: return 55; default: return -uterm; } break; case 28: switch(term) { case 1: case 3: case 4: case 6: case 7: case 9: case 10: case 11: case 12: case 13: case 15: case 18: case 19: case 20: case 21: case 25: case 36: case 37: case 38: case 46: return 56; default: return -uterm; } break; case 29:

switch(term) { case 6: return 58; case 10: return 59; case 18: return 57; default: return -uterm; } break; case 30: switch(term) { case 19: case 20: case 21: case 25: case 36: case 37: case 38: case 46: return 60; default: return -uterm; } break; case 31: switch(term) { case 13: return 61; default: return -uterm; }

break; case 32: switch(term) { case 19: case 20: case 21: case 25: case 36: case 37: case 38: case 46: return 62; default: return -uterm; } break; case 33: switch(term) { case 19: case 20: case 21: case 25: case 36: case 37: case 38: case 46: return 63; default: return -uterm; } break; case 34: switch(term)

{ case 30: case 31: case 32: case 33: case 34: case 35: return 64; case 39: case 42: case 43: return 65; default: return -uterm; } break; case 35: switch(term) { case 19: case 20: case 21: case 25: case 36: case 37: case 38: case 46: return 66; default: return -uterm; } break; case 36: switch(term) { case 24: case 25:

return 67; case 30: case 31: case 32: case 33: case 34: case 35: case 39: case 42: case 43: return 68; default: return -uterm; } break; case 37: switch(term) { case 19: case 20: case 21: case 25: case 36: case 37: case 38: case 46: return 69; default: return -uterm; } break; case 38: switch(term) { case 24: case 25: return 71;

case 26: case 27: case 28: return 70; case 30: case 31: case 32: case 33: case 34: case 35: case 39: case 42: case 43: return 71; default: return -uterm; } break; case 39: switch(term) { case 19: case 20: case 21: case 38: case 46: return 73; case 25: case 36: case 37: return 72; default: return -uterm; } break; case 40: switch(term)

{ case 19: return 76; case 20: return 75; case 21: return 77; case 38: return 74; case 46: return 78; default: return -uterm; } break; case 41: switch(term) { case 19: return 79; default: return -uterm; } break; case 42: switch(term) { case 30: return 82; case 31: return 80; case 32: return 84; case 33: return 85; case 34: return 83;

case 35: return 81; default: return -uterm; } break; case 43: switch(term) { case 24: return 86; case 25: return 87; default: return -uterm; } break; case 44: switch(term) { case 26: return 88; case 27: return 89; case 28: return 90; default: return -uterm; } break; case 45: switch(term) { case 25: return 91; case 36:

return 92; case 37: return 93; default: return -uterm; } break; case 46: switch(term) { case 19: case 20: case 21: case 25: case 36: case 37: case 38: case 39: case 46: return 94; case 47: return 95; default: return -uterm; } break; case 47: switch(term) { case 39: case 43: return 96; default: return -uterm; } break;

case 48: switch(term) { case 39: return 99; case 43: return 98; default: return -uterm; } break; case 49: switch(term) { case 39: return 101; case 43: return 100; default: return -uterm; } break; case 50: switch(term) { case 19: return 102; default: return -uterm; } break; } return 0; } typedef struct ustck

{ unsigned short int *utermstack; //栈指针 int stacklen; int top; }USTACK; USTACK utermstack; //非终结符栈 /*********************************************** 函数名:InitStack() 功能: 初始化非终结符栈深度为1*1024 参数: 无 返回值:1 成功 0 失败 ************************************************/ int InitStack() { utermstack.stacklen = 1; utermstack.utermstack = (unsigned short int *)malloc(utermstack.stacklen * 1024 * sizeof(unsigned short int)); memset(utermstack.utermstack , 0 , sizeof(utermstack.stacklen * 1024 * sizeof(unsigned short int))); utermstack.top = 0; if(utermstack.utermstack) return 1; else return 0; } /*********************************************** 函数名:ResizeStack() 功能: 扩展非终结符栈深度使之增加1024 参数: 无 返回值:1 成功 0 失败 ************************************************/ int ResizeStack() { unsigned short int *p = NULL; //栈空间当前长度 //栈顶指针

utermstack.stacklen ++; p = (unsigned short int *)malloc(utermstack.stacklen * 1024 * sizeof(unsigned short int)); memset(p , 0 , sizeof(utermstack.stacklen * 1024 * sizeof(unsigned short int))); memcpy( p, utermstack.utermstack ,(utermstack.stacklen-1) * 1024 * sizeof(unsigned short int) ); if(utermstack.utermstack != NULL) free(utermstack.utermstack); utermstack.utermstack = p; if(utermstack.utermstack) return 1; else return 0; } /*********************************************** 函数名:DestroyStack() 功能: 扩展非终结符栈深度使之增加1024 参数: 无 返回值:1 成功 0 失败 ************************************************/ int DestroyStack() { if(utermstack.utermstack != NULL) free(utermstack.utermstack); return 1; } /*********************************************** 函数名:IsStackEmpty() 功能: 判断非终结符栈是否为空 参数: 无 返回值:1 空 0 非空 ************************************************/ int IsStackEmpty()

{ if(utermstack.utermstack != NULL && utermstack.top > 0) return 0; else return 1; } /*********************************************** 函数名:PrintStep() 功能: 输出当前token字类别和符号栈内容 参数: 无 返回值:1 空 0 非空 ************************************************/ int PrintStep(int typecode) { int i = 0; printf("\n%x" , typecode); printf("\n"); for( i = 1 ; utermstack.utermstack != NULL && i <= utermstack.top ; i++ ) { switch(utermstack.utermstack[i]) { case 0x0100: printf("FunctionGroup "); break; case 0x0200: printf("Function "); break; case 0x0300: printf("FunctionHead "); break; case 0x0400: printf("FunctionBody "); break; case 0x0500: printf("BaseType "); break; case 0x0600:

printf("ForParList "); break; case 0x0700: printf("FormListMore "); break; case 0x0800: printf("Sentence "); break; case 0x0900: printf("Sen "); break; case 0x0a00: printf("DecSentence "); break; case 0x0b00: printf("IdList "); break; case 0x0c00: printf("IdMore "); break; case 0x0d00: printf("AssignmentSen "); break; case 0x0e00: printf("FunCallSen "); break; case 0x0f00: printf("ActParList "); break; case 0x1000: printf("ActParListMore "); break; case 0x1100: printf("ConditionalSen "); break; case 0x1200: printf("SwitchBody "); break;

case 0x1300: printf("ConsExpression "); break; case 0x1400: printf("ConsConExpressionMore "); break; case 0x1500: printf("ConsCountExpression "); break; case 0x1600: printf("ConsTermMore "); break; case 0x1700: printf("ConsTerm "); break; case 0x1800: printf("ConsFactorMore "); break; case 0x1900: printf("ConsFactor "); break; case 0x1a00: printf("ConsLost "); break; case 0x1b00: printf("SwiBodyMore "); break; case 0x1c00: printf("CaseBody "); break; case 0x1d00: printf("LoopSen "); break; case 0x1e00: printf("ForExpression "); break; case 0x1f00:

printf("ReturnSen "); break; case 0x2000: printf("Expression "); break; case 0x2100: printf("ConExpression "); break; case 0x2200: printf("ConExpressionMore "); break; case 0x2300: printf("CountExpression "); break; case 0x2400: printf("RemainTerm "); break; case 0x2500: printf("Term "); break; case 0x2600: printf("RemainFactor "); break; case 0x2700: printf("Factor "); break; case 0x2800: printf("Lost "); break; case 0x2900: printf("Variable "); break; case 0x2a00: printf("CmpOp "); break; case 0x2b00: printf("AddOp "); break;

case 0x2c00: printf("MultOp "); break; case 0x2d00: printf("SingleOp "); break; case 0x2e00: printf("FunCallSenMore "); break; case 0x2f00: printf("ActParListen "); break; case 0x3000: printf("ActParLisPrintf "); break; case 0x3100: printf("ActParLisScanf "); break; case 0x3200: printf("FunctionName "); break; case 0xFFFF: printf("Empty "); break; default: if(utermstack.utermstack[i] > 0x0100) printf("Unknow "); else printf("%x ",utermstack.utermstack[i]); break; } } printf("\n"); return 0; } /***********************************************

函数名:PrintStepToFile() 功能: 输出当前token字类别和符号栈内容到文件 参数: int toktype 当前token字, FILE* fp语法检查过程文件 返回值:1 空 0 非空 ************************************************/ int PrintStepToFile(int toktype , FILE* fp) { int i = 0; fprintf(fp,"\n%x" , toktype); fprintf(fp , "\n"); for( i = 1 ; utermstack.utermstack != NULL && i <= utermstack.top ; i++ ) { switch(utermstack.utermstack[i]) { case 0x0100: fprintf(fp , "FunctionGroup "); break; case 0x0200: fprintf(fp , "Function "); break; case 0x0300: fprintf(fp , "FunctionHead "); break; case 0x0400: fprintf(fp , "FunctionBody "); break; case 0x0500: fprintf(fp , "BaseType "); break; case 0x0600: fprintf(fp , "ForParList "); break; case 0x0700: fprintf(fp , "FormListMore "); break; case 0x0800: fprintf(fp , "Sentence "); break;

case 0x0900: fprintf(fp , "Sen "); break; case 0x0a00: fprintf(fp , "DecSentence "); break; case 0x0b00: fprintf(fp , "IdList "); break; case 0x0c00: fprintf(fp , "IdMore "); break; case 0x0d00: fprintf(fp , "AssignmentSen "); break; case 0x0e00: fprintf(fp , "FunCallSen "); break; case 0x0f00: fprintf(fp , "ActParList "); break; case 0x1000: fprintf(fp , "ActParListMore "); break; case 0x1100: fprintf(fp , "ConditionalSen "); break; case 0x1200: fprintf(fp , "SwitchBody "); break; case 0x1300: fprintf(fp , "ConsExpression "); break; case 0x1400: fprintf(fp , "ConsConExpressionMore "); break; case 0x1500:

fprintf(fp , "ConsCountExpression "); break; case 0x1600: fprintf(fp , "ConsTermMore "); break; case 0x1700: fprintf(fp , "ConsTerm "); break; case 0x1800: fprintf(fp , "ConsFactorMore "); break; case 0x1900: fprintf(fp , "ConsFactor "); break; case 0x1a00: fprintf(fp , "ConsLost "); break; case 0x1b00: fprintf(fp , "SwiBodyMore "); break; case 0x1c00: fprintf(fp , "CaseBody "); break; case 0x1d00: fprintf(fp , "LoopSen "); break; case 0x1e00: fprintf(fp , "ForExpression "); break; case 0x1f00: fprintf(fp , "ReturnSen "); break; case 0x2000: fprintf(fp , "Expression "); break; case 0x2100: fprintf(fp , "ConExpression "); break;

case 0x2200: fprintf(fp , "ConExpressionMore "); break; case 0x2300: fprintf(fp , "CountExpression "); break; case 0x2400: fprintf(fp , "RemainTerm "); break; case 0x2500: fprintf(fp , "Term "); break; case 0x2600: fprintf(fp , "RemainFactor "); break; case 0x2700: fprintf(fp , "Factor "); break; case 0x2800: fprintf(fp , "Lost "); break; case 0x2900: fprintf(fp , "Variable "); break; case 0x2a00: fprintf(fp , "CmpOp "); break; case 0x2b00: fprintf(fp , "AddOp "); break; case 0x2c00: fprintf(fp , "MultOp "); break; case 0x2d00: fprintf(fp , "SingleOp "); break; case 0x2e00: fprintf(fp , "FunCallSenMore ");

break; case 0x2f00: fprintf(fp , "ActParListen "); break; case 0x3000: fprintf(fp , "ActParLisPrintf "); break; case 0x3100: fprintf(fp , "ActParLisScanf "); break; case 0x3200: fprintf(fp , "FunctionName "); break; case 0xFFFF: fprintf(fp , "Empty "); break; default: if(utermstack.utermstack[i] > 0x0100) fprintf(fp , "Unknow "); else fprintf(fp , "%x ",utermstack.utermstack[i]); break; } } printf("\n"); return 0; }

/*********************************************** 函数名:Push() 功能: 符号入栈 参数: unsigned short int uterm 返回值:1 成功 0 失败 ************************************************/ int Push(unsigned short int uterm) 符号

{ if(utermstack.utermstack != NULL) { if(utermstack.top == utermstack.stacklen*1024-1 ) if( !ResizeStack()) return 0; utermstack.top ++; utermstack.utermstack[utermstack.top] = uterm ; return 1; } else return 0; } /*********************************************** 函数名:PushGramm() 功能: 产生式入栈 参数: unsigned short int uterm 产生式编号 返回值:1 成功 0 失败 ************************************************/ int PushGramm(unsigned short int uterm) { //unsigned short int grammar[103][32] int i = 0; if(uterm >= 103 || utermstack.utermstack == NULL) return 0; for(i = 0; i < 32 && grammar[uterm][i] != 0; i++); for(i-- ; i >= 0; i--) if(!Push(grammar[uterm][i])) return 0; return 1; } /*********************************************** 函数名:Pop() 功能: 弹出栈顶符号

参数: 无 返回值:>0 栈顶符号 0 栈空 ************************************************/ unsigned short int Pop() { unsigned short int t = 0; if(utermstack.utermstack != NULL && utermstack.top < utermstack.stacklen*1024 && utermstack.top > 0) { t = utermstack.utermstack[utermstack.top]; utermstack.top --; } return t; } /*********************************************** 函数名:ProcessGramm 功能: 语法分析(处理产生式) 参数: FILE* fp 语法检查过程文件指针 返回值:1 识别成功 0 失败 错误编号队列中为出错信息 ************************************************/ int ProcessGramm(FILE* fp) { int i = 0; unsigned short term = 0; int grammindex = 0; int err = 0; if(ResultData.pTokenList != NULL) { while( i < ResultData.nTokenListUsedLength ) { PrintStep(ResultData.pTokenList[i].typecode); if(fp != NULL) PrintStepToFile(ResultData.pTokenList[i].typecode , term = Pop(); if(term == 0) //弹出栈顶符号 //非法符号 fp);

break; else if(term == 0xFFFF) //ε空动作 continue; else if( term < 0x0100) //终结符 { if( term == ResultData.pTokenList[i].typecode) //当前token字与栈顶符号比较, 相同则继续 i++; else { //记录出错信息 break; } } else { //查找LL(1)分析表 grammindex = SearchLL1Table(term >> 8 , ResultData.pTokenList[i].typecode); //加入冲突消解 if(grammindex == 21 && i + 1 < ResultData.nTokenListUsedLength) { if( ResultData.pTokenList[i+1].typecode == 0x001d) //向右察看一个符号为 = 时 为22 grammindex = 22; else if( ResultData.pTokenList[i+1].typecode == 0x0026)//向右察看一个符号 不为 ( 时 为23 grammindex = 21; else grammindex = 23; } if(grammindex == 96 && i + 1 < ResultData.nTokenListUsedLength) { if( ResultData.pTokenList[i+1].typecode == 0x002d) //向右察看一个符号为 = 时 为22 grammindex = 97; } if(grammindex <= 0 || !PushGramm(grammindex))

break; //非终结符则将相应产生式入栈 } } if(i < ResultData.nTokenListUsedLength || !IsStackEmpty()) { return -grammindex; } else { return 1; } } else { return 0; } } /*********************************************** 函数名:CheckGramm 功能: 语法分析 参数: char* srcfilename 源文件名,用于生成语法检查过程文件名 返回值:1 识别成功 0 失败 错误编号队列中为出错信息 ************************************************/ int CheckGramm(char* srcfilename) { int errflag = 0; char grafilename[MAX_PATH] = {0}; FILE* fpGra = NULL; int i = 0; while(i< MAX_PATH-4 && srcfilename[i]!=0 && srcfilename[i]!='.' ) { grafilename[i] = srcfilename[i]; i++; } strcat(grafilename,".grm"); /* 生成 语法检查文件名 */ fpGra = fopen(grafilename, "w");

InitStack(); Push(0x0034); // #号入栈 PushGramm(0); //文法开始符号入栈 errflag = ProcessGramm(fpGra); DestroyStack(); if(fpGra != NULL) fclose(fpGra); return } int main(int argc , char* argv[]) { char srcname[MAX_PATH] = {0}; int errcode = 0; if( argc > 1) { strcpy(srcname, argv[1]); } else { printf("Input Source File Name Please:"); gets(srcname); } if(!InitResultData()) { printf("Alloc Memory Fail\n"); return 0; } if( Scaner(srcname)) printf("Compile Success!\n"); else printf("Compile Failed!\n"); errcode = CheckGramm(srcname); errflag;

if( errcode == 1 ) printf("Grammar check Success!\n"); else if(errcode < 0 ) printf("Grammar %d check Failed!\n" , -errcode); else printf("Token String is Empty!\n"); DeleteResultData(); getchar(); return 0; }




友情链接: