编译原理报告三四元式
四元式生成
一、目的和要求
1、目的
通过上机实习，加深对语法制导翻译原理的理解，掌握将语法分析所识别的语法范畴变换为某种中间代码的语义翻译方法。
2、要求
（1）选用目前世界上普遍采用的语义分析方法──语法制导翻译技术。
（2）语义分析对象重点考虑经过语法分析后已是正确的语法范畴，实习重点是语义子程序。
（3）中间代码选用比较常见的形式，例如四元式。
二、背景知识
属性文法：
A=(G，V，F)，其中：
G：一个CFG, 属性文法的基础。
V：有穷的属性集：每个属性与一个文法符号相关联，这些属性代表与文法符号相关的语义信息，如：类型、地址、值、代码、符号表内容等等。
属性与变量一样，可以进行计算和传递，属性加工的过程即是语义处理的过程。属性加工与语法分析同时进行。
属性的表示：标始符（或数），写在相应文法的下边，点记法：E.Val,E.Place,E.Type…。F：关于属性的属性断言或一组属性的计算规则(称为语义规则)。
断言或语义规则与一个产生式相联，只引用该产生式左端或右端的终结符或非终结符相联的属性。
属性有两类：
综合属性：归约型属性，用于“自下而上”传递信息。
继承属性：推导型属性，用于“自上而下”传递信息。
综合属性的例子：
非终结符E、T及F都有一个综合属性val,符号digit有一个综合属性，它的值由词法分析器提供。与产生式L→E对应的语义规则仅仅是打印由E产生的算术表达式的值的一个过程，我们可认为这条规则定义了L的一个虚属性。某些非终结符加上标是为了区分一个产生式中同一非终结符多次出现。设表达式为3＊5+4，则语义动作打印数值19。
L－属性文法：
一个属性文法称为L－属性文法，如果对于每个产生式A→X1X2…Xn，满足：
1、Xj（1≤j≤n）的继承属性仅依赖于下述属性值中的一种：A的继承属性或产生式右部位v
于Xj左边的符号X1，X2，…，Xj-1的属性。
2、A的综合属性，仅依赖于下述属性值中的一种：A的继承属性或产生式右部符号Xj（除
自身外）的任意属性。
L－属性文法的翻译器通常可借助于LL分析器实现。
在L－属性文法的基础上，LL分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算。
需要对LL分析器增加语义栈，以保存与栈中文法符号有关的继承属性值。
每当进行推导时，新的属性值就由栈中正在推导的产生式左边符号的属性值来计算。
S－属性文法：
一个属性文法称为S－属性文法,当且仅当满足如下条件：
1、所有非终结符的属性是综合属性；
2、同一产生式中相同符号的各综合属性之间无相互依赖关系；
3、如果q是某个产生式中文法符号V的继承属性，则属性q的值仅仅依赖于该产生式右部位于V左边的符号的属性。
S－属性文法的翻译器通常可借助于LR分析器实现。在S－属性文法的基础上，LR分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算。
语法制导翻译的基本思想：为每个产生式配上一个语义子程序，（该子程序描述了一个产生式所对应的翻译工作。这些工作包括：生成中间代码，查填有关的符号表，检查和报错，修改编译程序某些工作变量的值等）。在语法分析过程中，每当一个产生或用于匹配式进行归约时，就调用该产生式所对应的语义子程序，以完成即定的翻译任务。
基础源文法和基础目标文法：
SDTS的基础源文法(输入文法)
一个CFG：(V T，V N，P，S)，其中P={A→w|A→w，y属于R)。
SDTS的基础目标文法(输出文法)
一个CFG：(V N，?，P’，S)，其中P’={A→y|A→w，y属于R)。
SDTS的形式化定义：
SDTS是一个CFG,是一个五元组
T=( V T，V N，?，R，S)，其中：
1、V T是有穷的输入字母表（包含源语言中的符号）；
2、V N是有穷的非终结符集；
3、?是有穷的输出字母表（包含出现在输出串中的符号）；
4、R是形如A→w，y的规则的有穷集合；R中规则形式：A→w，y
A ∈V N，w∈(V T∪V N)*，y∈(V N∪? )*且y中那组非终结符是w中那组非终结符的置换。W：规则的源成分y：规则的翻译成分。
5、S ∈V N，是文法的开始符号。
主要的中间代码有：逆波兰、四元式、三元式、间接三元式、树。
三、实验内容
语法制导翻译是在语法分析的基础上增加语义操作来实现翻译的。原则上每个产生式对应一个语义子程序。在语法分析的过程中，当一个产生式获得匹配或进行归约时，相应的语义子程序便开始工作，生成中间代码，查填有关表格，检查并报告源程序中的错误，修改编译程序某些变量的值。
高级语言的语法结构类型很多，从实习的角度可分为以下六类：
⑴说明语句。如各种数据类型说明（整型、实型、布尔型、字符型、复型、双精度型、枚举、子界、数组、集合、文件、记录、指针等），各种数据空间特性说明（如公用语句，共名语句，等价语句等），初值语句。实习重点是内存空间的分配方法。
⑵顺序结构语句。典型代表是各类表达式（如算术表达式、布尔表达式、字符表达式、位表达）及相应的赋值语句。实习重点是算术表达式的翻译方法。
⑶控制结构语句。常见的有转移语句、条件语句和各种分叉语句。实习重点是拉链返填的方法。
⑷子程序结构。指子程序、函数、过程这类结构的定义和调用。实习重点是哑实结合的方法。
⑸循环结构。如计数循环、条件循环等。实习重点是循环化简的方法。
⑹格式语句。主要指输入输出语句的格式加工。实习重点是数据编辑的方法。根据教学要求可从以上六类中选择一至三类实习。
四、设计思路
模块结构：
（1）定义部分：定义常量、变量、数据结构。
（2）初始化：设立算符优先分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；
（3）控制部分：从键盘输入一个表达式符号串；
（4）利用算符优先分析算法进行表达式处理：根据算符优先分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。
（5）对生成的逆波兰式进行计算。
五、注意事项
1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符i，结束符#；
2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；
3.测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照；
六、相关代码
#include
#include
#include
using namespace std;
#define MAX 100
int m=0,sum=0;//sum用于计算运算符的个数
//m用于标记输入表达式中字符的个数
char JG='A';
char str[MAX];//用于存输入表达式
int token=0;//左括号的标志
/***********用于更改计算后数组中的值**************/ void change(int e) {
int f=e+2;
char ch=str[f];
if(ch>='A'&&ch<='Z')
{
for(int l=0;l { if(str[l]==ch) str[l]=JG; } } if(str[e]>='A'&&str[e]<='Z') { for(int i=0;i { if(str[i]==str[e]) str[i]=JG; } } } void chengchuchuli(int i,int m) { i++; for( i<=m-1;i++)//处理乘除运算 { if(str[i]=='*'||str[i]=='/') { cout<<"("< str[i-1]=str[i]=str[i+1]=JG; sum--; JG=(char)(int)JG++; } } } void jiajianchuli(int j,int m) { j++; for( j<=m-1;j++)//处理加减运算 { if(str[j]=='+'||str[j]=='-') { cout<<"("< JG=(char)(int)JG++; } } } /*扫描一遍从文件中读入表达式*/ void scan(FILE *fin) { int p[MAX]; char ch='a'; int c=-1,q=0; while(ch!=EOF) { ch=getc(fin); while(ch==' '||ch=='\n'||ch=='\t') ch=getc(fin);//消除空格和换行符 str[m++]=ch; if(ch=='='||ch=='+'||ch=='-'||ch=='*'||ch=='/') sum++; else if(ch=='(') { p[++c]=m-1; } else if(ch==')') { q=m-1; chengchuchuli(p[c],q);//从左括号处理到又括号 jiajianchuli(p[c],q); JG=(char)(int)JG--; str[p[c]]=str[m-1]=JG; c--; JG=(char)(int)JG++; } } } /*对表达是进行处理并输出部分四元式*/ void siyuanshi() { for(int i=0;i<=m-1;i++)//处理乘除运算 { if(str[i]=='*'||str[i]=='/') { cout<<"("< str[i-1]=str[i]=str[i+1]=JG; sum--; JG=(char)(int)JG++; } } for(int j=0;j<=m-1;j++)//处理加减运算 { if(str[j]=='+'||str[j]=='-') { cout<<"("< change(j-1); str[j-1]=str[j]=str[j+1]=JG; sum--; JG=(char)(int)JG++; } } for(int k=0;k<=m-1;k++)//处理赋值运算 { if(str[k]=='=') { JG=(char)(int)--JG; cout<<"("< change(k+1); str[k-1]=JG; } } } /***************主函数*******************/ void main() { char in[MAX]; //用于接收输入输出文件名 FILE *fin; //用于指向输入输出文件的指针 cout<<"请输入源程序文件名(例如ceshi.txt)："; cin>>in; cout< if ((fin=fopen(in,"r"))==NULL) //判断输入文件名是否正确 { cout< } cout<<"四元式如下："< scan(fin);//调用函数从文件中读入表达式 /********调用生成四元式的函数********/ siyuanshi(); /*********判断是否成功**********/ if(sum==0) cout<<"成功！"< } 运行结果: 编译原理语法分析实验报告 - 班级: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(标识符<标识符后缀>) 学号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 《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 . 编译原理实验专业：13级网络工程 语法分析器1 一、实现方法描述 所给文法为G【E】； E->TE’ E’->+TE’|空 T->FT’ T’->*FT’|空 F->i|(E) 递归子程序法： 首先计算出五个非终结符的first集合follow集，然后根据五个产生式定义了五个函数。定义字符数组vocabulary来存储输入的句子，字符指针ch指向vocabulary。从非终结符E函数出发，如果首字符属于E的first集，则依次进入T函数和E’函数，开始递归调用。在每个函数中，都要判断指针所指字符是否属于该非终结符的first集，属于则根据产生式进入下一个函数进行调用，若first集中有空字符，还要判断是否属于该非终结符的follow集。以分号作为结束符。 二、实现代码 头文件shiyan3.h #include #include int a=0; cout<<"按1结束程序"< 一、选择 1．将编译程序分成若干个“遍”是为了_使程序的结构更加清晰__。 2．正规式 MI 和 M2 等价是指__.M1 和 M2 所识别的语言集相等_。 3．中间代码生成时所依据的是 _语义规则_。 4．后缀式 ab+cd+/可用表达式__(a+b)/(c+d)_来表示。 6．一个编译程序中，不仅包含词法分析，_语法分析 ____，中间代码生成，代码优化，目标代码生成等五个部分。 7．词法分析器用于识别__单词___。 8．语法分析器则可以发现源程序中的___语法错误__。 9．下面关于解释程序的描述正确的是__解释程序的特点是处理程序时不产生目标代码 ___。 10．解释程序处理语言时 , 大多数采用的是__先将源程序转化为中间代码 , 再解释执行___方法。 11．编译过程中 , 语法分析器的任务就是__(2)(3)(4)___。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 12．编译程序是一种__解释程序__。 13．文法 G 所描述的语言是_由文法的开始符号推出的所有终极符串___的集合。 14．文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 3 型文法是___正则文法__。 15．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _产生式__。 16．通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括_表格处理和出错处理__。 17．文法 G[N]= （ {b} ， {N ， B} ， N ， {N→b│ bB ， B→bN} ），该文法所描述的语言是L(G[N])={b2i+1│ i ≥0} 18．一个句型中的最左_简单短语___称为该句型的句柄。 19．设 G 是一个给定的文法，S 是文法的开始符号，如果 S->x( 其中 x∈V*), 则称 x 是 文法 G 的一个__句型__。 21．若一个文法是递归的，则它所产生的语言的句子_是无穷多个___。 22．词法分析器用于识别_单词_。 23．在语法分析处理中， FIRST 集合、 FOLLOW 集合、 SELECT 集合均是_终极符集 ___。 24．在自底向上的语法分析方法中，分析的关键是_寻找句柄 ___。 25．在 LR 分析法中，分析栈中存放的状态是识别规范句型__活前缀__的 DFA 状态。 26．文法 G 产生的__句子___的全体是该文法描述的语言。 27．若文法 G 定义的语言是无限集，则文法必然是 __递归的_ 28．四种形式语言文法中，1 型文法又称为 _短语结构文法__文法。 29．一个文法所描述的语言是_唯一的__。 30． _中间代码生成___和代码优化部分不是每个编译程序都必需的。 31．_解释程序和编译程序___是两类程序语言处理程序。 32．数组的内情向量中肯定不含有数组的_维数___的信息。 33. 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组__D___。 34．文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 2 型文法是__上下文无关文法__。 35．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 __产生式___。 36．__ BASIC ___是一种典型的解释型语言。 37．与编译系统相比，解释系统___比较简单 , 可移植性好 , 执行速度慢__。 38．用高级语言编写的程序经编译后产生的程序叫__目标程序___。 39．编写一个计算机高级语言的源程序后 , 到正式上机运行之前，一般要经过__(1)(2)(3)__这几步: (1) 编辑 (2) 编译 (3) 连接 (4) 运行 40．把汇编语言程序翻译成机器可执行的目标程序的工作是由__编译器__完成的。 41．词法分析器的输出结果是__单词的种别编码和自身值__。 42．文法 G ：S→xSx|y 所识别的语言是_ xnyxn(n≥0)___。 43．如果文法 G 是无二义的，则它的任何句子α__最左推导和最右推导对应的语法树必定相同_。 44．构造编译程序应掌握___源程序目标语言编译方法___。 45．四元式之间的联系是通过__临时变量___实现的。 46．表达式( ┐ A ∨B)∧(C∨D)的逆波兰表示为___ A ┐ B∨CD∨∧__。 47. 优化可生成__运行时间短且占用存储空间小___的目标代码。 48．下列__删除多余运算 ____优化方法不是针对循环优化进行的。 49．编译程序使用__说明标识符的过程或函数的静态层次___区别标识符的作用域。 50．编译程序绝大多数时间花在___表格管理__ 上。 51．编译程序是对__高级语言的翻译___。 编译原理实验报告 班级 姓名： 学号： 自我评定： 实验一词法分析程序实现 一、实验目的与要求 通过编写和调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将字符形式的源程序流转化为一个由各类单词符号组成的流的词法分析方法。 二、实验内容 根据教学要求并结合学生自己的兴趣和具体情况，从具有代表性的高级程序设计语言的各类典型单词中，选取一个适当大小的子集。例如，可以完成无符号常数这一类典型单词的识别后，再完成一个尽可能兼顾到各种常数、关键字、标识符和各种运算符的扫描器的设计和实现。 输入：由符合或不符合所规定的单词类别结构的各类单词组成的源程序。 输出：把单词的字符形式的表示翻译成编译器的内部表示，即确定单词串的输出形式。例如，所输出的每一单词均按形如（CLASS，VALUE）的二元式编码。对于变量和常数，CLASS字段为相应的类别码；VALUE字段则是该标识符、常数的具体值或在其符号表中登记项的序号（要求在变量名表登记项中存放该标识符的字符串；常数表登记项中则存放该常数的二进制形式）。对于关键字和运算符，采用一词一类的编码形式；由于采用一词一类的编码方式，所以仅需在二元式的CLASS字段上放置相应的单词的类别码，VALUE字段则为“空”。另外，为便于查看由词法分析程序所输出的单词串，要求在CLASS字段上放置单词类别的助记符。 三、实现方法与环境 词法分析是编译程序的第一个处理阶段，可以通过两种途径来构造词法分析程序。其一是根据对语言中各类单词的某种描述或定义（如BNF），用手工的方式（例如可用C语言）构造词法分析程序。一般地，可以根据文法或状态转换图构造相应的状态矩阵，该状态矩阵同控制程序便组成了编译器的词法分析程序；也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序的另外一种途径是所谓的词法分析程序的自动生成，即首先用正规式对语言中的各类单词符号进行词型描述，并分别指出在识别单词时，词法分析程序所应进行的语义处理工作，然后由一个所谓词法分析程序的构造程序对上述信息进行加工。如美国BELL实验室研制的LEX就是一个被广泛使用的词法分析程序的自动生成工具。 总的来说，开发一种新语言时，由于它的单词符号在不停地修改，采用LEX等工具生成的词法分析程序比较易于修改和维护。一旦一种语言确定了，则采用手工编写词法分析程序效率更高。 四、实验设计 1）题目1：试用手工编码方式构造识别以下给定单词的某一语言的词法分析程序。 语言中具有的单词包括五个有代表性的关键字begin、end、if、then、else；标识符；整型常数；六种关系运算符；一个赋值符和四个算术运算符。参考实现方法简述如下。 单词的分类：构造上述语言中的各类单词符号及其分类码表。 表I 语言中的各类单词符号及其分类码表 单词符号类别编码类别码的助记符单词值 词法分析 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 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)都有 学号20102７９8 专业软件工程姓名薛建东 实验日期２013.04.０8 教师签字成绩实验报告 【实验名称】ＬL（1）语法分析 【实验目的】 通过完成预测分析法的语法分析程序,了解预测分析法和递归子程序法的区别和联系。使了解语法分析的功能，掌握语法分析程序设计的原理和构造方法,训练掌握开发应用程序的基本方法。 【实验内容】 ◆根据某一文法编制调试LL ( 1)分析程序，以便对任意输入的符号串进行分析。 ◆构造预测分析表,并利用分析表和一个栈来实现对上述程序设计语言的分析程序。 ◆分析法的功能是利用LＬ（１)控制程序根据显示栈栈顶内容、向前看符号以及LL(1) 分析表,对输入符号串自上而下的分析过程。 【设计思想】 （1）、LL(１)文法的定义 ＬL(1)分析法属于确定的自顶向下分析方法。LＬ（１)的含义是：第一个Ｌ表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式（规则)进行推导。 LL(1)文法的判别需要依次计算FIRＳT集、FOLＬＯW集和SELLＥＣT集,然后判断是否为LL（1)文法，最后再进行句子分析。 需要预测分析器对所给句型进行识别。即在LＬ(１)分析法中,每当在符号栈的栈顶出现非终极符时，要预测用哪个产生式的右部去替换该非终极符;当出现终结符时，判断其与剩余输入串的第一个字符是否匹配,如果匹配，则继续分析,否则报错。ＬＬ（1）分析方法要求文法满足如下条件：对于任一非终极符A的两个不同产生式Ａ→α，A→β,都要满足下面条件:ＳELEＣＴ(Ａ→α)∩SELＥCT（Ａ→β)＝? (2）、预测分析表构造 LL（1)分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推 基于编译原理的计算器设计与实现 首先看一下这个计算器的功能： CALC> set a = 1; b = 2 CALC> set c = 3 CALC> calc (10 + pow(b, c)) * sqrt(4) - 1 35.0 CALC> exit 如上所示，这个计算器的功能非常简单： 1.用set命令设置上下文中的变量。 2.用calc命令计算一个表达式的值。 3.用exit命令退出计算器。 我们把编译的重点放在calc命令后面的计算表达式的解析，其它的部分我们可以简单处理（如set命令可以这样简单处理：先按分号分隔得到多个赋值处理，再按等号分隔就可以在上下文中设置变量了，并不需要复杂的编译过程）。 如上的演示例子中，我们使用编译技术处理的部分是(10 + pow(b, c)) * sqrt(4) - 1，其它部分我们只使用简单的文本处理。 麻雀虽小，但五脏俱全，这个计算器包含编译技术中最必要的部分。虽然这次我们只是实现了一个计算器，但所使用的技术足以实现一个简单的脚本语言的解释器了。 这个计算器分为如下几个部分： 词法分析：把表达式的文本，解析成词法元素列表(tokenList)。 语法分析：把tokenList解析成语法树(syntaxTree)。 语义分析：把语法树转成汇编语言的代码(asm) 汇编器：把汇编代码翻译为机器码（字节码）。 虚拟机：执行字节码。 一般的编译步聚中不包含“汇编器”和“虚拟机”，而这里之所以包含这两个部分是因为：通常编译器会直接由中间代码生成机器码，而不是生成汇编代码，而这里我之所以要生成汇编代码的原因是“调试的时候汇编的可读性很好”，如果直接生成目标代码，则会非常难用肉眼来阅读。 自己实现虚拟机的原因是：现有的机器（包括物理机和虚拟机以及模拟器）的指令虽然也很丰富，但似乎都没有直接计算“乘方”或“开方”的指令，自已实现虚拟机可以任意设计计算指令，这样可以降低整个程序的复杂度。 因汇编器与虚拟机并不是编译原理的部分，所以下文中并不会描述其实现细节，但因为计算器代码编译后的目标代码就是汇编代码，所以需要把汇编指令做一下说明（以下把这个汇编语言简称为ASM）。 学年第学期《编译原理》实验报告 学院（系）：计算机科学与工程学院 班级：11303070A 学号：11303070*** 姓名：无名氏 指导教师：保密式 时间：2016 年7 月 目录 1．实验目的 (1) 2．实验内容及要求 (1) 3．实验方案设计 (1) 3.1 编译系统原理介绍 (1) 3.1.1 编译程序介绍 (2) 3.1.2 对所写编译程序的源语言的描述 (2) 3.2 词法分析程序的设计 (3) 3.3 语法分析程序设计 (4) 3.4 语义分析和中间代码生成程序的设计 (4) 4. 结果及测试分析 (4) 4.1软件运行环境及限制 (4) 4.2测试数据说明 (5) 4.3运行结果及功能说明 (5) 5．总结及心得体会 (7) 1．实验目的 根据Sample语言或者自定义的某种语言，设计该语言的编译前端。包括词法分析，语法分析、语义分析及中间代码生成部分。 2．实验内容及要求 （1）词法分析器 输入源程序，输出对应的token表，符号表和词法错误信息。按规则拼单词，并转换成二元形式；滤掉空白符，跳过注释、换行符及一些无用的符号；进行行列计数，用于指出出错的行列号，并复制出错部分；列表打印源程序；发现并定位词法错误； （2）语法分析器 输入token串，通过语法分析，寻找其中的语法错误。要求能实现Sample 语言或自定义语言中几种最常见的、基本的语法单位的分析：算术表达式、布尔表达式、赋值语句、if语句、for语句、while语句、do while语句等。 （3）语义分析和中间代码生成 输入token串，进行语义分析，修改符号表，寻找其中的语义错误，并生 成中间代码。要求能实现Sample语言或自定义语言中几种最常见的、基本的语法单位的分析：算术表达式、布尔表达式、赋值语句、if语句、for语句、while 语句、do while语句等。 实验要求：功能相对完善，有输入、输出描述，有测试数据，并介绍不足。3．实验方案设计 3.1 编译系统原理介绍 编译器逐行扫描高级语言程序源程序，编译的过程如下： (1).词法分析 识别关键字、字面量、标识符(变量名、数据名)、运算符、注释行(给人看的，一般不处理)、特殊符号(续行、语句结束、数组)等六类符号，分别归类等待处理。 (2).语法分析 一个语句看作一串记号(Token)流，由语法分析器进行处理。按照语言的文法检查判定是否是合乎语法的句子。如果是合法句子就以内部格式保存，否则报错。直至检查完整个程序。 (3).语义分析 语义分析器对各句子的语法做检查：运算符两边类型是否相兼容；该做哪些类型转换(例如，实数向整数赋值要"取整")；控制转移是否到不该去的地方；是 学号 20102798 专业软件工程姓名薛建东 实验日期2013.04.08 教师签字成绩 实验报告 【实验名称】LL（1）语法分析 【实验目的】 通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练掌握开发应用程序的基本方法。 【实验内容】 ◆根据某一文法编制调试LL （1 ）分析程序，以便对任意输入的符号串进行分析。 ◆构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序。 ◆分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号以及LL （1）分析表，对输入符号串自上而下的分析过程。 【设计思想】 （1）、LL（1）文法的定义 LL(1)分析法属于确定的自顶向下分析方法。LL(1)的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式(规则)进行推导。 LL(1)文法的判别需要依次计算FIRST集、FOLLOW集和SELLECT集,然后判断是否为LL(1)文法,最后再进行句子分析。 需要预测分析器对所给句型进行识别。即在LL(1)分析法中，每当在符号栈的栈顶出现非终极符时，要预测用哪个产生式的右部去替换该非终极符；当出现终结符时，判断其与剩余输入串的第一个字符是否匹配，如果匹配，则继续分析，否则报错。LL(1)分析方法要求文法满足如下条件：对于任一非终极符A的两个不同产生式A→α,A→β，都要满足下面条件：SELECT(A→α)∩SELECT(A→β)=? （2）、预测分析表构造 LL(1)分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推导。它的行对应文法的非终极符，列对应终极符，表中的值有两种：一是产生式的右部的字符串，一是null。若用M表示LL(1)分析表，则M可表示如下： 编译原理实验报告 课程：编译原理 系别：计算机系 班级：11网络 姓名：王佳明 学号：110912049 教师：刘老师 实验小组：第二组 1 实验一熟悉C程序开发环境、进行简单程序的调试 实验目的： 1、初步了解vc++6.0环境； 2、熟悉掌握调试c程序的步骤： 实验内容： 1、输入下列程序，练习Turbo C 程序的编辑、编译、运行。 #include 实验二词法分析器 一、实验目的： 设计、编制、调试一个词法分析子程序－识别单词，加深对词法分析原理的理解。 二、实验要求： 1.对给定的程序通过词法分析器弄够识别一个个单词符号，并以二元式(单词种别码，单词符号的属性值)显示。而本程序则是通过对给定路径的文件的分析后以单词符号和文字提示显示。 2.本程序自行规定： (1)关键字"begin","end","if","then","else","while","write","read", "do", "call","const","char","until","procedure","repeat" (2)运算符："+","-","*","/","=" (3)界符："{","}","[","]",";",",",".","(",")",":" (4)其他标记如字符串，表示以字母开头的标识符。 (5)空格、回车、换行符跳过。 在屏幕上显示如下： ( 1 , 无符号整数) ( begin , 关键字) ( if , 关键字) ( +, 运算符) ( ；, 界符) ( a , 普通标识符) 三、使用环境： Windows下的visual c++6.0; 四、调试程序： 1.举例说明文件位置：f：、、11.txt目标程序如下： begin x:=9 if x>0 then x:=x+1; while a:=0 do 3 实验二语法分析器 一、实验目的 通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培养适应社会多方面需要的能力。 二、实验内容 ◆根据某一文法编制调试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; 词法分析 一、实验目的 设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 二、实验要求 2.1 待分析的简单的词法 （1）关键字： begin if then while do end 所有的关键字都是小写。 （2）运算符和界符 ： = + - * / < <= <> > >= = ; ( ) # （3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义： ID = letter (letter | digit)* NUM = digit digit* （4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。 2.2 各种单词符号对应的种别码： 输入：所给文法的源程序字符串。 输出：二元组（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)…… 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 3.1 主程序示意图： 主程序示意图如图3-1所示。其中初始包括以下两个方面： ⑴关键字表的初值。 关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下： Char *rwtab[6] = {“begin”, “if”, “then”, “while”, “do”, “end”,}; 图3-1 （2）程序中需要用到的主要变量为syn,token和sum 3.2 扫描子程序的算法思想： 首先设置3个变量：①token用来存放构成单词符号的字符串；②sum用来整型单词；③syn用来存放单词符号的种别码。扫描子程序主要部分流程如图3-2所示。 编译原理考试题及答案汇总 一、选择 1．将编译程序分成若干个“遍”是为了_B__。 A . 提高程序的执行效率 B.使程序的结构更加清晰 C. 利用有限的机器内存并提高机器的执行效率 D.利用有限的机器内存但降低了机器的执行效率 2．正规式 MI 和 M2 等价是指__C__。 A . MI 和 M2 的状态数相等 B.Ml 和 M2 的有向弧条数相等。 C .M1 和 M2 所识别的语言集相等 D. Ml 和 M2 状态数和有向弧条数相等 3．中间代码生成时所依据的是 _C_。 A．语法规则 B．词法规则 C．语义规则 D．等价变换规则 4．后缀式 ab+cd+/可用表达式__B_来表示。 A． a+b/c+d B．(a+b)/(c+d) C． a+b/(c+d) D． a+b+c/d 6．一个编译程序中，不仅包含词法分析，_A____，中间代码生成，代码优化，目标代码生成等五个部分。 A．( ) 语法分析 B．( )文法分析 C．( )语言分析 D．( )解释分析 7．词法分析器用于识别__C___。 A．( ) 字符串 B．( )语句 C．( )单词 D．( )标识符 8．语法分析器则可以发现源程序中的___D__。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正 D．( ) 语法错误 9．下面关于解释程序的描述正确的是__B___。 (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1) C．( ) (1)(2)(3) D．( ) (2)(3) 10．解释程序处理语言时 , 大多数采用的是__B___方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 11．编译过程中 , 语法分析器的任务就是__B___。 实验一词法分析程序实现 一、实验目得与要求 通过编写与调试一个词法分析程序,掌握在对程序设计语言得源程序进行扫描得过程中,将字符流形式得源程序转化为一个由各类单词符号组成得流得词法分析方法 二、实验内容 基本实验题目：若某一程序设计语言中得单词包括五个关键字begｉｎ、end、if、then、elsｅ；标识符；无符号常数；六种关系运算符；一个赋值符与四个算术运算符，试构造能识别这些单词得词法分析程序（各类单词得分类码参见表Ｉ）。 表Ｉ语言中得各类单词符号及其分类码表 输入:由符合与不符合所规定得单词类别结构得各类单词组成得源程序文件。 输出：把所识别出得每一单词均按形如(CLASS，VＡLUE）得二元式形式输出,并将结果放到某个文件中。对于标识符与无符号常数，CＬASS字段为相应得类别码得助记符;V AL ＵＥ字段则就是该标识符、常数得具体值；对于关键字与运算符,采用一词一类得编码形式，仅需在二元式得CLASS字段上放置相应单词得类别码得助记符，V ALUE字段则为“空". 三、实现方法与环境 词法分析就是编译程序得第一个处理阶段，可以通过两种途径来构造词法分析程序.其一就是根据对语言中各类单词得某种描述或定义(如BＮF)，用手工得方式（例如可用Ｃ语言)构造词法分析程序。一般地,可以根据文法或状态转换图构造相应得状态矩阵,该状态矩阵连同控制程序一起便组成了编译器得词法分析程序;也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序得另外一种途径就是所谓得词法分析程序得自动生成，即首先用正规式对语言中得各类单词符号进行词型描述,并分别指出在识别单词时,词法分析程编译原理语法分析实验报告
编译原理-编写递归下降语法分析器
编译原理实验报告《LL(1)语法分析器构造》
编译原理实验报告(语法分析器)
编译原理
编译原理实验报告
编译原理词法分析和语法分析报告 代码(C语言版)
编译原理-语法分析-算符优先文法分析器
编译原理LL(1)语法分析实验报告
基于编译原理的计算器设计与实现
编译原理实验报告总结
编译原理LL(1)语法分析实验报告
编 译 原 理 实 验 报 告
编译原理 语法分析器 (java完美运行版)
编译原理词法分析和语法分析报告+代码(C语言版)
计算机题库编译原理试题汇总
编译原理实验报告一
- 新-编译原理语法分析实验报告
- 编译原理词法分析和语法分析报告+代码(C语言版)
- 编译原理SLR语法分析实验报告
- 编译原理实验报告(语法分析器)
- 编译原理实验报告
- 编译原理实验报告(词法分析器语法分析器)
- 编译原理词法分析和语法分析报告+代码(C语言版)[1]
- 编译原理语法分析实验报告
- 编译原理LL(1)语法分析实验报告
- 编译原理语法分析报告+代码
- 编译原理语法分析实验报告
- 编译原理语法分析实验报告
- 编译原理词法分析器实验报告
- 编译原理实验报告《LL(1)语法分析器构造》
- 编译原理实验报告(词法分析器语法分析器)
- 编译原理语法分析报告
- 编译原理实验报告《LL(1)语法分析器构造》资料整理
- 编译原理词法分析与语法分析实验报告
- 编译原理实验报告(词法分析器-语法分析器)
- 编译原理LL(1)语法分析实验报告