目录 1.引言 2 1.1问题描述 2 1.2需求与技术现状分析 2 2.程序总体设计 3 2.1设计目的 3 2.2设计要求 3 2.3.整体程序设计理念 4 2.4流程图 4 3.详细设计数据结构和算法 5 3.1.词法分析设计 5 3.语法分析设计 7 3.保存文件设计 7 4. 实现和测试系统 8 4.1词法分析 8 4.1语法分析 9 4.保存文件设计 13 4.4.系统测试 14 5. 总结与展望 23 5.1全文总结 23 5.2工作展望 23 6.体会 24 6.1总结 24 6.2特色 24 6.3不足 25 参考文献 25 附录 26 附录1： 26 附录2： 70 1.引言 1.1问题描述 抽象语法树(abstract syntax code, AST) 是源代码抽象语法结构的树形表示，树上的每个节点都表示源代码中的一种结构， 这是抽象的，因为抽象语法树不会表达真实语法的每一个细节， 例如，嵌套括号隐含在树的结构中，不以节点的形式呈现。抽象语法树不依赖源语言的语法，即语法分析阶段使用的上下文无文法，因为在写作方法时，文法经常等价转换（消除左递归、回溯、二义等） , 这将在文法分析中引入一些多余的成分，对后续阶段产生不利影响，甚至混乱。由于某些原因，许多编译器经常以语法分析树为前端，在后端建立清晰的界面。 1.2需求与技术现状分析 抽象语法树(Abstract Syntax Tree ,AST)作为程序的中间表达形式，广泛应用于程序分析等领域.抽象语法树可以轻松实现源程序浏览器、智能编辑器、语言翻译器等多种源程序处理工具。通常是作为编译器或解释器的组件出现的，它的作用是进行语法检查、并构建由输入的单词组成的数据结构（一般是语法分析树、抽象语法树等层次化的数据结构）。语法分析器通常使用独立的词法分析器从输入字符流中分离出单词，并将单词流作为输入。在实际开发中，语法分析器可以手工编写，也可以用工具(半)自动生成。 通过对源程序的实现，个人发现各种编译器的中间表示是语法分析树，AST，我觉得这个实验的最终目的是编译一个简单的语言编译器，所以我认为语法分析树的现状是编译器的内部原理，现在程序相对简单，词法识别和语法识别不够全面，只能识别相对简单和基本的源程序。 本文转载：http://www.biyezuopin.vip/onews.asp?id=16530
#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define MAXLENG 10 #define MAXSIZE 2 #define INFEASTABLE -1 #define OVERFLOW -2 #define QMAXSIZE 5 ///队列大小 typedef int status; ///定义数据元素类型 typedef char TElemType;///定义字符常量 #define LINE 1024 static char keywords[50][20]={
"char", "continue","break",
"else","for", "float","if","while",
"int","double","case",
"return","void","continue", "struct",
"switch","default"};
static char headfile[50][30]={
"#include<stdio.h>","#include<stdlib.h>","#include<string.h>","#includ<file.h>","#include<math.h>"};
typedef enum
{
ELSE=1,IF,INT,RETURN,VOID,WHILE,FOR,CHAR,FLOAT,LONG,LEQ,REQ,EQ,BREAK,CONTINUE,UNEQ,//16
PLUS,MINUS,TIMES,DIVISION,BIG,LITTLE,ASSIGN,SEMI,COMMA,LP,RP,LMP,//12
RMP,LBP,RBP,ERROR_TOKEN,IDENT,INT_CONST,LONG_CONST,CHAR_CONST,FLOAT_CONST,ID,END, //11
HONG1,HONG2,HONG3,HONG4,HONG5//5
}Token_texttype;
typedef enum Nodekind
{
ints,ids,voids,chars,floats,longs,INT_CONSTS,LONG_CONSTS,variable,shuzu,hanshu,hancanlist,hancan,fuheyuju,ifs,elses,whiles,returns,breaks,continues,
fuzhi,yunsuan,hong,hong1,hong2,hong3,hong4,hong5,shuzuyuansu,hanshudiaoyong,hanshudiaoyongcanlist,unknown
}NODEkind;//节点种类
typedef enum Expressiontype
{
Void,
Int,
Char,
Float
}expressiontype;//表达式种类
typedef struct TREENODE//树节点结构体孩子表示法
{
TREENODE * child;//左子节点
TREENODE * rchilde;//右子节点
int linenumber;//所在行
Nodekind NODEkind;//节点类型
char NODEstring[1100];//节点类型所代表的字符串，用于语法树打印
}TREENODE,*tokenTREE;
typedef struct token_text//token结构体
{
Token_texttype token_texttype;//token类型
char token_textstring[1100];//token串
int linenumber;//token行号
}Token;
Token_texttype gettoken_texttype(char c[]);
void scan(); //扫描，词法识别
char s[1005][1005];//文本
char p[1005][1005];//临时替换数组
char t[1005];//当前token_text串
char tk[1005];
char linshi[1100];//临时数组
int line; //文本行数
int zs; //注释标记
int tttt; //标记，结构数组个数
Token tokenlist[1000]; //token表声明
Token ctoken;//当前token
Token ltoken;//上一个token
int xb=0;//token下标
int blank=0;//先行空格
void gettoken_text();//得到token
void programerror();//输出错误
void match(Token_texttype toke);//匹配
TREENODE * compound_stmt();//函数声明
void printspace(int n);//打印空格
void printTREE(TREENODE * t);//打印语法分析树
TREENODE * NEWNODE(Nodekind kind);//创建新节点
TREENODE * function_listformat();//函数参数列表格式
TREENODE * call(TREENODE * k);//函数调用
TREENODE * factor(TREENODE * k); //带括号的表达式
TREENODE * term(TREENODE * k); //乘除表达式
TREENODE * additive_expression(TREENODE * k);//加成的表达式
TREENODE * simple_expression(TREENODE * k);//简单表达式
TREENODE * variabler(); //变量声明
TREENODE * expression(); //表达式声明
TREENODE * expression_stmt();//表达式声明
TREENODE * return_stmt();//返回式声明
TREENODE * continue_stmt();//continue声明
TREENODE * break_stmt();//break声明
TREENODE * while_stmt();//while声明
TREENODE * if_stmt();//if声明
TREENODE * else_stmt();//else声明
TREENODE * statement();//复合语句后者种类
TREENODE * statement_list();//复合语句体后者
TREENODE * local_declaration();//复合语句体前者
TREENODE * function_def(TREENODE * k);//函参
TREENODE * function_def_list(TREENODE * k);//函参列表
TREENODE * compound_stmt();//函数内容，复合语句
TREENODE * function_defs();//函数参数
TREENODE * declaration();//函数声明
TREENODE * declaration_list();//多个函数列表
TREENODE * program();//语法分析
void savefile(TREENODE * T);//,FILE *FP);//保存文件
void save(FILE * FP);
int main()
{
/*FILE *FP; int i = 0,j = 0; char w,c; printf("请输入将要读取的文件名，以.txt结尾：\n"); char file[30]; scanf("%s",file); if ((FP=fopen(file,"rb")) == NULL) printf("File open error\n "); else printf("文件读取成功\n"); while((c = fgetc(FP)) == 1) { if(c == '\n') { j = 0; i++; } else s[i][j++] = c; line = i; if(c == '#') break; } fclose(FP); */
printf("请输入一段代码，回车之后ctrl+z结束：\n");
int i=0;
int change;
line=0;
while(gets(s[line++]))
{
}
printf("单词识别 :\n");
scan();
// zhushi();
printf("\n语法分析 :\n");
TREENODE *t = program(); //生成ast树头结点
TREENODE *p;
p = t;
printf("输入数值：");
scanf("%d",&change);
getchar();
if(change == 1)
printTREE(t); //打印ast语法树
else if(change == 2)
{
FILE *FP;
printf("请输入文件名称：\n");
char file[30];
scanf("%s",file);
if ((FP=fopen(file,"w")) == NULL)
printf("文件打开失败\n ");
else
printf("文件打开成功\n");
savefile(p);
save(FP);
fclose(FP);
}
else
{
getchar();
return 0;
}
getchar();
return 0;
}
Token_texttype gettoken_texttype(char c[])
{
Token_texttype to;
if(!strcmp(c,"else"))
{
to=ELSE;
}
if(!strcmp(c,"break"))
{
to=BREAK;
}
if(!strcmp(c,"continue"))
{
to=CONTINUE;
}
else if(!strcmp(c,"if"))
{
to=IF;
}
else if(!strcmp(c,"return"))
{
to=RETURN;
}
else if(!strcmp(c,"int"))
{
to=INT;
}
else if(!strcmp(c,"char"))
{
to=CHAR;
}
else if(!strcmp(c,"float"))
{
to=FLOAT;
}
else if(!strcmp(c,"long"))
{
to=LONG;
}
else if(!strcmp(c,"void"))
{
to=VOID;
}
else if(!strcmp(c,"while"))
{
to=WHILE;
}
else if(!strcmp(c,"+"))
{
to=PLUS;
}
else if(!strcmp(c,"-"))
{
to=MINUS;
}
else if(!strcmp(c,"*"))
{
to=TIMES;
}
else if(!strcmp(c,"/"))
{
to=DIVISION;
}
else if(!strcmp(c,"<"))
{
to=LITTLE;
}
else if(!strcmp(c,"<="))
{
to=LEQ;
}
else if(!strcmp(c,"#include<stdio.h>"))
{
to = HONG1;
}
else if(!strcmp(c,"#include<stdlib.h>"))
{
to = HONG1;
}
else if(!strcmp(c,"#include<string.h>"))
{
to = HONG1;
}
else if(!strcmp(c,"#include<file.h>"))
{
to = HONG1;
}
else if(!strcmp(c,"#include<math.h>"))
{
to = HONG1;
}
else if(!strcmp(c,">"))
{
to=BIG;
}
else if(!strcmp(c,">="))
{
to=REQ;
}
else if(!strcmp(c,"=="))
{
to=EQ;
}
else if(!strcmp(c,"!="))
{
to=UNEQ;
}
else if(!strcmp(c,"="))
{
to=ASSIGN;
}
else if(!strcmp(c,";"))
{
to=SEMI;
}
else if(!strcmp(c,","))
{
to=COMMA;
}
else if(!strcmp(c,"("))
{
to=LP;
}
else if(!strcmp(c,")"))
{
to=RP;
}
else if(!strcmp(c,"["))
{
to = LMP;
}
else if(!strcmp(c,"]"))
{
to=RMP;
}
else if(!strcmp(c,"{"))
{
to=LBP;
}
else if(!strcmp(c,"}"))
{
to=RBP;
}
else if(!strcmp(c,"INT_CONST1"))
{
to=INT_CONST;
}
else if(!strcmp(c,"LONG_CONST1"))
{
to=LONG_CONST;
}
else if(!strcmp(c,"ID"))
{
to=ID;
}
else if(!strcmp(c,"end"))
{
to=END;
}
return to;
}
void scan()
{
zs = 0;
char uu[3];
int tt = 0;//tokenlist的下标
int i,j,m,l,n,b,d;//下标
int f,flag;//标记
int len;//当前行长度
char keywords[50][20]={
"char", "continue","break",
"else","for", "float","if","while",
"int","long","double","case",
"return","void","continue", "struct",
"switch","default"};//关键字
char headfile[50][30]={
"#include<stdio.h>","#include<stdlib.h>","#include<string.h>","#includ<file.h>","#include<math.h>"};
char compare2[10][1005]={
"<=",">=","==","!=","--","++","&&","||"};//双目比较符
char compare1