毕业设计论文—cminus词法分析和语法分析设计编译器编译原理设计Word格式.docx
《毕业设计论文—cminus词法分析和语法分析设计编译器编译原理设计Word格式.docx》由会员分享，可在线阅读，更多相关《毕业设计论文—cminus词法分析和语法分析设计编译器编译原理设计Word格式.docx（56页珍藏版）》请在冰点文库上搜索。
<
= >
>
= == !
= = ;
, （ ） [ ] { }
/* */
3其他标记是ID和NUM，通过下列正则表达式定义：
ID=letterletter*NUM=digitdigit*letter=a|..|z|A|..|Zdigit=0|..|9
大写和小写字母是有区别的
4空格由空白、换行符和制表符组成。
空格通常被忽略，除了它必须分开
ID、NUM关键字。
5注释用通常的C语言符号/*...*/围起来。
注释可以放在任何空白出现
的位置（即注释不能放在标记内）上，且可以超过一行。
注释不能嵌套
scanner的DFA
+-*<
=>
===!
=;
（）[]{}
INASSIGN
Whitespace
\t
\n
>
<
=,!
digit
=
NUM
[other]
START
letter
DONE
/ INID
SLAH
*
INCOMMENT
RETURN_INCO
ENDCOMMENT / MMENT
说明：
当输入的字符使DFA到达接受状态的时候，则可以确定一个单词了。
初始状态设置为START，当需要得到下一个token时，取得次token的第一个字符，并且按照
DFA与对此字符的类型分析，转换状态。
重复此步骤，直到DONE为止，输出token类型。
当字符为“/”时，状态转换为SLAH再判断下一个字符，如果为“*”则继续转到INCOMMENT，最后以“*”时转到ENDCOMMENT状态，表明是注释，如果其他的则是字符停滞于当前字符，并且输出“/”。
2.1.2程序流程图
源文件
读取源文件一
行输出
读取一个字符
否
是否到达终态
是
赋值token
输出token
2.1.3各文件或函数的设计说明
扫描程序用到:
scanner.h,scanner.cpp
Ø
scanner.h：
声明词法状态，词法分析
//DFA中的状态
typedefenum
{
START=1,INNUM,INID,INDBSYM,DONE
}DFAState;
//定义的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;
//定义的Token结构体，包括类型、对应的串、所在代码的行号
structToken
TokenTypetokenType;
stringtokenString;
intlineNo;
};
//每种TokenType对应的串，如tokenTypeString[ELSE]=="
ELSE"
const string tokenTypeString[32] = {"
OTHER"
"
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"
classScanner:
定义scanner.cpp中函数
scanner.cpp文件函数说明
voidScanner:
:
scan（）：
设置输出结果界面以及设置各种输出状态。
if（scanSuccess==false）
cout<
<
词法分析出错！
endl;
else
词法分析成功了！
printToken（）;
/*输出Token到文件Token.txt中*/
//正在删除注释
deleteComments（）
TokenTypeScanner:
returnTokenType（strings）//返回Token的类型
DFAStateScanner:
charType（charc）//返回字符的类型typedefenum
{ENDFILE,ERROR,IF,ELSE,INT,RETURN,VOID,WHILE, //关键字ID,NUM,
ASSIGN,PLUS,MINUS,TIMES,OVER,EQ,UEQ,LT,LPAREN,RPAREN,SEMI,BT,LQ,BQ,
DOU,LZGH,RZGH,LDGH,RDGH,//特殊字符：
=+-*/==!
=<
等
} TokenType;
2.1.4测试程序说明
根据附录A后面的例子，程序输入两个整数，计算并打印出它们的最大公因子，保存为a.txt。
/*AprogramtoperformEucild'
sAlgorithmtocomputegcd.*/
int gcd（intu,intv）
if（v==0）
returnu;
elsereturn
gcd（v,u-u/v*v）;
/*u-u/v*v==umodv*/
}
voidmain（void）
intx;
inty;
x=input（）;
y=input（）;
output（gcd（x,y））;
2.2、语法分析parse部分
2.2.1系统设计思想
parser用递归下降分析方法实现,通过调用词法分析函数
getToken实现语法分析。
根据C-语言的规则，得出BNF语法如下：
1.program->
declaration-list
2.declaration-list->
declaration-listdeclaration|declaration3.declaration->
var-declaration|fun-declaration
4.var-declaration->
type-specifierID;
|type-specfierID[NUM]5.type-specifier->
int|void
6.fun-specifierID（parans）compound-stmt7.params->
params-list|void
8.param-list->
param-list,param|param
9.param->
type-specifierID|type-specifierID[]pound-stmt->
{local-declarationsstatement-list}
11.local-declarations->
local-declarationsvar-declaration|empty12.statement-list->
statement-liststatement|empty
13.statement->
expression-stmt|compound-stmt|selection-stmt|iteration-stmt|return-stmt
14.expression-stmt->
expression;
|;
15.selection-stmt->
if（expression）statement|if（expression）statementelsestatement
16.iteration-stmt->
while（expression）statement17.return-stmt->
return;
|returnexpression;
18.expression->
var=expression|simple-expression19.var->
ID|ID[expression]
20.simple-expression->
additive-expression relop additive-expression|additive-expression
21.relop->
=|<
|>
=|==|!
22.additive-expression->
additive-expressionaddopterm|term23.addop->
+|-
24.term->
termmulopfactor|factor25.mulop->
*|/
26.factor->
（expression）|var|call|NUM27.call->
ID（args）
28.args->
arg-list|empty
29.arg-list->
arg-list,expression|expression
2.1.2语法分析程序流程图
符号表文件
获取终结符和
非终结符
构造文法分析
表
分析句型句子
输出结果
语法分析程序包括：
parser.cpp,parser.h
parser.cpp：
Parser:
Parser（）//界面设计
Token Parser :
getToken（）//获取scanner中保存在TokenList数组中的
Token，并且每次获取完之后数组下标指向下一个voidParser:
syntaxError（strings）//出错处理voidParser:
match（TokenTypeex）//匹配出错
TreeNode*Parser:
declaration（void）//类型匹配错误
TreeNode * Parser :
param_list（TreeNode * k）//k可能是已经被取出来的
VoidK，但又不是（void）类型的参数列表，所以一直传到param中去，作为其一个子节点
parse.h：
对parse.c的函数声明
//19种节点类型，分别表示int、id、void、数值、变量声明、数组声明、函数声明、函数声明参数列表、函数声明参数、复合语句体、if、while、return、赋值、
运算、数组元素、函数调用、函数调用参数列表、未知节点
typedefenum{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;
typedefenum{Void,Integer}ExpType;
ofstreamfout_Tree（"
tokenTree.txt"
）;
//输出语法树到文件
//treeNode定义 包括子节点、兄弟节点、所处行号、节点类型、属性、表达式返回类型
typedefstructtreeNode
TreeNode*newNode（Nodekindk）;
//根据节点类型新建节点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）;
根据附录A后面的例子，程序输入两个整数，计算并打印出它们的最大公因子，
保存为a.txt。
3.程序代码实现
按文件列出主要程序代码,添加必要的注释.
Scanner.cpp:
#include<
cstdlib>
iostream>
fstream>
string>
#include"
scanner.h"
#include<
vector>
usingnamespacestd;
/*
Name:
词法分析器
Copyright:
Author:
XXX
Date:
19-05-1412:
00
Description:
提取出token
*/
Scanner:
Scanner（）
scanSuccess=true;
charIndex=0;
str="
;
commentFlag=true;
sourseString="
lineCount=0;
scan（）
开始词法分析..."
booldoubleSym=false;
getSourseStringFromFile（"
sourseFile.txt"
intstate=START;
lineCount=0;
charch;
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
=INNUM）
state=DONE;
else
elseif（INID==state）//letter
=INID）
elseif（INDBSYM==state）//除了<
=!
之外的各种符号
if（'
='
str+=ch;
doubleSym=true;
doubleSym=false;
if（DONE==state）//接收状态
inttp=0;
\n'
tp=1;
Tokent;
t.lineNo=lineCount-tp;
t.tokenString=str;
t.tokenType=returnTokenType（str）;
if（ERROR==t.tokenType）
scanSuccess=false;
intlastState=charType（str[str.length（）-1]）;
if（lastState==INNUM || lastState==INID || （lastState==INDBSYM &
&
doubleSym==false））
backToLastChar（）;
str="
state=START;
if（doubleSym==true）
//输出Token到文件Token.txt中
TokenScanner:
getTokenAt（inttokenIndex）
Tokentoken;
token.lineNo=lineCount;
token.tokenString="
token.tokenType=ENDFILE;
if（tokenIndex<
tokenList.size（））
token=tokenList.at（tokenIndex++）;
returntoken;
getSourseStringFromFile（stringpath）
ifstreamfin（path.c_str（））;
stringtemp;
sourseString="
while（getline（fin,temp））
sourseString+=temp;
sourseString+='
fin.close（）;
正在删除注释..."
ofstreamfout_Sourse（"
intstate=1;
charch;
==ch）//文件结束break;
if（1==state）
/'
state=2;
state=1;
fout_Sourse<
ch;
elseif（2==state）
*'
state=3;
commentFlag=false;
/"
elseif（3==state）
state=4;
state=3;
elseif（4==state）
elseif（'
state=5;
if（5==state）//结束状态，处理
commentFlag=true;
state=1;
if（!
commentFlag）
cout<
注释错误，没有结束符！
scanSuccess=false;
注释已经成功删除！
TokenTypet;
if（s=="
else"
）
t=ELSE;
升级会员 