编译原理课程设计
For循环语句的语法分析及语义分析程序设计
----递归下降法、输出四元式1.系统描述
1．1目的
通过设计、编制、调试一个FOR循环语句的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。1．2设计内容及步骤
对循环语句的运行过程描述：FOR（赋值语句1或空；布尔表达式2；循环变量+步长）{ 赋值语句 }，for中的三个部分都可以包含多于一个的式子，其中第一部分为对循环变量赋初值；第二部分为判断循环条件是否满足，里面会用到循环变量；第三部分为对每执行一次循环就对循环变量做一次改变，并以此为基础判断循环条件。该语句的执行顺序为，第一次执行该循环第一部分的语句，在完成循环体部分的执行后，进入第三部分对循环变量做调整，然后到第二部分判断循环条件是否满足情况，是则进入循环体，然后再按以上顺序循环做；否则跳出循环。得到以下流程图：
(1)写出递归下降语法分析方法要求的文法和属性文法描述。
(2)描述递归下降语法分析方法的思想。
(3)给出中间代码序列的结构设计。
(4)完成相应的词法分析、语法分析和语义分析程序设计。
(5)测试用例和测试结果。设计不同的测试用例以显示程序的各种功能，包括简
单的for循环和for循环的嵌套。并记录测试结果。
2 翻译过程
2.1词法分析
词法分析是计算机科学中将字符序列转换为单词（Token）序列的过程。进
行语法分析的程序或者函数叫作词法分析器（Lexical analyzer，简称Lexer），也叫扫描器（Scanner）。词法分析器一般以函数的形式存在，供语法分析器调用。词法分析是编译过程中的第一个阶段，在语法分析前进行。也可以和语法分析
结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。简化设计、改进编译效率、增加编译系统的可移植性。词法分析是编制一个读单词的过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。单词的分类主要分为五类：
1. 关键字：由程序语言定义的具有固定意义的标识符。也称为保留字或基本字。
2. 标识符：用来表示程序中各种名字的字符串。
3. 常数：常数的类型一般有整型、实型、布尔型、文字型。
4. 运算符：如+、－、*、/ 等。
5. 界限符：如逗号、分号、括号等。
这里将词法分析程序设计成一个子程序，每当语法分析程序需要一个单词时，则调用该子程序。词法分析程序每调用一次，便从源程序文件中读入一些字符，直到识别出一个单词。
2.2、语法分析
采用递归下降方法，为对应文法中的每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串。若输入串是给定文法的句子，则从文法的开始符号出发一定能推导出与输入的单词串完全相同的句子。
语法分析是编译过程的一个逻辑阶段。语法分析的任务是在的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等。语法分析
程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述.语法分析程序可以用YACC等工具自动生成。
语法分析是编译程序的核心部分,其主要任务是确定语法结构,检查语法错误，报告错误的性质和位置，并进行适当的纠错工作。语法分析的主要工作：是识别由词法分析给出的单词序列是否是给定的正确句子（程序）。语法分析常用的方法：自顶向下的语法分析和自底向上的语法分析两大类。此次设计中语法分析中主要通过递归下降分析法对语法分析处理过程进行控制，使输出的三地址表示的翻译的工作有条不紊的进行，同时识别语法分析中的语法错误。
递归下降法主要采用自顶向下方法，即从文法的开始符号开始进行分析，逐渐推导的往下构造语法树，使其树叶正好构造出所给定的源程序串。自顶向下方法的关键是确定在推导过程中选择候选式的问题。当进行推导时，一个非终结符可能对应多个产生式，这样我们就无法事先知道应该用哪个产生式，因此实用都作了一些限制。以便在任何情况下都能确定应该用的产生式。
自顶向下的主要思想是从开始符出发导出句型并一个符号一个符号地与给定终结符串进行匹配。如果全部匹配成功，则表示开始符号可推导出给定的终结符串。因此判定给定终结符号串是正确句子。
在语法分析的同时可由语法分析程序调用相应的语义子程序进行语义处理，完成附加在所使用的产生式上的语义规则描述，并生成四元式的中间代码形式。词法分析程序和语法分析程序的关系：
2.3中间代码生成
中间代码，也称中间语言，是复杂性介于源程序语言和机器语言的一种表示形式。为了使编译程序有较高的目标程序质量，或要求从编译程序逻辑结构上把与机器无关和与机器有关的工作明显的分开来时，许多编译程序都采用了某种复杂性介于源程序语言和机器语言之间的中间语言。中间代码（语言）是一种特殊结构的语言，编译程序所使用的中间代码有多种形式。按其结构分常见的有逆波兰式（后缀式）、三地址代码（三元式、四元式）和树形表示（抽象语法树）、DAG
表示。本次课程设计要实现的是四元式表示。
2.4属性文法
对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。所谓语法制导的翻译指的是在语法分析过程中，完成这些语义规则描述的动作，从而实现语义处理。一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每个产生式上。本系统中所使用FOR循环语句的文法包括FOR语句本身，赋值表达式和布尔表达式。
3 递归下降法
递归下降法又称递归子程序法。在程序语言的语法定义中有许多采用递归定义。我们在对它进行语法分析时，编制的处理程序也采取递归的方式，可使其结构简单易读。但由于频繁地调用子程序大大地降低了分析速度。
3.1 主要思想
对每个非终结符按其产生式结构写出相应语法分析子程序。因为文法递归相应子程序也递归，子程序的结构与产生式结构几乎一致。所以称此种方法称为递归子程序法或递归下降法。
3.2 用程序表示递归子程序的内部结构
设A是一个非终结符：A→β1
A→β2
┊
A→βn
则写ζ(A) ? if char∈first(β1) thenζ(β1)
else if char∈first(β2 ) then ζ(β2 )
else…
if char∈first(βn ) then ζ(βn)
else ERROR
其中ζ(βi)表示调用处理符号串βi的子程序。
对A的任一右部i 设为：βi = y1 y2 … yn
则定义ζ( βi) ?beginζ(y1);ζ(y2);…;ζ(yn) end
其中yj可分为下列两种情况（j=1,…,n):
1) yj∈VT,则ζ( yj) if char≠ yj then ERROR else READ(char)
2) yj∈VN,则ζ(yj)表示调用关于yj的递归子程序。
3．3递归下降法对文法的限制：
1任一非终结符B都不是左递归的，否则会产生死循环。
2对A的任意两个右部βi , βj ,有：first(βi)∩first(βj)=φ 。First(βi)表示βi所能导出串的第一个符号的集合。显然，每个βi的first(βi)是互不相同的，否则则无法判断应执行哪个ζ(βi )。
4 文法及属性文法的描述
对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。所谓语法制导的翻译指的是在语法分析过程中，完成这些语义规则描述的动作，从而实现语义处理。一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每个产生式上。形式上讲，属性文法是一个三元组 :A=(G，V，F)，其中：
G:是一个上下文无关文法；
V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连,这些属性代表与文法符号相关信息；F:关于属性的属性断言或一组属性的计算规则(称为语义规则) 。断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终结符相联的属性。
5.解题过程
5.1 文法设计
本次课程设计具体文法需要满足的条件如下：
1)S->for (A;B;C) {D}
2)A->G=F|ε
3)B->G
4)C->G++|G--|G=F
5)D->SD|C;D|ε
6)E->G|0|1|2|3|4|5|6|7|8|9
7)F->E*E|E/E|E+E|E-E|-E|E
8)G->a|b|c…|x|y|z
由于递归下降法需要文法为LL(1)文法，而该文法这个时候并不是LL（1）文法，顾要对其进行消除做递归的操作。1.提取做公共因子 2.消除左递归后，得到文法如下：
1)S->for (A; B; C) {D}
2)A->G=F|ε
3)B->GJ
4)C->GH
5)D->SD|C;D|ε
6)E->G|0|1|2|3|4|5|6|7|8|9
7)F->EI|-E
8)G->a|b|c…|x|y|z
9)H->++|--|=F
10)I->*E|/E|+E|-E|ε
11)J->
12)K->E|=E
以上文法为消除左公共因子和消除左递归后的情况，检验发现，他确实为LL(1)文法。注意，本次报告为了简化题目来避免递归等情况的发生，提出了以下限制：1.每次+-*/运算都只能有一次；2.每次的变量都只能由一个字符组成；
3.数字在0~9范围内；
4.必须对控制变量初始化
5.2语法分析方法设计
通过该文法，结合课件上的例子，可以看出，我们可以把每一个终结符都设计为一个子函数，通过互相调用来以递归子程序的形式完成程序设计。这里拿以下文法来打个比方：
E→TE′
E′→+T E′|ε
T→FT ′
T′→ * FT′|ε
F→i |（E）
根据以上文法可写出：
（1）E→TE′
非终结符E对应的子程序为：
E( ) {T( );E'( );}
E′→+T E′|ε
非终结符E'对应的子程序为：
E' ( )
{ if sym＝’+’ { read(sym);T( ); E' ( ); }
else if sym∈FOLLOW(E') return;
else error( );
}
这个非终结符给了一个很好的例子，里面同时包括了非终结符和终结符，这个子程序按照通过以该非终结符为左端的产生式，逐个分析后面的符号，若是终结符，就读入它；若是非终结符，就调用这个函数；否则若出现不可能的情况就报错。这里面还有一个比较特殊的情况，即产生式中有空串的存在，这个时候除了讨论产生式中已有的终结符外，由编译原理的相关原理可以知道，Follow集包含某非终结符后面可能出现的所有的终结符，因此还需要该终结符讨论Follow集，再判断是否出错。
对每个产生式都作类似处理后，主函数情况如下：
main( ){
read(sym);E( );
if (sym= ='#' ) printf(“分析成功”)；
else printf(“分析失败”)；
}
这里判断分析完所有开始符号所产生的符号列后，判断该句子是否为该文法的合法句子，这里需要检查下个字符是否为字符‘#’，由于产生式中是不含‘#’
的，这里它代表着输入句子的结束。若在调用完了所有非终结符的函数后，下一个字符不为‘#’，说明推出的句子只是输入句子的一部分，而该句子并不是该文法的合法句子，若是等于‘#’的，说明该句子可以在有限不内由文法得出，是该文法合法的句子。
完成以上部分以后就可以判别该句子是否是合法的了，然后下一步是生成中间代码，这里以四元式进行表示。我的想法是，在判断非终结符的时候，以本题为例，初始符号S->for(A;B;C){D},其中的A,B,C,D分别都代表着不同形式的式子，像有比大小，运算，赋值等，大多数每一个都是可以用一个四元式来表示的，因此，这里我采取的方法是在程序分析过程中，将每个非终结符推出的句子分别按字符和运算符用两个数组存储起来，待这个非终结符分析完毕以后，就将这两个数组中的数据复制到一个结构体数组中，结构体中有五个元素，分别是运算符，第一个运算数，第二个运算数，下一个跳转的结点，运算得到的运算结果。这时两个数组中的数据，由于类型不同，这里用if else给他们不同的方法给存储四元式的结构体数组赋值保存下来。
在分析完所有的程序后，若该句子合法，就输出这些中间代码，这个时候的四元式是按分析顺序排列的，因此不符合正确的运行顺序，需要设计算法将他们排列布置好。其中中间代码的形式为（操作符，操作数1，操作数2，运算结果/跳转目的地址）。
5.3算法描述
递归下降法是一种有顶到底逐个字符分析的方法，由于递归下降法的使用，需要写出所有非终结符的分析函数，他们之间互相调用，这里对他们就不做详细描述了，有一点要说明，对非终结符A B C D来说，他们是比较特别的，我们会就他们为单位，来建立ArgStack和OpStack两个字符数组，同时记录其中的字符个数flag1和flag2。这些函数串联了整个语法分析的过程。
getSYS(){}
若当前OpStack中存的操作符为=-，那么这里需要对两个四元式进行初始化，对ArgStack[flag1-1]的元素进行求负运算，并将结果赋给ArgStack[flag1-2]的元素。
若当前运算符为！=，--，>=或<=。将四元式的op的第一个元素赋值为字符j，剩下两个赋值为当前运算符，操作数分别为ArgStack中第一个和第二个元素组成，最后的跳转位置待定。
若当前运算符为+ - * /，那么这里需要产生两个四元式，第一个四元式用来进行运算，运算符为其中一个，两个操作数为ArgStack中的后两个，第四个为结果，是一个临时变量，用t来表示；第二个进行赋值，运算符为=，两个操作数分别为t和空，运行结果为ArgStack中的第一个元素。
若当前运算符为< >的情况，那么这里的运算符即为OpStack中第一个元素，两个操作数为ArgStack中的前两个元素，第四个为跳转地址，这里初始化为他后面两个的位置。
若当前运算符为++或--，则四元式很简单，运算符为+或-，第一个操作数与第四个结果均为ArgStack中第一个元素，而第二个运算数为1.
}
Sort（）{//主要实现对生成的四元式规范化
先找到对循环变量自加或自减的位置，对呀S产生式中C的位置，、；
从四元式组的末尾开始检测，遇到符合条件的就把他移到队尾；
再检测判断语句的正确性，从四元式组由开始向后，若遇到与循环变量有关的判断语句，则将它的跳转地址设置为他的位置加上2；
然后对每个循环变量自加位置的后面，都添加上直接跳转语句，由于我们都知道在for语句中，循环变量在每次方法体运行完成后变化后，都要跳到判断条件那里做判断，因此，这里由末尾到头将新添加的四元式的跳转地址设置依次等于从四元式开头开始查找的条件判断列的地址。
}
Print（）{
对已经完成组织的四元式列进行输出}
Analyze（）{
调用S（）；
并且判断是否该句子在该文法下合法；}
Main（）{
对各种数组进行初始化，包括四元式；
输入要分析的字符串；
将这些字符串合并在一个字符数组中；
调用分析语句的程序；
}
5.4 用例分析
1）该用例是本分析程序的一个比较典型的简单的输入，得到结果如下：
2）当for语句嵌套for语句时的运行结果：
3）当多输入一个字符时，程序的运行结果，这里是在结尾处多加了一个字符‘}’
4）为了简化问题，本程序是不支持字符串的，只支持单个字符作为标识符，当输入两个或以上字母或数字时，会出现以下错误：
5）由下图可知，本程序的for语句中必须对循环变量进行初始化：
6）增加下难度，三层for循环的嵌套，输出正确
6.程序的评价及心得体会：
首先，本程序优点是能正确的分析出许多for循环下的用例且比较易懂支持循环嵌套。但是相对于我从网上看的那些程序来说，网上的程序都是可以从文件中直接读入数据的，而不用将程序每次运行都要输入或是存在代码中，输出也是在文件中，相比之下我的输入方法就比较麻烦，每次运行都需要重新输入要分析的程序，当然也可以在程序段中初始化一段程序。并且这里的语句的适用范围并不大，例如数字只能是一位数等，有一些缺陷。
在编写这个程序的过程中，遇到的最大的困难就是如何将程序与四元式连接起来的问题，其中语法分析过程中的各个非终结符为名的函数的互相调用的方法提醒了我，为什么不在这个过程中添加一些功能，是分析过的字符进到数组中，到了一个地方时加以分析呢，这就是S（）里面语句和getSYS（）函数的由来；另外在编写的过程中有些粗心了，因为一个变量名的错误，造成结果出错或陷入死循环，要花费很多时间来找到并修改他，也就浪费了许多时间。再者就是对文件数据流的掌握不是很好。应当学习更多的内容来补上，像算符优先法等内容。本次课程设计，花了许多时间，也曾抓狂，但结果也算是小小的胜利吧。再接再厉，继续努力！
7.参考文献：
《编译原理》主编：吕映芝、张素琴、蒋维杜出版社：清华大学出版社
出版时间：2004年11月8.源程序清单：
#include
#include
using namespace std;
#define LINE 10
#define LENGTH 30//输入时的最大的行数和每行的字符数
#define SIZE 30//四元式数组的大小
int flag,flag1,flag2;//flag1用来标记运算符的栈的尾，flag2用来标记运算数的栈的尾
int Number;//用来记录四元式的个数
int NUMBER;//用来记录回去的位置
char
array[100],ArgStack[5],OpStack[5];//arr ay用来存储合并后的所有输入，
ArgStack用来存储某一个非终结符推出的字符，如数字和字母，OpStack数组用来存放某一个阶段一个非终结符推出的运算符
void
A(),B(),C(),D(),E(),F(),G(),H(),I(),J(),K(),S(); //声明函数，他们都为非终结符
struct siyuanshi{//每个四元式中
char op[3];//操作符字符数组
char arg1;//第一个操作数
char arg2;//第二个操作数
char result;//运算结果
int next;//跳转的位置
}sys[SIZE];//四元式的结构体，包含五个元素
void error(){
cout<<"语句结构错误！"< exit(1); }//当在分析过程中，发现该句子下一个字符是不可能出现的，则输出错误并退出程序 void initial1(char s[LINE][LENGTH]){ for(int i=0;i for(int j=0;j s[i][j]='\0';//对二维字符数组进行初始化为'\0'，该数组为输入时用到的数组 } void initial2(char array[100],int n){//对一维字符数组进行初始化为'\0' for(int i=0;i array[i]='\0'; } void K(){// K->E|=E if(array[flag]=='='){ OpStack[flag2]=array[flag]; flag2++;flag++; E(); } else if((array[flag]<=122 && array[flag]>=97)||(array[flag]>=48 && array[flag]<=57)){//若为字母或者数字 E(); } else error(); } void J(){// J-> if(array[flag]=='<'||array[flag]= ='>'){ OpStack[flag2]=array[flag]; flag2++; flag++; K(); } else if(array[flag]=='='||array[flag]=='!'){ OpStack[flag2]=array[flag]; flag2++;flag++; if(array[flag]=='='||array[flag]=='='){ flag++; E(); } else error(); } else error(); } void I(){// I->*E|/E|+E|-E|ε if(array[flag]=='*'||array[flag]= ='/'||array[flag]=='+'||array[flag]=='-'){ OpStack[flag2]=array[flag]; flag2++; flag++; E(); } else if(array[flag]==';'||array[flag]==')'){ return; } else error(); } void H(){// H->++|--|=F if((array[flag]=='+'&&array[flag +1]=='+')||(array[flag]=='-'&&array[flag+ 1]=='-')){ OpStack[flag2]=array[flag]; OpStack[flag2+1]=array[flag+1]; flag2=flag2+2; flag=flag+2; } else if(array[flag]=='='){ OpStack[flag2]=array[flag]; flag2++; flag++; F(); } else error(); } void G(){// G->a|b|c…|x|y|z if(array[flag]<=122 && array[flag]>=97){ ArgStack[flag1]=array[flag]; flag1++;flag++; } else error(); } void F(){// F->EI|-E if(array[flag]=='-'){ OpStack[flag2]=array[flag]; flag2++; flag++; E(); } else if((array[flag]<=122 && array[flag]>=97)||(array[flag]>=48 && array[flag]<=57)){ E(); I(); } else error(); } void E(){// E->G|0|1|2|3|4|5|6|7|8|9 if(array[flag]<=122 && array[flag]>=97) G(); else if(array[flag]>=48 && array[flag]<=57){ ArgStack[flag1]=array[flag]; flag1++;flag++; return; } else error(); } void D(){// D->SD|C;D|ε if(array[flag]=='f'&&array[flag+ 1]=='o'&&array[flag+2]=='r'){ S(); D(); } else if(array[flag]<=122 && array[flag]>=97){ C(); if(array[flag]==';'){ flag++; D(); } else error(); } else if(array[flag]=='}') return; else error(); } void C(){// C->GH G(); H(); } void B(){// B->GJ G(); J(); } void A(){// A->G=F|ε G(); if(array[flag]=='='){ OpStack[flag2]=array[flag]; flag2++;flag++; F(); } else error(); } void getSYS(){//在对两个数组ArgStack和OpStack赋值好了以后调用这个函数，他负责按照两个数组中的内容合成对四元式中的各部分进行赋值 if(flag1==flag2){//flag1和flag2分别代表ArgStack和OpStack中的字符个数 if(ArgStack[flag1-1]=='-'){//=中等号右边为负数的情况 sys[Number].arg1='0'; sys[Number].arg2=ArgStack[flag1-1] ; sys[Number].op[0]='-'; sys[Number].result=ArgStack[flag1-2]; } else {// <= != ==和>=的情况 sys[Number].arg1=ArgStack[flag1-2] ; sys[Number].arg2=ArgStack[flag1-1] ; sys[Number].op[0]='j'; sys[Number].op[1]=OpStack[flag2-2 ]; sys[Number].op[2]=OpStack[flag2-1]; sys[Number].next=Number+2; Number++; sys[Number].op[0]='j'; sys[Number].arg1='_'; sys[Number].arg2='_'; } } else if(flag1>flag2){ if(flag1==3){// +-*/的情况sys[Number].arg1=ArgStack[flag1-2] ; sys[Number].arg2=ArgStack[flag1-1] ; sys[Number].op[0]=OpStack[flag2-1 ]; sys[Number].result='t'; Number++; sys[Number].arg1=ArgStack[flag1-3] ; sys[Number].arg2='_'; sys[Number].op[0]='j'; sys[Number].op[1]='='; sys[Number].result='t'; } else{//=的情况 if(OpStack[flag2-1]=='='){ sys[Number].op[0]='='; sys[Number].arg2='_'; sys[Number].result=ArgStack[flag1-1]; sys[Number].arg1=ArgStack[flag1-2] ; } else{//<和>的情况 sys[Number].op[0]='j'; sys[Number].op[1]=OpStack[flag2-1 ]; sys[Number].next=Number+2; sys[Number].arg2=ArgStack[1]; sys[Number].arg1=ArgStack[flag1-2] ; Number++; sys[Number].op[0]='j'; sys[Number].arg1='_'; sys[Number].arg2='_';} } } else if(flag1 sys[Number].arg2='1'; sys[Number].result=ArgStack[flag1-1]; if(OpStack[flag2-1]=='+') sys[Number].op[0]='+'; else sys[Number].op[0]='-';} Number++; flag1=0;flag2=0;//将ArgStack 和OpStack两个数组清空 initial2(ArgStack,5); initial2(OpStack,5);} void S(){// S->for (A; B; C) {D}开始符号S if(array[flag]=='f'&&array[flag+ 1]=='o'&&array[flag+2]=='r'&&array[flag +3]=='('){ flag=flag+4;//flag标记目前分析的字符的位置 A(); if(ArgStack[0]!=' '){//若这个时候分析的表不为空，就调用getSYS 对四元式中元素进行赋值 getSYS(); ArgStack[0]=' '; } if(array[flag]==';'){ flag++; B(); if(ArgStack[0]!=' '){ getSYS(); ArgStack[0]=' '; } if(array[flag]==';'){ flag++; C(); if(ArgStack[0]!=' '){ getSYS(); ArgStack[0]=' '; } if(array[flag]==')'&&array[flag+1]==' {'){ flag+=2; D(); if(ArgStack[0]!=' '){ getSYS(); ArgStack[0]=' ';} if(array[flag]=='}') flag++; else error();} else error();} else error();} else error();} else error(); } void sort(){//由于开始的四元式组的顺序以及跳转的位置并不正确，只 是按程序分析的顺序进行排列的。这里对赋值完成的四元式进行排序，补充，对跳转位置的赋值等 siyuanshi s;int i,k; int j=Number;//Number为四元式的个数 for(i=Number-1;i>0;i--){ if((sys[i].op[0]=='+'||sys[i].op[0]=='-')&&sys[i].arg1==sys[i].result){//将循环变量的自加四元式向下移，同时嵌套中的对应的四元式在前面 s.arg1=sys[i].arg1; s.arg2=sys[i].arg2; s.next=sys[i].next; s.op[0]=sys[i].op[0]; s.result=sys[i].result; for(j=i;j sys[j].arg1=sys[j+1].arg1; sys[j].arg2=sys[j+1].arg2; sys[j].next=sys[j+1].next; for(k=0;k<5;k++) sys[j].op[k]=sys[j+1].op[k]; sys[j].result=sys[j+1].result;} sys[j].arg1=s.arg1; sys[j].arg2=s.arg2; sys[j].next=s.next; sys[j].op[0]=s.op[0]; sys[j].op[1]='\0'; sys[j].result=s.result;} } for(j=0;j if(sys[j].op[0]=='j'&&(sys[j].op[1 ]=='<'||sys[j].op[1]=='>'||sys[j].op[1]==' !'||sys[j].op[1]=='=')&&sys[j].arg2!='_') sys[j].next=j+2; } int temp=0; for(i=Number-1;i>=0;i--){//由于在C完成后，需要到B来判断条件是否满足，这里在循环变量改变的四元式后添加跳转语句，跳到判断语句的地方 if((sys[i].op[0]=='+'||sys[i].op[0]=='-') && sys[i].arg1==sys[i].result){//若找到循环变量自变的C部分语句 for(j=Number-1;j>i;j--){//将该语句后面的四元式统统后移 sys[j+1].arg1=sys[j].arg1; sys[j+1].arg2=sys[j].arg2; sys[j+1].next=sys[j].next; for(k=0;k<3;k++) sys[j+1].op[k]=sys[j].op[k]; sys[j+1].result=sys[j].result;} sys[i+1].op[0]='j';//对该语句后面空出来的一个四元式赋值为跳转到判断语句的四元式 sys[i+1].arg1='_'; sys[i+1].arg2='_'; Number++; k=temp; while((sys[k].op[0]!='j' || sys[k].arg2=='_')&&k k++; temp=k+1; sys[i+1].next=k; } } temp=1; for(i=0;i 断语句不成立时的跳转位置的设置 if(sys[i].next==0 && sys[i].result==' '){ sys[i].next=Number-temp+1; temp++;}} } void print(){//对结果修改完成后的四元式组的输出 for(int i=0;i cout< int j=0; while(sys[i].op[j]!=' '&&j<3){ cout< j++; } cout<<','; cout< if(sys[i].next!=0) cout< else cout< cout<<')'< cout< } void analyze(){//分析该程序，调用S（）；开始语法分析该程序 S(); if(array[flag]=='#') { cout<<"分析成功！该句子可由本文法正确推出。分析得到的四元式如下："< sort(); print();} else cout<<"分析失败！该句子不能由本文法推出。"< void main(){ char s[10][30],temp=0,Analyze=0; int i=-1,line; cout<<"请输入要进行分析的代码段，注意换行以#结束："< initial1(s);//由于输入需要换行，s这个二维数组的每一行都是用来存一个字符串的 while(i<0||s[i][0]!='#') gets(s[++i]); line=i; initial2(array,100);//初始化array数组，array数组有s二维数组的各行合并得到 int j=0; for(i=0;i j=0; while(s[i][j]!='\0') array[temp++]=s[i][j++];} for(i=0;i cout< flag=0;//用来标记分析程序的位置 flag1=0;flag2=0;Number=0;NU MBER=0; initial2(ArgStack,5); initial2(OpStack,5); for(i=0;i sys[i].arg1=' '; sys[i].arg2=' '; sys[i].next=0; sys[i].op[0]=' '; sys[i].op[1]=' '; sys[i].op[2]=' '; sys[i].result=' ';} analyze();} 《编译原理》课程设计大纲 课程编号： 课程名称：编译原理/Compiler Principles 周数/学分：1周/1学分 先修课程：高级程序设计语言、汇编语言、离散数学、数据结构 适用专业：计算机科学与技术专业、软件工程专业 开课学院，系或教研室：计算机科学与技术学院 一、课程设计的目的 课程设计是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，设计题中的问题比平时的练习题要复杂，也更接近实际。编译原理这门课程安排的课程设计的目的是旨在要求学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容，选择合适的数据逻辑结构表示问题，然后编制算法和程序完成设计要求，从而进一步培养学生独立思考问题、分析问题、解决实际问题的动手能力。 要求学生在上机前应认真做好各种准备工作，熟悉机器的操作系统和语言的集成环境，独立完成算法编制和程序代码的编写。 设计时间： 开发工具： （1） DOS环境下使用Turbo C； （2） Windows环境下使用Visual C++ 。 （3） 其它熟悉语言。 二、课程设计的内容和要求 设计题一：算术表达式的语法分析及语义分析程序设计。 1.目的 通过设计、编制、调试一个算术表达式的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词 法检查和分析。 2.设计内容及要求： 算术表达式的文法： 〈无符号整数〉∷＝ 〈数字〉{〈数字〉} 〈标志符〉∷＝ 〈字母〉{〈字母〉｜〈数字〉} 〈表达式〉∷＝ [＋｜－]〈项〉{〈加法运算符〉〈项〉} 〈项〉∷＝ 〈因子〉{〈乘法运算符〉〈因子〉} 〈因子〉∷＝ 〈标志符〉｜〈无符号整数〉｜‘（’〈表达式〉‘）’ 〈加法运算符〉∷＝ ＋｜－ 〈乘法运算符〉∷＝ ＊｜／ （1） 分别选择递归下降法、算符优先分析法（或简单优 先法）完成以上任务，中间代码选用逆波兰式。 （2） 分别选择LL（1）、LR法完成以上任务，中间代码选 用四元式。 （3） 写出算术表达式的符合分析方法要求的文法，给出 分析方法的思想，完成分析程序设计。 （4） 编制好分析程序后，设计若干用例，上机测试并通 过所设计的分析程序。 设计题二：简单计算器的设计 1．目的 通过设计、编制、调试一个简单计算器程序，加深对语法及语 义分析原理的理解，并实现词法分析程序对单词序列的词法检 查和分析。 2.设计内容及要求 算术表达式的文法： ＜PL0编译器-PCompiler＞ 软件需求说明书 作者：刁诗云、麻汉华、潘彦荃、周津、李程完成日期：2009年6月7日 签收人： 签收日期： 修改情况记录： 目录 软件需求说明书 (1) 1 引言 (1) 1.1 编写目的 (1) 1.2 项目背景 (1) 2 项目概述 (2) 2.1 产品描述 (2) 2.2 产品功能 (2) 2.3 用户特点 (2) 3 具体需求 (3) 3.1 EBNF定义的PL/0文法 (3) 3.2 语法图 (4) 3.3 功能需求 (6) 3.4 系统概要设计 (15) 1 引言 1.1 编写目的 为了清楚表达客户提出的需求，便于用户理解和确认项目所包含的具体功能需求、性能需求以及非公能性需求，因此以文件化的形式，把系统整体及其部分的业务流程、系统功能进行了详细的说明。同时，此文也对开发人员起到引导的作用，请认真阅读。 1.2 项目背景 PL/0是由世界著名计算机科学家、PASCAL语言的创始人N.Wirth教授选择提供的。在选择PL/0语言的过程中，Wirth很费了一番脑筋。一方面他希望借助这个语言，能尽可能把程序设计语言和编译技术一些最重要的内容都讲到；但另一方面又不希望内容太多，太杂，而希望尽可能简单一些，以便与有限的课时和课程范围相适应。于是他精心选择提供了这个PL/0语言。事实证明，它非常适合于编译技术的教学，目前已被国内越来越多的编译教材所采用。 PL/0语言的语句类型比较丰富，能适应各种可能的程序结构。最进本的是赋值语句。组合结构语句有语句串、条件语句和循环语句。还有重要的子程序概念，是通过过程说明和过程调用两部分实现的。至于数据类型和数据结构，PL/0则特别简单，只有整数类型一种，没有数据结构，因此只允许有整常数和整数变量的说明以及相应的算术运算表达式。PL/0允许在一个过程范围内说明常数、变量和过程。这些常数、变量和过程只在它们被说明的过程范围内有效。PL/0语言也允许递归调用，既可以间接递归，也可以直接递归。 编译原理程序设计报告 一个简单文法的编译器的设计与实现专业班级：计算机1406班 组长姓名：宋世波 组长学号： 20143753 指导教师：肖桐 2016年12月 设计分工 组长学号及姓名：宋世波20143753 分工：文法及数据结构设计 词法分析 语法分析（LL1） 基于DAG的中间代码优化 部分目标代码生成 组员1学号及姓名：黄润华20143740 分工：中间代码生成(LR0) 部分目标代码生成 组员2学号及姓名：孙何奇20143754 分工：符号表组织 部分目标代码生成 摘要 编译器是将便于人编写，阅读，维护的高级计算机语言翻译为计算机能解读、运行的低阶机器语言的程序。编译是从源代码（通常为高阶语言）到能直接被计算机或虚拟机执行的目标代码（通常为低阶语言或机器语言）的翻译过程。 一．编译器的概述 1.编译器的概念 编译器是将便于人编写，阅读，维护的高级计算机语言翻译为计算机能解读、运行的低阶机器语言的程序。编译器将原始程序作为输入，翻译产生使用目标语言的等价程序。源代码一般为高阶语言如Pascal、C++、Java 等，而目标语言则是汇编语言或目标机器的目标代码，有时也称作机器代码。 2．编译器的种类 编译器可以生成用来在与编译器本身所在的计算机和操作系统（平台）相同的环境下运行的目标代码，这种编译器又叫做“本地”编译器。另外，编译器也可以生成用来在其它平台上运行的目标代码，这种编译器又叫做交叉编译器。交叉编译器在生成新的硬件平台时非常有用。“源码到源码编译器”是指用一种高阶语言作为输入，输出也是高阶语言的编译器。例如: 自动并行化编译器经常采用一种高阶语言作为输入，转换其中的代码，并用并行代码注释对它进行注释（如OpenMP）或者用语 编译原理课程设计报告 实验名称编译原理课程设计 班级 学号 姓名 指导教师 实验成绩 2013 年06月 一、实验目的 通过设计、编写和调试，将正规式转换为不确定的有穷自动机，再将不确定的有穷自动机转换为与之等价的确定的有穷自动机，最后再将确定有穷自动机进行简化。 通过设计、编写和调试构造LR(0)项目集规范簇和LR分析表、对给定的符号串进行LR分析的程序，了解构造LR(0)分析表的步骤，对文法的要求，能够从文法G出发生成LR(0)分析表，并对给定的符号串进行分析。 二、实验内容 正规式——>NFA——>DFA——>MFA 1.正规式转化为不确定的有穷自动机 （1）目的与要求 通过设计、编写和调试将正规式转换为不确定的有穷自动机的程序，使学生了解Thompson算法，掌握转换过程中的相关概念和方法，NFA的表现形式可以是表格或图形。 （2）问题描述 任意给定一个正规式r（包括连接、或、闭包运算），根据Thompson算法设计一个程序，生成与该正规式等价的NFA N。 （3）算法描述 对于Σ上的每个正规式R，可以构造一个Σ上的NFA M，使得L(M)=L(R)。 步骤1：首先构造基本符号的有穷自动机。 步骤2：其次构造连接、或和闭包运算的有穷自动机。 （4）基本要求 算法实现的基本要求是： (1) 输入一个正规式r； (2) 输出与正规式r等价的NFA。（5）测试数据 输入正规式：(a|b)*(aa|bb)(a|b)* 得到与之等价的NFA N （6）输出结果 2.不确定的有穷自动机的确定化 （1）目的与要求 通过设计、编写和调试将不确定的有穷自动机转换为与之等价的确定的有穷自动机的程序，使学生了解子集法，掌握转换过程中的相关概念和方法。DFA的表现形式可以是表格或图形。（2）问题描述 任意给定一个不确定的有穷自动机N，根据算法设计一个程序，将该NFA N变换为与之等价的DFA D。 （3）算法描述 用子集法将NFA转换成接受同样语言的DFA。 步骤一：对状态图进行改造 (1) 增加状态X,Y,使之成为新的唯一的初态和终态。从X引ε弧到原初态结点, 从原终态结 点引ε弧到Y结点。 (2) 对状态图进一步进行如下形式的改变 课程设计(论文)任务书 软件学院学院软件工程专业07-1班 一、课程设计(论文)题目LL(1)分析过程模拟 二、课程设计(论文)工作自 2010 年 6 月 22日起至 2010 年 6月 28 日止。 三、课程设计(论文) 地点: 四、课程设计(论文)内容要求： 1．本课程设计的目的 （1）使学生掌握LL（1）模块的基本工作原理； （2）培养学生基本掌握LL（1）分析的基本思路和方法； （3）使学生掌握LL（1）的调试； （4）培养学生分析、解决问题的能力； （5）提高学生的科技论文写作能力。 2．课程设计的任务及要求 1）基本要求： （1）分析LL（1）模块的工作原理； （2）提出程序的设计方案； （3）对所设计程序进行调试。 2）创新要求： 在基本要求达到后，可进行创新设计，如改算法效率。 3）课程设计论文编写要求 （1）要按照书稿的规格打印誊写课程设计论文 （2）论文包括目录、绪论、正文、小结、参考文献、附录等 （3）课程设计论文装订按学校的统一要求完成 4）答辩与评分标准： （1）完成原理分析：20分； （2）完成设计过程（含翻译）：40分； （3）完成调试：20分； （4）回答问题：20分。 5）参考文献： （1）张素琴，吕映芝，蒋维杜，戴桂兰.编译原理（第2版）.清华大学出版社 （2）丁振凡.《Java语言实用教程》北京邮电大学出版社 6）课程设计进度安排 内容天数地点 构思及收集资料2图书馆 编程与调试4实验室 撰写论文1图书馆、实验室 学生签名： 2009 年6 月22 日 课程设计(论文)评审意见 （1）完成原理分析（20分）：优（）、良（）、中（）、一般（）、差（）；（2）设计分析（20分）：优（）、良（）、中（）、一般（）、差（）；（3）完成调试（20分）：优（）、良（）、中（）、一般（）、差（）；（4）翻译能力（20分）：优（）、良（）、中（）、一般（）、差（）；（5）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性及考勤是否降等级：是（）、否（） 评阅人：职称： 年月日 编译原理课程设计报告 课题名称： C-语言编译器设计（scanner和parser） 提交文档学生姓名： 提交文档学生学号： 同组成员名单：无 指导教师姓名：金军 指导教师评阅成绩： 指导教师评阅意见： . . 提交报告时间： 2011年 6 月 17 日 1.课程设计目标 设计C-Minus编译器分为scanner和parser两个部分。scanner主要作用是对目标代码进行扫描，列出关键字，变量等内容；parser主要对语法进行分析并生成语法树。 2.分析与设计 ●实现方法：代码用C语言编译而成。其中scanner为手工实现，主要采用switch-case结构实现 状态转换；parser部分采用递归下降分析方法实现。 ●扫描器：C-的词法如下： 1、语言的关键字：i f el se i nt return void while 2、专用符号：+ - * /< <= > >= == != =; , ( ) [ ] { } /* */ 3、其他标记是变量（ID）和数字（NUM），通过下列正则表达式定义： ID = letter letter* NUM = di git digi t* letter = a|..|z|A|..|Z digi t = 0|..|9 4、空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开ID、NUM关键字 5. 注释用通常的C语言符号/ * . . . * /围起来。注释可以放在任何空白出现的位置(即注释不能放在 标记内)上，且可以超过一行。注释不能嵌套 其DFA图如下： 分析器：以下为C-的语法规则BNF: 编译原理课程设计 自顶向下语法分析器 学院（系）：计算机科学与技术学院学生姓名：xxxxxxxxx 学号：xxxxxxxxx 班级：电计1102 大连理工大学 Dalian University of Technology 目录 1 系统概论 语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器在编译程序中的地位如图1所示： 图1 语法分析器在编译程序中的地位 语言的语法结构是用上下文无关文法描述的。因此，语法分析器的工作本质上就是按文法的产生式，识别输入符号串是否为一个句子。这里所说的输入串是指由单词符号（文法的终结符）组成的有限序列。对一个文法，当给你一串（终结）符号时，怎样知道它是不是该文法的一个句子呢？这就要判断，看是否能从文法的开始符号出发推导出这个输入串。或者，从概念上讲，就是要建立一棵与输入串相匹配的语法分析树。 自顶向下分析法就是语法分析办法中的一类。顾名思义，自顶向下就是从文法的开始符号出发，向下推导，推出句子。这种方法是带“回溯”的。 自顶向下分析的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号（根结）出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。 实现这种自顶向下的带回溯试探法的一个简单途径是让每个非终结符对应一个递归子程序。每个这种子程序可作为一个布尔过程。一旦发现它的某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回“真”值；否则，保持原来的语法树和IP值不变，并返回“假”值。 2 需求分析 以前，人们对语法的分析都建立在人工的基础上，人工分析虽然能够做到侧类旁推，但终究人力有限，再精密的分析都会出现或多或少的错误。为减少因人为产生的错误，并加快 编译原理课程设计报告 课题名称：C- Minus词法分析和语法分析设计 提交文档学生姓名：X X X 提交文档学生学号：XXXXXXXXXX 同组成员名单：X X X 指导教师姓名：X X 指导教师评阅成绩： 指导教师评阅意见： . . 提交报告时间：2015年6月10日 1.课程设计目标 实验建立C-编译器。只含有扫描程序（scanner）和语法分析（parser）部分。 2.分析与设计 C-编译器设计的整体框架，本实验实现扫描处理和语法分析程序（图中粗黑部分）。 2.1 、扫描程序scanner部分 2.1.1系统设计思想 设计思想：根据DFA图用switch-case结构实现状态转换。 惯用词法： ①语言的关键字：else if int return void while ②专用符号：+ - * / < <= > >= == != = ; , ( ) [ ] { } /* */ ③其他标记是ID和NUM，通过下列正则表达式定义： ID = letter letter* NUM = digit digit* letter = a|..|z|A|..|Z digit = 0|..|9 大写和小写字母是有区别的 ④空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开ID、NUM 关键字。 ⑤注释用通常的C语言符号/ * . . . * /围起来。注释可以放在任何空白出现的位置(即注释不能放在标记内)上，且可以超过一行。注释不能嵌套 scanner的DFA 说明：当输入的字符使DFA到达接受状态的时候，则可以确定一个单词了。初始状态设置为START，当需要得到下一个token时，取得次token的第一个字符，并且按照DFA与对此字符的类型分析，转换状态。重复此步骤，直到DONE为止，输出token类型。当字符为“/”时，状态转换为SLAH再判断下一个字符，如果为“*”则继续转到INCOMMENT，最后以“*”时转到ENDCOMMENT状态，表明是注释，如果其他的则是字符停滞于当前字符，并且输出“/”。 2.1.2程序流程图 编译原理-词法分析器的设计 一．设计说明及设计要求 一般来说，编译程序的整个过程可以划分为五个阶段：词法分析、语法分析、中间代码生成、优化和目标代码生成。本课程设计即为词法分析阶段。词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词（也称单词符号或符号）。如保留字（关键字或基本字）、标志符、常数、算符和界符等等。 二．设计中相关关键字说明 1．基本字：也称关键字，如C语言中的 if , else , while , do ,for,case,break, return 等。 2．标志符：用来表示各种名字，如常量名、变量名和过程名等。 3．常数：各种类型的常数，如12，6.88，和“ABC” 等。 4．运算符：如 + ，- , * , / ,%, < , > ,<= , >= 等。5．界符，如逗点，冒号，分号，括号，# ，〈〈，〉〉等。 三、程序分析 词法分析是编译的第一个阶段，它的主要任务是从左到右逐个字符地对源 程序进行 扫描，产生一个个单词序列，用以语法分析。词法分析工作可以是独立的一遍，把字符流的源程序变为单词序列，输出在一个中间文件上，这个文件做为语法分析程序的输入而继续编译过程。然而，更一般的情况，常将 词法分析程序设计成一个子程序，每当语法分析程序需要一个单词时，则 调用该子程序。词法分析程序每得到一次调用，便从源程序文件中读入一 些字符，直到识别出一个单词，或说直到下一个单词的第一个字符为止。 四、模块设计 下面是程序的流程图 五、程序介绍 在程序当前目录里建立一个文本文档，取名为infile.txt,所有需要分析的程序都写在此文本文档里，程序的结尾必须以“@”标志符结束。程序结果输出在同一个目录下，文件名为outfile.txt，此文件为自动生成。本程序所输出的单词符号采用以下二元式表示：（单词种别，单词自身的值）如程序输出结果(57,"#")(33,"include")(52,"<")(33,"iostream") 等。 程序的功能：（1）能识别C语言中所有关键字（共32个）（单词种别分别为1 — 32 ，详情见程序代码相关部分，下同） （2）能识别C语言中自定义的标示符（单词种别为 33） （3）能识别C语言中的常数（单词种别为0） （4）能识别C语言中几乎所有运算符（单词种别分别为41 — 54） （5）能识别C语言中绝大多数界符（单词种别分别为 55 — 66）六、运行结果 输入文件infile.txt 运行结果（输出文件 outfile.txt） $ 编译原理课程设计报告 设计题目编译代码生成器设计 、 学生姓名 班级 学号 指导老师 成绩 ` 一、课程设计的目的 编译原理课程兼有很强的理论性和实践性，是计算机专业的一门非常重要的专业基础课程，它在系统软件中占有十分重要的地位，是计算机专业学生的一门主修课。为了让学生能够更好地掌握编译原理的基本理论和编译程序构造的基本方法和技巧，融会贯通本课程所学专业理论知识，提高他们的软件设计能力，特设定该课程的课程设计，通过设计一个简单的PASCAL语言（EL语言）的编译程序，提高学生设计程序的能力，加深对编译理论知识的理解与应用。 二、课程设计的要求 1、明确课程设计任务，复习编译理论知识，查阅复印相关的编译资料。 2、按要求完成课程设计内容，课程设计报告要求文字和图表工整、思路清晰、算法正 确。 3、@ 4、写出完整的算法框架。 5、编写完整的编译程序。 三、课程设计的内容 课程设计是一项综合性实践环节，是对平时实验的一个补充，课程设计内容包括课程的主要理论知识，但由于编译的知识量较复杂而且综合性较强，因而对一个完整的编译程序不适合平时实验。通过课程设计可以达到综合设计编译程序的目的。本课程的课程设计要求学生编写一个完整的编译程序，包括词法分析器、语法分析器以及实现对简单程序设计语言中的逻辑运算表达式、算术运算表达式、赋值语句、IF语句、While语句以及do…while语句进行编译，并生成中间代码和直接生汇编指令的代码生成器。 四、总体设计方案及详细设计 总体设计方案： 1.总体模块 【 2. \ 详细设计： 界面导入设计 (1)一共三个选项： ①choice 1--------cifafenxi ②choice 2--------yufafenxi ③choice 3--------zhongjiandaima (2)界面演示 } 图一 2011-2012学年第二学期 《编译原理》课程设计报告 学院：计算机科学与工程学院 班级： 学生姓名：学号： 成绩： 指导教师： 时间：2012年5 月 目录 一、课程设计的目的 ---------------------------------------------------------------- - 1 - 二、课堂实验及课程设计的内容 -------------------------------------------------- - 1 - 2.1、课堂实验内容-------------------------------------------------------------- - 1 - 2.2、课程设计内容-------------------------------------------------------------- - 1 - 三、visual studio 2008 简介------------------------------------------------------- - 2 - 四、问题分析及相关原理介绍 ----------------------------------------------------- - 3 - 4.1、实验部分问题分析及相关原理介绍 ---------------------------------- - 3 - 4.1.1、词法分析功能介绍及分析------------------------------------- - 3 - 4.1.2、语法分析功能介绍及分析------------------------------------- - 3 - 4.1.3、语义分析功能介绍及分析------------------------------------- - 4 - 4.2、课程设计部分问题分析及相关原理介绍 ---------------------------- - 5 - 4.2.1、编译程序介绍 ----------------------------------------------------- - 5 - 4.2.2、对所写编译程序的源语言的描述（C语言） -------------- - 6 - 4.2.3、各部分的功能介绍及分析 -------------------------------------- - 7 - 4.3、关键算法：单词的识别-------------------------------------------------- - 8 - 4.3.1、算法思想介绍 ----------------------------------------------------- - 8 - 4.3.2、算法功能及分析 -------------------------------------------------- - 8 - 五、设计思路及关键问题的解决方法 ------------------------------------------ - 10 - 5.1、编译系统------------------------------------------------------------------ - 10 - 5.1.1、设计思路 --------------------------------------------------------- - 10 - 5.2、词法分析器总控算法--------------------------------------------------- - 12 - 5.2.1、设计思路 --------------------------------------------------------- - 12 - 5.2.2、关键问题及其解决方法 --------------------------------------- - 13 - 六、结果及测试分析-------------------------------------------------------------- - 14 - 6.1、软件运行环境及限制--------------------------------------------------- - 14 - 6.2、测试数据说明------------------------------------------------------------ - 14 - 6.3、运行结果及功能说明--------------------------------------------------- - 16 - 6.4、测试及分析说明--------------------------------------------------------- - 16 - 七、总结及心得体会 --------------------------------------------------------------- - 17 - 7.1、设计过程------------------------------------------------------------------ - 17 - 7.2、困难与收获 ------------------------------------------------------------- - 17 - 八、参考文献 ------------------------------------------------------------------------ - 18 - 编译原理： 编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。编译原理是计算机专业设置的一门重要的专业课程。编译原理课程是计算机相关专业学生的必修课程和高等学校培养计算机专业人才的基础及核心课程，同时也是计算机专业课程中最难及最挑战学习能力的课程之一。编译原理课程内容主要是原理性质，高度抽象。 编译原理课程设计： 《编译原理课程设计》是2007年11月浙江大学出版社出版的图书，作者是冯雁、鲁东明、李莹。 内容简介： 本书围绕着编译技术的基本原理和方法，以模拟程序设计语言SPL的编译器的设计和实现为主线，结合词法分析、语法分析、语义分析、代码生成、代码优化、错误处理等各个基本模块，对原理和实现方法进行了详细分析。该编译器可接受SPL的程序，并将其翻译成汇编语言程序，最终实现汇编语言到8086/8088机器语言的翻译。本书为编译技术等相关课程的实验提供了参考。在附件中还提供了三类不同类型和难度的实验题，可供课程实验选择。 第1章引论： 1.1本书介绍 1.2SPL语言的特点及实验安排 1.2.1SPL语言的特点 1.2.2SPL语言编译器的主要结构1.2.3实验安排 1.3平台的选择和介绍 1.3.1LEX简介 1.3.2YACC简介 第2章词法分析： 2.1词法分析器的基本框架 2.2词法分析器的基本原理 2.2.1DFA的构造和实现 2.2.2词法分析的预处理 2.2.3实现词法分析器的注意要点2.3词法分析器的实现 2.3.1SPL语言单词属性字 2.3.2SPL词法分析器的输入和输出2.3.3SPL词法分析器的分析识别第3章语法分析： 3.1语法分析的基本框架 3.1.1上下文无关文法 3.1.2语法分析过程 3.1.3语法分析过程中的数据结构3.2语法分析的基本方法 河海大学 编译原理课程设计 学生姓名： 学号： 班级： 专业：--------- 指导教师： 编译原理 课程设计指导书 题目一基于语法制导翻译的表达式转换编译器 一、设计目的 通过本课程设计获得对实际编译器的构造原理、过程和方法的感性认识，全面掌握语法制导翻译技术。 二、设计内容 采用语法制导翻译模式设计一个包含词法分析、语法分析、符号表管理、错误处理及输出等功能模块的、由中缀表达式到后缀表达式的完整编译器。该翻译器的规格说明如下： start → list eof list → expr;list |ε expr → expr + term { print(‘+’) } | expr –term { print(‘-’) } | term term → term * factor { print(‘*’) } | term / factor { print(‘/’) } | term div factor { print(‘DIV’) } | term mod factor { print(‘MOD’) } factor → ( expr ) | id { print( https://www.wendangku.net/doc/6b9327546.html, ) } | num { print( num.value ) } 三、设计要求 1、使用模块化设计思想来设计该编译器； 2、词法分析模块用于读入输入串，并将其转换成供语法分析模块使用的记号流。其中包括滤掉空格和注释、识别常数、识别标识符和关键字等功能； 3、要求在语法分析模块中利用语法制导翻译技术完成具体的中缀表达式到后缀表达式的翻译，其中包括按前述翻译器的规格说明构建对应表达式、项、因子的非终结符expr、term 和factor的函数以及检查记号是否匹配的函数；并在不匹配时调用错误处理模块； 4、要求符号表管理模块主要完成符号表对应数据结构的具体实现功能； 5、错误处理模块负责报告错误信息及位置，并终止分析过程； 6、输出模块完成翻译后所得到的后缀表达式的输出。 先简要分析一下语法分析的大致流程： 当有句子要进行处理时，首先要对其进行词法分析来分解出该句子中的每个符号，然后将该句子按照算符优先算法压入归约栈中，如果可以顺利归约，则说明这是一个合法的句子，否则该句子非法。 这里有一个需要考虑的地方，就是如何进行归约。由于文法已经给定，所以我们考虑设计一个文法表，文法表中的内容就是可归约串的种别码的顺序，比如v=E可以表示为9,1,13。这样的话当我们要进行一次归约时，只用按顺序存储最左素短语中符号的种别码，然后拿这个种别码序列与文法表进行匹配，就可知道当前归约需要执行哪些操作。 还有一点需要注意，就是如何对一个表达式进行求值。这里需要我们设计一个二元组的变量名表，这个变量名表可以根据变量的名称来返回变量的数据。变量名表的具体设计见详细设计部分。 由于是简化分析，所以这个程序只考虑整数的处理。 有了上面的分析，可以构造出算符优先分析算法的流程图，如下图所示。 详细设计 （1）词法分析部分 由于词法分析的内容在课程设计1中已经介绍，并且这次的状态转换图与课程设计1中的非常相似，所以这里就不过多介绍。（2）优先关系表 在程序中我们用一个二维数组priTable[][]来存储算符间的优先关系。priTable[a][b]=1表示a>b; 。priTable[a][b]=0表示a=b; 。priTable[a][b]=-1表示a 集美大学计算机工程学院实验报告 课程名称：编译原理班级： 指导教师：： 实验项目编号：实验一学号： 实验项目名称：词法分析器的设计实验成绩： 一、实验目的 通过设计编制调试一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 二、实验容 编写一个词法分析器，从输入的源程序（编写的语言为C语言的一个子集）中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示） 三、实验要求 1、词法分析器的功能和输出格式 词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符 2 别单词的类型，将标识符和常量分别插入到相应的符号表中，增加错误处理等。 3、编程语言不限。 四、实验设计方案 1、数据字典 本实验用到的数据字典如下表所示： 3、实验程序 #include 编译原理课程设计报告 设计题目编译代码生成器设计 学生姓名 班级 学号 指导老师 成绩 一、课程设计的目的 编译原理课程兼有很强的理论性和实践性，是计算机专业的一门非常重要的专业基础课程，它在系统软件中占有十分重要的地位，是计算机专业学生的一门主修课。为了让学生能够更好地掌握编译原理的基本理论和编译程序构造的基本方法和技巧，融会贯通本课程所学专业理论知识，提高他们的软件设计能力，特设定该课程的课程设计，通过设计一个简单的PASCAL语言（EL语言）的编译程序，提高学生设计程序的能力，加深对编译理论知识的理解与应用。 二、课程设计的要求 1、明确课程设计任务，复习编译理论知识，查阅复印相关的编译资料。 2、按要求完成课程设计内容，课程设计报告要求文字和图表工整、思路清晰、算法正 确。 3、写出完整的算法框架。 4、编写完整的编译程序。 三、课程设计的内容 课程设计是一项综合性实践环节，是对平时实验的一个补充，课程设计内容包括课程的主要理论知识，但由于编译的知识量较复杂而且综合性较强，因而对一个完整的编译程序不适合平时实验。通过课程设计可以达到综合设计编译程序的目的。本课程的课程设计要求学生编写一个完整的编译程序，包括词法分析器、语法分析器以及实现对简单程序设计语言中的逻辑运算表达式、算术运算表达式、赋值语句、IF语句、While语句以及do…while语句进行编译，并生成中间代码和直接生汇编指令的代码生成器。 四、总体设计方案及详细设计 总体设计方案： 1.总体模块 主程序 词法分析程序语法分析 程序 中间代码 生成程序 2. 表2.1 各种单词符号对应的种别码 单词符号种别码单词符号种别码bgin 1 ：17 If 2 ：= 18 Then 3 < 20 wile 4 <> 21 do 5 <= 22 end 6 > 23 lettet（letter|digit）* 10 >= 24 dight dight* 11 = 25 + 13 ；26 —14 ( 27 * 15 ) 28 / 16 # 0 详细设计： 4.1界面导入设计 (1)一共三个选项： ①choice 1--------cifafenxi ②choice 2--------yufafenxi ③choice 3--------zhongjiandaima (2)界面演示 图一 摘要 使用过现代计算机的人都知道，多数用户是应用高级语言来实现他们所需要的计算的。现在计算机系统一般都含有不只一个的高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序，供用户按不同需要进行选择。高级语言编译程序是计算机系统软件最主要的组成部分之一，也是用户最直接关系的工具之一。 计算机上执行一个高级语言程序一般分为两步：第一，用一个编译程序把高级语言翻译成机器语言程序；第二，运行所得的机器语言程序求得计算结果。 通常说的翻译程序是指能够把某一种语言程序转换成另一种语言程序（目标语言程序）。如果源语言诸如Fortran，Pascal，C，Ada或java这样的高级语言，而目标程序是诸如汇编语言或者机器语言这类的低级语言，这样的一个翻译程序就是称为编译程序。 一个编译程序的工作过程一般可以划分为五个阶段：词法分析、语法分析、语义分析与中间代码生成、优化、目标代码生成。每个阶段都是从上一个阶段得到结果，对他进行分析，并且根据一些外部环境(例如符号表等)得到最终的输出结果。要构造一个编译程序，可以按照这样的阶段来分别构造，最后来连调。 现在人们已经建立了多种编制部分编译程序或整个编译程序的有效工具。有些能用于自动生成扫描器(如LEX)，有些可以用于自动产生语法分析器(如YACC)，有些甚至可以用来自动产生整个的编译程序。这些构造编译程序的工具成为编译程序－编译程序、编译程序产生器或翻译程序书写系统，他们是按照编译程序和目标语言的形式描述而自动产生编译程序的。 编译程序是一极其庞大而又复杂的系统，掌握它比较苦难。但是一旦对其掌握，对以后的程序语言设计，系统软件分析，系统软件设计，形式语言研究等方面都是非常有好处的。 关键字：C语言、、编译、扫描器、语法分析 编译原理 课程设计指导书 题目一基于语法制导翻译的表达式转换编译器 一、设计目的 通过本课程设计获得对实际编译器的构造原理、过程和方法的感性认识，全面掌握语法制导翻译技术。 二、设计内容 采用语法制导翻译模式设计一个包含词法分析、语法分析、符号表管理、错误处理及输出等功能模块的、由中缀表达式到后缀表达式的完整编译器。该翻译器的规格说明如下： start → list eof list → expr | expr → expr + term { print(‘+’) } | expr –term { print(‘-’) } | term |ε term → term * factor { print(‘*’) } | term / factor { print(‘/’) } | term div factor { print(‘DIV’) } | term mod factor { print(‘MOD’) } factor → ( expr ) | id { print( https://www.wendangku.net/doc/6b9327546.html, ) } | num { print( num.value ) } 三、设计要求 1、使用模块化设计思想来设计该编译器； 2、词法分析模块用于读入输入串，并将其转换成供语法分析模块使用的记号流。其中包括滤掉空格和注释、识别常数、识别标识符和关键字等功能； 3、要求在语法分析模块中利用语法制导翻译技术完成具体的中缀表达式到后缀表达式的翻译，其中包括按前述翻译器的规格说明构建对应表达式、项、因子的非终结符expr、term 和factor的函数以及检查记号是否匹配的函数；并在不匹配时调用错误处理模块； 4、要求符号表管理模块主要完成符号表对应数据结构的具体实现功能； 5、错误处理模块负责报告错误信息及位置，并终止分析过程； 6、输出模块完成翻译后所得到的后缀表达式的输出。 广西大学 编译原理课程设计 专业：计算机科学与技术 姓名： 课程：编译原理 指导教师： 目录 一．程序简介与分析---------------------------------------------------------1 二．程序适用围-----------------------------------------------------------1 三．词法分析---------------------------------------------------------------1 四．语法分析---------------------------------------------------------------3 五．语义分析和中间代码生成------------------------------------------------9 六．代码生成--------------------------------------------------------------11 七．流程图----------------------------------------------------------------12 八．实现------------------------------------------------------------------13 九．程序运行结果----------------------------------------------------------13 十．总结------------------------------------------------------------------18 十一.附录（源程序）--------------------------------------------------------19编译原理课程设计
编译原理课程设计
编译原理课程设计报告(一个完整的编译器)
(重庆理工大学计算机学院)编译原理课程设计报告
编译原理课程设计报告_LL(1)分析过程模拟
编译原理课程设计
编译原理课程设计
CMinus词法分析和语法分析设计编译器编译原理课程设计报告书
编译原理课程设计-词法分析器(附含源代码)
编译原理课程设计----C语言编译器的实现
编译原理课程设计报告
编译原理课程设计
编译原理课程设计
编译原理课程设计
编译原理实验-词法分析器的设计说明
编译原理课程设计 C语言编译器的实现
编译原理课程设计---一个简单编译器的设计与分析
编译原理实验题目
编译器_编译原理课程设计报告书
- 编译原理课程设计参考选题
- 编译原理实验自动生成LR(0)分析表
- 太原理工大学编译原理实验
- 编译原理课程设计报告
- 编译原理课程设计
- 编译原理课程设计报告(一个完整的编译器)
- 编译原理课程设计-词法分析器(附含源代码)
- 编译原理课程设计参考选题
- (重庆理工大学计算机学院)编译原理课程设计报告
- 编译原理课程设计指导书(含参考选题)(2016版)
- 编译原理课程设计项目
- 编译原理课程设计报告
- 编译原理课程设计
- CMinus词法分析和语法分析设计编译器编译原理课程设计报告书
- 编译原理课程设计
- 编译原理课程设计报告
- 编译原理课程设计简介
- 编译原理课程设计报告(一个完整的编译器)
- 编译原理课程设计
- 编译原理课程设计