语法分析器(含完整源码)
语法分析实验报告
一、实验目的：
1. 了解单词(内部编码)符号串中的短语句型结构形成规律。
2. 理解和掌握语法分析过程中语法分析思想(LL，LR)的智能算法化方法。
二、实验内容：
构造自己设计的小语言的语法分析器：
1. 小语言的语法描述(语法规则)的设计即文法的设计；
2. 把文法形式符号中所隐含的信息内容挖掘出来并用LL或LR 的资料形式(分析表)表示出来；
3. 语法分析的数据输入形式和输出形式的确定；
4. 语法分析程序各个模块的设计与调试。
主要设备和材料：电脑、winxp操作系统、VC语言系统
三、实验分工：
学号姓名实验分工
08 实验代码设计及编写
08150 检查校对代码
0815 写电子版实验报告
08150 查找、分析、整理资料
08150 查找、分析、整理资料
08050
0815
081
四、实验步骤：
1、语法规则
①<程序>::= {<变量定义语句>|<赋值语句>|<条件语句> |<循环语句> }
②<变量定义语句>::=var 变量{，变量}；
③<赋值语句>::=变量：= <表达式>；
④<表达式>::=标识符{运算符标识符}；
⑤<标识符>::=变量|常量
⑥<运算符>::=+ | - | * | / | >= | <=
⑦<条件语句>::=
⑧
⑨
⑩<循环语句>::=while(表达式) [begin] {赋值语句| 条件语句| 循环语句} [end]
<输出语句>::=prn 表达式
--注1：若if语句、else语句、循环语句中出现begin，后面的end 必须出现，即begin与end同对出现
--注2：if、while后的"（"，"）"表示终结符，而不是定义成分优先的说明符号
2、分析表：
: = 变量常量，；运算
（ )
符
变量
定义->②->②->②->②
赋值
语句->③->③->③->③ ->③
条件
语句->⑦->⑦->⑦->⑦->⑦->⑦->⑦循环
语句->⑩->⑩->⑩->⑩->⑩->⑩->⑩输出
语句->->->
分析表(续)：
while var begin end if then prn
变量定义->②
赋值语句
条件语句->⑦->⑦->⑦->⑦
循环语句->⑩->⑩->⑩
输出语句-> 3、调试和测试
五、源代码（见附录）：
六、实验总结：
本实验在词法分析的基础上，对提取出的标识符进行语法判断。对已有的语法规则运用LL(1)文法判别并进行构造分析表时，遇到的最大困难是：当发生规约冲突时，该如何处理。如对于产生式s-->aAb，当对a进行规约时，满足语法规则的β（用户输入串中当前要进行规约的标识符）只有有限种，而不满足的却有无限种情况。当发生规约冲突时，如何在这无限种情况中，确定冲突的具体信息，以便用户查找。在反复的尝试和验证中，我们发现发生冲突的用户输入串满足一定的规律，且按这种规律可以把这无限种情况化归为有限类，于是我们找出其中规律并进行划分，然后再对这些有限类冲突进行处理。七、实验心得:
通过这次实验有以下几点收获:
1． LR(1)的构造使得对理论的知识理解的更加透彻。其中LR（1）分析表构造了很多遍，一直无法得到正确结果，这是恒心的考验。2．在写程序中用类数组来存放单词属性使得对单词各项值的调用更加方便，特别是对出错信息的检测有很大的作用。
3．本实验是在词法基础上的更进一步，在词法程序上添加语法程序，更加理解二者之间的关系。词法分析为语法分析提供了词法单元，方便分析，使程序模块化，易于读懂。
附录：
#include
#include
#include
#include
#include
#include
using namespace std;
#define Max 655 //最大代码长度
#define WordMaxNum 256 //变量最大个数#define DigitNum 256 //常量最大个数
#define MaxKeyWord 32 //关键字数量
#define MaxOptANum 8 //运算符最大个数
#define MaxOptBNum 4 //运算符最大个数
#define MaxEndNum 11 //界符最大个数
typedef struct DisplayTable
{
int Index; //标识符所在表的下标
int type; //标识符的类型
int line; //标识符所在表的行数
char symbol[20]; //标识符所在表的名称
}Table;
int TableNum = 0; //display表的表项总数
char Word[WordMaxNum][20]; //标识符表
char Digit[WordMaxNum][20]; //数字表
int WordNum = 0; //变量表的下标
int DigNum = 0; //常量表的下标
bool errorFlag = 0; //错误标志
int TableIndex = -1; //display 表的下标索引
int beginCount = 0;//遇到begin加1，遇到end减1
int ifCount = 0; //遇到if加1
Table *table = new Table[Max];
//关键字
const char* const KeyWord[MaxKeyWord] = {"and","array", "begin","case","char","constant","do","else","end","false", "for","if","input","integer","not","of","or","output", "packed","procedure","program","read","real","repeat","set", "then", "to", "type", "until", "var","while", "with","prn"};
// 单目运算
const char OptA[] = {'+','-','*','/','=','#','<','>'};
//双目运算符
const char *OptB[] = {"<=",">=",":=","<>"};
// 界符
const char End[] = {'(', ')' , ',' , ';' , '.' , '[' , ']' , ':' , '{' , '}' , '"'};
void error(char str[20],int nLine, int errorType)
{
errorFlag = 1;
cout <<" \nError : ";
switch(errorType)
{
case 1:
cout << "第" << nLine-1 <<"行" << str << " 变量的长度超过限制！\n";
break;
case 2:
cout << "第" << nLine-1 <<"行" << str << " 小数点错误！\n";
break;
case 3:
cout << "第" << nLine-1 <<"行" << str << " 常量的长度超过限制！\n";
break;
}//switch
}//error
void Scanner(char ch[],int chLen,int nLine)
{
int chIndex = 0;
while(chIndex < chLen) //对输入的字符扫描
{
/****************处理空格和tab***************************/ //忽略空格和tab
while(ch[chIndex] == ' ' || ch[chIndex] == 9 ) { chIndex ++; }
/*************************处理换行符*********************/ //遇到换行符，行数加1
while(ch[chIndex] == 10)
{ nLine++;chIndex ++;}
/***************************标识符**********************/
if( isalpha(ch[chIndex])) //以字母、下划线开头
{
char str[256];
int strLen = 0;
//是字母、下划线
while(isalpha(ch[chIndex]) || ch[chIndex] == '_' )
{
str[strLen ++] = ch[chIndex];
chIndex ++;
while(isdigit(ch[chIndex]))//不是第一位，可以为数字
{
str[strLen ++] = ch[chIndex];
chIndex ++;
}
}
str[strLen] = 0; //字符串结束符
if(strlen(str) > 20) //标识符超过规定长度，报错处理
{
error(str,nLine,1);
}
else
{
int i;
for(i = 0;i < MaxKeyWord; i++) //与关键字匹配//是关键字，写入table表中
if(strcmp(str, KeyWord[i]) == 0)
{
strcpy(table[TableNum].symbol,str);
table[TableNum].type = 1; //关键字
table[TableNum].line = nLine;
table[TableNum].Index = i;
TableNum ++;
break;
}
if(i >= MaxKeyWord) //不是关键字
{
table[TableNum].Index = WordNum;
strcpy(Word[WordNum++],str);
table[TableNum].type = 2; //变量标识符
strcpy(table[TableNum].symbol,str);
table[TableNum].line = nLine;
TableNum ++;
}
}
}
/**************************常数**************************/ else if(isdigit(ch[chIndex])) //遇到数字
{
int flag = 0;
char str[256];
int strLen = 0;
//数字和小数点
while(isdigit(ch[chIndex]) || ch[chIndex] == '.')
{
//flag表记小数点的个数，0时为整数，1时为小数，2时出错
if(ch[chIndex] == '.')
flag ++;
str[strLen ++] = ch[chIndex];
chIndex ++;
}
str[strLen] = 0;
if(strlen(str) > 20) //常量标识符超过规定长度20，报错处理{
error(str,nLine,3);
}
if(flag == 0)
{
table[TableNum].type = 3; //整数
}
if(flag == 1)
{
table[TableNum].type = 4; //小数
}
if(flag > 1)
{
error(str,nLine,2);
}
table[TableNum].Index = DigNum;
strcpy(Digit[DigNum ++],str);
strcpy(table[TableNum].symbol,str);
table[TableNum].line = nLine;
TableNum ++;
}
/*************************运算符************************/ else
{
//用来区分是不是无法识别的标识符，0为运算符，1为界符
int errorFlag;
char str[3];
str[0] = ch[chIndex];
str[1] = ch[chIndex + 1];
str[2] = '\0';
int i;
for( i = 0;i < MaxOptBNum;i++)//MaxOptBNum) if(strcmp(str,OptB[i]) == 0)
{
errorFlag = 0;
table[TableNum].type = 6;
strcpy(table[TableNum].symbol,str);
table[TableNum].line = nLine;
table[TableNum].Index = i;
TableNum ++;
chIndex = chIndex + 2;
break;
}
if(i >= MaxOptBNum)
{
for( int k = 0;k < MaxOptANum; k++)
if(OptA[k] == ch[chIndex])
{
errorFlag = 0;
table[TableNum].type = 5;
table[TableNum].symbol[0] = ch[chIndex];
table[TableNum].symbol[1] = 0;
table[TableNum].line = nLine;
table[TableNum].Index = k;
TableNum ++;
chIndex ++;
break;
}
/*************************界符************************/ for(int j = 0;j < MaxEndNum;j ++)
if(End[j] ==ch[chIndex])
{
errorFlag = 1;
table[TableNum].line = nLine;
table[TableNum].symbol[0] = ch[chIndex];
table[TableNum].symbol[1] = 0;
table[TableNum].Index = j;
table[TableNum].type = 7;
TableNum ++;
chIndex ++;
}
/********************其他无法识别字符*****************/ //开头的不是字母、数字、运算符、界符
if(errorFlag != 0 && errorFlag != 1) { char str[256];
int strLen = -1;
str[strLen ++] = ch[chIndex];
chIndex ++;
while(*ch != ' ' || *ch != 9 || ch[chIndex] != 10)
{
str[strLen ++] = ch[chIndex];
chIndex ++;
}
str[strLen] = 0;
table[TableNum].type = 8;
strcpy(table[TableNum].symbol,str);
table[TableNum].line = nLine;
table[TableNum].Index = -2;
TableNum ++;
}
}
}
}
/**************把十进制小数转为16进制******************/ void Trans(double x,int p) //把十进制小数转为16进制
{
int i=0; //控制保留的有效位数
while(i { if(x==0) //如果小数部分是0 break; //则退出循环 else { int k=int(x*16); //取整数部分 x=x*16-int(k); //得到小数部分 if(k<=9) cout< else cout< }; i++; }; 语法分析程序大作业 一、作业目的和要求 通过设计、编制、调试一个典型的语法分析程序（任选有代表性的语法分析方法，如LL(1)、递归下降分析法、LR、算符优先分析法）等，作为编制语法分析程序的依据，对词法分析器所提供的单词序列进行语法检测和结构分析，实现并进一步掌握常用的语法分析方法。 二、作业内容 选择对各种常见高级程序设计语言都较为通用的语法结构作为分析对象（例如表达式、if、while、for等等），给出其文法规则描述（注意，文法规则的描述要符合所选分析方法的要求，比如用LL(1)分析法，文法必须是LL(1)文法），设计并实现一个完整的语法分析程序。 输入：源程序以文件的形式输入。 输出：对于输入的源程序，如果输入源程序是给定文法定义的合法程序，则输出”success”，如果不是，即输入源程序有错误，则输出“Error”,并且尽可能指出出错位置和原因。 三、作业要求 1、说明语法分析的源语言是什么？ 能分析的语法成分有哪些（比如if、while、表达式、switch等等）。 给出每个语法规则的文法描述。（可以自定义语法成分，设计合理的语法规则。） 2、说明选择的语法分析方法是哪种？描述总体设计思路和主要的流程图。 3、编程实现，程序中编写的各种函数，需要给出注释，说明函数的作用。 四、结果分析 1、输入正确的源程序截图： 输出结果截图： 2、输入错误的源程序截图： 输出结果截图： 3、总结（自己的心得体会、你编写的语法分析程序的优缺点） 作业分工 上交内容：将以下文件打包压缩，压缩包命名：班级学号姓名_语法分析大作业 学号姓名以组长名字命名即可 1、本报告 2、语法分析程序代码 3、编译生成可执行程序 4、用于测试的源程序代码文件。 实验二语法分析器 一、实验目的 通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培养适应社会多方面需要的能力。 二、实验内容 ◆根据某一文法编制调试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; 《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 一、实验内容和目的 1. 已知待分析的C语言子集的语法，用EBNF表示如下： (1)<程序>→main()<语句块> (2)<语句块>→“{” <语句串>“}” (3)<语句串>→<语句>{;<语句>} ; (4)<语句>→<赋值语句>|<条件语句>|<循环语句> (5)<赋值语句>→ID=<表达式> (6)<条件语句>→if(条件)<语句块> (7)<循环语句>→while(<条件>)<语句块> (8)<条件>→<表达式><关系运算符><表达式> (9)<表达式>→<项>{+<项>}|<项>{-<项>} (10)<项>→<因子>{*<因子>}|<因子>{/<因子>} (11)<因子>→ID|NUM|(<表达式>) (12)<关系运算符>→<|<=|>|>=|==|!= 2. 实验目的、要求实现的功能 实验目的：编制一个语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析。 实验要求：在上机(一)词法分析的基础上，采用递归子程序法或其他适合的语法分析方法，实现其语法分析程序。要求编译后能检查出语法错误。 3. 将实验方法改写为适合预测分析法的文法如下： (1) <程序>→main()<语句块> (2)<语句块>→{ <语句串>} (3)<语句串>→<语句>; <语句串> (3_1) <语句串>→ε (4)<语句>→<赋值语句> (5)<语句>→<条件语句> (6) <语句>→<循环语句> (7)<赋值语句>→ID=<表达式> (8)<条件语句>→if(<条件>)<语句块> (9)<循环语句>→while(<条件>)<语句块> (10)<条件>→<表达式><关系运算符><表达式> (11)<表达式>→<项><表达式`> (11_1)<表达式`>→+<项><表达式`> (11_2)<表达式`>→-<项><表达式`> (11_3)<表达式`>→ε (12) <项>→<因子><项`> (12_1) <项`>→*<因子><项`> (12_2)<项`>→/<因子><项`> (12_3)<项`>→ε (13) <因子>→ID (14) <因子>→NUM (15) <因子>→(<表达式>) (16) <关系运算符>→< (17) <关系运算符>→<= 语法分析器的设计 一、实验内容 语法分析程序用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 语义分析程序的设计与实现 班号：2008211316姓名：张荣学号：08211627序号：26 实验日期：2010-11-23 一：实验内容： (2) 二：实验要求： (2) 三：实验方法： (2) ◆由LEX建立YACC的词法分析程序 (2) ◆yacc原理介绍 (3) ◆词法分析 (4) ◆解析器如何工作 (5) ◆Yacc环境 (6) ◆常用代码 (7) 第四：YACC内部名称： (7) 第五：运行结果（源代码见附录） (8) 第六：实验总结 (9) 第七：附录 (10) 附录一：yacc程序，加注释 (10) 附录二：词法分析器的工作原理 (16) 一：实验内容： 编写语法分析程序，实现对算术表达式的语法分析，要求所分析的算术表达式由如下的文法产生。 ◆E->E+T|E-T|T ◆T->T*F|T/F|F ◆F->id|(E)|num 二：实验要求： 在对表达式进行分析的同时，输出所采用的产生式。 可以采用多种方法 ◆编写递归调用程序，实现自顶向下的分析。 ◆编写LL(1)语法分析程序，要求： ◇编程实现算法4.2，为给定的文法自动构造预测分析表 ◇编程实现算法4.1，构造LL(1)预测分析程序， ◆编写语法分析程序，实现自底向上的分析，要求： ◇构造识别所有活前缀的DFA ◇构造LR分析表 ◇编程实现算法4.3，构造LR分析程序 ◆利用yacc自动生成语法分析程序，调用LEX自动生成的词法分析器程序 三：实验方法： ◆由LEX建立YACC的词法分析程序 由LEX产生的词法分析程序可用于YACC，LEX编译程序根据LEX 源程序产生词法分析程序yylex(),这个名字就是YACC所需要的词法分析程序的名字。如果YACC要调用LEX产生的词法分析程序，则在YACC源程序的第三部分用语句#include“lex.yy.c”代替函数yylex()的定义，这一yylex()就可以访问YACC中记号的名字，因为LEX的输出时候YACC输出文件的一部分，所有，每个LEX的动作都返回YACC 知道的终结符。 在UNIX的环境下，如果LEX源程序在first.l中，YACC的源程序在second.y中，可以使用以下命令得到所需要的分析程序。 Lex first.l Yacc second.y cc-o yaccdemo y.tab.c lex.yy.c ◆yacc原理介绍 Yacc 是用可移植的C 语言写成的。接受的规定类别是非常一般性的: 带有去歧义规则的LALR(1) 文法。 Yacc 提供了一个通用工具来在计算机程序的输入上施加结构。Yacc 用户准备输入处理的规定；它包括描述输入结构的规则，在识别了这些规则的时候调用的代码，和做基本输入的一个低层例程。Yacc 接着生成一个函数来控制输入处理。这个函数叫做解析器(parser)，它调用用户提供的低层输入例程(词法分析器(analyzer))来从输入流中选取基本项目(叫做记号(token))。依据叫做文法规则的输入结构规则来组织这些记号；在识别了这些规则中的某一个的时候，接着调用为这个规则提供的叫做动作的用户代码；动作有能力返回值并 编译原理程序设计实验报告 ——表达式语法分析器的设计班级：计算机1306班：涛学号：20133967 实验目标：用LL（1）分析法设计实现表达式语法分析器 实验容： ⑴概要设计：通过对实验一的此法分析器的程序稍加改造，使其能够输出正确的表达式的token序列。然后利用LL（1）分析法实现语法分析。 ⑵数据结构： int op=0; //当前判断进度 char ch; //当前字符 char nowword[10]=""; //当前单词 char operate[4]={'+','-','*','/'}; //运算符 char bound[2]={'(',')'}; //界符 struct Token { int code; char ch[10]; }; //Token定义 struct Token tokenlist[50]; //Token数组struct Token tokentemp; //临时Token变量struct Stack //分析栈定义 { char *base; char *top; int stacksize; }; ⑶分析表及流程图 逆序压栈 int IsLetter(char ch) //判断ch是否为字母 int IsDigit(char ch) //判断ch是否为数字 int Iskey(char *string) //判断是否为关键字 int Isbound(char ch) //判断是否为界符 int Isboundnum(char ch) //给出界符所在token值int init(STack *s) //栈初始化 int pop(STack *s,char *ch) //弹栈操作 int push(STack *s,char ch) //压栈操作 void LL1(); //分析函数 源程序代码：（加入注释） 题目：词法分析器的设计与实现 一、引言................................ 错误!未定义书签。 二、词法分析器的设计 (3) 2.1词的内部定义 (3) 2.2词法分析器的任务及功能 (3) 3 2.2.2 功能： (4) 2.3单词符号对应的种别码： (4) 三、词法分析器的实现 (5) 3.1主程序示意图： (5) 3.2函数定义说明 (6) 3.3程序设计实现及功能说明 (6) 错误!未定义书签。 7 7 四、词法分析程序的C语言源代码： (7) 五、结果分析： (12) 摘要：词法分析是中文信息处理中的一项基础性工作。词法分析结果的好坏将直接影响中文信息处理上层应用的效果。通过权威的评测和实际应用表明,IRLAS是一个高精度、高质量的、高可靠性的词法分析系统。众所周知,切分歧义和未登录词识别是中文分词中的两大难点。理解词法分析在编译程序中的作用，加深对有穷自动机模型的理解，掌握词法分析程序的实 现方法和技术，用c语言对一个简单语言的子集编制一个一遍扫描的编译程序，以加深对编译原理的理解,掌握编译程序的实现方法和技术。Abstract:lexical analysis is a basic task in Chinese information processing. The results of lexical analysis will directly affect the effectiveness of the application of Chinese information processing. The evaluation and practical application show that IRLAS is a high precision, high quality and high reliability lexical analysis system. It is well known that segmentation ambiguity and unknown word recognition are the two major difficulties in Chinese word segmentation. The understanding of lexical analyse the program at compile, deepen of finite automata model for understanding, master lexical analysis program implementation method and technology, using C language subset of a simple language compilation of a scanned again compiler, to deepen to compile the principle solution, master compiler implementation method and technology. 关键词：词法分析器?扫描器?单词符号?预处理 Keywords: lexical analyzer word symbol pretreatment scanner 一、引言 运用C语言设计词法分析器，由指定文件读入预分析的源程序，经过词法分析器的分析，将结果写入指定文件。本程序是在Visual?Studio环境下，使用C语言作为开发工具。基于实验任务 实验五LL(1)文法识别程序设计 一、实验目的 通过LL(1)文法识别程序的设计理解自顶向下的语法分析思想。 二、实验重难点 FIRST集合、FOLLOW集合、SELECT集合元素的求解，预测分析表的构造。 三、实验内容与要求 实验内容： 1．阅读并理解实验案例中LL(1)文法判别的程序实现； 2．参考实验案例，完成简单的LL(1)文法判别程序设计。 四、实验学时 4课时 五、实验设备与环境 C语言编译环境 六、实验案例 1．实验要求 参考教材93页预测分析方法，94页图5.11 预测分析程序框图，编写表达式文法的识别程序。要求对输入的LL(1)文法字符串，程序能自动判断所给字符串是否为所给文法的句子，并能给出分析过程。 表达式文法为： E→E+T|T T→T*F|F F→i|(E) 2．参考代码 为了更好的理解代码，建议将图5.11做如下标注： /* 程序名称：LL(1)语法分析程序*/ /* E->E+T|T */ /* T->T*F|F */ /* F->(E)|i */ /*目的: 对输入LL(1)文法字符串，本程序能自动判断所给字符串是否为所给文法的句子，并能给出分析过程。 /********************************************/ /* 程序相关说明*/ /* A=E' B=T' */ /* 预测分析表中列号、行号*/ /* 0=E 1=E' 2=T 3=T' 4=F */ /* 0=i 1=+ 2=* 3=( 4=) 5=# */ /************************************/ #include"iostream" #include "stdio.h" #include "malloc.h" #include "conio.h" /*定义链表这种数据类型参见： https://www.wendangku.net/doc/7b14682148.html,/link?url=_owQzf8PRZOt9H-5oXIReh4X0ClHo6zXtRdWrdSO5YBLpKl NvkCk0qWqvFFxjgO0KzueVwEQcv9aZtVKEEH8XWSQCeVTjXvy9lxLQ_mZXeS###*/ struct Lchar{ char char_ch; struct Lchar *next; }Lchar,*p,*h,*temp,*top,*base; /*p指向终结符线性链表的头结点，h指向动态建成的终结符线性链表节点，top和base分别指向非终结符堆栈的顶和底*/ 语法分析器的设计实验报告 一、实验内容 语法分析程序用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 《编译原理》实验报告题目: 语法分析器的制作 学生姓名:江荣吉 班级: 学号: 指导教师: 成绩: 西安邮电大学计算机学院 2015 年 6 月 7 日 一：实验目的 熟悉语法分析的过程； 理解相关文法的步骤； 熟悉First集和Follow集生成 二：实验要求 对于给定的文法，试编写调试一个语法分析程序： 要求和提示： （1）可选择一种你感兴趣的语法分析方法（LL(1)、算符优先、递归下降、SLR(1)等）作为编制语法分析程序的依据。 （2）对于所选定的分析方法，如有需要，应选择一种合适的数据结构，以构造所给文法的机内表示。 （3）能进行分析过程模拟。如输入一个句子，能输出与句子对应的语法树，能对语法树生成过程进行模拟；能够输出分析过程每一步符号栈的变化情 况。 设计一个由给定文法生成First集和Follow集并进行简化的算法动态模拟。 三：实验过程 1：文法： E->TE’ E’->+TE’|ε T->FT’ T’->*FT’|ε F->(E)|i: 2程序描述（LL(1)文法） 本程序是基于已构建好的某一个语法的预测分析表来对用户的输入字符串进行分析，判断输入的字符串是否属于该文法的句子。 基本实现思想：接收用户输入的字符串（字符串以“#”表示结束）后，对用做分析栈的一维数组和存放分析表的二维数组进行初始化。然后取出分析栈的栈顶字符，判断是否为终结符，若为终结符则判断是否为“#”且与当前输入符号一样，若是则语法分析结束，输入的字符串为文法的一个句子，否则出错若不为“#”且与当前输入符号一样则将栈顶符号出栈，当前输入符号从输入字符串中除去，进入下一个字符的分析。若不为“#”且不与当前输入符号一样，则出错。 LR分析程序设计 1实验目的 （1）构造LR 分析程序，利用它进行语法分析，判断给出的符号串是否为 该文法识别的句子； （2）了解LR分析方法是严格的从左向右扫描，和自底向上的语法分析方法。 2实验内容和实验要求 (1)LR分析器能够构造来识别所有能用上下文无关文法写的程序设计语言的结构。 (2)LR分析方法是已知的最一般的无回溯，移进-归约方法，它能够和其他移进-归约方法一样有效地实现。 (3)LR方法能分析的文法类是预测分析法能分析的文法类的真超集。 3 待分析的语法描述 E->vI:T I->I,i|i T->r 4算法描述 LR分析法基本思想 LR分析法是一种能够根据分析栈中的文法符号串（状态）和向右顺序查看第k个输入字符就能够唯一确定LR（k）分析器的动作是移进还是用哪一条产生式归约的分析方法。 采用LR（0）分析法进行本次实验，即无需向前查看输入符号就能够确定分析器的动作。 实现方法 LR（0）分析器由三个部分组成： (1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。 (2)分析表，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。由于它是总控程序的依据，所以在程序的第一部分就已经定义好。 (3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。 分析器的动作就是由栈顶状态和当前输入符号所决定。 (4)LR分析器及时察觉语法错误,快到自左向右扫描输入的最大可能。 为了使一个文法是LR的，只要保证当句柄出现在栈顶时，自左向右扫描的移进-归约分析器能够及时识别它便足够了。当句柄出现在栈顶时，LR分析器必须要扫描整个栈就可以知道这一点，栈顶的状态符号包含了所需要的一切信息。如果仅知道栈内的文法符号就能确定栈顶是什么句柄。由于LR分析表的转移函数本 《编译原理》 课程设计 院系信息科学与技术学院 专业软件工程 年级 2011级 学号 20112723 姓名林苾湲 西南交通大学信息科学与技术学院 2013年 12月 目录 课程设计1 词法分析器 (2) 1.1 设计题目 (2) 1.2 设计容 (2) 1.3 设计目的 (2) 1.4 设计环境 (2) 1.5 需求分析 (2) 1.6 概要设计 (2) 1.7 详细设计 (4) 1.8 编程调试 (5) 1.9 测试 (11) 1.10 结束语 (13) 课程设计2 赋值语句的解释程序设计 (14) 2.1 设计题目 (14) 2.2 设计容 (14) 2.3 设计目的 (14) 2.4 设计环境 (14) 2.5 需求分析 (15) 2.6 概要设计 (16) 2.7 详细设计 (16) 2.8 编程调试 (24) 2.9 测试 (24) 2.10 结束语 (25) 课程设计一词法分析器设计 一、设计题目 手工设计c语言的词法分析器（可以是c语言的子集）。 二、设计容 处理c语言源程序，过滤掉无用符号，判断源程序中单词的合法性，并分解出正确的单词，以二元组形式存放在文件中。 三、设计目的 了解高级语言单词的分类，了解状态图以及如何表示并识别单词规则，掌握状态图到识别程序的编程。 四、设计环境 该课程设计包括的硬件和软件条件如下： 4.1.硬件 （1）Intel Core Duo CPU P8700 （2）存4G 4.2.软件 （1）Window 7 32位操作系统 （2）Microsoft Visual Studio c#开发平台 4.3.编程语言 C#语言 五、需求分析 5.1.源程序的预处理：源程序中，存在许多编辑用的符号，他们对程序逻辑功能无任何影响。例如：回车，换行，多余空白符，注释行等。在词法分析之前，首先要先剔除掉这些符号，使得词法分析更为简单。 5.2.单词符号的识别并判断单词的合法性：将每个单词符号进行不同类别的划分。单词符号可以划分成5中。 (1)标识符：用户自己定义的名字，常量名，变量名和过程名。 (2)常数：各种类型的常数。 (3) 保留字（关键字）：如if、else、while、int、float等。 (4) 运算符：如+、-、*、<、>、=等。 (5)界符：如逗号、分号、括号等。 5.3.将所有合法的单词符号转化为便于计算机处理的二元组形式：（单词分类号，单词自身值）；以图形化界面显示出来。 5.4.可选择性地将结果保存到文件中。 六、概要设计 6.1．数据类型 6.1.1.单词的分类：本词法分析器演示的是C语言的一个子集，故字符集如下： 实验三语法分析器的设计 一、实验内容 设计、编写和调试构造LR（0）项目集规范簇或实现基于LR分析表对给定的符号串进行LR 分析的程序。以下两个内容任选其中一项： （1）对于给定的文法，实现构造识别该文法全部活前缀DFA的程序。 （2）对于给定的LR分析表和符号串，设计程序以实现所输入符号串是否为合法符号串。 要求用JAVA语言编程。（可参考实验指导书P149至P156） 二、程序代码 AnalysisOfGrammer.java package analysis; import javax.swing.*; import javax.swing.table.DefaultTableModel; import java.awt.*; import java.awt.event.*; import java.io.*; import java.util.LinkedList; publicclass AnalysisOfGrammer extends JApplet{ private JFileChooser jfc = new JFileChooser(new File(".")); private JButton jbt1 = new JButton("打开文法文件"); private JButton jbt2 = new JButton("构造LR规范簇"); private JButton jbt3 = new JButton("构造LR分析表"); private JButton jbt4 = new JButton("清空"); private JButton jbt5 = new JButton("退出"); private JLabel jl1 = new JLabel("LR(0)项目集规范簇"); private JLabel jl2 = new JLabel("LR(0)分析表"); private JPanel p3 = new JPanel(); private JTextArea jta1 = new JTextArea(); private String[] grammer = new String[50]; privateint count = 0; private LinkedList 实验内容： 可选择LL1分析法、算符优先分析法、LR分析法之一，实现如下表达式文法的语法分析器： （1）E→E+T | E-T | T （2）T→T*F | T/F | F （3）F→P^F | P （4）P→(E) | i 实验环境： Windows XP 实验分析： （1）定义部分：定义常量、变量、数据结构。 （2）初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）； （3）控制部分：从键盘输入一个表达式符号串； （4）利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分 实验程序： #include {'r','r','s','r','r','r'}, {'r','r','r','r','r','r'}, {'r','r','r','r','r','r'} }; char snum[12][6]={//数字表 {5,1,1,4,2,1}, {3,6,5,3,2,0}, {2,2,7,2,2,2}, {4,4,4,4,4,4}, {5,1,1,4,2,1}, {6,6,6,6,6,6}, {5,1,1,4,2,1}, {5,1,1,4,2,1}, {3,6,5,3,11,4}, {1,1,7,1,1,1}, {3,3,3,3,3,3}, {5,5,5,5,5,5} }; int go2[12][3]={//goto表 {1,2,3}, {0,0,0}, {0,0,0}, {0,0,0}, {8,2,3}, {0,0,0}, {0,9,3}, {0,0,10}, {0,0,0}, {0,0,0}, {0,0,0}, {0,0,0} }; void action(int i,char *&a,char &how,int &num,char &A,int &b)//action函数[i,a] { int j; switch(*a) { case 'i': j=0;break; case '+': j=1;break; case '*': j=2;break; case '(': 编译原理课程设计报告 课题名称：编译原理课程设计 C-语言词法与语法分析器的实现 C-词法与语法分析器的实现 1.课程设计目标 （1）题目实用性 C-语言拥有一个完整语言的基本属性，通过编写C-语言的词法分析和语法分析，对于理解编译原理的相关理论和知识有很大的作用。通过编写C-语言词法和语法分析程序，能够对编译原理的相关知识：正则表达式、有限自动机、语法分析等有一个比较清晰的了解和掌握。（2）C-语言的词法说明 ①语言的关键字： else if int return void while 所有的关键字都是保留字，并且必须是小写。 ②专用符号： + - * / < <= > >= == != = ; , ( ) [ ] { } /* */ ③其他标记是ID和NUM，通过下列正则表达式定义： ID = letter letter* NUM = digit digit* letter = a|..|z|A|..|Z digit = 0|..|9 注：ID表示标识符，NUM表示数字，letter表示一个字母，digit表示一个数字。 小写和大写字母是有区别的。 ④空格由空白、换行符和制表符组成。空格通常被忽略。 ⑤注释用通常的c语言符号/ * . . . * /围起来。注释可以放在任何空白出现的位置(即注释不能放在标记)上，且可以超过一行。注释不能嵌套。 （3）程序设计目标 能够对一个程序正确的进行词法及语法分析。 2.分析与设计 （1）设计思想 a.词法分析 词法分析的实现主要利用有穷自动机理论。有穷自动机可用作描述在输入串中识别模式的过程，因此也能用作构造扫描程序。通过有穷自动机理论能够容易的设计出词法分析器。b.语法分析 语法分析采用递归下降分析。递归下降法是语法分析中最易懂的一种方法。它的主要原理是，对每个非终结符按其产生式结构构造相应语法分析子程序，其中终结符产生匹配命令，而非终结符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与产生式结构几乎是一致的。 （2）程序流程图 程序主流程图： 词法分析: 语法分析：语法分析程序的要求
编译原理 语法分析器 (java完美运行版)
编译原理实验报告《LL(1)语法分析器构造》
编译原理(语法分析程序设计)
编译原理语法分析器实验
语义分析程序的设计与实现
编译原理实验二语法分析器LL(1)实现
词法分析器的实现与设计
实验5 LL(1)语法分析程序的设计与实现(C语言)
语法分析器实验报告
西安邮电大学编译原理语法分析器的制作
lR语法分析器设计
编译原理词法分析器语法分析课程设计报告书
编译语言-语法分析器的设计
语法分析C语言程序
编译原理课程设计报告C语言词法与语法分析器的实现
- 语法分析器的设计与实现
- 编译原理词法语法语义分析器设计打印版
- 词法分析器的实现与设计
- 语法分析器的设计
- C语言语法分析器
- 实验三：语法分析器的设计
- 编译原理词法语法语义分析器设计
- 编译语言-语法分析器的设计
- 语法分析器实验报告
- 编译原理课程设计--语法分析器-预测分析法
- 语法分析器的设计
- 语法分析器的设计与实现
- 编译原理实验-词法分析器的设计与实现.docx
- 毕业设计编译原理设计报告c语言词法与语法分析器的实现
- 编译原理实验报告5-语法分析程序的设计()
- 词法分析器的设计与实现
- lR语法分析器设计
- C_minus语言词法分析器的设计
- 语法分析器的设计与实现
- 《编译原理》语法分析器实验报告模板-课程设计-信安