四川大学计算机学院-C-语言编译器-编译原理课程设计报告内附源码-递归下降-c-minus.doc
- 文档编号:18952562
- 上传时间:2024-09-13
- 格式:DOC
- 页数:73
- 大小:904.04KB
四川大学计算机学院-C-语言编译器-编译原理课程设计报告内附源码-递归下降-c-minus.doc
《四川大学计算机学院-C-语言编译器-编译原理课程设计报告内附源码-递归下降-c-minus.doc》由会员分享,可在线阅读,更多相关《四川大学计算机学院-C-语言编译器-编译原理课程设计报告内附源码-递归下降-c-minus.doc(73页珍藏版)》请在冰点文库上搜索。
《编译原理课程设计报告》计算机学院计科x班xxx094304xxxx
编译原理课程设计报告
课题名称:
C-词法扫描器及语法分析器实现
提交文档学生姓名:
XXX
提交文档学生学号:
0943041XXX
同组成员名单:
无
指导教师姓名:
张兵
指导教师评阅成绩:
指导教师评阅意见:
.
.
提交报告时间:
2012年6月2日
目录
1课程设计目标 3
2分析与设计 4
2.1程序结构 4
2.2程序流程 5
3词法分析 6
3.1代码结构分析 6
3.2Token定义 7
3.2.1Token的定义和类型 7
3.2.2Token的种别码 7
3.3DAF分析 8
3.3.1删除注释DFA 8
3.3.2词法分析DFA 10
4语法分析 14
4.1代码结构分析 14
4.2节点定义 15
4.2.1节点定义和类型 15
4.2.2各类型节点的描述 16
4.3递归向下语法分析 16
4.3.1C-文法 16
4.3.2递归向下分析过程 17
5测试结果 34
5.1流程 34
5.2词法分析结果 34
5.3词法分析出错 38
5.4语法分析结果 39
5.5语法分析出错 41
6总结 42
6.1词法分析编写过程 42
6.2语法分析编写过程 43
6.3成果和收获 43
7附录 44
7.1scanner.h源文件 44
7.2scanner.cpp源文件 45
7.3parser.h源文件 55
7.4parser.cpp源文件 56
1课程设计目标
学生在学习《编译原理》课程过程中,结合各章节的构造编译程序的基本理论,要求用C或C++语言描述及上机调试,实现一个C-Minus小编译程序(包括词法分析,语法分析等重要子程序),使学生将理论与实际应用结合起来,受到软件设计等开发过程的全面训练,从而提高学生软件开发的能力。
要求:
(1)设计词法分析器
设计各单词的状态转换图,并为不同的单词设计种别码。
将词法分析器设计成供语法分析器调用的子程序。
功能包括:
a.具备预处理功能。
将不翻译的注释等符号先滤掉,只保留要翻译的符号串,即要求设计一个供词法分析调用的预处理子程序;
b.能够拼出语言中的各个单词;
c.返回(种别码,属性值)。
(2)语法分析
要求用学习过的自底向上或自顶向下的分析方法等,实现对表达式、各种说明语句、控制语句进行语法分析。
若语法正确,则用语法制导翻译法进行语义翻译;生成并打印出语法树;若语法错误,要求指出出错性质和出错位置(行号)。
2分析与设计
2.1程序结构
本节主要分析程序的代码结构和代码工程文件的划分。
(程序由两个类组成:
Scanner类和Parser类,分别为词法分析和语法分析类。
工程分为四个文件:
scanner.h、scanner.cpp、parser.h、parser.cpp,分别对应Scanner类和Parser类的声明和实现文件)。
本程序采用C++语言以面向对象的思想编写,程序分为两部分:
词法分析(Scanner)和语法分析(Parser),分别将两个处理阶段封装成Scanner类和Parser类,两个类各司其职,分别完成词法分析和语法分析的任务。
Scanner类主要的工作是过滤注释、词法分析获取Token。
Parser类的主要工作是根据Scanner类词法分析之后的Token进行语法分析,生成语法树,最后并输出语法树。
在处理过程中,Scanner类的对象作为Parser类的一个成员变量,配合Parser类进行语法分析。
工程文件总体上是按照两个类的格局分为四个文件,分别是两个类的声明文件和实现文件。
四个文件分别为scanner.h和scanner.cpp以及parser.h和parser.cpp,他们分别是Scanner类声明文件、Scanner类实现文件、Parser类声明文件、Parser类实现文件。
词法分析
scanner.h:
与词法分析相关的类(Scanner类)的声明
scanner.cpp:
词法分析阶段类(Scanner类)的实现
语法分析
parser.h:
与语法分析相关的类(Parser类)的声明
parser.cpp:
语法分析阶段类(Parser类)的实现
2.2程序流程
在程序中,Scanner类的对象(scanner)作为Parser类中的一个成员变量,配合Parser类进行语法分析。
它们的关系是这样的:
Parser类的一个成员变量scanner首先对源程序删除注释,然后进行词法分析获取所有Token,并将获取的Token存储在scanner对象的tokenList(vector类型)中。
然后Parser类的语法分析程序就根据tokenList中的Token进行语法分析,生成语法树,最后打印语法树。
同时,这也是程序的流程。
整体程序流程图
开始
删除注释
出错
词法分析
T
F
结束
语法分析
出错
出错
输出出错信息
T
F
F
T
从文件获取源代码
3词法分析
3.1代码结构分析
词法分析阶段的代码被封装成一个类——Scanner,scanner.h中主要是Scanner类的声明代码,scanner.cpp中主要是Scanner类的实现代码。
Scanner类对外提供的函数主要有:
getSourseStringFromFile(strings)(从文件中获取待分析的源代码)、deleteComments()(过滤注释)、scan()(词法分析主程序)。
词法分析的过程主要是:
lScanner调用getSourseStringFromFile(strings),从文件中获取待分析的源代码
lScanner调用deleteComments(),将注释过滤掉,如果注释出错,则不进行词法分析
lScanner调用scan(),进行词法分析,将分析得到的所有Token保存在Scanner类的成员变量tokenList中,以备语法阶段调用,并将Token输出到文件Token.txt中
以上三个函数构成了词法分析的骨架,在Scanner类中还有其他成员变量和函数,主要作为这三个函数处理过程的中间步骤,为这三个函数服务。
Scanner类的代码结构和主要的成员变量和函数如下图所示:
其他函数和成员变量的作用和含义:
lvoidbackToLastChar():
在词法分析过程中,回退一个字符
lDFAStatecharType(char):
返回字符的类型(按状态分),如whitespace返回START,0-9返回NUM
lchargetNextChar():
获取到下一个字符
lTokengetTokenAt(int):
根据下标从tokenList数组中获取词法分析后所保存的Token(供语法分析阶段调用)
lvoidprintToken():
将词法分析好的Token输出到文件Token.txt中
lTokenTypereturnTokenType(strings):
根据字符串返回对应的31种Token类型,如字符串"int"将返回INT,"var"将返回ID
lintcharIndex:
配合getNextChar()和backToLastChar()使用(分别自增和自减1),用以指示当前待分析的char在源代码中的位置
lboolcommentFlag:
标注注释开始的标志,为true时表示正在注释体内,即源代码进入"/*"之后且"*/"之前的状态
lintlineCount:
对行号计数,表示当前词法分析在源代码的行位置(每次获取到的char为'/n'就自增1)
lboolscanSuccess:
词法分析是否成功的标志
lstringsourseString:
获取源代码的字符串
lstringstr:
在分析过程中保存Token对应的串
lvector
保存Token序列
3.2Token定义
3.2.1Token的定义和类型
Token定义:
//定义的Token结构体,包括类型、对应的串、所在代码的行号
structToken
{
TokenTypetokenType;
stringtokenString;
intlineNo;
};
Token类型(TokenType):
程序中,将Token的类型分为31种,分别对应于else、if、int、return、void、while、+、-、*、/、<、<=、>、>=、==、!
=、=、;、,、(、)、[、]、{、}、/*、*/、num、id、错误、文件结束,TokenType的定义和种别码分别如下所示:
//定义的Token的类型(31种),分别对应于else、if、int、return、void、while、+、-、*、/、<、<=、>、>=、==、!
=、=、;、,、(、)、[、]、{、}、/*、*/、num、id、错误、结束
typedefenum
{
ELSE=1,IF,INT,RETURN,VOID,WHILE,
PLUS,MINUS,TIMES,OVER,LT,LEQ,GT,GEQ,EQ,NEQ,ASSIGN,SEMI,COMMA,LPAREN,RPAREN,LMBRACKET,RMBRACKET,LBBRACKET,RBBRACKET,LCOMMENT,RCOMMENT,
NUM,ID,ERROR,ENDFILE
}TokenType;
3.2.2Token的种别码
TokenType的种别码如下表所示,共31种
单词符号
种别码
Value
单词符号
种别码
Value
else
ELSE
1
=
ASSIGN
17
if
IF
2
;
SEMI
18
int
INT
3
COMMA
19
return
RETURN
4
(
LPAREN
20
void
VOID
5
)
RPAREN
21
while
WHILE
6
[
LMBRACKET
22
+
PLUS
7
]
RMBRACKET
23
-
MINUS
8
{
LBBRACKET
24
*
TIMES
9
}
RBBRACKET
25
/
OVER
10
/*
LCOMMENT
26
<
LT
11
*/
RCOMMENT
27
<=
LEQ
12
num
NUM
28
>
GT
13
id
ID
29
>=
GEQ
14
错误
ERROR
30
==
EQ
15
结束
ENDFILE
31
!
=
NEQ
16
3.3DAF分析
由于词法分析程序分为两个步骤处理:
删除注释和词法分析获取Token。
所以对应有两个DFA,程序分别根据这两个DFA进行编写,现根据DFA分析两程序deleteComments()和scan()如下:
3.3.1删除注释DFA
删除注释的DFA描述:
删除注释的DFA如下所示,一共分为5个状态,在开始状态1时,如果输入的字符为/,则进入状态2,此时有可能进入注释状态,如果在状态2时,输入的字符为*,则进入注释状态,状态将转到3,如果在状态3时,输入的字符为*,则有可能结束注释状态,此时状态将转到状态4,如果在状态4时输入的字符为/,则注释状态结束,状态转移到结束状态。
对应的DFA的代码分析:
删除注释的功能通过Scanner类的成员函数deleteComments()实现,功能是将源代码中的注释过滤掉,将其余代码输出到sourceFile.txt文件中。
deleteComments()函数按照上面的DFA编写,在函数中,state变量表示状态,共分为5个状态:
l在状态1时,如果输入的字符为/,则进入状态2,否则仍处在状态1,且输出输入的字符
l在状态2时,(此时可能进入注释状态),如果输入的字符为*,则进入注释状态,状态将转到3,否则跳转到状态1,并输出/和输入的字符
l在状态3时,(此时可能结束注释状态),如果输入的字符为*,此时状态将转到状态4,否则继续在状态3
l在状态4时,如果输入的字符为/,则注释状态结束,状态转移到结束状态
相应的DFA代码:
代码如下所示:
voidScanner:
:
deleteComments()
{
ofstreamfout_Sourse("sourseFile.txt");
intstate=1;
charch;
while(state<6)
{
ch=getNextChar();
if('\0'==ch)//文件结束
break;
if(1==state)//DFA中的状态
{
if('/'==ch)
state=2;
else
{
state=1;
fout_Sourse< } } elseif(2==state)//DFA中的状态 { if('*'==ch) { state=3; commentFlag=false; } else { state=1; fout_Sourse<<"/"< } } elseif(3==state)//DFA中的状态 { if('*'==ch) state=4; else { state=3; } } elseif(4==state)//DFA中的状态 { if('*'==ch) state=4; elseif('/'==ch) state=5; else { state=3; } } if(5==state)//结束状态,处理 { commentFlag=true; state=1; } } if(! commentFlag) { cout<<"注释错误,没有结束符! "< scanSuccess=false; } } 3.3.2词法分析DFA 词法分析的DFA描述: 词法分析的DFA如下所示,一共分为5个状态: START、INNUM、INID、INDBSYM、DONE。 状态START表示开始状态,状态INNUM表示数字类型(NUM)Token的状态,状态INID表示字符串类型Token的状态(如关键字和一般的标示符),状态INDBSYM表示双目运算符型Token的状态(如<=、>=、! =、==),状态DONE表示接收状态。 l在开始状态START时 Ø如果输入的字符为空白符,如空格换行等,则仍在START状态 Ø如果输入的字符为digit,则进入状态INNUM,即可能是数字类型(NUM)Token的状态 Ø如果输入的字符为letter,则进入状态INID,即可能是字符串类型Token的状态 Ø如果输入的字符为>、<、! 、=,则进入状态INDBSYM,即可能是双目运算符型Token的状态 Ø如果输入的字符为是除以上之外的,则进入状态DONE,这次输入的字符可能是单目运算符、错误等 l在状态INNUM时 Ø如果输入的字符为digit,则仍停留在INNUM状态 Ø如果输入的为其他的字符,则转到DONE状态 l在状态INID时 Ø如果输入的字符为letter,则仍停留在INID状态 Ø如果输入的为其他的字符,则转到DONE状态 l在状态INDBSYM时 Ø如果输入的字符为=,将双目运算标志赋值为true后转到DONE状态 Ø如果输入的为其他的字符,则直接转到DONE状态 l在状态DONE时 接受状态,根据分析过程中获取的字符串确定Token的类型,并生成和保存相应的Token 对应的DFA的代码分析: 词法分析的功能通过Scanner类的成员函数scan()实现,功能是根据过滤掉注释的源代码获取Token并保存,获取到的Token通过printToken()函数输出到Token.txt文件中。 scan()函数按照上面的DFA编写,在函数中,doubleSym变量表示双目运算符标志,当doubleSym为true时表示INDBSYM状态接收到的字符为'=',str变量是在词法分析过程中用来存储分析的Token的字符串,如INT型Token在分析过程中得到"int"的字符串,变量ch为当前输入的字符。 分析到最后,在状态DONE中,根据分析过程中获取的str确定Token的类型,并生成和保存相应的Token。 程序一共分为5个状态: START、INNUM、INID、INDBSYM、DONE。 函数在各状态下的处理分析如下: l在开始状态START时 Ø如果输入的字符为空白符,如空格换行等,则仍在START状态 Ø如果输入的字符为digit,则进入状态INNUM,即可能是数字类型(NUM)Token的状态,同时将ch添加到str中去(str+=ch) Ø如果输入的字符为letter,则进入状态INID,即可能是字符串类型Token的状态,同时将ch添加到str中去(str+=ch) Ø如果输入的字符为>、<、! 、=,则进入状态INDBSYM,即可能是双目运算符型Token的状态,同时将ch添加到str中去(str+=ch) Ø如果输入的字符为是除以上之外的,则进入状态DONE,同时将ch添加到str中去(str+=ch),这次输入的字符可能是单目运算符、错误等 l在状态INNUM时 Ø如果输入的字符为digit,则仍停留在INNUM状态,同时将ch添加到str中去(str+=ch) Ø如果输入的为其他的字符,则转到DONE状态 l在状态INID时 Ø如果输入的字符为letter,则仍停留在INID状态,同时将ch添加到str中去(str+=ch) Ø如果输入的为其他的字符,则转到DONE状态 l在状态INDBSYM时 Ø如果输入的字符为=,将双目运算标志赋值为true后转到DONE状态,同时将ch添加到str中去(str+=ch),并将doubleSym赋值为true(doubleSym=true),表示ch为‘=’ Ø如果输入的为其他的字符,则直接转到DONE状态 l在状态DONE时 接受状态,根据分析过程中获取的字符串确定Token的类型,并生成和保存相应的Token,同时将str设为空,(以便分析下一个Token)。 在DFA中,[other]表示ch没有被添加到str中后的转移,所以当状态是通过条件[other]跳转到DONE状态的情况时,则需将分析的字符回退回去(backToLastChar())。 相应的DFA代码: 代码如下: voidScanner: : scan() { booldoubleSym=false; getSourseStringFromFile("sourseFile.txt"); intstate=START; lineCount=0; charch; //每一次循环都执行一次DFA,并获取到一个Token while(state<6) { ch=getNextChar(); if('\0'==ch)//到达文件末尾,文件结束 { Tokent; t.lineNo=lineCount; t.tokenString=""; t.tokenType=ENDFILE; tokenList.push_back(t); break; } if(START==state)//初始状态和空格 { state=charType(ch); if(state! =START) str+=ch; } elseif(INNUM==state)//digit { state=charType(ch); if(state! =INNUM) state=DONE; else str+=ch; } elseif(INID==state)//letter { state=charType(ch); if(state! =INID) state=DONE; else str+=ch; } elseif(INDBSYM==state)//除了<>=! 之外的各种符号 { if('='==ch) { str+=ch; doubleSym=true; } else doubleSym=false; state=DONE; } if(DONE==state)//接收状态 { inttp=0; if('\n'==ch) tp=1; //根据str生成Token Tokent; t.lineNo=lineCount-tp; t.tokenString=str; t.tokenType=returnTokenType(str); tokenList.push_back(t); if(ERROR==t.tokenType) scanSuccess=false; //针对[other]的情形,回退一个字符 intlastState=charType(str[str.length()-1]); if(lastState==INNUM||lastState==INID||(lastState==INDBSYM&&doubleSym==fal
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 四川 大学计算机 学院 语言 编译器 编译 原理 课程设计 报告 源码 递归 下降 minus