课程设计任务书
题目：简单编译器的设计与实现
姓名：莫飞飞
学号： 200712230111
专业： 07本二
课程：编译原理
指导教师：王艳秋职称：
完成时间：2009年12月--2009年1月
枣庄学院计算机科学系
课程设计的任务和具体要求
任务：结合各章节的构造编译程序的基本理论，完成一简单编译器的设计与实现。使学生将理论与实际应用结合起来，受到软件设计等开发
过程的全面训练，从而提高学生软件开发的能力。
要求：1.用C或C++语言描述及上机调试，实现一个小编译器：
2.完成符号表的构造，
3.理解词法分析，语法分析，目标代码生成等重要子程序。
指导教师签字：日期：
指导教师评语
成绩：指导教师签字：日期：课程设计所需软件、硬件等
软件：WIN-TC、Word文档
硬件：一台计算机
课程设计进度计划
参考文献、资料索引
1.《程序设计语言编译原理》，陈火旺编著，国防工业出版社
2.《编译原理》，吕映芝、张素琴、蒋维杜编著，清华大学出版社
3.《编译原理》，Alfred V.Aho 等，李建中译，机械工业出版社
一、总体设计方案及主要思想：
1.主要思想：
编译器是靠编译程序实现，而编译程序是指把某一种语言程序（源程序）转换成另一种语言程序（目标程序）的翻译过程。
编译过程分为五个步骤：词法分析；语法分析；语义分析；中间代码的产生与优化；目标代
四元式
单词符号
语法单位
四元式
目标代码
词法分析器
语法分析器
语义分析与中间代码生成器
优化段
源程序
表 格 管 理
出 错 处 理
目标代码生成器
码生成。编译程序的结构可以按照这五阶段的任务模块进行设计。图一是编译程序的总框：
（图一）
2.设计方案：
（1）设计符号表。图二是符号表的格式：
（图二）
确定符号表的组织方式，一般应包括名字栏和信息栏，其中名字栏作为关键字。要考虑能够存储有关名字的信息，并可以高效地完成如下操作：
a.查找：根据给定的名字，在符号表中查找其信息。如果该名字在符号表中不存在，则将其加入到符号表中，否则返回指向该名字的指针；
b.删除：从符号表中删除给定名字的表项。
（2）设计词法分析器
设计各单词的状态转换图，并为不同的单词设计种别码。流程图见附录图三。将词法分析器设计成供语法分析器调用的子程序。功能包括：
a.具备预处理功能。将不翻译的注释等符号先滤掉，只保留要翻译的符号串，即要求
设计一个供词法分析调用的预处理子程序；
b.能够拼出语言中的各个单词；
c.将拼出的标识符填入符号表；
d.返回（种别码，属性值）。
算法代码：
int code, value;
strToken := “”; /*置strToken为空串*/
GetChar(); GetBC();
if (IsLetter())
begin
while (IsLetter() or IsDigit())
begin
Concat(); GetChar();
end
Retract();
code := Reserve();
if (code = 0)
begin
value := InsertId(strToken);
return ($ID, value);
end
else
return (code, -);
End
else if (IsDigit())
begin
while (IsDigit())
begin
Concat( ); GetChar( );
end
Retract();
value := InsertConst(strToken);
return($INT, value);
end
else if (ch =‘=’) return ($ASSIGN, -);
Else if (ch =‘+’) return ($PLUS, -);
else if (ch =‘*’)
begin
GetChar();
if (ch =‘*’) return ($POWER, -);
Retract(); return ($STAR, -);
end
else if (ch =‘;’) return ($SEMICOLON, -);
else if (ch =‘(’) return ($LPAR, -);
else if (ch =‘)’) return ($RPAR, -);
else ProcError( ); /* 错误处理*/
（3）语法分析器
综合来说，有预测分析法、递归下降分析法、算符优先分析法、SLR分析法，实现对表达式、各种说明语句、控制语句进行语法分析。这里我用来递归下降法来完成语法分析。（代码见实现部分）
（4）目标代码生成器
能完成指定寄存器个数的情况下将一中间代码程序段翻译成汇编语言目标代码（汇编指令应包括加、减、乘、除），要求指令条数最少的情况下，尽量使用寄存器，尽量少访问内存，这样才能做到运行效率高。
附录：
图三.词法转换状态转换图
二.实现及主要代码
【流程图】
（图四）
1、符号表的设计：
struct{//定义符号表结构
char name[8];
int address;
}vartable[maxvartablep];//改符号表最多容纳maxvartablep个记录
2、词法分析程序设计与实现：
//下面定义保留字，为简化程序，使用字符指针数组保存所有保留字。
//如果想增加保留字，可继续添加，并修改保留字数目
#define keywordSum 8
Char*keyword[keywordSum]={ "if","else","for","while","do","int","read ","write"};
//下面定义纯单分界符，如需要可添加
char singleword[50]="+-*(){};,:";
//下面定义双分界符的首字符
char doubleword[10]="><=!";
extern char Scanin[300], Scanout[300]; //用于接收输入输出文件名,在
extern FILE *fin,*fout; //用于指向输入输出文件的指针,在TEST_main.c中定义int TESTscan()//词法分析函数
{
........//文件打开程序略
ch=getc(fin);
while(ch!=EOF)
{
while (ch==' '||ch=='\n'||ch=='\t') ch=getc(fin);
if (isalpha(ch)) //如果是字母，则进行标识符处理
{
token[0]=ch; j=1;
ch=getc(fin);
while(isalnum(ch)) //如果是字母数字则组合标识符
{
token[j++]=ch; //组合的标识符保存在token中
ch=getc(fin); //读下一个字符
}
token[j]='\0'; //标识符组合结束 //查保留字
n=0;
while ((n if (n>=keywordSum) //不是保留字，输出标识符 fprintf(fout,"%s\t%s\n","ID",token); //输出标识符符号 else//是保留字，输出保留字 fprintf(fout,"%s\t%s\n",token,token); //输出保留字符号 } else if (isdigit(ch))//数字处理 { token[0]=ch; j=1; ch=getc(fin); //读下一个字符 while (isdigit(ch)) //如果是数字则组合整数 { token[j++]=ch; //组合整数保存在token中 ch=getc(fin); //读下一个字符 } token[j]='\0'; //整数组合结束 fprintf(fout,"%s\t%s\n","NUM",token); //输出整数符号 } else if (strchr(singleword,ch)>0) //单分符处理 { token[0]=ch; token[1]='\0'; ch=getc(fin);//读下一个符号以便识别下一个单词 fprintf(fout,"%s\t%s\n",token,token); //输出单分界符符号 }else if (strchr(doubleword,ch)>0) //双分界符处理 { token[0]=ch; ch=getc(fin); //读下一个字符判断是否为双分界符 if (ch=='=') //如果是=，组合双分界符 { token[1]=ch;token[2]='\0'; //组合双分界符结束 ch=getc(fin); //读下一个符号以便识别下一个单词 } else//不是=则为单分界符 token[1]='\0'; fprintf(fout,"%s\t%s\n",token,token); //输出单或双分界符符号 } else if (ch=='/') //注释处理 { ch=getc(fin); //读下一个字符 if (ch=='*') //如果是*，则开始处理注释 { char ch1; ch1=getc(fin); //读下一个字符 do { ch=ch1;ch1=getc(fin);} //删除注释 while ((ch!='*' || ch1!='/')&&ch1!=EOF); //直到遇到注释结束符*/或文件尾 ch=getc(fin);//读下一个符号以便识别下一个单词 } else //不是*则处理单分界符/ { token[0]='/'; token[1]='\0'; fprintf(fout,"%s\t%s\n",token,token); //输出单分界符/ } } else//错误处理 { token[0]=ch;token[1]='\0'; ch=getc(fin); //读下一个符号以便识别下一个单词 es=3; //设置错误代码 fprintf(fout,"%s\t%s\n","ERROR",token); //输出错误符号 } } fclose(fin);//关闭输入输出文件 fclose(fout); return(es); //返回主程序 } 3、语法与语义分析的实现及主要代码 语法规则： /*<程序>::={<声明序列><语句序列>} program::={ /*<声明序列>::=<声明序列><声明语句>|<声明语句> 改成 /*<声明语句> ::=int <变量>； /*<语句序列>::=<语句序列><语句>|<语句> // 改成 /*<语句>::= | /* 其中动作符号的含义如下 @BRF↑label1 ：输出 BRF label1, @BR↑label2：输出 BR label2, @SETlabel↓label1：设置标号label1 @SETlabel↓label2：设置标号label2 */ /* //动作解释如下： //@SETlabel↑label1：设置标号label1 //@BRF↑label2 ：输出 BRF label2, //@BR↓label1：输出 BR label1, //@SETlabel↓label2：设置标号label2 */ /* //动作解释如下： //@SETlabel↑label1：设置标号label1 //@BRF↑label2 ：输出 BRF label2, //@BR↓label1：输出 BR label1, //@SETlabel↓label2：设置标号label2 */ /* 动作解释： 1. @SETlabel↓label1：设置标号label1 2. @BRF↑label2 ：输出 BRF label2, 3. @BR↑label3：输出 BR label3, 4. @SETlabel↓label4：设置标号label4 5. @BR↑label1：输出 BR label1, 6. @SETlabel↓label3：设置标号label3 7. @BR↑label4：输出 BR label4, 8. @SETlabel↓label2：设置标号label2 */ /* //动作解释： //@ OUT：输出 OUT*/ /*<复合语句>::={<语句序列>} //动作解释： //@LOOK↓n↑d:查符号表n，给出变量地址d; 没有，变量没定义 //@IN：输出IN //@STI↓d：输出指令代码STI d*/ /*<表达式语句>::=<<表达式>;|; /*<表达式>::=<标识符>=<布尔表达式>|<布尔表达式> /*<布尔表达式>::=<算术表达式>|<算术表达式>(>|<|>=|<=|==|!=)<算术表达式> /*<算术表达式>::=<项>{(+|-)<项>} /*<项>::=<因子>{(*|/)<因子>} < term >::= /*<因子>::=(<算术表达式>)|<标识符>|<无符号整数> < factor >::=( 子函数的定义及部分代码： int program(); int compound_Stat(); int statement(); int expression_Stat(); int expression(); int bool_expr(); int additive_expr(); int term(); int factor(); int if_stat(); int while_stat(); int for_stat(); int write_stat(); int read_stat(); int declaration_stat(); int declaration_list(); int statement_list(); int compound_stat(); char token[20],token1[40];/*token保存单词符号，token1保存单词值*/ extern char Scanout[300]; /*保存词法分析输出文件名*/ FILE *fp; /*用于指向输入输出文件的指针*/ int TESTparse() { int es=0; if((fp=fopen(Scanout,"r"))==NULL) { printf("\n打开%s错误!\n",Scanout); es=10; return(es); } if (es==0) es=program()； switch(es) { case 0: printf("语法分析成功!\n");break; case 10: printf("打开文件 %s失败!\n",Scanout);break; case 1: printf("缺少{!\n");break; case 2: printf("缺少}!\n");break; case 3: printf("缺少标识符!\n");break; case 4: printf("少分号!\n");break; case 5: printf("缺少(!\n");break; case 6: printf("缺少)!\n");break; case 7: printf("缺少操作数!\n");break; case 21: printf("符号表溢出!\n");break; case 22: printf("变量重复定义!\n");break; case 23: printf("变量未声明!\n");break; } fclose(fp); fclose(fout); return(es); } 4.主函数： void main(){ int es=0; es=TESTscan();//调词法分析 if (es>0) printf("词法分析有错,编译停止!"); else printf("词法分析成功!\n"); if (es==0) { es=TESTparse(); //调语法、语义分析并生成代码｝｝ 四、测试与分析 把代码写在1.txt文档里，经词法分析的结果放在12.Txt里，语法分析器把12.Txt 当作输入文件，把分析的结果放在122.Txt里。 最后查看12.Txt和122.Txt文档，看看结果如何，是否符合要求。 部分结果如下： 【12.Txt：】ID b = = NUM 1 ）） < < write write ; ; ......... 【122.Txt】int int ID b ; ; read read ............. 查看12.Txt和122.Txt里的内容，经过分析结果符合要求，因为是简单的编译器，所以词法和语法分析的结果相对比较简单。 五、心得体会 经过做这次的课程设计，我学到了很多，巩固了以前所学的知识，也让自己掌握了不少自己不的东西，经过前后的复习、归纳、总结，对课本知识有了系统的掌握和理解。 首先对符号表有了一定的认识（包括名字栏和信息栏，其中名字栏作为关键字）；其次对编译原理的工作原理有了更深的了解，尤其是编译程序的这五个步骤中的词法（设计各单 词的状态转换图，并为不同的单词设计种别码），语法（用递归下降分析法实现对表达式、各种说明语句、控制语句进行语法分析）和语义分析了解更细更好，总体上把握了编程过程；最后是目标代码生成器，能完成指定寄存器个数的情况下将一中间代码程序段翻译成汇编语言目标代码。 编译原理语法分析实验报告 - 班级:XXX 学号:XXX 姓名:XXX 年月日 1、摘要: 用递归子程序法实现对pascal的子集程序设计语言的分析程序 2、实验目的: 通过完成语法分析程序，了解语法分析的过程和作用 3、任务概述 实验要求:对源程序的内码流进行分析，如为文法定义的句子输出”是”否则输出”否”,根据需要处理说明语句填写写相应的符号表供以后代码生成时使用 4、实验依据的原理 递归子程序法是一种自顶向下的语法分析方法，它要求文法是LL(1)文法。通过对文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式时，程序能够按LL(1)形式唯一地确定选择某个候选式进行推导，最终识别输入串是否与文法匹配。 递归子程序法的缺点是:对文法要求高，必须满足LL(1)文法，当然在某些语言中个别产生式的推导当不满足LL(1)而满足LL(2)时，也可以采用多向前扫描一个符号的办法;它的另一个缺点是由于递归调用多，所以速度慢占用空间多，尽管这样，它还是许多高级语言，例如PASCAL，C等编译系统常常采用的语法分析方法。 为适合递归子程序法，对实验一词法分析中的文法改写成无左递归和无左共因子的,,,如下: <程序>?<程序首部><分程序>。 <程序首部>?PROGRAM标识符; <分程序>?<常量说明部分><变量说明部分><过程说明部分> <复合语句> <常量说明部分>?CONST<常量定义><常量定义后缀>;|ε <常量定义>?标识符=无符号整数 <常量定义后缀>?，<常量定义><常量定义后缀> |ε <变量说明部分>?VAR<变量定义><变量定义后缀> |ε <变量定义>?标识符<标识符后缀>:<类型>; <标识符后缀>?，标识符<标识符后缀> |ε <变量定义后缀>?<变量定义><变量定义后缀> |ε <类型>?INTEGER | LONG <过程说明部分>?<过程首部><分程序>;<过程说明部分后缀>|ε <过程首部>?PROCEDURE标识符<参数部分>; <参数部分>?(标识符: <类型>)|ε <过程说明部分后缀>?<过程首部><分程序>;<过程说明部分后缀>|ε <语句>?<赋值或调用语句>|<条件语句>|<当型循环语句>|<读语句> |<写语句>|<复合语句>|ε <赋值或调用语句>?标识符<后缀> <后缀>?:=<表达式>|(<表达式>)|ε <条件语句>?IF<条件>THEN<语句> <当型循环语句>?WHILE<条件>DO <语句> <读语句>?READ(标识符<标识符后缀>) 语义分析实验报告 一、实验目的： 通过上机实习，加深对语法制导翻译原理的理解，掌握将语法分析所识别的语法成分变换为中间代码的语义翻译方法。 二、实验要求： 采用递归下降语法制导翻译法，对算术表达式、赋值语句进行语义分析并生成四元式序列。 三、算法思想： 1、设置语义过程。 （1）emit(char *result,char *ag1,char *op,char *ag2) 该函数的功能是生成一个三地址语句送到四元式表中。 四元式表的结构如下： struct { char result[8]; char ag1[8]; char op[8]; char ag2[8]; }quad[20]; (2) char *newtemp() 该函数回送一个新的临时变量名，临时变量名产生的顺序为T1，T2，… char *newtemp(void) { char *p; char m[8]; p=(char *)malloc(8); k++; itoa(k,m,10); strcpy(p+1,m); p[0]=’t’; return(p); } 2、函数lrparser 在原来语法分析的基础上插入相应的语义动作：将输入串翻译成四元式序列。在实验中我们只对表达式、赋值语句进行翻译。 四、源程序代码： #include 实验1-3-《编译原理》词法分析程序设计方案 实验1-3 《编译原理》S语言词法分析程序设计 方案 一、实验目的 了解词法分析程序的两种设计方法之一：根据状态转换图直接编程的方式； 二、实验内容 1．根据状态转换图直接编程 编写一个词法分析程序，它从左到右逐个字符的对源程序进行扫描，产生一个个的单词的二元式，形成二元式（记号）流文件输出。在此，词法分析程序作为单独的一遍，如下图所示。 源程序词法分析程序二元式文件 具体任务有： （1）组织源程序的输入 （2）拼出单词并查找其类别编号，形成二元式输出，得到单词流文件 （3）删除注释、空格和无用符号 （4）发现并定位词法错误，需要输出错误的位置在源程序中的第几行。将错误信息输出到屏幕上。 （5）对于普通标识符和常量，分别建立标识符表和常量表（使用线性表存储），当遇到一 个标识符或常量时，查找标识符表或常量表，若存在，则返回位置，否则返回0并且填写符号表或常量表。 标识符表结构：变量名，类型（整型、实型、字符型），分配的数据区地址 注：词法分析阶段只填写变量名，其它部分在语法分析、语义分析、代码生成等阶段逐步填入。 常量表结构：常量名，常量值 三、实验要求 1．能对任何S语言源程序进行分析 在运行词法分析程序时，应该用问答形式输入要被分析的S源语言程序的文件名，然后对该程序完成词法分析任务。 2．能检查并处理某些词法分析错误 词法分析程序能给出的错误信息包括：总的出错个数，每个错误所在的行号，错误的编号及错误信息。 本实验要求处理以下两种错误（编号分别为1，2）： 1：非法字符：单词表中不存在的字符处理为 编译原理实验报告实验名称：实验一编写词法分析程序 实验类型：验证型实验 指导教师：何中胜 专业班级：13软件四 姓名：丁越 学号： 电子邮箱： 实验地点：秋白楼B720 实验成绩： 日期：2016年3 月18 日 一、实验目的 通过设计、调试词法分析程序，实现从源程序中分出各种单词的方法；熟悉词法分析 程序所用的工具自动机，进一步理解自动机理论。掌握文法转换成自动机的技术及有穷自动机实现的方法。确定词法分析器的输出形式及标识符与关键字的区分方法。加深对课堂教学的理解；提高词法分析方法的实践能力。通过本实验，应达到以下目标： 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。 二、实验过程 以编写PASCAL子集的词法分析程序为例 1.理论部分 （1）主程序设计考虑 主程序的说明部分为各种表格和变量安排空间。 数组 k为关键字表，每个数组元素存放一个关键字。采用定长的方式，较短的关键字 后面补空格。 P数组存放分界符。为了简单起见，分界符、算术运算符和关系运算符都放在 p表中 （编程时，还应建立算术运算符表和关系运算符表，并且各有类号），合并成一类。 id和ci数组分别存放标识符和常数。 instring数组为输入源程序的单词缓存。 outtoken记录为输出内部表示缓存。 还有一些为造表填表设置的变量。 主程序开始后，先以人工方式输入关键字，造 k表；再输入分界符等造p表。 主程序的工作部分设计成便于调试的循环结构。每个循环处理一个单词；接收键盘上 送来的一个单词；调用词法分析过程；输出每个单词的内部码。 ⑵词法分析过程考虑 将词法分析程序设计成独立一遍扫描源程序的结构。其流程图见图1-1。 图1-1 该过程取名为 lexical，它根据输入单词的第一个字符（有时还需读第二个字符），判断单词类，产生类号：以字符 k表示关键字；i表示标识符；c表示常数；p表示分界符；s表示运算符（编程时类号分别为 1，2，3，4，5）。 对于标识符和常数，需分别与标识符表和常数表中已登记的元素相比较，如表中已有 该元素，则记录其在表中的位置，如未出现过，将标识符按顺序填入数组id中，将常数 变为二进制形式存入数组中 ci中，并记录其在表中的位置。 lexical过程中嵌有两个小过程：一个名为getchar，其功能为从instring中按顺序取出一个字符，并将其指针pint加1；另一个名为error，当出现错误时，调用这个过程， 输出错误编号。 2.实践部分 学号107 成绩 编译原理上机报告 名称：编写递归下降语法分析器 学院：信息与控制工程学院 专业：计算机科学与技术 班级：计算机1401班 姓名：叶达成 2016年10月31日 一、上机目的 通过设计、编制、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握常用的语法分析方法。通过本实验，应达到以下目标： 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。 二、基本原理和上机步骤 递归下降分析程序实现思想简单易懂。程序结构和语法产生式有直接的对应关系。因为每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。 递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。 每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。 自上向下分析过程中，如果带回溯，则分析过程是穷举所有可能的推导，看是否能推导出待检查的符号串。分析速度慢。而无回溯的自上向下分析技术，当选择某非终结符的产生时，可根据输入串的当前符号以及各产生式右部首符号而进行，效率高，且不易出错。 无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。 无左递归：既没有直接左递归，也没有间接左递归。 无回溯：对于任一非终结符号U的产生式右部x1|x2|…|x n，其对应的字的首终结符号两两不相交。 如果一个文法不含回路（形如P?+ P的推导），也不含以ε为右部的产生式，那么可以通过执行消除文法左递归的算法消除文法的一切左递归（改写后的文法可能含有以ε为右部的产生式）。 三、上机结果 测试数据： (1)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# (2)输出结果：i+i*i#为合法符号串 (3)输入一符号串如i+i*#,要求输出为“非法的符号串”。 程序清单： #include 编译原理实验报告 姓名： 学号： 班级： 学院： 南昌大学信息工程学院计算机系 2014年6月 目录 实验一 (3) 实验二 (8) 实验三 (15) 实验1 词法分析程序的设计 学生姓名：学号：专业班级： 实验类型：□验证□综合□设计□创新实验日期：实验成绩： 一、实验目的 掌握计算机语言的词法分析程序的开发方法。 二、实验内容 编制一个能够分析三种整数、标识符、主要运算符和主要关键字的词法分析程序。 三、实验要求 1、根据以下的正规式，编制正规文法，画出状态图； 标识符<字母>(<字母>|<数字字符>)* 十进制整数0 |（1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）* 如有余力，则进一步分析八进制和十六进制整数，其正规式如下： 八进制整数0（1|2|3|4|5|6|7）（0|1|2|3|4|5|6|7）* 十六进制整数0x（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）* 运算符和界符+ - * / > < =<= >=( ) ；{ } 关键字main if then else while do int (可根据需要添加) 2、根据状态图，设计词法分析函数int scan( )，完成以下功能： 1）从文本文件中读入测试源代码，根据状态转换图，分析出一个单词， 2）以二元式形式输出单词<单词种类，单词属性> 其中单词种类用整数表示： 0：标识符 1：十进制整数 2：八进制整数 3：十六进制整数 运算符和界符，关键字采用一字一符，不编码 其中单词属性表示如下： 标识符，整数由于采用一类一符，属性用单词表示 运算符和界符，关键字采用一字一符，属性为空 3、编写测试程序，反复调用函数scan( )，输出单词种别和属性。 四、实验环境 PC微机 DOS操作系统或Windows 操作系统 Turbo C 程序集成环境或Visual C++ 程序集成环境 编译原理实验--词法分析器 实验一词法分析器设计 【实验目的】 1(熟悉词法分析的基本原理，词法分析的过程以及词法分析中要注意的问题。 2(复习高级语言，进一步加强用高级语言来解决实际问题的能力。 3(通过完成词法分析程序，了解词法分析的过程。 【实验内容】 用C语言编写一个PL/0词法分析器，为语法语义分析提供单词，使之能把输入的字符 串形式的源程序分割成一个个单词符号传递给语法语义分析，并把分析结果(基本字， 运算符，标识符，常数以及界符)输出。 【实验流程图】 【实验步骤】 1(提取pl/0文件中基本字的源代码 while((ch=fgetc(stream))!='.') { int k=-1; char a[SIZE]; int s=0; while(ch>='a' && ch<='z'||ch>='A' && ch<='Z') { if(ch>='A' && ch<='Z') ch+=32; a[++k]=(char)ch; ch=fgetc(stream); } for(int m=0;m<=12&&k!=-1;m++) for(int n=0;n<=k;n++) { if(a[n]==wsym[m][n]) ++s; else s=0; if(s==(strlen(wsym[m]))) {printf("%s\t",wsym[m]);m=14;n=k+1;} } 2(提取pl/0文件中标识符的源代码 while((ch=fgetc(stream))!='.') { int k=-1; char a[SIZE]=" "; int s=0; while(ch>='a' && ch<='z'||ch>='A' && ch<='Z') { if(ch>='A' && ch<='Z') ch+=32; a[++k]=(char)ch; ch=fgetc(stream); } for(int m=0;m<=12&&k!=-1;m++) for(int n=0;n<=k;n++) { if(a[n]==wsym[m][n]) ++s; else s=0; if(s==(strlen(wsym[m]))) {m=14;n=k+1;} } if(m==13) for(m=0;a[m]!=NULL;m++) printf("%c ",a[m]); 《LL（1）分析器的构造》实验报告 一、实验名称 LL(1)分析器的构造 二、实验目的 设计、编制、调试一个LL(1)语法分析器，利用语法分析器对符号串的识别，加深对语法分析原理的理解。 三、实验内容和要求 设计并实现一个LL(1)语法分析器，实现对算术文法: G[E]:E->E+T|T T->T*F|F F->(E)|i 所定义的符号串进行识别，例如符号串i+i*i为文法所定义的句子，符号串ii+++*i+不是文法所定义的句子。 实验要求: 1、检测左递归，如果有则进行消除； 2、求解FIRST集和FOLLOW集； 3、构建LL(1)分析表； 4、构建LL分析程序，对于用户输入的句子，能够利用所构造的分析程序进行分析，并显示出分析过程。 四、主要仪器设备 硬件：微型计算机。 软件： Code blocks（也可以是其它集成开发环境）。 五、实验过程描述 1、程序主要框架 程序中编写了以下函数，各个函数实现的作用如下： void input_grammer(string *G);//输入文法G //将文法G预处理得到产生式集合P，非终结符、终结符集合U、u， int eliminate_1(string *G,string *P,string U,string *GG);//消除文法G中所有直接左递归得到文法GG int* ifempty(string* P,string U,int k,int n);//判断各非终结符是否能推导为空 string* FIRST_X(string* P,string U,string u,int* empty,int k,int n)；求所有非终结符的FIRST集 string FIRST(string U,string u,string* first,string s)；//求符号串s=X1X2...Xn的FIRST集 string** create_table(string *P,string U,string u,int n,int t,int k,string* first)；//构造分析表 void analyse(string **table,string U,string u,int t,string s)；//分析符号串s 2、编写的源程序 #include 课程实验报告课程名称：《编译原理》 专业班级：信息安全1302 学号： 姓名： 指导教师： 报告日期：2015年11月6日 计算机科学与技术学院 目录 目录 (2) 1 实验一词法分析 (3) 1.1实验目的 (3) 1.2实验要求 (3) 1.3算法思想 (4) 1.4实验程序设计说明 (5) 1.5词法分析实现 (6) 1.6词法实验结果及结果分析 (11) 2 实验二语法分析 (12) 2.1 实验目的 (12) 2.2 实验要求 (12) 2.3 算法思想 (12) 2.4 实验程序设计说明 (14) 2.5 语法分析实现 (14) 4 实验中遇到的问题及解决 (22) 参考资料 (23) 1 实验一词法分析 1.1 实验目的 设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 1.2 实验要求 1、待分析的简单的词法 （1）关键字： main int char if else for while 所有的关键字都是小写。 （2）运算符和界符 ：= + -* / < <= <> > >= = == != ; ( ) [ ] { } #（3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义： ID = letter (letter | digit)* NUM = digit digit* （4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。 2、各种单词符号对应的种别码： 表1 各种单词符号对应的种别码 3、词法分析程序的功能： 输入：所给文法的源程序字符串。 输出：二元组（syn,token或sum）构成的序列。 其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。 例如：对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件，经过词法分析后输出如下序列： (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 1.3 算法思想 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 1、主程序示意图： 主程序示意图如图1所示。其中初始包括以下两个方面： ⑴关键字表的初值。 关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下： Char *rwtab[6] = {“begin”, “if”, “then”, “while”, “do”, “end”,}; 开始 置初值 调用扫描子程序 输出单词二元组 否 输入串结束? 是 结束 图1 主程序示意图 实验1-3 《编译原理》S语言词法分析程序设计方案 一、实验目的 了解词法分析程序的两种设计方法之一：根据状态转换图直接编程的方式； 二、实验内容 1．根据状态转换图直接编程 编写一个词法分析程序，它从左到右逐个字符的对源程序进行扫描，产生一个个的单词的二元式，形成二元式（记号）流文件输出。在此，词法分析程序作为单独的一遍，如下图所示。 具体任务有： （1）组织源程序的输入 （2）拼出单词并查找其类别编号，形成二元式输出，得到单词流文件 （3）删除注释、空格和无用符号 （4）发现并定位词法错误，需要输出错误的位置在源程序中的第几行。将错误信息输出到屏幕上。 （5）对于普通标识符和常量，分别建立标识符表和常量表（使用线性表存储），当遇到一个标识符或常量时，查找标识符表或常量表，若存在，则返回位置，否则返回0并且填写符号表或常量表。 标识符表结构：变量名，类型（整型、实型、字符型），分配的数据区地址 注：词法分析阶段只填写变量名，其它部分在语法分析、语义分析、代码生成等阶段逐步填入。 常量表结构：常量名，常量值 三、实验要求 1．能对任何S语言源程序进行分析 在运行词法分析程序时，应该用问答形式输入要被分析的S源语言程序的文件名，然后对该程序完成词法分析任务。 2．能检查并处理某些词法分析错误 词法分析程序能给出的错误信息包括：总的出错个数，每个错误所在的行号，错误的编号及错误信息。 本实验要求处理以下两种错误（编号分别为1，2）： 1：非法字符：单词表中不存在的字符处理为非法字符，处理方式是删除该字符，给出错误信息，“某某字符非法”。 2：源程序文件结束而注释未结束。注释格式为：/* …… */ 四、保留字和特殊符号表 词法分析 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 3.1 主程序示意图： 扫描子程序主要部分流程图 其他 词法分析程序的C语言程序源代码： // 词法分析函数: void scan() // 数据传递: 形参fp接收指向文本文件头的文件指针； // 全局变量buffer与line对应保存源文件字符及其行号，char_num保存字符总数。 void scan() { char ch; int flag,j=0,i=-1; while(!feof(fp1)) { ch=fgetc(fp1); flag=judge(ch); printf("%c",ch);//显示打开的文件 if(flag==1||flag==2||flag==3) {i++;buffer[i]=ch;line[i]=row;} else if(flag==4) {i++;buffer[i]='?';line[i]=row;} else if(flag==5) {i++;buffer[i]='~';row++;} else if(flag==7) continue; else cout<<"\n请注意，第"< 编译原理实验报告 实验名称：编写语法分析分析器实验类型： 指导教师： 专业班级： 学号： 电子邮件： 实验地点： 实验成绩： 一、实验目的 通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。 1、选择最有代表性的语法分析方法，如LL(1) 语法分析程序、算符优先分析程序和LR分析分析程序，至少选一题。 2、选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。 二、实验过程 编写算符优先分析器。要求： （a）根据算符优先分析算法，编写一个分析对象的语法分析程序。读者可根据自己的能力选择以下三项(由易到难)之一作为分析算法中的输入： Ⅰ：通过构造算符优先关系表，设计编制并调试一个算法优先分析程序Ⅱ：输入FIRSTVT，LASTVT集合，由程序自动生成该文法的算符优先关系矩阵。 Ⅲ：输入已知文法，由程序自动生成该文法的算符优先关系矩阵。（b）程序具有通用性，即所编制的语法分析程序能够使用于不同文法以及各种输入单词串，并能判断该文法是否为算符文法和算符优先文法。 （c）有运行实例。对于输入的一个文法和一个单词串，所编制的语法分析程序应能正确地判断，此单词串是否为该文法的句子，并要求输出分析过程。 三、实验结果 算符优先分析器： 测试数据：E->E+T|T T->T*F|F F->(E)|i 实验结果：(输入串为i+i*i+i) 四、讨论与分析 自下而上分析技术－算符优先分析法： 算符文法：一个上下无关文法G，如果没有且没有P→..QR...(P ,Q ,R属于非终结符)，则G是一个算符文法。 FIRSTVT集构造 1、若有产生式P →a...或P →Qa...，则a∈FIRSTVT(P)。 2、若有产生式P→...，则FIRSTVT(R)包含在FIRSTVT(P)中。由优先性低于的定义和firstVT集合的定义可以得出：若存在某个产生式：…P…，则对所有：b∈firstVT(P)都有：a≦b。 构造优先关系表： 1、如果每个非终结符的FIRSTVT和LASTVT集均已知,则可构造优先关系表。 2、若产生式右部有...aP...的形式，则对于每个b∈FIRSTVT(P)都有 编译原理程序设计报告 一个简单文法的编译器的设计与实现专业班级：计算机1406班 组长姓名：宋世波 组长学号： 20143753 指导教师：肖桐 2016年12月 设计分工 组长学号及姓名：宋世波20143753 分工：文法及数据结构设计 词法分析 语法分析（LL1） 基于DAG的中间代码优化 部分目标代码生成 组员1学号及姓名：黄润华20143740 分工：中间代码生成(LR0) 部分目标代码生成 组员2学号及姓名：孙何奇20143754 分工：符号表组织 部分目标代码生成 摘要 编译器是将便于人编写，阅读，维护的高级计算机语言翻译为计算机能解读、运行的低阶机器语言的程序。编译是从源代码（通常为高阶语言）到能直接被计算机或虚拟机执行的目标代码（通常为低阶语言或机器语言）的翻译过程。 一．编译器的概述 1.编译器的概念 编译器是将便于人编写，阅读，维护的高级计算机语言翻译为计算机能解读、运行的低阶机器语言的程序。编译器将原始程序作为输入，翻译产生使用目标语言的等价程序。源代码一般为高阶语言如Pascal、C++、Java 等，而目标语言则是汇编语言或目标机器的目标代码，有时也称作机器代码。 2．编译器的种类 编译器可以生成用来在与编译器本身所在的计算机和操作系统（平台）相同的环境下运行的目标代码，这种编译器又叫做“本地”编译器。另外，编译器也可以生成用来在其它平台上运行的目标代码，这种编译器又叫做交叉编译器。交叉编译器在生成新的硬件平台时非常有用。“源码到源码编译器”是指用一种高阶语言作为输入，输出也是高阶语言的编译器。例如: 自动并行化编译器经常采用一种高阶语言作为输入，转换其中的代码，并用并行代码注释对它进行注释（如OpenMP）或者用语 编译原理词法分析程序设计实验报告 【实验目的】 1．了解词法分析的主要任务。 2．熟悉编译程序的编制。 【实验容】 根据某文法，构造一基本词法分析程序。找出该语言的关键字、标识符、整数以及其他一些特殊符号，给出单词的种类和值。 【实验要求】 1.构造一个小语言的文法 类C小语言文法（以EBNF表示） <程序>：：=<分程序>{<分程序>} . <分程序>：：=<标识符>’(’<变量说明部分>{,<变量说明部分>}’)’<函数体> <变量说明部分>：：=int<标识符>{,<标识符>} <函数体>：：=’{’[<变量说明部分>;]<语句序列>’}’ <语句序列>：：=<语句序列>;<语句>|<语句> <语句>：：=<赋值语句>|<条件语句>|<循环语句>|<函数调用语句> <赋值语句>：：=<标识符>=<表达式> <表达式>：：=[+|-]<项>{<加法运算符><项>} <项>：：=<因子>{<乘法运算符><因子>} <因子>：=<标识符>|<无符号整数> <加法运算符>：：= +|- <乘法运算符>：：= *|/ <条件语句>：：=if<条件>’{’<语句序列>’}’[else’{’<语句序列>’}’] <条件>：：=<表达式><关系运算符><表达式> <关系运算符>：：= ==|!=|>|<|>=|<= <循环语句>：：=for’(’<表达式>;<条件>;<表达式>’)’ ’{’<语句序列>’}’ <函数调用语句>：：=<标识符>’(’<标识符>{,<标识符>}|<空>’)’ <标识符>：：=<字母>{<字母>|<数字>} <无符号整数>：：=<数字>{<数字>} <字母>：：=a|b|c|…|X|Y|Z <数字>：：=0|1|2|…|8|9 单词分类情况 关键字：int if else for 标识符：以字母开头的字母和数字的组合 关系运算符： ==|!=|>|<|>=|<= 加法运算符：+|- 乘法运算符： *|/界符：，；{ } ( ) 2.设计单词的输出形式，单词的种类和值的表示方法 种别码单词值 如：1 int 3. 编写词法分析程序cffx.c 实现基本的词法分析器，能够分析关键字、标识符、数字、运算符（需要有“==”或“：=”之类需要超前搜索的运算符）以及其他一些符号。 // 编译原理词法分析程序.cpp #include 实验报告 班级：14 姓名： oneseven 学号： 一．题目：词法分析程序设计与实现 * 二．实验内容：设计并实现 C 语言的词法分析程序，要求如下。 (1) 可以识别出用C语言编写的源程序中的每个单词符号，并以记号的形式输出每个单词符号。 (2) 可以识别并读取源程序中的注释。 (3) 可以统计源程序中的语句行数、单词个数和字符个数，其中标点和空格不计算为单词，并输出统计结果。 (4) 检查源程序中存在的非法字符错误，并可以报告错误所在的行列位置。 三．实现要求：采用C/C++作为实现语言，手工编写词法分析程序。 ； 四．实现功能：基本完成了实验内容中要求的所有功能。(1)识别出源程序中的每个单词符号，并以记号的形式输出每个单词符号(2)识别并读取源程序中的注释(3) 统计源程序中的语句行数、单词个数和字符个数(4) 检查源程序中存在的非法字符错误，并可以报告错误所在的行列位置。 注：本程序未把注释中的单词符号，“”中的单词符号统计在单词个数中。单词个数只包括了标示符，关键字，无符号数。 五．实验原理： 1.词法分析程序的功能： 输入源程序，输出单词符号的记号形式，如图所示： > 源程序词法分析器单词符号的记号形式 词法分析器 2.处理过程：每次调用词法分析程序，它均能自动继续扫描下去，形成下一个单词，直至整个源程序全部扫描完毕，并形成相应的单词串形式的源程序。 六．代码 #include 实验二语法分析器 一、实验目的 通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培养适应社会多方面需要的能力。 二、实验内容 ◆根据某一文法编制调试LL （1 ）分析程序，以便对任意输入的符号串 进行分析。 ◆构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分 析程序。 ◆分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号 以及LL（1）分析表，对输入符号串自上而下的分析过程。 三、LL（1）分析法实验设计思想及算法 ◆模块结构： （1）定义部分：定义常量、变量、数据结构。 （2）初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）； （3）控制部分：从键盘输入一个表达式符号串； （4）利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。 四、实验要求 1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。 2、如果遇到错误的表达式，应输出错误提示信息。 3、对下列文法，用LL（1）分析法对任意输入的符号串进行分析：（1）E->TG （2）G->+TG|—TG （3）G->ε （4）T->FS （5）S->*FS|/FS （6）S->ε （7）F->(E) （8）F->i 输出的格式如下： 五、实验源程序 LL1.java import java.awt.*; import java.awt.event.*; import javax.swing.*; import javax.swing.table.DefaultTableModel; import java.sql.*; import java.util.Vector; public class LL1 extends JFrame implements ActionListener { /** * */ private static final long serialVersionUID = 1L; JTextField tf1; JTextField tf2; JLabel l; JButton b0; JPanel p1,p2,p3; JTextArea t1,t2,t3; JButton b1,b2,b3; 电子科技大学 实验报告 学生姓名：学号：指导教师： 实验地点：实验时间： 一、实验室名称：计算机学院软件工程实验室 二、实验项目名称：词法分析器的设计与实现 三、实验学时：4学时 四、实验原理 1.编译程序要求对高级语言编写的源程序进行分析和合成，生成目标程序。词法分析是对源程序进行的首次分析，实现词法分析的程序为词法分析程序。 2.词法分析的功能是从左到右逐个地扫描源程序字符串，按照词法规则识别出单词符号作为输出，对识别过程中发现的词法错误，输出相关信息。 3.状态转换图是有限有向图，是设计词法分析器的有效工具。 五、实验目的 通过设计词法分析器的实验，使同学们了解和掌握词法分析程序设计的原理及相应的程序设计方法，同时提高编程能力。 六、实验内容 实现求n！的极小语言的词法分析程序，返回二元式作为输出。 七、实验器材（设备、元器件） 1.操作系统：Windows XP 2.开发工具：VC6.0 3.普通PC即可 八、实验步骤 （1）启动VC6.0，创建空白工程项目。选择菜单中的“文件”->“新建”->“项目”，在弹出的对话框中，左边的“项目类型”框中，选择“Visual C++ 项目”，在右边框中，选择“空项目(.Net)”，在对话框下边，选择工程文件存放目录及输入名称，如Example1，单击“确定”。 （2）建立相应的单词符号与种别对照表； （3）根据状态转换图编写相应的处理函数； （4）完成词法分析器； （5）编译与调试以上程序； （6）生成相应的*.dyd文件，作为后面语法分析的输入文件。 九、实验数据及结果分析 可以对源程序进行词法分析，如果有错给出出错信息和所在行数，如果无错则生成二元式文件。 十、实验结论 本实验程序较好地完成了词法分析程序的设计与实现，能够对所给文法的程序进行词法分析，在没有词法错误的时候生成相应的二元式文件。该实验程序可一次性给出源程序中的词法错误。 十一、总结及心得体会 通过该实验，对词法分析程序的设计，以及运用C语言进行编程有了更深刻的理解，同时加深了自己对词法分析程序的原理的理解与掌握，提高了自己的动手能力。 十二、对本实验过程及方法、手段的改进建议 程序设计合理，代码可进一步优化。 报告评分： 指导教师签字： 语法分析器的设计 一、实验内容 语法分析程序用LL(1)语法分析方法。首先输入定义好的文法书写文件(所用的文法可以用LL(1)分析)，先求出所输入的文法的每个非终结符是否能推出空，再分别计算非终结符号的FIRST集合，每个非终结符号的FOLLOW集合，以及每个规则的SELECT集合，并判断任意一个非终结符号的任意两个规则的SELECT 集的交集是不是都为空，如果是，则输入文法符合LL(1)文法，可以进行分析。对于文法： G[E]: E->E+T|T T->T*F|F F->i|(E) 分析句子i+i*i是否符合文法。 二、基本思想 1、语法分析器实现 语法分析是编译过程的核心部分，它的主要任务是按照程序的语法规则，从由词法分析输出的源程序符号串中识别出各类语法成分，同时进行词法检查，为语义分析和代码生成作准备。这里采用自顶向下的LL(1)分析方法。 语法分析程序的流程图如图5-4所示。 语法分析程序流程图 该程序可分为如下几步： （1）读入文法 （2）判断正误 （3）若无误，判断是否为LL(1)文法 （4）若是，构造分析表； （5）由句型判别算法判断输入符号串是为该文法的句型。 三、核心思想 该分析程序有15部分组成： （1）首先定义各种需要用到的常量和变量； （2）判断一个字符是否在指定字符串中； （3）读入一个文法； （4）将单个符号或符号串并入另一符号串； （5）求所有能直接推出&的符号； （6）求某一符号能否推出‘& ’； （7）判断读入的文法是否正确； （8）求单个符号的FIRST； （9）求各产生式右部的FIRST； （10）求各产生式左部的FOLLOW； （11）判断读入文法是否为一个LL(1)文法； （12）构造分析表M； （13）句型判别算法； （14）一个用户调用函数； （15）主函数； 下面是其中几部分程序段的算法思想： 1、求能推出空的非终结符集 Ⅰ、实例中求直接推出空的empty集的算法描述如下： void emp(char c){ 参数c为空符号 char temp[10];定义临时数组 int i; for(i=0;i<=count-1;i++)从文法的第一个产生式开始查找 { if 产生式右部第一个符号是空符号并且右部长度为1, then将该条产生式左部符号保存在临时数组temp中 将临时数组中的元素合并到记录可推出&符号的数组empty中。 } Ⅱ、求某一符号能否推出'&' int _emp(char c) { //若能推出&，返回1；否则，返回0 int i,j,k,result=1,mark=0; char temp[20]; temp[0]=c; temp[1]='\0'; 存放到一个临时数组empt里,标识此字符已查找其是否可推出空字 如果c在可直接推出空字的empty[]中,返回1 for(i=0;;i++) { if(i==count) return(0); 找一个左部为c的产生式 j=strlen(right[i]); //j为c所在产生式右部的长度 if 右部长度为1且右部第一个字符在empty[]中. then返回1(A->B,B可推出空) if 右部长度为1但第一个字符为终结符,then 返回0(A->a,a为终结符) else编译原理语法分析实验报告
编译原理语义分析实验报告——免费!
实验1-3-《编译原理》词法分析程序设计方案
编译原理实验报告实验一编写词法分析程序
编译原理-编写递归下降语法分析器
编译原理实验报告
编译原理实验--词法分析器
编译原理实验报告《LL(1)语法分析器构造》
编译原理报告 (2)
实验1-3-《编译原理》词法分析程序设计方案
编译原理词法分析和语法分析报告 代码(C语言版)
编译原理-语法分析-算符优先文法分析器
编译原理课程设计报告(一个完整的编译器)
编译原理词法分析程序的设计实验报告
北邮编译原理-词法分析文档和程序
编译原理 语法分析器 (java完美运行版)
编译原理标准实验报告
编译原理语法分析器实验
相关主题
文本预览