精品C语言词法分析器和C语言语法分析器编译原理毕业论文.docx
《精品C语言词法分析器和C语言语法分析器编译原理毕业论文.docx》由会员分享，可在线阅读，更多相关《精品C语言词法分析器和C语言语法分析器编译原理毕业论文.docx（83页珍藏版）》请在冰点文库上搜索。
精品C语言词法分析器和C语言语法分析器编译原理毕业论文
《编译原理课程设计》课程报告
题目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,
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+”
3Token定义
3.1token类型
保留字
autobreakcasecharconst
continuedefaultdodoubleelse
enumexternfloatforgoto
ifintlongredisterreturn
shortsignedsizeofstaticstruct
switchtypedefunionunsignedvoid
volatilewhile
特殊符号
+-*++--+=-=*=<<=>>===!
==;,（）[]{}**:
文件结束、错误
EOFERROR
其它token
NUMIDCHARACTERSTRING
3.2tokenType类型代码
4DFA设计
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状态
●在状态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
5代码结构分析
5.1主要结构
词法分析部分的代码在scan.c和scan..c中的getToken（）函数对源文件进行词法分析。
5.2函数和成员变量的作用和含义
voidprintToken（TokenType,constchar*）;*输出token*
char*copyString（char*）;*字符串复制*
TokenTypegetToken（void）;*词法分析函数*
staticintgetNextChar（void）*获取下一个字符*
staticvoidungetNextChar（void）*退回一个字符*
staticTokenTypereservedLookup（char*s）*查找对应的保留字*
chartokenString[MAXTOKENLEN+1];*token字符串*
intlineno=0;*当前行号*
staticcharlineBuf[BUFLEN];*整行代码缓冲区*
staticintlinepos=0;*当前行的位置*
staticintbufsize=0;*缓冲区大小*
staticintEOF_flag=FALSE;*文件结束标志*
6实验结果与分析
6.1测试文件test.c
*test.c*
intmain（void）
{
###
inta=0;
floatb=20.1;
charc[]="abcdefg";
chard='h';
if（a>=2）
{
b+=0.1
a++;
}
}
6.2测试结果
6.3结果分析
test.c文件中包括注释，保留字，整数和小数，标识符，特殊符号，字符串以及错误输入。
本程序成功对test.c文件进行了词法分析，对注释进行了忽略，输出了相应的行号、类型、取值，对于错误的输入显示ERROR。
7小结
通过编写C语言词法分析器，我对编译器的基本原理有了更深的认识，同时掌握了DFA的设计与实现。
在最开始的编写过程中，我总是把词法和语法分析混淆，比如一些错误应该在语法分析中判断，我却写进了词法分析中，后来我逐步认识到词法分析的作用就是提取源代码中的Token。
在DFA的实现过程中，我主要参考了书后tiny语言DFA的实现方法，将它扩展到C语言。
另外C语言词法比较复杂，因为时间关系我省略了一些，比如位运算符，转义字符等等，希望今后能完善。
C-语言语法分析器
1实验目的及意义
用C语言编制TinyC-语言的语法分析程序，实现对词法分析程序所提供的Token序列的语法检查和结构分析。
2文法规则（EBNF）
program→declaration-list
declaration_list→declaration{declaration}
declaration→var-declaration|fun-declaration
var_declaration→type-specifierID;|type-specifierID[NUM];
type-specifier→int|void
fun-declatation→type-specifierID（params）|compound-stmt
params→param_list|void
param_list→param{,param}
param→type-specifierID{[]}
compound-stmt→{local-declarationstatement-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[elsestatement]
iteration-stmt→while（expression）statement
return-stmt→return[expression];
expression→var=expression|simple-expression
relop→<=|<|>|>=|==|!
=
var→ID|ID[expression]
simple-expression－>additive-expression{relopadditive-expression}
additive-expression→term{addopterm}
addop→+|-
term→factor{mulopfactor}
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
未知节点
无
3.2节点定义
typedefstructtreeNode
{
structtreeNode*child[4];
structtreeNode*sibling;
intlineno;
NodeKindnodekind;
union{TokenTypeop;intval;constchar*name;}attr;
ExpTypetype;
}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（"endfileerror"）;
}
returnt;
}
文法
declaration_list→declaration{declaration}
分析函数
TreeNode*declaration_list（void）
说明
声明序列是由若干声明构成，declaration_list（void）函数中直接调用declaration（）函数返回树节点，当前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（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）;
returnt;
}
文法
declaration→var-declaration|fun-declaration
var_declaration→type-specifierID;|type-specifierID[NUM];
fun-declatation→type-specifierID（params）|compound-stmt
type-specifier→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;
TreeNode*a=NULL;
if（token==INT）
{
p=newNode（IntK）;
match（INT）;
}
elseif（token==VOID）
{
p=newNode（VoidK）;
match（VOID）;
}
else
{
syntaxError（"typeerror"）;
}
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（）;
}
elseif（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）;
}
elseif（token==SEMI）
{
t=newNode（Var_DeclK）;
t->child[0]=p;
t->child[1]=q;
match（SEMI）;
}
else
{
syntaxError（""）;
}
}
else
{
syntaxError（""）;
}
returnt;
}
文法
params→param_list|void
分析函数
TreeNode*params（void）
说明
参数列表，根节点ParamsK，首先判断token是否是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->child[0]=p;
}
else参数列表为（voidid,[……]）
{
t->child[0]=param_list（p）;
}
}
elseif（token==INT）
{
t->child[0]=param_list（p）;
}
else
{
syntaxError（""）;
}
returnt;
}
文法
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）
{
TreeNode*q=NULL;
match（COMMA）;
q=param（k）;
if（q!
=NULL）
{
if（t==NULL）
{
t=p=q;
}
else
{
p->sibling=q;
p=q;
}
}
}
returnt;
}
文法
param→type-specifierID{[]}
分析函数
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）
升级会员 