LL(1)语法分析实验报告
一、实验题目 LL（1）语法分析
二、实验目的
通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，检查语法错误，进一步掌握常用的语法分析方法。
三、实验内容
构造LL(1)语法分析程序，任意输入一个文法符号串，并判断它是否为文法的一个句子。程序要求为该文法构造预测分析表，并按照预测分析算法对输入串进行语法分析，判别程序是否符合已知的语法规则，如果不符合则输出错误信息。
消除递归前的文法消除递归和提取公因子后的等价文法
S →S ∨ a T | a T | ∨ a T S→aTS’ |vaTS’
T →∧ a T | ∧a S’→vaTS’ |ε
T→∧ a T’
T’→∧ aT’
|ε
根据已建立的分析表，对下列输入串：a∧ a∧ a进行语法分析，判断其是否符合文法。
四、实验要求
1.根据已由的文法规则建立LL（1）分析表；
2.输出分析过程。
请输入待分析的字符串: a∧ a∧ a
符号栈输入串所用产生式
#S a∧ a∧ a#
#S’Ta a∧ a∧ a# S→aTS’
#S’T ∧ a∧ a#
# S’T’a∧∧ a∧ a# T→∧ a T’
# S’T’a a∧ a#
# S’T’∧ a#
# S’T’a∧∧ a# T’→∧ aT’
# S’ T’a a#
# S’ T’#
# S’ # T’→ε
# # S’→ε
五、程序思路
模块结构：
1、定义部分：定义常量、变量、数据结构。
2、初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体等）；
3、运行程序：让程序分析一个text文件，判断输入的字符串是否符合文法定义的规则；
4、利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示简单的错误提示。
六、程序源代码
/* 程序名称： LL(1)文法分析程序 */
/* S->S>aT|aT|>aT */
/* T-> /************************************/ /********************************************/ /* 程序相关说明 */ /* A=S’ B=T’ */ /* 0=S 1=S’ 2=T 3=T’*/ /* 0=a 1=< 2=#*/ /************************************/ #include"iostream.h" #include "stdio.h" #include "malloc.h" #include "conio.h" struct Lchar{ char char_ch; struct Lchar *next; }Lchar,*p,*h,*temp,*top,*base; char curchar; char curtocmp; int right; int table[4][3]={{1,0,0}, {0,0,1}, {0,1,0}, {0,1,1}}; int i,j; void push(char pchar) temp=(struct Lchar*)malloc(sizeof(Lchar)); temp->char_ch=pchar; temp->next=top; top=temp; } void pop(void) { curtocmp=top->char_ch; if(top->char_ch!='#') top=top->next; } void doforpush(int t) { switch(t) { case 3:push('A');push('T');push('a');push('<');break; case 0:push('A');push('T');push('a');break; case 6:push('T');push('a');push('<');break; case 21:push('B');push('a');push('<');break; case 31:push('T');break; } } void changchartoint() switch(curtocmp) { case 'S':i=0;break; case 'A':i=1;break; case 'T':i=2;break; case 'B':i=3;break; } switch(curchar) { case 'a':j=0;break; case '<':j=1;break; case '#':j=2; } } void dosome(void) { int t; for(;;) { pop(); curchar=h->char_ch; printf("\n%c\t%c",curchar,curtocmp); if(curtocmp=='#' && curchar=='#') if(curtocmp=='S'||curtocmp=='A'||curtocmp=='T'||curtocmp=='B') { if(curtocmp!='#') { changchartoint(); if(table[i][j]) { t=10*i+j; doforpush(t); continue; } else { right=0; break; } } else if(curtocmp!=curchar) { right=0; break; } break; } else if(curtocmp!=curchar) { right=0; break; } else { h=h->next; continue; } } } void main(void) { char ch; cout<<"* 文件名称: 语法分析"< cout<<"/* 程序相关说明 */"< cout<<"---------------------------------------------------------------------"< cout<<"-/* A=S’ B=T’ */"< cout<<"-* 目的: 对输入LL(1)文法字符串，本程序能自动判断所给字符串是 -"< cout<<"-* 否为所给文法的句子，并能给出分析过程。 -"< cout<<"-*-------------------------------------------------------------------"< cout<<" 表达式文法为："< cout<<" S->S>aT|aT|>aT "< cout<<" T-> cout<<"请在下行输入要分析的串(#号结束)："< right=1; base=(struct Lchar*)malloc(sizeof(Lchar)); base->next=NULL; base->char_ch='#'; temp=(struct Lchar*)malloc(sizeof(Lchar)); temp->next=base; temp->char_ch='S'; top=temp; h=(struct Lchar*)malloc(sizeof(Lchar)); h->next=NULL; p=h; do{ ch=getch(); putch(ch); if(ch=='a'||ch=='<'||ch=='#') { temp=(struct Lchar*)malloc(sizeof(Lchar)); temp->next=NULL; temp->char_ch=ch; h->next=temp; h=h->next; } else { temp=p->next; printf("\nInput a wrong char!Input again:\n"); for(;;) { if (temp!=NULL) printf("%c",temp->char_ch); else break; temp=temp->next; } }while(ch!='#'); p=p->next; h=p; dosome(); if(right) printf("\n成功!\n"); else printf("\n错误!\n"); getch(); } 七、程序调试与测试结果（输出结果截屏）特别注明：程序中使用“<”代替“ ”。输入a 若输入aa# 则显示错误信息如图： 注意：所有的输入串都要以#结束。 八：实验总结： 实验前首先要明白实验的目的，了解什么是LL（1）语法，实验前首先要写出分析表，然后 写出实验输出的分析过程，然后再写代码，分析实验结果。 《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 xx理工大学 《编译原理》 题目语法分析程序 姓名： 学号： 班级： 一、实验目的 编制一个递归下降分析程序，实现对词法分析程序所提供的单词序列的语法检查和结构分析。 二、实验要求 利用C语言编制递归下降分析程序，并对简单语言进行语法分析。 2.1 待分析的简单语言的语法 用扩充的BNF表示如下： ⑴<程序>：：=begin<语句串>end ⑵<语句串>：：=<语句>{；<语句>} ⑶<语句>：：=<赋值语句> ⑷<赋值语句>：：=ID：=<表达式> ⑸<表达式>：：=<项>{+<项> | -<项>} ⑹<项>：：=<因子>{*<因子> | /<因子> ⑺<因子>：：=ID | NUM | （<表达式>） 2.2 实验要求说明 输入单词串，以“#”结束，如果是文法正确的句子，则输出成功信息，打印“success”，否则输出“error”。 例如： 输入begin a:=9; x:=2*3; b:=a+x end # 输出success 输入x:=a+b*c end # 输出error 2.3 语法分析程序的酸法思想 ⑴主程序示意图如图2-1所示。 图2-1 语法分析主程序示意图 ⑵递归下降分析程序示意图如图2-2所示。 ⑶语句串分析过程示意图如图2-3所示。 图2-2 递归下降分析程序示意图 图2-3 语句串分析示意图 ⑷statement 语句分析程序流程如图2-4、2-5、2-6、2-7所示。 图2-4 statement 语句分析函数示意图 图2-5 expression 表达式分析函数示意图 图2-7 factor分析过程示意图三、语法分析程序的C语言程序源代码 #include "stdio.h" #include "string.h" char prog[100],token[8],ch; char *rwtab[6]={"begin","if","then","while","do","end"}; int syn,p,m,n,sum; int kk; factor(); expression(); yucu(); term(); statement(); lrparser(); scaner(); main() { p=kk=0; printf("\nGrade:05 Class:03 Name:Qiyubing Number:200507096 \n"); printf("\n----Please input the string end with '#':-------- \n"); do 编译技术 班级网络0802 学号3080610052姓名叶晨舟 指导老师朱玉全2011年 7 月 4 日 一、目的 编译技术是理论与实践并重的课程，而其实验课要综合运用一、二年级所学的多门课程的内容，用来完成一个小型编译程序。从而巩固和加强对词法分析、语法分析、语义分析、代码生成和报错处理等理论的认识和理解；培养学生对完整系统的独立分析和设计的能力，进一步培养学生的独立编程能力。 二、任务及要求 基本要求： 1．词法分析器产生下述小语言的单词序列 这个小语言的所有的单词符号，以及它们的种别编码和内部值如下表： 单词符号种别编码助记符内码值 DIM IF DO STOP END 标识符 常数（整）= + * ** ， （ ）1 2 3 4 5 6 7 8 9 10 11 12 13 14 $DIM $IF $DO $STOP $END $ID $INT $ASSIGN $PLUS $STAR $POWER $COMMA $LPAR $RPAR - - - - - - 内部字符串 标准二进形式 - - - - - - 对于这个小语言，有几点重要的限制： 首先，所有的关键字（如IF﹑WHILE等）都是“保留字”。所谓的保留字的意思是，用户不得使用它们作为自己定义的标示符。例如，下面的写法是绝对禁止的： IF（5）=x 其次，由于把关键字作为保留字，故可以把关键字作为一类特殊标示符来处理。也就是说，对于关键字不专设对应的转换图。但把它们（及其种别编码）预先安排在一张表格中（此表叫作保留字表）。当转换图识别出一个标识符时，就去查对这张表，确定它是否为一个关键字。 再次，如果关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔（此时，空白符不再是完全没有意义的了）。例如，一个条件语句应写为 LL(1)语法分析实验报告 一、实验题目 LL（1）语法分析 二、实验目的 通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，检查语法错误，进一步掌握常用的语法分析方法。 三、实验内容 构造LL(1)语法分析程序，任意输入一个文法符号串，并判断它是否为文法的一个句子。程序要求为该文法构造预测分析表，并按照预测分析算法对输入串进行语法分析，判别程序是否符合已知的语法规则，如果不符合则输出错误信息。 消除递归前的文法消除递归和提取公因子后的等价文法 S →S ∨ a T | a T | ∨ a T S→aTS’ |vaTS’ T →∧ a T | ∧a S’→vaTS’ |ε T→∧ a T’ T’→∧ aT’ |ε 根据已建立的分析表，对下列输入串：a∧ a∧ a进行语法分析，判断其是否符合文法。 四、实验要求 1.根据已由的文法规则建立LL（1）分析表； 2.输出分析过程。 请输入待分析的字符串: a∧ a∧ a 符号栈输入串所用产生式 #S a∧ a∧ a# #S’Ta a∧ a∧ a# S→aTS’ #S’T ∧ a∧ a# # S’T’a∧∧ a∧ a# T→∧ a T’ # S’T’a a∧ a# # S’T’∧ a# # S’T’a∧∧ a# T’→∧ aT’ # S’ T’a a# # S’ T’# # S’ # T’→ε # # S’→ε 五、程序思路 模块结构： 1、定义部分：定义常量、变量、数据结构。 2、初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体等）； 3、运行程序：让程序分析一个text文件，判断输入的字符串是否符合文法定义的规则； 4、利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示简单的错误提示。 六、程序源代码 /* 程序名称： LL(1)文法分析程序 */ /* S->S>aT|aT|>aT */ /* T-> . 编译原理实验专业：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结束程序"< 编译原理实验报告 实验名称：分析调试语义分析程序 TEST抽象机模拟器完整程序 保证能用！！！！！ 一、实验目的 通过分析调试TEST语言的语义分析和中间代码生成程序，加深对语法制导翻译思想的理解，掌握将语法分析所识别的语法范畴变换为中间代码的语义翻译方法。 二、实验设计 程序流程图 extern int TESTScan(FILE *fin,FILE *fout); FILE *fin,*fout; //用于指定输入输出文件的指针 int main() { char szFinName[300]; char szFoutName[300]; printf("请输入源程序文件名（包括路径）:"); scanf("%s",szFinName); printf("请输入词法分析输出文件名（包括路径）："); scanf("%s",szFoutName); if( (fin = fopen(szFinName,"r")) == NULL) { printf("\n打开词法分析输入文件出错！\n"); return 0; } if( (fout = fopen(szFoutName,"w")) == NULL) { printf("\n创建词法分析输出文件出错！\n"); return 0; } int es = TESTScan(fin,fout); fclose(fin); fclose(fout); if(es > 0) printf("词法分析有错，编译停止！共有%d个错误！\n",es); else if(es == 0) { printf("词法分析成功！\n"); int es = 0; 编译原理实验报告 实验一 一、实验名称：词法分析器的设计 二、实验目的：1，词法分析器能够识别简单语言的单词符号 2，识别出并输出简单语言的基本字.标示符.无符号整数.运算符.和界符。 三、实验要求：给出一个简单语言单词符号的种别编码词法分析器 四、实验原理： 1、词法分析程序的算法思想 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 2、程序流程图 （1 （2）扫描子程序 3 五、实验内容： 1、实验分析 编写程序时，先定义几个全局变量a[]、token[]（均为字符串数组),c,s( char型)，i,j,k（int型），a[]用来存放输入的字符串，token[]另一个则用来帮助识别单词符号，s用来表示正在分析的字符。字符串输入之后，逐个分析输入字符，判断其是否‘#’，若是表示字符串输入分析完毕，结束分析程序，若否则通过int digit(char c)、int letter(char c)判断其是数字，字符还是算术符,分别为用以判断数字或字符的情况，算术符的判断可以在switch语句中进行，还要通过函数int lookup(char token[])来判断标识符和保留字。 2 实验词法分析器源程序： #include 词法分析器实验报告 词法分析器设计 一、实验目的： 对C语言的一个子集设计并实现一个简单的词法分析器，掌握利用状 态转换图设计词法分析器的基本方法。利用该词法分析器完成对源程 序字符串的词法分析。输出形式是源程序的单词符号二元式的代码， 并保存到文件中。 二、实验内容： 1. 设计原理 词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。 理论基础：有限自动机、正规文法、正规式 词法分析器(Lexical Analyzer) 又称扫描器(Scanner)：执行词法分析的程序 2. 词法分析器的功能和输出形式 功能:输入源程序、输出单词符号 程序语言的单词符号一般分为以下五种：关键字、标识符、常数、运算符,界符 3. 输出的单词符号的表示形式: 单词种别用整数编码，关键字一字一种，标识符统归为一种，常数一种，各种符号各一种。 4. 词法分析器的结构 单词符号 5. 状态转换图实现 三、程序设计 1．总体模块设计 /*用来存储目标文件名*/ string file_name; /*提取文本文件中的信息。*/ string GetText(); /*获得一个单词符号,从位置i开始查找。并且有一个引用参数j，用来返回这个单词最后一个字符在str的位置。*/ string GetWord(string str,int i,int& j); /*这个函数用来除去字符串中连续的空格和换行 int DeleteNull(string str,int i); /*判断i当前所指的字符是否为一个分界符，是的话返回真，反之假*/ bool IsBoundary(string str,int i); /*判断i当前所指的字符是否为一个运算符，是的话返回真，反之假*/ bool IsOperation(string str,int i); #include 学号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)分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推 实验三语法分析器 一、实验目的： 理解和掌握LL(1)语法分析方法的基本原理；根据给出的LL(1)文法，掌握LL(1)分析表的构造及分析过程的实现，掌握语法分析方法和程序设计方法。 二、实验要求： 对每个非终极符按其产生式结构构造相应语法分析子程序，其中终极符产生匹配命令，而非终极符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与。产生式结构几乎是一致的，通过设计、编程、调试出一个具体语法分析程序。 三、实验原理： 语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器的工作本质上是按文法的产生式，识别输入串是否是一个句子。自上而下分析法的主旨是，对任何输入串，试图用一切可能的方法，从文法开始符号出发，自上而下地为输入串建立一棵语法树。这种方法本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。 对于一个文法满足以下三个条件，则称该文法为LL(1)文法。 文法不含有左递归。 对于文法中的每一个非终结符A的各个产生式的侯选首符集两两不相交。即，若A->Q1|Q2|…|Qn 则FIRST(Qi) ^FIRST(Qj)=null (i!=j) 对文法中的每个非终结符号A，若他存在某个侯选首符集包含空串，则FIRST(A)^FOLLOW(A)=null 对于一个文法满足LL(1)条件时，我们就可以对其输入串进行有效的无回溯的自上而下分析程序，这个分析程序是由一组递归过程组成的，每个过程对应文法的一个非终结符号。 四、实验步骤： 1、功能描述： 根据给定的文法，由程序生成项集族和语法分析表，对输入的源程序进行词法分析，得到语法分析的输入串，经过语法分析后得到三个栈，它们分别是状态栈，字符栈，输入栈，从而分析出输入的源程序是否有语法错误。 2、构造自己设计的小语言的语法分析器： (1) 语言的语法描述(语法规则)的设计即文法的设计； (2) 把文法形式符号中所隐含的信息内容挖掘出来并用LL或LR的资料形式(分析表)表示出来； (3) 语法分析的数据输入形式和输出形式的确定； #include 词法分析器实验报告 一、实验目的及要求 本次实验通过用C语言设计、编制、调试一个词法分析子程序，识别单词，实现一个C语言词法分析器，经过此过程可以加深对编译器解析单词流的过程的了解。 运行环境： 硬件：windows xp 软件：visual c++6.0 二、实验步骤 1.查询资料，了解词法分析器的工作过程与原理。 2.分析题目，整理出基本设计思路。 3.实践编码，将设计思想转换用c语言编码实现，编译运行。 4.测试功能，多次设置包含不同字符，关键字的待解析文件，仔细察看运行结果，检测该分析器的分析结果是否正确。通过最终的测试发现问题，逐渐完善代码中设置的分析对象与关键字表，拓宽分析范围提高分析能力。 三、实验内容 本实验中将c语言单词符号分成了四类：关键字key（特别的将main说明为主函数）、普通标示符、常数和界符。将关键字初始化在一个字符型指针数组*key[]中，将界符分别由程序中的case列出。在词法分析过程中，关键字表和case列出的界符的内容是固定不变的（由程序中的初始化确定），因此，从源文件字符串中识别出现的关键字，界符只能从其中选取。标识符、常数是在分析过程中不断形成的。 对于一个具体源程序而言，在扫描字符串时识别出一个单词，若这个单词的类型是关键字、普通标示符、常数或界符中之一，那么就将此单词以文字说明的形式输出．每次调用词法分析程序，它均能自动继续扫描下去，形成下一个单词，直到整个源程序全部扫描完毕，从而形成相应的单词串。 输出形式例如：void $关键字 流程图、程序流程图： 程序： #include 词法分析 一、实验目的 设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 二、实验要求 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．设计表达式的语法分析器算法（使用预测分析） 2．编写一段代码并上机调试查看其运行结果 三、实验要求 使用LL（1）分析算法设计表达式的语法分析器 LL（1）文法是一个自上而下的语法分析方法，它是从文法的开始符号出发，生成句子的最左推导，从左到右扫描源程序，每次向前查看一个字符，确定当前应该选择的产生式。 实现LL（1）分析的另一种有效方法是使用一张分析表和一个栈进行联合控制。 预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前a的输入符号行事的。对于任何（X，a），总控程序每次都执行三种可能的动作之一。 1.若X＝a＝“#”，则宣布分析成功，停止分析过程 2.若X＝a≠“#”，则把X从STACK栈顶逐出，让a指向下一 个输入符号。 3.若X是一个非终结符，则查看分析表。 四、运行结果 （本程序只能对由'i','+','*','(',')'构成的以'#'结束的字符串进行分析） 五、源程序实现 /*LL(1)分析法源程序，只能在VC++中运行*/ #include 编译原理语法分析器实验报告 班级： 学号： 姓名： 实验名称语法分析器 一、实验目的 1、根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。 2、本次实验的目的主要是加深对自上而下分析法的理解。 二、实验内容 [问题描述] 递归下降分析法： 0.定义部分：定义常量、变量、数据结构。 1.初始化：从文件将输入符号串输入到字符缓冲区中。 2.利用递归下降分析法分析，对每个非终结符编写函数，在主函数中调用文法开始符号的函数。 LL（1）分析法： 模块结构： 1、定义部分：定义常量、变量、数据结构。 2、初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体等）； 3、运行程序：让程序分析一个text文件，判断输入的字符串是否符合文法定义的规则； 4、利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式 符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示简 单的错误提示。 [基本要求] 1. 对数据输入读取 2. 格式化输出分析结果 2．简单的程序实现词法分析 public static void main(String args[]) { LL l = new LL(); l.setP(); String input = ""; boolean flag = true; while (flag) { try { InputStreamReader isr = new InputStreamReader(System.in); BufferedReader br = new BufferedReader(isr); System.out.println(); System.out.print("请输入字符串(输入exit退出)："); input = br.readLine(); } catch (Exception e) { e.printStackTrace(); } if(input.equals("exit")){ flag = false; }else{ l.setInputString(input); l.setCount(1, 1, 0, 0); l.setFenxi(); System.out.println(); System.out.println("分析过程"); System.out.println("----------------------------------------------------------------------"); System.out.println(" 步骤| 分析栈 | 剩余输入串| 所用产生式"); System.out.println("----------------------------------------------------------------------"); boolean b = l.judge(); System.out.println("----------------------------------------------------------------------"); if(b){ System.out.println("您输入的字符串"+input+"是该文法的一个句子"); }else{ System.out.println("您输入的字符串"+input+"有词法错误！"); 实验内容： 可选择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 '(': 基于LR(1)的语法分析程序 1.设计目的： 设计、编制和调试一个典型的LR(1)分析器，进一步掌握LR(1)语法分析方法,掌握用预测分析方法分析LR(1)文法的具体过程，加深对LR(1)文法和预测分析方法的理解。 2.设计要求： （1）根据LR(1)分析法编写一个语法分析程序，.输入已给定文法，直接输入根据己知文法构造的LR(1)分析表。 （2）对于输入的符号串，所编制的语法分析程序应能正确判断此串是否为文法的句子，并要求输出分析过程。 3.设计过程： 3.1 LR(1)文法的含义： LR分析法的规约过程是规范推倒的逆过程，所以LR分析过程是一种规范规约的逆过程，L表示从左到右扫描输入串，R表示最左规约（即最右推导的逆过程），括号中的1表示向右查看输入符号数为1。LR（1）项目可以看成两个部分组成，一部分和LR （0）项目相同，这部分成为心，另一部分为向前搜索符集合。所以只有当面临的输入符属于向前搜索符的集合，才做规约动作，其他情况均出错。LR（1）方法恰好解决SLR（1）方法在某些情况下存在的无效规约问题。 3.2 设计思想： 根据自身实际情况，给定了编译原理书中的一个LR(1)文法，求出其项目集合转换函数，从而得出此LR(1)文法的分析表，在程序中直接输出此分析表，并根据分析表中的内容可对输入的符 号串进行分析，判断是接受还是出错，从而得出该输入的符号串是否为文法的一个句子。 3.3 算法描述： 1.CLOSURE(I)的构造 CLOSURE(I)表示和I中项目可以识别同样活前缀的所有项目的集合。它可以有以下方法得到： (1)I中的所有项目都属于CLOSURE(I)； (2)若项目[A→a.Bβ,a]属于CLOSURE(I)，B→ξ是一个产生式，那么，对于FIRST<βa>中的每一个中介符b,如果[β→.ξ,b]原来不在CLOSURE(I)中，则把它加进去； (3)重复执行步骤（2），直到CLOSURE(I)不再增大为止。 2.GO(I,X)的构造 GO(I,X)=CLOSURE(J) 其中J={任何形如[A→aX.Β,a]的项目[A→a.X.Β,a]属于I} 3.FIRST集合的构造 在这个程序中使用的是FIRST(βa)，这基于每一个非终结符的FRIST集合（终结符的FIRST就是它本身）。所以需要对每一个非终结符构造其FIRST集合。 方法如下： 连续使用下面的规则，直到每个集合FIRST不再增大为止。 （1）若X属于V T，则FIRST(X)={X}。 （2）若X属于V N，且有产生式X→a…，则把A加入到FIRST(X)中；若X→ξ也是一条产生式，则把ξ也加入到FIRST 中。 4.LR(1)分析表的构造 在实现GO(I,X)时，记录下状态的转化。得到分析表中的移进部分。然后再扫描所有的项目集，找到其中包含归约项目的哪些项目集，根据其中项目，得到分析表中那些鬼月的部分。 4 设计内容 4.1 主要变量说明： #define SIZE 20 //宏定义，定义sSIZE为12 #define sSIZE 12 //宏定义，定义sSIZE为12编译原理实验报告《LL(1)语法分析器构造》
语法分析程序报告
编译原理词法分析器语法分析器实验报告
语法分析程序实验报告及代码
编译原理实验报告(语法分析器)
TEST语言 -语法分析,词法分析实验报告
编译原理实验报告(词法分析器-语法分析器).doc
词法分析器实验报告
四川大学Cminus语法分析器纯代码
编译原理LL(1)语法分析实验报告
语法分析器实验报告
语法分析器源代码
词法分析器实验报告
编译原理词法分析和语法分析报告+代码(C语言版)
语法分析(自上而下分析)实验报告
编译原理语法分析器实验报告
语法分析C语言程序
基于LR(1)的语法分析程序报告
相关主题
文本预览