C语言词法分析器和C语言语法分析器编译原理课程设计

1、精选优质文档-倾情为你奉上编译原理课程设计课程报告题目 C语言词法分析器和C-语言语法分析器 学生姓名 学生学号 指导教师 提交报告时间 2019 年 6 月 8 日C语言词法分析器1 实验目的及意义1. 熟悉C语言词法2. 掌握构造DFA的过程3. 掌握利用DFA实现C语言的词法分析器4. 理解编译器词法分析的工作原理2 词法特点及正则表达式2.1词法特点2.1.1 保留字AUTO, BREAK , CASE , CHAR , CONST , CONTINUE , DEFAULT , DO , DOUBLE , ELSE, ENUM , EXTERN , FLOAT , FOR , GOTO

2、, IF , INT , LONG , REGISTER , RETURN, SHORT , SIGNED , SIZEOF , STATIC , STRUCT , SWITCH , TYPEDEF , UNION , UNSIGNED , VOID, VOLATILE , WHILE,2.1.2 符号 + - * / + - += -= *= < <= > >= = != = ; , ( ) /* */ : 2.2 正则表达式 whitespace = (newline|blank|tab|comment)+ digit=0|.|9 nat=digit+ signed

3、Nat=(+|-)?nat NUM=signedNat(“.”nat)? letter = a|.|z|A|.|Z ID = letter(letter|digit|“_”)+ CHAR = 'other+' STRING = “other+”3 Token定义3.1 token类型保留字auto break case char const continue default do double elseenum extern float for gotoif int long redisterreturnshort signed sizeof static struct swi

4、tch typedef union unsignedvoid volatile while特殊符号+ - * / + - += -= *= < <= > >= = != = ; , ( ) /* */ :文件结束、错误EOF ERROR其它tokenNUM ID CHARACTER STRINGtypedef enum /错误、结束 ENDFILE,ERROR, /保留字 AUTO,BREAK,CASE,CHAR,CONST,CONTINUE ,DEFAULT , DO ,DOUBLE, ELSE, ENUM, EXTERN , FLOAT ,FOR , GOTO,IF

5、, INT, LONG,REGISTER , RETURN, SHORT, SIGNED ,SIZEOF ,STATIC, STRUCT ,SWITCH, TYPEDEF ,UNION, UNSIGNED , VOID,VOLATILE , WHILE, /其他token ID,NUM,CHARACTER,STRING,/特殊符号 /+、-、*、/、+、-、+=、-=、*=、<、<=、>、>=、=、!=、=、;、,、(、)、/、/*、*/、:PLUS,MINUS,TIMES,OVER,SELFPLUS,SELFMINUS,PLUSASSIGN,MINUSASSIGN,T

6、IMESASSIGN,LT,LEQ,GT,GEQ,EQ,NEQ,ASSIGN,SEMI,COMMA,LPAREN, MINUSASSIGN,TIMESASSIGN,LT,LEQ,GT,GEQ,EQ,NEQ,ASSIGN,SEMI,COMMA,LPAREN, RPAREN,LBRACKET,RBRACKET, LCBRACKET,RCBRACKET,LCOMMENT,RCOMMENT,COLON TokenType;3.2 tokenType类型代码4 DFA设计4.1 注释的DFA设计注释的DFA如下所示，一共分为5个状态，在开始状态1时，如果输入的字符为/,则进入状态2，此时有可能进入注释状

7、态，如果在状态2时，输入的字符为*，则进入注释状态，状态将转到3，如果在状态3时，输入的字符为*，则有可能结束注释状态，此时状态将转到状态4，如果在状态4时输入的字符为/，则注释状态结束，状态转移到结束状态。4.2 词法分析的DFA设计词法分析的DFA如下所示，一共分为10个状态：START、INNUM、INNUM1、INNUM2、INID、INCOMPARE、INOPERATE、INSTRING、INCHAR、DONE。状态START表示开始状态，状态INNUM，INNUM1，INNUM2表示数字类型（NUM）Token的状态，状态INID表示标示符（ID）类型Token的状态，状态INOP

8、ERATE表示算数运算符型Token的状态，状态INOCOMPARE表示比较运算符型Token的状态，INSTRING表示字符串（STRING）类型Token的状态，INCHAR表示字符（CHARACTER）类型Token的状态，状态DONE表示接收状态。l 在开始状态START时Ø 如果输入的字符为空白符，如空格换行等，则仍在START状态Ø 如果输入的字符为digit，则进入状态INNUM，即可能是数字类型（NUM）Token的状态Ø 如果输入的字符为letter，则进入状态INID，即可能是标识符类型Token的状态Ø 如果输入的字符为>、&

9、lt;、!、=，则进入状态INCOMPARE，即可能是比较运算符型Token的状态Ø 如果输入的字符为+、*、/，则进入状态INOPERATE，即可能是算数运算符类型Token的状态Ø 如果输入的字符为，则进入状态INCHAR，即可能是字符类型Token的状态Ø 如果输入的字符为“，则进入状态INSTRING，即可能是字符串类型Token的状态Ø 如果输入的字符为是除以上之外的，则进入状态DONE，这次输入的字符可能是单目运算符、错误等l 在状态INNUM时Ø 如果输入的字符为digit，则仍停留在INNUM状态Ø 如果输入的字符为”

10、.”，则转到INNUM1状态l 在状态INNUM1时Ø 如果输入的字符为digit，则进入INNUM2状态l 在状态INNUM2时l 如果输入的为其他的字符，则转到DONE状态Ø 如果输入字符为digit，则停留在INNUM2状态Ø 如果输入的为其他字符，则转到DONE状态l 在状态INID时Ø 如果输入的字符为letter或“_”或digit，则仍停留在INID状态Ø 如果输入的为其他的字符，则转到DONE状态l 在状态INCOMPARE时Ø 如果输入的字符为=，则转到DONE状态Ø 如果输入的为其他的字符，则直接转到DO

11、NE状态l 在状态INOPERATE时Ø 如果输入的字符为=，转到DONE状态Ø 如果输入的为其他的字符，则直接转到DONE状态l 在状态INCOMPARE时Ø 如果输入的字符为=，则转到DONE状态Ø 如果输入的为其他的字符，则直接转到DONE状态l 在状态INCHAR时Ø 如果输入为单引号，则转到DONE状态Ø 如果输入的为其他字符，则停留在INCHAR状态l 在状态INSTRING时Ø 如果输入为双引号，则转到DONE状态Ø 如果输入的为其他字符，则停留在INSTRING状态l 在状态DONE时接受状态，根据

12、分析过程中获取的字符串确定Token的类型，并生成和保存相应的Token5 代码结构分析5.1主要结构词法分析部分的代码在scan.c和scan.h文件中，全局变量以及公共函数代码在global.h以及util.h和util.c文件中。主函数中进行文件打开和关闭，并调用scan.c中的getToken（）函数对源文件进行词法分析。5.2 函数和成员变量的作用和含义void printToken(TokenType,const char*); /*输出token */char* copyString(char *); /* 字符串复制 */TokenType getToken(void); /*

13、 词法分析函数*/static int getNextChar(void) /* 获取下一个字符 */static void ungetNextChar(void) /* 退回一个字符 */static TokenType reservedLookup (char * s) /* 查找对应的保留字*/char tokenStringMAXTOKENLEN+1; /* token字符串*/int lineno = 0; /* 当前行号 */static char lineBufBUFLEN; /* 整行代码缓冲区 */ static int linepos = 0; /* 当前行的位置*/ st

14、atic int bufsize = 0; /* 缓冲区大小*/static int EOF_flag = FALSE; /* 文件结束标志 */6 实验结果与分析6.1 测试文件test.c/*test.c*/int main(void)# int a = 0; float b = 20.1; char c = "abcdefg" char d = 'h' if(a>=2) b+=0.1 a+; 6.2 测试结果6.3结果分析test.c文件中包括注释，保留字，整数和小数，标识符，特殊符号，字符串以及错误输入。本程序成功对test.c文件进行了词法分

15、析，对注释进行了忽略，输出了相应的行号、类型、取值，对于错误的输入显示ERROR。7 小结通过编写C语言词法分析器，我对编译器的基本原理有了更深的认识，同时掌握了DFA的设计与实现。在最开始的编写过程中，我总是把词法和语法分析混淆，比如一些错误应该在语法分析中判断，我却写进了词法分析中，后来我逐步认识到词法分析的作用就是提取源代码中的Token。在DFA的实现过程中，我主要参考了书后tiny语言DFA的实现方法，将它扩展到C语言。另外C语言词法比较复杂，因为时间关系我省略了一些，比如位运算符，转义字符等等，希望今后能完善。C-语言语法分析器1 实验目的及意义用C语言编制Tiny/C-语言的语法

16、分析程序，实现对词法分析程序所提供的Token序列的语法检查和结构分析。 2 文法规则（EBNF）programdeclaration-listdeclaration_list declaration declaration declarationvar-declaration|fun-declarationvar_declaration type-specifier ID; | type-specifier ID NUM;type - specifier int | voidfun-declatationtype-specifier ID (params) | compound-stmtpa

17、ramsparam_list | voidparam_listparam, paramparam type-specifier ID compound-stmt local-declaration statement-listlocal-declarations empty var- declarationstatement-liststatementstatementexpression-stmt | compound-stmt | selection-stmt | iteration-stmt | return-stmtexpression-stmt expression;selectio

18、n-stmtif (expression) statement else statementiteration-stmtwhile (expression)statementreturn-stmtreturn expression;expression var = expression | simple-expressionrelop < = | < | > | > = | = = | ! =varID | ID expressionsimple-expression>additive-expression relop additive-expression ad

19、ditive-expressiontermaddop term addop + | -termfactormulop factor mulop * | /factor(expression) | var | call | NUMcallID( args )argsarg-list | emptyarg-list expression, expression3 节点类型及定义3.1节点类型节点类型描述子节点IntKInt型变量或返回值无VoidKvoid型变量或返回值无IdK标示符id无ConstK数值无Var_DeclK变量声明变量类型+变量名Var_DeclK数组声明数组名+数组大小FunK

20、函数声明返回类型+函数名+参数列表+函数体ParamsKFunK的参数列表参数（如果有多个参数，则之间为兄弟节点）ParamKFunK的参数参数类型+参数名CompK复合语句体变量声明列表+语句列表Selection_StmtKif条件表达式+IF体+ELSE体Iteration_StmtKwhile条件表达式+循环体Return_StmtKreturn表达式AssignK赋值被赋值变量+赋值变量OpK运算运算符左值+运算符右值Arry_ElemK数组元素数组名+下标CallK函数调用函数名+参数列表ArgsKCallK的参数列表表达式UnkownK未知节点无3.2节点定义typedef st

21、ruct treeNodestruct treeNode * child4;struct treeNode * sibling;int lineno;NodeKind nodekind;union TokenType op; int val; const char * name; attr; ExpType type; TreeNode;4 代码结构分析文法programdeclaration-list分析函数TreeNode * parse(void)说明C-程序由一个声明序列组成，parse（void）函数首先执行getToken()然后直接调用declaration_list()返回树节

22、点代码TreeNode * parse(void)TreeNode * t;token = getToken();t = declaration_list();if(token!=ENDFILE) syntaxError("endfile error");return t;文法declaration_list declaration declaration 分析函数TreeNode * declaration_list(void)说明声明序列是由若干声明构成，declaration_list(void)函数中直接调用declaration()函数返回树节点，当前token为

23、INT或VOID时，调用declaration()返回之前树节点的兄弟节点。代码TreeNode * declaration_list(void)TreeNode * t = declaration();TreeNode * p =t;/程序以变量声明开始 while(token!=INT)&&(token!=VOID)&&(token!=ENDFILE) syntaxError("开始不是类型声明"); token = getToken(); if(token=ENDFILE) break; while(token=INT|token=VO

24、ID)TreeNode * q;q = declaration();if (q!=NULL)if (t=NULL)t=p=q;elsep->sibling=q;p=q;match(ENDFILE);return t;文法declarationvar-declaration|fun-declarationvar_declaration type-specifier ID; | type-specifier ID NUM;fun-declatationtype-specifier ID (params) | compound-stmt type-specifier int | void分析函

25、数 TreeNode * declaration(void)说明首先判断类型，执行match函数， 匹配类型和ID，向前探测1个token的值确定是函数声明还是变量声明，如果token为，则是数组变量声明，返回节点Array_DeclK, token为（,则是函数声明，返回节点FunK, token为;则是普通变量声明，返回节点Var_DeclK代码TreeNode * declaration(void)TreeNode * t = NULL;TreeNode * p = NULL;TreeNode * q = NULL;TreeNode * s = NULL;TreeNode * a = N

26、ULL;if (token=INT)p=newNode(IntK);match(INT);else if (token=VOID)p=newNode(VoidK);match(VOID);else syntaxError("type error");if(p!=NULL&&token=ID)q = newNode(IdK);q-> = copyString(tokenString); match(ID);if (token=LPAREN)t = newNode(FunK);t->child0 = p; /p是t子节点t->

27、child1 = q;match(LPAREN);t->child2 = params();match(RPAREN);t->child3 = compound_stmt();else if (token=LBRACKET)t = newNode(Var_DeclK);a = newNode(Arry_DeclK);t->child0 = p; /p是t子节点t->child1 = a;match(LBRACKET);s = newNode(ConstK);s->attr.val = atoi(tokenString);match(NUM);a->child

28、0=q;a->child1=s;match(RBRACKET);match(SEMI);else if (token=SEMI)t = newNode(Var_DeclK);t->child0 = p;t->child1 = q;match(SEMI);elsesyntaxError("");elsesyntaxError("");return t;文法paramsparam_list | void分析函数TreeNode * params(void)说明参数列表，根节点ParamsK，首先判断token是否是VOID，如果是VOID则

29、匹配，判断下一个token，如果是右括号，则参数列表中只有子节点VoidK，如果是ID，则子节点是param_list,如果开始时token是INT,则参数列表子节点是param_list代码TreeNode * params(void)TreeNode * t = newNode(ParamsK);TreeNode * p = NULL;if (token=VOID)p = newNode(VoidK);match(VOID);if (token=RPAREN)if(t!=NULL)t->child0 = p;else/参数列表为(void id,) t->child0 = pa

30、ram_list(p);else if (token=INT)t->child0 = param_list(p);else syntaxError("");return t;文法param_listparam, param分析函数TreeNode * param_list(TreeNode * k)说明说明参数列表由param序列组成，并由逗号隔开。param_list(TreeNode * k)函数使用递归向下分析方法直接调用param(TreeNode * k)函数，并返回树节点代码TreeNode * param_list(TreeNode * k)TreeNo

31、de * t = param(k);TreeNode * p = t; k = NULL;/没有要传给param的VoidK，所以将k设为NULLwhile (token=COMMA)TreeNode * q = NULL;match(COMMA);q = param(k);if (q!=NULL)if (t=NULL)t=p=q;elsep->sibling = q;p = q;return t;文法param type-specifier ID 分析函数TreeNode * param(TreeNode * k)说明探测token是INT还是VOID，决定子节点类型是IntK还是Vo

32、idK，IdK作为第二个子节点，向前探测一个token，如果是左中括号，则产生第三个子节点代码TreeNode * param(TreeNode * k)TreeNode * t = newNode(ParamK);TreeNode * p = NULL;TreeNode * q = NULL;if(k=NULL&&token=VOID)p = newNode(VoidK);match(VOID);else if(k=NULL&&token=INT)p = newNode(IntK);match(INT);else if (k!=NULL)p = k;if(p!

33、=NULL)t->child0 = p;if (token=ID)q = newNode(IdK);q-> = copyString(tokenString);t->child1 = q;match(ID);elsesyntaxError("");if (token=LBRACKET&&(t->child1!=NULL)/match(LBRACKET);t->child2 = newNode(IdK);match(RBRACKET);else return t; else syntaxError("&

34、quot;);return t;文法compound-stmt local-declaration statement-list分析函数TreeNode * compound_stmt(void)说明复合语句，直接调用local_declaration()函数和statement_list()函数，产生两个子节点代码TreeNode * compound_stmt(void) TreeNode * t = newNode(CompK);match(LCBRACKET);t->child0 = local_declaration();t->child1 = statement_lis

35、t(); match(RCBRACKET);return t;文法local-declarations empty var- declaration分析函数TreeNode * local_declaration(void)说明全局变量声明，可以是空，也可以是若干变量声明，首先判断token是否等于INT或VOID，从而得知是否为空，若不为空则创建一个Var_DeclK节点代码TreeNode * local_declaration(void) TreeNode * t = NULL;TreeNode * q = NULL;TreeNode * p = NULL;while(token=INT

36、 | token=VOID) p = newNode(Var_DeclK);if(token=INT)TreeNode * q1 = newNode(IntK);p->child0 = q1;match(INT);else if(token=VOID)TreeNode * q1 = newNode(VoidK);p->child0 = q1;match(INT);if(p!=NULL)&&(token=ID) TreeNode * q2 = newNode(IdK); q2-> = copyString(tokenString);p->

37、child1 = q2;match(ID);if(token=LBRACKET) TreeNode * q3 = newNode(Var_DeclK);p->child3 = q3;match(LBRACKET);match(RBRACKET);match(SEMI);else if(token=SEMI)match(SEMI);elsematch(SEMI); else syntaxError("");if(p!=NULL)if(t=NULL)t = q = p;elseq->sibling = p;q = p;return t;文法statement-lis

38、tstatement分析函数TreeNode * statement_list(void)说明调用statement()创建根节点，向前探测一个token，创建兄弟节点代码TreeNode * statement_list(void) TreeNode * t = statement(); TreeNode * p = t;while (IF=token | LCBRACKET=token | ID=token | WHILE=token | RETURN =token | SEMI=token | LPAREN=token | NUM=token) TreeNode * q;q = stat

39、ement();if(q!=NULL)if(t=NULL) t = p = q;else p->sibling = q;p = q;return t;文法statementexpression-stmt| compound-stmt | selection-stmt | iteration-stmt | return-stmt分析函数TreeNode * statement(void)说明statement由表达式或复合语句或if语句或while语句或return语句构成。statement(void)函数通过判断先行Token类型确定到底是哪一种类型。如果是IF则调用selection

40、_statement()，如果是WHILE，则调用iteration_stmt()，如果是RETURN，则调用return()，如果是左大括号，则是复合语句类型，如果是ID、SEMI、LPAREN、NUM，则是表达式语句类型代码TreeNode * statement(void) TreeNode * t = NULL;switch(token)case IF:t = selection_stmt(); break;case WHILE:t = iteration_stmt(); break;case RETURN:t = return_stmt(); break;case LCBRACKET

41、:t = compound_stmt(); break;case ID: case SEMI: case LPAREN: case NUM: t = expression_stmt(); break;default:syntaxError("");token = getToken();break;return t;文法expression-stmt expression;分析函数TreeNode * expression_stmt(void)说明说明表达式语句有一个可选的且后面跟着分号的表达式。expression_stmt(void)函数通过判断先行token类型是否为分

42、号，如果不是则直接调用函数expression()代码TreeNode * expression_stmt(void) TreeNode * t = NULL;if(token=SEMI) match(SEMI);return t;else t = expression();match(SEMI);return t;文法expression var = expression | simple-expression分析函数TreeNode * expression(void)说明expression(void)函数通过判断先行Token类型是否为ID，如果不是说明只能是simple_expres

43、sion情况，则调用simple_expression(TreeNode * k)函数递归向下分析；如果是ID说明可能是赋值语句，或simple_expression中的var和call类型的情况，所以再求其Follow集合，如果集合求出来是赋值类型的Token，则说明是赋值语句，于是新建一个AssignK节点就行；如果集合求出来不是赋值类型的Token则说明是simple_expression中的var和call类型的情况，然后再调用simple_expression(TreeNode * k)函数递归向下分析，并将已经取出IdK节点传递给simple_expression(TreeNode

44、 * k)函数代码TreeNode * expression(void) TreeNode * t = var();if(t=NULL)/不是以ID开头，只能是simple_expression情况 t = simple_expression(t); else/以ID开头，可能是赋值语句，或simple_expression中的var和call类型的情况 TreeNode * p = NULL;if(token=ASSIGN)/赋值语句 p = newNode(AssignK);/p-> = ;match(ASSIGN);p->child0 = t;p->c

45、hild1 = expression();return p;else /simple_expression中的var和call类型的情况 t = simple_expression(t); return t;文法varID | ID expression分析函数TreeNode * var(void)说明创建IdK节点，判断先行token类型是否是中括号，如果是就创建Arry_ElemK节点，调用expression()得到子节点代码TreeNode * var(void) TreeNode * t = NULL;TreeNode * p = NULL;TreeNode * q = NULL;

46、if(token=ID)p = newNode(IdK);p-> = copyString(tokenString); match(ID);if(token=LBRACKET) match(LBRACKET);q = expression();match(RBRACKET);t = newNode(Arry_ElemK);t->child0 = p;t->child1 = q;elset = p;return t;文法simple-expression>additive-expression relop additive-expression relo

47、p < = | < | > | > = | = = | ! =分析函数TreeNode * simple_expression(TreeNode * k)说明simple_expression(TreeNode * k)函数先调用additive_expression(TreeNode * k)函数返回一个节点，然后再一直判断后面的Token是否为<=、<、>、>=、=、!=，如果是则新建OpK节点，然后令之前的节点为其第一个子节点，然后继续调用additive_expression(TreeNode * k)函数返回一个节点，作为OpK节点的第

48、二个节点代码TreeNode * simple_expression(TreeNode * k) TreeNode * t = additive_expression(k);k = NULL;if(EQ=token | GT=token | GEQ=token | LT=token | LEQ=token | NEQ=token) TreeNode * q = newNode(OpK);q->attr.op = token; q->child0 = t;t = q;match(token);t->child1 = additive_expression(k); return

49、t;return t;5 实验结果与分析测试文本test.cint a10;int min(int a,int low,void a)int k; int x; int i;k=low;while(i<low)a0=1;if(k>0)x=1;return x;测试结果成功实现语法分析6 小结通过这次实验，我加深了对语法分析的认识，掌握了递归向下分析方法，实现了对词法分析程序所提供的Token序列的语法检查和结构分析。 语法分析程序编写相对于词法分析要困难得多，首先要将BNF化为EBNF，运用递归向下的方法进行编写，构造出语法树，判别语法分析过程中是否出错以及出错位置和错误类型。虽然EBNF转换成代码的过程原理比较简单，但是操作起来比较繁琐。一开始我对TreeNode数据结构也不是很理解，通过阅读书后的tiny语言语法分析源代码，我弄懂了语法树的输出。附录（源代码）Main.c#include "global.h"#include "util.h"#include "scan.h"/* 全局变量 */int lineno = 0;/* 编译过程标志 */int EchoSource = TRUE;int TraceSca