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

1、四川大学编译原理课程设计 学号2012141461017编译原理课程设计课程报告题目 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 , flo

2、at , for , goto, 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 na

3、t=digit+ signednat=(+|-)?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 st

4、atic struct switch 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

5、 ,for , goto,if, 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,plusassig

6、n,minusassign,timesassign,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时，如果输入的字符为/,则进

7、入状态2，此时有可能进入注释状态，如果在状态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）类型

8、token的状态，状态inoperate表示算数运算符型token的状态，状态inocompare表示比较运算符型token的状态，instring表示字符串（string）类型token的状态，inchar表示字符（character）类型token的状态，状态done表示接收状态。l 在开始状态start时Ø 如果输入的字符为空白符，如空格换行等，则仍在start状态Ø 如果输入的字符为digit，则进入状态innum，即可能是数字类型（num）token的状态Ø 如果输入的字符为letter，则进入状态inid，即可能是标识符类型token的状态Ø

9、 如果输入的字符为>、<、!、=，则进入状态incompare，即可能是比较运算符型token的状态Ø 如果输入的字符为+、*、/，则进入状态inoperate，即可能是算数运算符类型token的状态Ø 如果输入的字符为，则进入状态inchar，即可能是字符类型token的状态Ø 如果输入的字符为“，则进入状态instring，即可能是字符串类型token的状态Ø 如果输入的字符为是除以上之外的，则进入状态done，这次输入的字符可能是单目运算符、错误等l 在状态innum时Ø 如果输入的字符为digit，则仍停留在innum状态&

10、#216; 如果输入的字符为”.”，则转到innum1状态l 在状态innum1时Ø 如果输入的字符为digit，则进入innum2状态l 在状态innum2时l 如果输入的为其他的字符，则转到done状态Ø 如果输入字符为digit，则停留在innum2状态Ø 如果输入的为其他字符，则转到done状态l 在状态inid时Ø 如果输入的字符为letter或“_”或digit，则仍停留在inid状态Ø 如果输入的为其他的字符，则转到done状态l 在状态incompare时Ø 如果输入的字符为=，则转到done状态Ø 如果输入

11、的为其他的字符，则直接转到done状态l 在状态inoperate时Ø 如果输入的字符为=，转到done状态Ø 如果输入的为其他的字符，则直接转到done状态l 在状态incompare时Ø 如果输入的字符为=，则转到done状态Ø 如果输入的为其他的字符，则直接转到done状态l 在状态inchar时Ø 如果输入为单引号，则转到done状态Ø 如果输入的为其他字符，则停留在inchar状态l 在状态instring时Ø 如果输入为双引号，则转到done状态Ø 如果输入的为其他字符，则停留在instring状态l

12、在状态done时接受状态，根据分析过程中获取的字符串确定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 get

13、token(void); /* 词法分析函数*/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;

14、 /* 当前行的位置*/ static 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文件中包括注释，保留字，整数和小数，标识符，特殊符号，字符串以及错误输入。本程序成功

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

16、言编制tiny/c-语言的语法分析程序，实现对词法分析程序所提供的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) |

17、compound-stmtparamsparam_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 expr

18、ession;selection-stmtif (expression) statement else statementiteration-stmtwhile (expression)statementreturn-stmtreturn expression;expression var = expression | simple-expressionrelop < = | < | > | > = | = = | ! =varid | id expressionsimple-expression>additive-expression relop additiv

19、e-expression additive-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数

20、组声明数组名+数组大小funk函数声明返回类型+函数名+参数列表+函数体paramskfunk的参数列表参数（如果有多个参数，则之间为兄弟节点）paramkfunk的参数参数类型+参数名compk复合语句体变量声明列表+语句列表selection_stmtkif条件表达式+if体+else体iteration_stmtkwhile条件表达式+循环体return_stmtkreturn表达式assignk赋值被赋值变量+赋值变量opk运算运算符左值+运算符右值arry_elemk数组元素数组名+下标callk函数调用函数名+参数列表argskcallk的参数列表表达式unkownk未知节点无3.

21、2节点定义typedef struct 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()然后直接调用declara

22、tion_list()返回树节点代码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()函

23、数返回树节点，当前token为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(tok

24、en=int|token=void)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-specifie

25、r int | void分析函数 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;t

26、reenode * a = null;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

27、; /p是t子节点t->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(n

28、um);a->child0=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是

29、否是void，如果是void则匹配，判断下一个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-

30、>child0 = param_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(tree

31、node * k)treenode * 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，决

32、定子节点类型是intk还是voidk，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!=n

33、ull)p = k;if(p!=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 synt

34、axerror("");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

35、= statement_list(); 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;

36、while(token=int | 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(toke

37、nstring);p->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;

38、文法statement-liststatement分析函数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) treeno

39、de * q;q = statement();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类型确定到底是哪一种类型。如果

40、是if则调用selection_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

41、;case lcbracket: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)函数通过

42、判断先行token类型是否为分号，如果不是则直接调用函数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，如果不是说明只

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

44、ession(treenode * 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->chi

45、ld0 = t;p->child1 = 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;treen

46、ode * q = null;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-

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

48、回一个节点，作为opk节点的第二个节点代码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_express

49、ion(k); return 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 li