C语言词法分析器和C-语言语法分析器编译原理课程设计［精］
《编译原理课程设计》课程
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
题目 C语言词法分析器和C-语言语法分析器
学生姓名
学生学号
指导教师
提交报告时间 2019 年 6 月 8 日
四川大学《编译原理课程设计》 学号2012141461017
C语言词法分析器
1 实验目的及意义
1. 熟悉C语言词法
2. 掌握构造DFA的过程
3. 掌握利用DFA实现C语言的词法分析器
4. 理解编译器词法分析的工作原理
2 词法特点及正则
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
达式
2.1词法特点
2.1.1 保留字
AUTO, BREAK , CASE , CHAR , CONST ,
CONTINUE , DEFAULT , DO , DOUBLE , ELSE,
ENUM , EXTERN , FLOAT , 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
nat=digit+
signedNat=(+|-)?nat
NUM=signedNat(“.”nat)?
letter = a|..|z|A|..|Z
ID = letter(letter|digit|“_”)+
CHAR = 'other+' STRING = “other+”
1
四川大学《编译原理课程设计》 学号2012141461017
3 Token定义
3.1 token类型
保留字 auto break case char const
continue default do double else
enum extern float for goto
if int long redister return
short signed sizeof static struct
switch typedef union unsigned void
volatile while
特殊符号 + - * / ++ -- += -= *= < <= > >= == != = ; , ( ) [ ] { } /*
*/ :
文件结束、错误 EOF ERROR
其它token NUM ID CHARACTER STRING
3.2 tokenType类型代码
typedef enum
{
//错误、结束
ENDFILE,ERROR,
//保留字
AUTO,BREAK,CASE,CHAR,CONST,CONTINUE ,DEFAULT , DO ,DOUBLE, ELSE,
ENUM, EXTERN , FLOAT ,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,PLUSASSIGN,
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;
2
四川大学《编译原理课程设计》 学号2012141461017
4 DFA设计
4.1 注释的DFA设计
注释的DFA如下所示，一共分为5个状态，在开始状态1时，如果输入的字符为/, 则 进入状态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)类型Token的状态，状态INOPERATE表示算数运算符型Token的状态，状态INOCOMPARE表示比较运算符型Token的状态，INSTRING表示字符串(STRING)类型Token的状态，INCHAR表示字符(CHARACTER)类型Token的状态，状态DONE表示接收状态。
, 在开始状态START时
, 如果输入的字符为空白符，如空格换行等，则仍在START状态
, 如果输入的字符为digit，则进入状态INNUM，即可能是数字类型(NUM)Token的状态
, 如果输入的字符为letter，则进入状态INID，即可能是标识符类型Token的状态
, 如果输入的字符为>、<、!、=，则进入状态INCOMPARE，即可能是比较运算符型Token的状态
, 如果输入的字符为+、—、*、/，则进入状态INOPERATE，即可能是算数运算符类型Token的状态
, 如果输入的字符为‘，则进入状态INCHAR，即可能是字符类型Token的状态
, 如果输入的字符为“，则进入状态INSTRING，即可能是字符串类型Token的状态
, 如果输入的字符为是除以上之外的，则进入状态DONE，这次输入的字符可能是单目运算符、错误等 , 在状态INNUM时
, 如果输入的字符为digit，则仍停留在INNUM状态
, 如果输入的字符为”.”，则转到INNUM1状态
3
四川大学《编译原理课程设计》 学号2012141461017
, 在状态INNUM1时
, 如果输入的字符为digit，则进入INNUM2状态 , 在状态INNUM2时
, 如果输入的为其他的字符，则转到DONE状态
, 如果输入字符为digit，则停留在INNUM2状态
, 如果输入的为其他字符，则转到DONE状态 , 在状态INID时
, 如果输入的字符为letter或“_”或digit，则仍停留在INID状态
, 如果输入的为其他的字符，则转到DONE状态 , 在状态INCOMPARE时
, 如果输入的字符为=，则转到DONE状态
, 如果输入的为其他的字符，则直接转到DONE状态 , 在状态INOPERATE时
, 如果输入的字符为=，转到DONE状态
, 如果输入的为其他的字符，则直接转到DONE状态 , 在状态INCOMPARE时
, 如果输入的字符为=，则转到DONE状态
, 如果输入的为其他的字符，则直接转到DONE状态 , 在状态INCHAR时
, 如果输入为单引号，则转到DONE状态
, 如果输入的为其他字符，则停留在INCHAR状态 , 在状态INSTRING时
, 如果输入为双引号，则转到DONE状态
, 如果输入的为其他字符，则停留在INSTRING状态 , 在状态DONE时
接受状态，根据分析过程中获取的字符串确定Token的类型，并生成和保存相应的Token
4
四川大学《编译原理课程设计》 学号2012141461017
5 代码结构分析
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); /* 词法分析函数*/
static int getNextChar(void) /* 获取下一个字符 */
static void ungetNextChar(void) /* 退回一个字符 */
static TokenType reservedLookup (char * s) /* 查找对应的保留字*/
char tokenString[MAXTOKENLEN+1]; /* token字符串*/
int lineno = 0; /* 当前行号 */
static char lineBuf[BUFLEN]; /* 整行代码缓冲区 */
static int linepos = 0; /* 当前行的位置*/
static int bufsize = 0; /* 缓冲区大小*/
static int EOF_flag = FALSE; /* 文件结束标志 */
5
四川大学《编译原理课程设计》 学号2012141461017
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
四川大学《编译原理课程设计》 学号2012141461017
6.3结果分析
test.c文件中包括注释，保留字，整数和小数，标识符，特殊符号，字符串以及错误输入。
本程序成功对test.c文件进行了词法分析，对注释进行了忽略，输出了相应的行号、类型、取值，对于错误的输入显示ERROR。
7 小结
通过编写C语言词法分析器，我对编译器的基本原理有了更深的认识，同时掌握了DFA的设计与实现。
在最开始的编写过程中，我总是把词法和语法分析混淆，比如一些错误应该在语法分析中判断，我却写进了词法分析中，后来我逐步认识到词法分析的作用就是提取源代码中的Token。在DFA的实现过程中，我主要参考了书后tiny语言DFA的实现方法，将它扩展到C语言。另外C语言词法比较复杂，因为时间关系我省略了一些，比如位运算符，转义字符等等，希望今后能完善。
7
四川大学《编译原理课程设计》 学号2012141461017
C-语言语法分析器
1 实验目的及意义
用C语言编制Tiny/C-语言的语法分析程序，实现对词法分析程序所提供的Token
序列的语法检查和结构分析。
2 文法规则(EBNF)
program?declaration-list
declaration_list ? declaration{ declaration }
declaration?var-declaration|fun-declaration
var_declaration ?type-specifier ID; | type-specifier ID [NUM]; type - specifier ? int | void
fun-declatation?type-specifier ID (params) | compound-stmt params?param_list | void
param_list?param{, param}
param? type-specifier ID{[ ]}
compound-stmt?{ local-declaration statement-list} local-declarations ? empty {var- declaration}
statement-list?{statement}
statement?expression-stmt | compound-stmt | selection-stmt | iteration-stmt | return-stmt
expression-stmt? [expression];
selection-stmt?if (expression) statement [else statement]
iteration-stmt?while (expression)statement
return-stmt?return [expression];
expression? var = expression | simple-expression relop ? < = | < | > | > = | = = | ! =
var?ID | ID [expression]
simple-expression,>additive-expression{ relop additive-expression } additive-expression?term{addop term }
addop ? + | -
8
四川大学《编译原理课程设计》 学号2012141461017
term?factor{mulop factor }
mulop ?* | /
factor?(expression) | var | call | NUM call?ID( args )
args?arg-list | empty
arg-list? expression{, expression}
3 节点类型及定义
3.1节点类型
节点类型 描述 子节点 IntK Int型变量或返回值 无
VoidK void型变量或返回值 无
IdK 标示符id 无
ConstK 数值 无
Var_DeclK 变量声明 变量类型+变量名 Var_DeclK 数组声明 数组名+数组大小 FunK 函数声明 返回类型+函数名+参数列表+函数体 ParamsK FunK的参数列表 参数(如果有多个参数，则之间为兄弟节点)
ParamK FunK的参数 参数类型+参数名 CompK 复合语句体 变量声明列表+语句列表 Selection_StmtK if 条件表达式+IF体+[ELSE体] Iteration_StmtK while 条件表达式+循环体 Return_StmtK return [表达式]
AssignK 赋值 被赋值变量+赋值变量 OpK 运算 运算符左值+运算符右值 Arry_ElemK 数组元素 数组名+下标 CallK 函数调用 函数名+参数列表 ArgsK CallK的参数列表 [表达式]
UnkownK 未知节点 无
9
四川大学《编译原理课程设计》 学号2012141461017
3.2节点定义
typedef struct treeNode
{
struct treeNode * child[4];
struct treeNode * sibling;
int lineno;
NodeKind nodekind;
union { TokenType op; int val; const char * name;} attr;
ExpType type;
} TreeNode;
4 代码结构分析
文法 program?declaration-list
分析函数 TreeNode * parse(void)
说明 C-程序由一个声明序列组成，parse(void)函数首先执行getToken()然后直接调用
declaration_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()函数返回树节点，当前token为INT或VOID时，调用declaration()
返回之前树节点的兄弟节点。
TreeNode * declaration_list(void) 代码
{
TreeNode * t = declaration();
10
四川大学《编译原理课程设计》 学号2012141461017
TreeNode * p =t;
//程序以变量声明开始
while((token!=INT)&&(token!=VOID)&&(token!=ENDFILE))
{
syntaxError("开始不是类型声明");
token = getToken();
if(token==ENDFILE)
break;
}
while(token==INT||token==VOID)
{
TreeNode * q;
q = declaration();
if (q!=NULL)
{
if (t==NULL)
{
t=p=q;
}
else
{
p->sibling=q;
p=q;
}
}
}
match(ENDFILE);
return t;
}
文法 declaration?var-declaration|fun-declaration
var_declaration ?type-specifier ID; | type-specifier ID [NUM];
fun-declatation?type-specifier ID (params) | compound-stmt
type-specifier ? int | void
分析函数 TreeNode * declaration(void)
说明 首先判断类型，执行match函数， 匹配类型和ID，向前探测1个token的值确定是函数声明还是变量声明，如果token为’[’，则是数组变量声明，返回节点Array_DeclK, token
为’(’,则是函数声明，返回节点FunK, token为’;’则是普通变量声明，返回节点
11
四川大学《编译原理课程设计》 学号2012141461017
Var_DeclK
TreeNode * declaration(void) 代码
{
TreeNode * t = NULL;
TreeNode * p = NULL;
TreeNode * q = NULL;
TreeNode * s = NULL;
TreeNode * 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->attr.name = copyString(tokenString);
match(ID);
if (token==LPAREN)
{
t = newNode(FunK);
t->child[0] = p; //p是t子节点
t->child[1] = q;
match(LPAREN);
t->child[2] = params();
match(RPAREN);
t->child[3] = compound_stmt();
}
else if (token==LBRACKET)
12
四川大学《编译原理课程设计》 学号2012141461017
{
t = newNode(Var_DeclK);
a = newNode(Arry_DeclK);
t->child[0] = p; //p是t子节点
t->child[1] = a;
match(LBRACKET);
s = newNode(ConstK);
s->attr.val = atoi(tokenString);
match(NUM);
a->child[0]=q;
a->child[1]=s;
match(RBRACKET);
match(SEMI);
}
else if (token==SEMI)
{
t = newNode(Var_DeclK);
t->child[0] = p;
t->child[1] = q;
match(SEMI);
}
else
{
syntaxError("");
}
}
else
{
syntaxError("");
}
return t;
}
文法 params?param_list | void
分析函数 TreeNode * params(void)
说明 参数列表，根节点ParamsK，首先判断token是否是VOID，如果是VOID则匹配，判断下一
个token，如果是右括号，则参数列表中只有子节点VoidK，如果是ID，则子节点是
param_list,如果开始时token是INT,则参数列表子节点是param_list
13
四川大学《编译原理课程设计》 学号2012141461017
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->child[0] = p;
}
else//参数列表为(void id,[……])
{
t->child[0] = param_list(p);
}
}
else if (token==INT)
{
t->child[0] = param_list(p);
}
else
{
syntaxError("");
}
return t;
}
文法 param_list?param{, param}
分析函数 TreeNode * param_list(TreeNode * k)
说明 说明参数列表由param序列组成，并由逗号隔开。param_list(TreeNode * k)函数使用递归向
下分析方法直接调用param(TreeNode * k)函数，并返回树节点
TreeNode * param_list(TreeNode * k) 代码
{
TreeNode * t = param(k);
TreeNode * p = t;
k = NULL;//没有要传给param的VoidK，所以将k设为NULL
while (token==COMMA)
14
四川大学《编译原理课程设计》 学号2012141461017
{
TreeNode * q = NULL;
match(COMMA);
q = param(k);
if (q!=NULL)
{
if (t==NULL)
{
t=p=q;
}
else
{
p->sibling = q;
p = q;
}
}
}
return t;
}
文法 param? type-specifier ID{[ ]}
分析函数 TreeNode * param(TreeNode * k)
说明 探测token是INT还是VOID，决定子节点类型是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);
}
15
四川大学《编译原理课程设计》 学号2012141461017
else if (k!=NULL)
{
p = k;
}
if(p!=NULL)
{
t->child[0] = p;
if (token==ID)
{
q = newNode(IdK);
q->attr.name = copyString(tokenString);
t->child[1] = q;
match(ID);
}
else
{
syntaxError("");
}
if (token==LBRACKET&&(t->child[1]!=NULL))//@@@@@@@@@@@@
{
match(LBRACKET);
t->child[2] = newNode(IdK);
match(RBRACKET);
}
else
{
return t;
}
}
else
{
syntaxError("");
}
return t;
}
文法 compound-stmt?{ local-declaration statement-list}
分析函数 TreeNode * compound_stmt(void)
说明 复合语句，直接调用local_declaration()函数和statement_list()函数，产生两个子节
16
四川大学《编译原理课程设计》 学号2012141461017
点
TreeNode * compound_stmt(void) 代码
{
TreeNode * t = newNode(CompK);
match(LCBRACKET);
t->child[0] = local_declaration();
t->child[1] = 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;
while(token==INT || token==VOID)
{
p = newNode(Var_DeclK);
if(token==INT)
{
TreeNode * q1 = newNode(IntK);
p->child[0] = q1;
match(INT);
}
else if(token==VOID)
{
TreeNode * q1 = newNode(VoidK);
p->child[0] = q1;
match(INT);
}
if((p!=NULL)&&(token==ID))
{
17
四川大学《编译原理课程设计》 学号2012141461017
TreeNode * q2 = newNode(IdK);
q2->attr.name = copyString(tokenString);
p->child[1] = q2;
match(ID);
if(token==LBRACKET)
{
TreeNode * q3 = newNode(Var_DeclK);
p->child[3] = q3;
match(LBRACKET);
match(RBRACKET);
match(SEMI);
}
else if(token==SEMI)
{
match(SEMI);
}
else
{
match(SEMI);
}
}
else
{
syntaxError("");
}
if(p!=NULL)
{
if(t==NULL)
t = q = p;
else
{
q->sibling = p;
q = p;
}
}
}
return t;
}
18
四川大学《编译原理课程设计》 学号2012141461017
文法 statement-list?{statement}
分析函数 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 = statement();
if(q!=NULL)
{
if(t==NULL)
{
t = p = q;
}
else
{
p->sibling = q;
p = q;
}
}
}
return t;
}
文法 statement?expression-stmt| compound-stmt | selection-stmt | iteration-stmt
| return-stmt
分析函数 TreeNode * statement(void)
说明 statement由表达式或复合语句或if语句或while语句或return语句构成。
statement(void)函数通过判断先行Token类型确定到底是哪一种类型。如果是IF则调用
selection_statement()，如果是WHILE，则调用iteration_stmt()，如果是RETURN，则
调用return()，如果是左大括号，则是复合语句类型，如果是ID、SEMI、LPAREN、NUM，则是
表达式语句类型
19
四川大学《编译原理课程设计》 学号2012141461017
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:
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类型是否为分号，如果不是则直接调用函数expression()
TreeNode * expression_stmt(void) 代码
{
TreeNode * t = NULL;
if(token==SEMI)
{
match(SEMI);
return t;
20
四川大学《编译原理课程设计》 学号2012141461017
}
else
{
t = expression();
match(SEMI);
}
return t;
}
文法 expression? var = expression | simple-expression
分析函数 TreeNode * expression(void)
说明 expression(void)函数通过判断先行Token类型是否为ID，如果不是说明只能是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_expression(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->attr.name = ;
match(ASSIGN);
p->child[0] = t;
p->child[1] = expression();
return p;
}
21
四川大学《编译原理课程设计》 学号2012141461017
else //simple_expression中的var和call类型的情况
{
t = simple_expression(t);
}
}
return t;
}
文法 var?ID | ID [expression]
分析函数 TreeNode * var(void)
说明 创建IdK节点，判断先行token类型是否是中括号，如果是就创建Arry_ElemK节点，调用
expression()得到子节点
TreeNode * var(void) 代码
{
TreeNode * t = NULL;
TreeNode * p = NULL;
TreeNode * q = NULL;
if(token==ID)
{
p = newNode(IdK);
p->attr.name = copyString(tokenString);
match(ID);
if(token==LBRACKET)
{
match(LBRACKET);
q = expression();
match(RBRACKET);
t = newNode(Arry_ElemK);
t->child[0] = p;
t->child[1] = q;
}
else
{
t = p;
}
}
return t;
}
22
四川大学《编译原理课程设计》 学号2012141461017
文法 simple-expression,>additive-expression{ relop additive-expression }
relop ? < = | < | > | > = | = = | ! =
分析函数 TreeNode * simple_expression(TreeNode * k)
说明 simple_expression(TreeNode * k)函数先调用additive_expression(TreeNode * k)
函数返回一个节点，然后再一直判断后面的Token是否为<=、<、>、>=、==、!=，如果是则新建
OpK节点，然后令之前的节点为其第一个子节点，然后继续调用
additive_expression(TreeNode * k)函数返回一个节点，作为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->child[0] = t;
t = q;
match(token);
t->child[1] = additive_expression(k);
return t;
}
return t;
}
5 实验结果与分析
测试文本test.c
int a[10];
int min(int a[],int low,void a)
{
int k; int x; int i;
k=low;
while(i
0)
{
x=1;
}
}
return x;
}
测试结果
24
四川大学《编译原理课程设计》 学号2012141461017
成功实现语法分析
6 小结
通过这次实验，我加深了对语法分析的认识，掌握了递归向下分析方法，实现了对词法分析程序所提供的Token序列的语法检查和结构分析。
语法分析程序编写相对于词法分析要困难得多，首先要将BNF化为EBNF，运用递归向下的方法进行编写，构造出语法树，判别语法分析过程中是否出错以及出错位置和错误类型。虽然EBNF转换成代码的过程原理比较简单，但是操作起来比较繁琐。一开始我对TreeNode数据结构也不是很理解，通过阅读书后的tiny语言语法分析源代码，
我弄懂了语法树的输出。
25
四川大学《编译原理课程设计》 学号2012141461017
附录(源代码)
Main.c
#include "global.h"
#include "util.h"
#include "scan.h"
/* 全局变量 */
int lineno = 0;
/* 编译过程标志 */
int EchoSource = TRUE;
int TraceScan = TRUE;
int Error = FALSE;
int main(void)
{
TreeNode * syntaxTree;
char pgm[120]; /*用于存储文件名*/
printf("输入文件名:");
scanf("%s",pgm);
if (strchr (pgm, '.') == NULL)
{
strcat(pgm,".c");
}
source = fopen(pgm,"r");
if (source==NULL)
{
fprintf(stderr,"File %s not found\n",pgm);
exit(1);
}
listing = stdout; /* listing在屏幕上输出 */
fprintf(listing,"\nC COMPILATION: %s\n",pgm);
// while (getToken()!=ENDFILE)
// {
// ;
// }
syntaxTree = parse();
printTree(syntaxTree);
fclose(source);
return 0;
}
26
四川大学《编译原理课程设计》 学号2012141461017
Parse.h
#ifndef _PARSE_H_
#define _PARSE_H_
TreeNode * parse(void);
#endif
Parse.c
#include "global.h" #include "util.h"
#include "scan.h"
#include "parse.h" static TokenType token; /* holds current token */
TreeNode * parse(void);
TreeNode * declaration_list(void); TreeNode * declaration(void);
TreeNode * params(void);
TreeNode * param_list(TreeNode * k); TreeNode * param(TreeNode * k); TreeNode * compound_stmt(void); TreeNode * local_declaration(void); TreeNode * statement_list(void); TreeNode * statement(void);
TreeNode * expression_stmt(void); TreeNode * selection_stmt(void); TreeNode * iteration_stmt(void); TreeNode * return_stmt(void);
TreeNode * expression(void);
TreeNode * var(void);
TreeNode * simple_expression(TreeNode * k); TreeNode * additive_expression(TreeNode * k); TreeNode * term(TreeNode * k);
TreeNode * factor(TreeNode * k); TreeNode * call(TreeNode * k);
TreeNode * args(void);
static void syntaxError(char * message) {
fprintf(listing,"\n>>> ");
fprintf(listing,"Syntax error at line %d: %s",lineno,message);
27
四川大学《编译原理课程设计》 学号2012141461017
Error = TRUE;
}
static void match(TokenType expected) {
if (token == expected)
token = getToken();
else
{
syntaxError("unexpected token -> ");
printToken(token,tokenString);
fprintf(listing," ");
}
}
TreeNode * parse(void)
{
TreeNode * t;
token = getToken();
t = declaration_list();
if(token!=ENDFILE)
{
syntaxError("endfile_error");
}
return t;
}
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==VOID)
28
四川大学《编译原理课程设计》 学号2012141461017
{
TreeNode * q;
q = declaration();
if (q!=NULL)
{
if (t==NULL)
{
t=p=q;
}
else
{
p->sibling=q;
p=q;
}
}
}
match(ENDFILE);
return t;
}
TreeNode * declaration(void) {
TreeNode * t = NULL;
TreeNode * p = NULL;
TreeNode * q = NULL;
TreeNode * s = NULL;
TreeNode * a = NULL;
if (token==INT)
{
p=newNode(IntK);
match(INT);
}
else if (token==VOID)
{
p=newNode(VoidK);
match(VOID);
}
else
29
四川大学《编译原理课程设计》 学号2012141461017
{
syntaxError("类型错误");
}
if(p!=NULL&&token==ID)
{
q = newNode(IdK);
q->attr.name = copyString(tokenString);
match(ID);
if (token==LPAREN)
{
t = newNode(FunK);
t->child[0] = p; //p是t子节点
t->child[1] = q;
match(LPAREN);
t->child[2] = params();
match(RPAREN);
t->child[3] = compound_stmt();
}
else if (token==LBRACKET)
{
t = newNode(Var_DeclK);
a = newNode(Arry_DeclK);
t->child[0] = p; //p是t子节点
t->child[1] = a;
match(LBRACKET);
s = newNode(ConstK);
s->attr.val = atoi(tokenString);
match(NUM);
a->child[0]=q;
a->child[1]=s;
match(RBRACKET);
match(SEMI);
}
else if (token==SEMI)
{
t = newNode(Var_DeclK);
t->child[0] = p;
t->child[1] = q;
30
四川大学《编译原理课程设计》 学号2012141461017
match(SEMI);
}
else
{
syntaxError("");
}
}
else
{
syntaxError("");
}
return t;
}
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->child[0] = p;
}
else//参数列表为(void id,[……])
{
t->child[0] = param_list(p);
}
}
else if (token==INT)
{
t->child[0] = param_list(p);
}
else
{
syntaxError("");
31
四川大学《编译原理课程设计》 学号2012141461017
}
return t;
}
TreeNode * param_list(TreeNode * k) {
TreeNode * t = param(k);
TreeNode * p = t;
k = NULL;//没有要传给param的VoidK，所以将k设为NULL
while (token==COMMA)
{
TreeNode * q = NULL;
match(COMMA);
q = param(k);
if (q!=NULL)
{
if (t==NULL)
{
t=p=q;
}
else
{
p->sibling = q;
p = q;
}
}
}
return t;
}
TreeNode * param(TreeNode * k) {
TreeNode * t = newNode(ParamK);
TreeNode * p = NULL;
TreeNode * q = NULL;
if(k==NULL&&token==VOID)
{
p = newNode(VoidK);
match(VOID);
}
32
四川大学《编译原理课程设计》 学号2012141461017
else if(k==NULL&&token==INT)
{
p = newNode(IntK);
match(INT);
}
else if (k!=NULL)
{
p = k;
}
if(p!=NULL)
{
t->child[0] = p;
if (token==ID)
{
q = newNode(IdK);
q->attr.name = copyString(tokenString);
t->child[1] = q;
match(ID);
}
else
{
syntaxError("");
}
if (token==LBRACKET&&(t->child[1]!=NULL))//@@@@@@@@@@@@
{
match(LBRACKET);
t->child[2] = newNode(IdK);
match(RBRACKET);
}
else
{
return t;
}
}
else
{
syntaxError("");
}
return t;
}
33
四川大学《编译原理课程设计》 学号2012141461017
TreeNode * compound_stmt(void) {
TreeNode * t = newNode(CompK);
match(LCBRACKET);
t->child[0] = local_declaration();
t->child[1] = statement_list();
match(RCBRACKET);
return t;
}
TreeNode * local_declaration(void) {
TreeNode * t = NULL;
TreeNode * q = NULL;
TreeNode * p = NULL;
while(token==INT || token==VOID)
{
p = newNode(Var_DeclK);
if(token==INT)
{
TreeNode * q1 = newNode(IntK);
p->child[0] = q1;
match(INT);
}
else if(token==VOID)
{
TreeNode * q1 = newNode(VoidK);
p->child[0] = q1;
match(INT);
}
if((p!=NULL)&&(token==ID))
{
TreeNode * q2 = newNode(IdK);
q2->attr.name = copyString(tokenString);
p->child[1] = q2;
match(ID);
if(token==LBRACKET)
34
四川大学《编译原理课程设计》 学号2012141461017
{
TreeNode * q3 = newNode(Var_DeclK);
p->child[3] = q3;
match(LBRACKET);
match(RBRACKET);
match(SEMI);
}
else if(token==SEMI)
{
match(SEMI);
}
else
{
match(SEMI);
}
}
else
{
syntaxError("");
}
if(p!=NULL)
{
if(t==NULL)
t = q = p;
else
{
q->sibling = p;
q = p;
}
}
}
return t;
}
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)
{
35
四川大学《编译原理课程设计》 学号2012141461017
TreeNode * q;
q = statement();
if(q!=NULL)
{
if(t==NULL)
{
t = p = q;
}
else
{
p->sibling = q;
p = q;
}
}
}
return t;
}
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:
t = compound_stmt();
break;
case ID: case SEMI: case LPAREN: case NUM:
t = expression_stmt();
break;
default:
syntaxError("");
token = getToken();
36
四川大学《编译原理课程设计》 学号2012141461017
break;
}
return t;
}
TreeNode * selection_stmt(void) {
TreeNode * t = newNode(Selection_StmtK);
match(IF);
match(LPAREN);
if(t!=NULL)
{
t->child[0] = expression();
}
match(RPAREN);
t->child[1] = statement();
if(token==ELSE)
{
match(ELSE);
if(t!=NULL)
{
t->child[2] = statement();
}
}
return t;
}
TreeNode * expression_stmt(void) {
TreeNode * t = NULL;
if(token==SEMI)
{
match(SEMI);
return t;
}
else
{
t = expression();
match(SEMI);
}
return t;
37
四川大学《编译原理课程设计》 学号2012141461017
}
TreeNode * iteration_stmt(void) {
TreeNode * t = newNode(Iteration_StmtK);
match(WHILE);
match(LPAREN);
if(t!=NULL)
{
t->child[0] = expression();
}
match(RPAREN);
if(t!=NULL)
{
t->child[1] = statement();
}
return t;
}
TreeNode * return_stmt(void) {
TreeNode * t = newNode(Return_StmtK);
match(RETURN);
if (token==SEMI)
{
match(SEMI);
return t;
}
else
{
if(t!=NULL)
{
t->child[0] = expression();
}
}
match(SEMI);
return t;
}
TreeNode * expression(void)
38
四川大学《编译原理课程设计》 学号2012141461017
{
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->attr.name = ;
match(ASSIGN);
p->child[0] = t;
p->child[1] = expression();
return p;
}
else //simple_expression中的var和call类型的情况
{
t = simple_expression(t);
}
}
return t;
}
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->child[0] = t;
t = q;
match(token);
t->child[1] = additive_expression(k);
return t;
}
return t;
39
四川大学《编译原理课程设计》 学号2012141461017
}
TreeNode * additive_expression(TreeNode * k) {
TreeNode * t = term(k);
k = NULL;
while((token==PLUS)||(token==MINUS))
{
TreeNode * q = newNode(OpK);
q->attr.op = token;
q->child[0] = t;
match(token);
q->child[1] = term(k);
t = q;
}
return t;
}
TreeNode * term(TreeNode * k) {
TreeNode * t = factor(k);
k = NULL;
while((token==TIMES)||(token==OVER))
{
TreeNode * q = newNode(OpK);
q->attr.op = token;
q->child[0] = t;
t = q;
match(token);
q->child[1] = factor(k);
}
return t;
}
TreeNode * factor(TreeNode * k) {
TreeNode * t = NULL;
if(k!=NULL)//k为上面传下来的已经解析出来的以ID开头的var,可能为call或var
{
if(token==LPAREN && k->nodekind!=Arry_ElemK) //call
{
40
四川大学《编译原理课程设计》 学号2012141461017
t = call(k);
}
else
{
t = k;
}
}
else//没有从上面传下来的var
{
switch(token)
{
case LPAREN:
match(LPAREN);
t = expression();
match(RPAREN);
break;
case ID:
k = var();
if(LPAREN==token && k->nodekind!=Arry_ElemK)
{
t = call(k);
}
break;
case NUM:
t = newNode(ConstK);
if((t!=NULL)&&(token==NUM))
{
t->attr.val = atoi(tokenString);
}
match(NUM);
break;
default:
syntaxError("");
token = getToken();
break;
}
}
return t;
}
TreeNode * var(void)
41
四川大学《编译原理课程设计》 学号2012141461017
{
TreeNode * t = NULL;
TreeNode * p = NULL;
TreeNode * q = NULL;
if(token==ID)
{
p = newNode(IdK);
p->attr.name = copyString(tokenString);
match(ID);
if(token==LBRACKET)
{
match(LBRACKET);
q = expression();
match(RBRACKET);
t = newNode(Arry_ElemK);
t->child[0] = p;
t->child[1] = q;
}
else
{
t = p;
}
}
return t;
}
TreeNode * call(TreeNode * k)
{
TreeNode * t = newNode(CallK);
if(k!=NULL)
t->child[0] = k;
match(LPAREN);
if(token==RPAREN)
{
match(RPAREN);
return t;
}
else if(k!=NULL)
{
t->child[1] = args();
42
四川大学《编译原理课程设计》 学号2012141461017
match(RPAREN);
}
return t;
}
TreeNode * args(void) {
TreeNode * t = newNode(ArgsK);
TreeNode * s = NULL;
TreeNode * p = NULL;
if(token!=RPAREN)
{
s = expression();
p = s;
while(token==COMMA)
{
TreeNode * q;
match(COMMA);
q = expression();
if(q!=NULL)
{
if(s==NULL)
{
s = p = q;
}
else
{
p->sibling = q;
p = q;
}
}
}
}
if(s!=NULL)
{
t->child[0] = s;
}
return t;
}
Scan.h
43
四川大学《编译原理课程设计》 学号2012141461017
#ifndef _SCAN_H_
#define _SCAN_H_
#define MAXTOKENLEN 40 extern char tokenString[MAXTOKENLEN+1]; TokenType getToken(void);
#endif
Scan.c
#include "global.h"
#include "util.h"
#include "scan.h"
typedef enum
{
START,INCOMPARE,INCOMMENT,INCOMMENT2,INOPERATE,INNUM,INNUM2,INID,INCHAR,INSTRING
,DONE
} StateType;
char tokenString[MAXTOKENLEN+1];
#define BUFLEN 256
TokenType doubleOp;
static int quote;
static char lineBuf[BUFLEN]; /* 整行代码缓冲去 */ static int linepos = 0; /* 在一行中的位置 */ static int bufsize = 0; /* 缓冲大小 */ static int EOF_flag = FALSE; /* 文件结束标志*/ /* 读取下一个字符 */
static int getNextChar(void)
{
if (!(linepos < bufsize))
{
lineno++;
if (fgets(lineBuf,BUFLEN-1,source))
{
fprintf(listing,"%4d: %s",lineno,lineBuf);
bufsize = strlen(lineBuf);
linepos = 0;
return lineBuf[linepos++];
}
else
44
四川大学《编译原理课程设计》 学号2012141461017
{
EOF_flag = TRUE;
return EOF;
}
}
else
{
return lineBuf[linepos++];
}
}
/* 退回一个字符 */
static void ungetNextChar(void)
{
if (!EOF_flag)
{
linepos-- ;
}
}
/* 保留字结构体 */
static struct
{
char* str;
TokenType tok;
} reservedWords[MAXRESERVED]
=
{
{"auto",AUTO},{"break",BREAK},{"case",CASE},{"char",CHAR},{"const",CONST},
{"continue",CONTINUE},{"default",DEFAULT},{"do",DO},{"double",
DOUBLE},{"else",ELSE},
{"enum",ENUM},{"extern",EXTERN}, {"float",FLOAT} , {"for",FOR} ,
{"goto",GOTO},
{"if",IF}, {"int",INT},{"long",LONG}, {"register",REGISTER} ,
{"return",RETURN},
{"short",SHORT}, {"signed",SIGNED},{"sizeof" ,SIZEOF} ,
{"static" ,STATIC},{"struct", STRUCT} ,
{"switch", SWITCH},{"typedef", TYPEDEF},{"union", UNION },{"unsigned" ,UNSIGNED},{"void",VOID},
{"volatile",VOLATILE},{"while", WHILE} };
/* 查找保留字 */
45
四川大学《编译原理课程设计》 学号2012141461017
static TokenType reservedLookup (char * s)
{
int i;
for (i=0; i'||c == '<'||c == '!'||c == '=')
{
state = INCOMPARE;
switch(c)
46
四川大学《编译原理课程设计》 学号2012141461017
{
case '<':
doubleOp = LT;
break;
case '>':
doubleOp = GT;
break;
case '=':
doubleOp = EQ;
break;
case '!':
doubleOp = NEQ;
break;
}
}
else if (c == '+'||c == '-'||c == '*')
{
state = INOPERATE;
switch(c)
case '+':
doubleOp = PLUS;
break;
case '-':
doubleOp = MINUS;
break;
case '*':
doubleOp = TIMES;
break;
}
else if (c == 34||c == 39) /*引号*/
{
save=FALSE;
if (c==34)
{
state = INSTRING;
quote=34;
}
if (c==39)
{
state = INCHAR;
quote=39;
47
四川大学《编译原理课程设计》 学号2012141461017
}
}
else if ((c == ' ') || (c == '\t') || (c == '\n'))
{
save = FALSE;
}
else if (c == '/')
{
c = getNextChar();
if (c=='*')
{
save = FALSE;
state = INCOMMENT;
}
else
{
ungetNextChar();
currentToken = OVER;
}
}
else
{
state = DONE;
switch (c)
{
case EOF:
save = FALSE;
currentToken = ENDFILE;
break;
case '(':
currentToken = LPAREN;
break;
case ')':
currentToken = RPAREN;
break;
case ';':
currentToken = SEMI;
break;
case ':':
currentToken = COLON;
break;
48
四川大学《编译原理课程设计》 学号2012141461017
case ',':
currentToken = COMMA;
break;
case '[':
currentToken = LBRACKET;
break;
case ']':
currentToken = RBRACKET;
break;
case '{':
currentToken = LCBRACKET;
break;
case '}':
currentToken = RCBRACKET;
break;
default:
currentToken = ERROR;
break;
}
}
break;
case INCOMMENT:
save = FALSE;
switch(c)
{
case '*':
state = INCOMMENT2;
break;
default:
state = INCOMMENT;
break;
}
break;
break;
case INCOMMENT2:
save = FALSE;
switch(c)
{
case '*':
state = INCOMMENT2;
break;
49
四川大学《编译原理课程设计》 学号2012141461017
case '/':
state=START;
break;
default:
state=INCOMMENT;
break;
}
break;
case INCOMPARE:
state = DONE;
if (c == '=')
{
if (doubleOp==LT)
{
currentToken = LEQ;
}
if (doubleOp==GT)
{
currentToken = GEQ;
}
if (doubleOp==EQ)
{
currentToken = EQ;
}
if (doubleOp==NEQ)
{
currentToken = NEQ;
}
}
else
{
/* backup in the input */
ungetNextChar();
save = FALSE;
currentToken = ASSIGN;
}
break;
case INOPERATE:
state = DONE;
if (c == '=')
{
50
四川大学《编译原理课程设计》 学号2012141461017
if (doubleOp==PLUS)
{
currentToken = PLUSASSIGN;
}
if (doubleOp==MINUS)
{
currentToken = MINUSASSIGN;
}
if (doubleOp==TIMES)
{
currentToken = TIMESASSIGN;
}
}
else if(doubleOp == PLUS &&c == '+')
{
currentToken = SELFPLUS;
}
else if(doubleOp == MINUS &&c == '-')
{
currentToken = SELFPLUS;
}
else
{
ungetNextChar();
save=FALSE;
currentToken=doubleOp;
}
break;
case INCHAR:
switch(c)
{
case EOF:
state = DONE;
currentToken = ENDFILE;
break;
case 39:
if (quote==39)
{
save=FALSE;
state=DONE;
currentToken=CHARACTER;
51
四川大学《编译原理课程设计》 学号2012141461017
}
break;
}
break;
case INSTRING:
switch(c)
{
case EOF:
state = DONE;
currentToken = ENDFILE;
break;
case 34:
if (quote==34)
{
save=FALSE;
state=DONE;
currentToken=STRING;
}
break;
}
break;
case INNUM:
if (!isdigit(c)&&c!='.')
{
/* backup in the input */
ungetNextChar();
save = FALSE;
state = DONE;
currentToken = NUM;
}
if (c=='.')
{
state = INNUM2;
currentToken = NUM;
}
break;
case INNUM2:
if (!isdigit(c))
{
/* backup in the input */
ungetNextChar();
52
四川大学《编译原理课程设计》 学号2012141461017
save = FALSE;
state = DONE;
currentToken = NUM;
}
break;
case INID:
if (!(isalpha(c)||isdigit(c)||c=='_'))
{
/* backup in the input */
ungetNextChar();
save = FALSE;
state = DONE;
currentToken = ID;
}
break;
case DONE:
default: /* should never happen */
fprintf(listing,"Scanner Bug: state= %d\n",state);
state = DONE;
currentToken = ERROR;
break;
}
if ((save) && (tokenStringIndex <= MAXTOKENLEN))
{
tokenString[tokenStringIndex++] = (char) c;
}
if (state == DONE)
{
tokenString[tokenStringIndex] = '\0';
if (currentToken == ID)
{
currentToken = reservedLookup(tokenString);
}
}
}
// fprintf(listing,"\t%d: ",lineno);
// printToken(currentToken,tokenString);
return currentToken;
53
四川大学《编译原理课程设计》 学号2012141461017
}
Global.h
#ifndef _GLOBAL_H_
#define _GLOBAL_H_
#include
#include
#include
#include
#ifndef FALSE
#define FALSE 0
#endif
#ifndef TRUE
#define TRUE 1
#endif
//保留字数量
#define MAXRESERVED 32
typedef enum
//tokens:
{
//错误、结束
ENDFILE,ERROR,
//保留字else、if、int、return、void、while
//ELSE,IF,INT,RETURN,VOID,WHILE,
AUTO,BREAK , CASE , CHAR , CONST ,
CONTINUE , DEFAULT , DO , DOUBLE , ELSE,
ENUM , EXTERN , FLOAT , FOR , GOTO,
IF , INT , LONG , REGISTER , RETURN,
SHORT , SIGNED , SIZEOF , STATIC , STRUCT ,
SWITCH , TYPEDEF , UNION , UNSIGNED , VOID,
VOLATILE , WHILE,
//num、id
ID,NUM,CHARACTER,STRING,
//符号+、-、*、/、++、--、+=、-=、*=、<、<=、>、>=、==、!=、=、;、,、(、)、[、]、{、}、
/*、*/、:
PLUS,MINUS,TIMES,OVER,SELFPLUS,SELFMINUS,PLUSASSIGN,MINUSASSIGN,TIMESASSIGN,LT,L
EQ,GT,GEQ,EQ,NEQ,ASSIGN,SEMI,COMMA,LPAREN,
RPAREN,LBRACKET,RBRACKET,LCBRACKET,RCBRACKET,LCOMMENT,RCOMMENT,COLON
} TokenType;
FILE* source;
54
四川大学《编译原理课程设计》 学号2012141461017
FILE* listing;
FILE* code;
extern int lineno;
/************************************************************************/ /*语法分析 */ /************************************************************************/
typedef enum {IntK, IdK, VoidK, ConstK, Var_DeclK, Arry_DeclK, FunK, ParamsK, ParamK, CompK, Selection_StmtK, Iteration_StmtK, Return_StmtK, AssignK, OpK, Arry_ElemK, CallK, ArgsK, UnkownK} NodeKind;
typedef enum {Void,Integer} ExpType;
//const int max_child = 4;
//treeNode定义 包括子节点、兄弟节点、所处行号、节点类型、属性、表达式返回类型 typedef struct treeNode
{
struct treeNode * child[4];
struct treeNode * sibling;
int lineno;
NodeKind nodekind;
//union {StmtKind stmt,ExpT };
union { TokenType op; int val; const char * name;} attr;
ExpType type;
} TreeNode;
extern int Error;
#endif
Util.h
#ifndef _UTIL_H_
#define _UTIL_H_
void printToken(TokenType,const char*);
char* copyString(char *);
55
四川大学《编译原理课程设计》 学号2012141461017
TreeNode * newNode(NodeKind kind); void printTree( TreeNode * ); #endif
Util.c
#include "global.h" #include "util.h"
//extern const int MAXCHILDREN;
void printToken(TokenType token,const char* tokenString)
{
switch(token)
{
case AUTO:
case BREAK:
case CASE:
case CHAR:
case CONST:
case CONTINUE:
case DEFAULT:
case DO:
case DOUBLE:
case ELSE:
case ENUM:
case EXTERN:
case FLOAT:
case FOR:
case GOTO:
case IF:
case INT:
case LONG:
case REGISTER:
case RETURN:
case SHORT:
case SIGNED:
case SIZEOF:
case STATIC:
case STRUCT:
case SWITCH:
case TYPEDEF:
56
四川大学《编译原理课程设计》 学号2012141461017
case UNION:
case UNSIGNED:
case VOID:
case VOLATILE:
case WHILE:
fprintf(listing,"reserved word:%s\n",tokenString);
break;
case PLUS:
fprintf(listing,"+\n");
break;
case MINUS:
fprintf(listing,"-\n");
break;
case TIMES:
fprintf(listing,"*\n");
break;
case OVER:
fprintf(listing,"/\n");
break;
case SELFPLUS:
fprintf(listing,"++\n");
break;
case SELFMINUS:
fprintf(listing,"--\n");
break;
case PLUSASSIGN:
fprintf(listing,"+=\n");
break;
case MINUSASSIGN:
fprintf(listing,"-=\n");
break;
case TIMESASSIGN:
fprintf(listing,"*=\n");
break;
case LT:
fprintf(listing,"<\n");
break;
case LEQ:
fprintf(listing,"<=\n");
break;
case GT:
57
四川大学《编译原理课程设计》 学号2012141461017
fprintf(listing,">\n");
break;
case GEQ:
fprintf(listing,">=\n");
break;
case EQ:
fprintf(listing,"==\n");
break;
case NEQ:
fprintf(listing,"!=\n");
break;
case ASSIGN:
fprintf(listing,"=\n");
break;
case SEMI:
fprintf(listing,";\n");
break;
case COMMA:
fprintf(listing,",\n");
break;
case COLON:
fprintf(listing,":\n");
break;
case LPAREN:
fprintf(listing,"(\n");
break;
case RPAREN:
fprintf(listing,")\n");
break;
case LBRACKET:
fprintf(listing,"[\n");
break;
case RBRACKET:
fprintf(listing,"]\n");
break;
case LCBRACKET:
fprintf(listing,"{\n");
break;
case RCBRACKET:
fprintf(listing,"}\n");
break;
58
四川大学《编译原理课程设计》 学号2012141461017
case LCOMMENT:
fprintf(listing,"/*\n");
break;
case RCOMMENT:
fprintf(listing,"*/\n");
break;
case ENDFILE:
fprintf(listing,"EOF\n");
break;
case ID:
fprintf(listing,"ID,name= %s\n",tokenString);
break;
case CHARACTER:
fprintf(listing,"CHARACTER,val= %s\n",tokenString);
break;
case STRING:
fprintf(listing,"STRING,val= %s\n",tokenString);
break;
case NUM:
fprintf(listing,"NUM,val= %s\n",tokenString);
break;
case ERROR:
fprintf(listing,"ERROR: %s\n",tokenString);
break;
default:
fprintf(listing,"Unknown token:%d\n",token);
break;
}
}
TreeNode * newNode(NodeKind kind)
{
TreeNode * t = (TreeNode *) malloc(sizeof(TreeNode));
int i;
if (t==NULL)
fprintf(listing,"Out of memory error at line %d\n",lineno);
else {
for (i=0;i<4;i++)
t->child[i] = NULL;
t->sibling = NULL;
t->nodekind = kind;
59
四川大学《编译原理课程设计》 学号2012141461017
t->lineno = lineno;
if (kind==OpK||kind==IntK||kind==IdK)
{
if(kind==IdK)
t->attr.name = "";
t->type=Integer;
}
if(kind==ConstK)
t->attr.val = 0;
}
return t;
}
static indentno = 0;
#define INDENT indentno+=2 #define UNINDENT indentno-=2
static void printSpaces(void) {
int i;
for (i=0;inodekind)
{
case VoidK:
fprintf(listing,"Void\n");
break;
case IntK:
fprintf(listing,"Int\n");
break;
60
四川大学《编译原理课程设计》 学号2012141461017
case IdK:
fprintf(listing,"ID:%s\n",tree->attr.name);
break;
case ConstK:
fprintf(listing,"Const:%d\n",tree->attr.val);
break;
case Var_DeclK:
fprintf(listing,"Var_Decl\n");
break;
case Arry_DeclK:
fprintf(listing,"Arry_Decl\n");
break;
case FunK:
fprintf(listing,"Fun\n");
break;
case ParamsK:
fprintf(listing,"Params\n");
break;
case ParamK:
fprintf(listing,"Param\n");
break;
case CompK:
fprintf(listing,"Comp\n");
break;
case Selection_StmtK:
fprintf(listing,"If\n");
break;
case Iteration_StmtK:
fprintf(listing,"While\n");
break;
case Return_StmtK:
fprintf(listing,"Return\n");
break;
case AssignK:
fprintf(listing,"Assign\n");
break;
case OpK:
fprintf(listing,"Op:\n");
printToken(tree->attr.op,"\0");
break;
case Arry_ElemK:
61
四川大学《编译原理课程设计》 学号2012141461017
fprintf(listing,"Arry_Elem\n");
break;
case CallK:
fprintf(listing,"Call\n");
break;
case ArgsK:
fprintf(listing,"Arg_s\n");
break;
default:
fprintf(listing,"Unknown node kind\n");
break;
}
//else fprintf(listing,"Unknown node kind\n");
for (i=0;i<4;i++)
printTree(tree->child[i]);
tree = tree->sibling;
}
UNINDENT;
}
char * copyString(char * s) {
int n;
char * t;
if (s==NULL) return NULL;
n = strlen(s)+1;
t = malloc(n);
if (t==NULL)
fprintf(listing,"Out of memory error at line %d\n",lineno);
else strcpy(t,s);
return t;
}
62
浙公网安备 33021202002483