LL1语法分析器实验报告
更新时间:2024-01-13 22:17:01 阅读量: 教育文库 文档下载
南京信息工程大学实验(实习)报告
实验(实习)名称 LL(1)文法语法分析设计实验(实习)日期 11月28日得分指导教师林美华 系计算机专业计算机科学与技术年级 2011 班次计科3班姓名王欣学号 20112308915
一. 实验目的
1.熟悉判断LL(1)文法的方法及对某一输入串的分析过程。 2.学会构造表达式文法的预测分析表。
二. 实验内容
编写一个语法分析程序,对于给定的输入串,能够判断识别该串是否为给定文法的句型。
三. 实验步骤
从键盘读入输入串,并判断正误;
若无误,由程序自动构造FIRST、FOLLOW集以及SELECT集合,判断是否为LL(1)文法; 若符合LL(1)文法,由程序自动构造LL(1)分析表; 由算法判断输入符号串是否为该文法的句型 【源代码】
#include \#include \#define MaxRuleNum 8 #define MaxVnNum 5 #define MaxVtNum 5
#define MaxStackDepth 20 #define MaxPLength 20 #define MaxStLength 50
struct pRNode /*产生式右部结构*/ {
int rCursor; /*右部序号*/ struct pRNode *next; };
struct pNode /*产生式结点结构*/ {
int lCursor; /*左部符号序号*/ int rLength; /*右部长度*/
/*注当rLength = 1 时,rCursor = -1为空产生式*/ struct pRNode *rHead; /*右部结点头指针*/ };
char Vn[MaxVnNum + 1]; /*非终结符集*/ int vnNum;
char Vt[MaxVtNum + 1]; /*终结符集*/
int vtNum;
struct pNode P[MaxRuleNum]; /*产生式*/ int PNum; /*产生式实际个数*/ char buffer[MaxPLength + 1]; char ch; /*符号或string ch;*/
char st[MaxStLength]; /*要分析的符号串*/
struct collectNode /*集合元素结点结构*/ {
int nVt; /*在终结符集中的下标*/ struct collectNode *next; };
struct collectNode* first[MaxVnNum + 1]; /*first集*/ struct collectNode* follow[MaxVnNum + 1]; /*follow集*/
int analyseTable[MaxVnNum + 1][MaxVtNum + 1 + 1];
/*预测分析表存放为产生式的编号,+1用于存放结束符,多+1用于存放#(-1)*/ int analyseStack[MaxStackDepth + 1]; /*分析栈*/ int topAnalyse; /*分析栈顶*/
/*int reverseStack[MaxStackDepth + 1]; /*颠倒顺序栈*/ /*int topReverse; /*倒叙栈顶*/
void Init();/*初始化*/ int IndexCh(char ch);
/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置,-1表示未找到*/ void InputVt(); /*输入终结符*/ void InputVn();/*输入非终结符*/
void ShowChArray(char* collect, int num);/*输出Vn或Vt的内容*/ void InputP();/*产生式输入*/
bool CheckP(char * st);/*判断产生式正确性*/ void First(int U);/*计算first集,U->xx...*/ void AddFirst(int U, int nCh); /*加入first集*/
bool HaveEmpty(int nVn); /*判断first集中是否有空(-1)*/ void Follow(int V);/*计算follow集*/
void AddFollow(int V, int nCh, int kind);/*加入follow集, kind = 0表加入follow集,kind = 1加入first集*/
void ShowCollect(struct collectNode **collect);/*输出first或follow集*/ void FirstFollow();/*计算first和follow*/ void CreateAT();/*构造预测分析表*/ void ShowAT();/*输出分析表*/
void Identify(char *st);/*主控程序,为操作方便*/
/*分析过程显示操作为本行变换所用,与教程的显示方式不同*/ void InitStack();/*初始化栈及符号串*/ void ShowStack();/*显示符号栈中内容*/
void Pop();/*栈顶出栈*/
void Push(int r);/*使用产生式入栈操作*/
#include \void main(void) {
char todo,ch; Init(); InputVn(); InputVt(); InputP(); getchar(); FirstFollow();
printf(\所得first集为:\ ShowCollect(first);
printf(\所得follow集为:\ ShowCollect(follow); CreateAT(); ShowAT(); todo = 'y';
while('y' == todo) {
printf(\是否继续进行句型分析?(y / n):\ todo = getchar();
while('y' != todo && 'n' != todo) {
printf(\ todo = getchar(); }
if('y' == todo) {
int i;
InitStack();
printf(\请输入符号串(以#结束) : \ ch = getchar(); i = 0;
while('#' != ch && i < MaxStLength) {
if(' ' != ch && '\\n' != ch) {
st[i++] = ch; }
ch = getchar(); }
if('#' == ch && i < MaxStLength) {
st[i] = ch; Identify(st); } else
printf(\输入出错!\\n\ } }
getchar(); }
void Init() {
int i,j; vnNum = 0; vtNum = 0; PNum = 0;
for(i = 0; i <= MaxVnNum; i++) Vn[i] = '\\0';
for(i = 0; i <= MaxVtNum; i++) Vt[i] = '\\0';
for(i = 0; i < MaxRuleNum; i++) {
P[i].lCursor = NULL; P[i].rHead = NULL; P[i].rLength = 0; }
PNum = 0;
for(i = 0; i <= MaxPLength; i++) buffer[i] = '\\0';
for(i = 0; i < MaxVnNum; i++) {
first[i] = NULL; follow[i] = NULL; }
for(i = 0; i <= MaxVnNum; i++) {
for(j = 0; j <= MaxVnNum + 1; j++) analyseTable[i][j] = -1; } }
/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置,-1表示未找到*/ int IndexCh(char ch) {
int n;
n = 0; /*is Vn?*/
while(ch != Vn[n] && '\\0' != Vn[n]) n++;
if('\\0' != Vn[n]) return 100 + n; n = 0; /*is Vt?*/
while(ch != Vt[n] && '\\0' != Vt[n]) n++;
if('\\0' != Vt[n]) return n; return -1; }
/*输出Vn或Vt的内容*/
void ShowChArray(char* collect) {
int k = 0;
while('\\0' != collect[k]) {
printf(\ }
printf(\}
/*输入非终结符*/ void InputVn() {
int inErr = 1; int n,k; char ch; while(inErr) {
printf(\请输入所有的非终结符,注意:\
printf(\请将开始符放在第一位,并以#号结束:\\n\ ch = ' '; n = 0;
/*初始化数组*/
while(n < MaxVnNum) {
Vn[n++] = '\\0'; }
n = 0;
while(('#' != ch) && (n < MaxVnNum)) {
if(' ' != ch && '\\n' != ch && -1 == IndexCh(ch))
{
Vn[n++] = ch; vnNum++; }
ch = getchar(); }
Vn[n] = '#'; /*以“#”标志结束用于判断长度是否合法*/ k = n; /*k用于记录n以便改Vn[n]='\\0'*/ if('#' != ch) {
if( '#' != (ch = getchar())) {
while('#' != (ch = getchar())) ;
printf(\符号数目超过限制!\\n\ inErr = 1; continue; } }
/*正确性确认,正确则,执行下下面,否则重新输入*/ Vn[k] = '\\0'; ShowChArray(Vn); ch = ' ';
while('y' != ch && 'n' != ch) {
if('\\n' != ch) {
printf(\输入正确确认?(y/n):\ }
scanf(\ }
if('n' == ch) {
printf(\录入错误重新输入!\\n\ inErr = 1; } else {
inErr = 0; } } }
/*输入终结符*/ void InputVt()
{
int inErr = 1; int n,k; char ch; while(inErr) {
printf(\请输入所有的终结符,注意:\ printf(\以#号结束:\\n\ ch = ' '; n = 0;
/*初始化数组*/
while(n < MaxVtNum) {
Vt[n++] = '\\0'; }
n = 0;
while(('#' != ch) && (n < MaxVtNum)) {
if(' '!= ch && '\\n' != ch && -1 == IndexCh(ch)) {
Vt[n++] = ch; vtNum++; }
ch = getchar(); }
Vt[n] = '#'; /*以“#”标志结束*/
k = n; /*k用于记录n以便改Vt[n]='\\0'*/ if('#' != ch) {
if( '#' != (ch = getchar())) {
while('#' != (ch = getchar())) printf(\符号数目超过限制!\\n\ inErr = 1; continue; } }
/*正确性确认,正确则,执行下下面,否则重新输入*/ Vt[k] = '\\0'; ShowChArray(Vt); ch =' ';
while('y' != ch && 'n' != ch) {
if('\\n' != ch)
{
printf(\输入正确确认?(y/n):\ }
scanf(\ }
if('n' == ch) {
printf(\录入错误重新输入!\\n\ inErr = 1; } else {
inErr = 0; } } }
/*产生式输入*/ void InputP() {
char ch;
int i = 0, n,num;
printf(\请输入文法产生式的个数:\ scanf(\ PNum = num;
getchar(); /*消除回车符*/
printf(\请输入文法的%d个产生式,并以回车分隔每个产生式:\ printf(\ while(i < num) {
printf(\第%d个:\ /*初始化*/
for(n =0; n < MaxPLength; n++) buffer[n] = '\\0'; /*输入产生式串*/ ch = ' '; n = 0;
while('\\n' != (ch = getchar()) && n < MaxPLength) {
if(' ' != ch)
buffer[n++] = ch; }
buffer[n] = '\\0';
/* printf(\ if(CheckP(buffer))
{
/*填写入产生式结构体*/ pRNode *pt, *qt;
P[i].lCursor = IndexCh(buffer[0]); pt = (pRNode*)malloc(sizeof(pRNode)); pt->rCursor = IndexCh(buffer[3]); pt->next = NULL; P[i].rHead = pt; n = 4;
while('\\0' != buffer[n]) {
qt = (pRNode*)malloc(sizeof(pRNode)); qt->rCursor = IndexCh(buffer[n]); qt->next = NULL; pt->next = qt; pt = qt; n++; }
P[i].rLength = n - 3; i++;
/*调试时使用*/ } else
printf(\输入符号含非法在成分,请重新输入!\\n\ } }
/*判断产生式正确性*/ bool CheckP(char * st) {
int n;
if(100 > IndexCh(st[0])) return false; if('-' != st[1]) return false; if('>' != st[2]) return false;
for(n = 3; '\\0' != st[n]; n ++) {
if(-1 == IndexCh(st[n])) return false; }
return true; }
/*====================first & follow======================*/
/*计算first集,U->xx...*/ void First(int U) {
int i,j;
for(i = 0; i < PNum; i++) {
if(P[i].lCursor == U) {
struct pRNode* pt; pt = P[i].rHead; j = 0;
while(j < P[i].rLength) {
if(100 > pt->rCursor) {
/*注:此处因编程出错,使空产生式时
rlength同样是1,故此处同样可处理空产生式*/ AddFirst(U, pt->rCursor); break; } else {
if(NULL == first[pt->rCursor - 100]) {
First(pt->rCursor); }
AddFirst(U, pt->rCursor); if(!HaveEmpty(pt->rCursor)) {
break; } else {
pt = pt->next; } } j++; }
if(j >= P[i].rLength) /*当产生式右部都能推出空时*/ AddFirst(U, -1); } } }
/*加入first集*/
void AddFirst(int U, int nCh) /*当数值小于100时nCh为Vt*/ /*当处理非终结符时,AddFirst不添加空项(-1)*/ {
struct collectNode *pt, *qt; int ch; /*用于处理Vn*/ pt = NULL; qt = NULL; if(nCh < 100) {
pt = first[U - 100]; while(NULL != pt) {
if(pt->nVt == nCh) break; else {
qt = pt;
pt = pt->next; } }
if(NULL == pt) {
pt = (struct collectNode *)malloc(sizeof(struct collectNode)); pt->nVt = nCh; pt->next = NULL;
if(NULL == first[U - 100]) {
first[U - 100] = pt; } else {
qt->next = pt; /*qt指向first集的最后一个元素*/ }
pt = pt->next; } } else {
pt = first[nCh - 100]; while(NULL != pt) {
ch = pt->nVt; if(-1 != ch) {
AddFirst(U, ch); }
pt = pt->next; } } }
/*判断first集中是否有空(-1)*/ bool HaveEmpty(int nVn) {
if(nVn < 100) /*为终结符时(含-1),在follow集中用到*/ return false;
struct collectNode *pt; pt = first[nVn - 100]; while(NULL != pt) {
if(-1 == pt->nVt) return true; pt = pt->next; }
return false; }
/*计算follow集,例:U->xVy,U->xV.(注:初始符必含#——\void Follow(int V) {
int i;
struct pRNode *pt ;
if(100 == V) /*当为初始符时*/ AddFollow(V, -1, 0 ); for(i = 0; i < PNum; i++) {
pt = P[i].rHead;
while(NULL != pt && pt->rCursor != V) /*注此不能处理:U->xVyVz的情况*/ pt = pt->next; if(NULL != pt) {
pt = pt->next; /*V右侧的符号*/
if(NULL == pt) /*当V后为空时V->xV,将左符的follow集并入V的follow集中*/ {
if(NULL == follow[P[i].lCursor - 100] && P[i].lCursor != V) {
Follow(P[i].lCursor); }
AddFollow(V, P[i].lCursor, 0); }
else /*不为空时V->xVy,(注意:y->),调用AddFollow加入Vt或y的first集*/ {
while(NULL != pt && HaveEmpty(pt->rCursor)) {
AddFollow(V, pt->rCursor, 1); /*y的前缀中有空时,加如first集*/ pt = pt->next; }
if(NULL == pt) /*当后面的字符可以推出空时*/ {
if(NULL == follow[P[i].lCursor - 100] && P[i].lCursor != V) {
Follow(P[i].lCursor); }
AddFollow(V, P[i].lCursor, 0); }
else /*发现不为空的字符时*/ {
AddFollow(V, pt->rCursor, 1); } } } } }
/*当数值小于100时nCh为Vt*/
/*#用-1表示,kind用于区分是并入符号的first集,还是follow集 kind = 0表加入follow集,kind = 1加入first集*/ void AddFollow(int V, int nCh, int kind) {
struct collectNode *pt, *qt; int ch; /*用于处理Vn*/ pt = NULL; qt = NULL;
if(nCh < 100) /*为终结符时*/ {
pt = follow[V - 100]; while(NULL != pt) {
if(pt->nVt == nCh) break; else {
qt = pt;
pt = pt->next; }
}
if(NULL == pt) {
pt = (struct collectNode *)malloc(sizeof(struct collectNode)); pt->nVt = nCh; pt->next = NULL;
if(NULL == follow[V - 100]) {
follow[V - 100] = pt; } else {
qt->next = pt; /*qt指向follow集的最后一个元素*/ }
pt = pt->next; } }
else /*为非终结符时,要区分是加first还是follow*/ {
if(0 == kind) {
pt = follow[nCh - 100]; while(NULL != pt) {
ch = pt->nVt;
AddFollow(V, ch, 0); pt = pt->next; } } else {
pt = first[nCh - 100]; while(NULL != pt) {
ch = pt->nVt; if(-1 != ch) {
AddFollow(V, ch, 1); }
pt = pt->next; } } } }
/*输出first或follow集*/
void ShowCollect(struct collectNode **collect) {
int i;
struct collectNode *pt; i = 0;
while(NULL != collect[i]) {
pt = collect[i];
printf(\ while(NULL != pt) {
if(-1 != pt->nVt) {
printf(\ } else
printf(\ pt = pt->next; } i++; }
printf(\}
/*计算first和follow*/ void FirstFollow() {
int i; i = 0;
while('\\0' != Vn[i]) {
if(NULL == first[i]) First(100 + i); i++; }
i = 0;
while('\\0' != Vn[i]) {
if(NULL == follow[i]) Follow(100 + i); i++; } }
/*=================构造预测分析表,例:U::xyz=============*/
void CreateAT() {
int i;
struct pRNode *pt;
struct collectNode *ct; for(i = 0; i < PNum; i++) {
pt = P[i].rHead;
while(NULL != pt && HaveEmpty(pt->rCursor)) {
/*处理非终结符,当为终结符时,定含空为假跳出*/ ct = first[pt->rCursor - 100]; while(NULL != ct) {
if(-1 != ct->nVt)
analyseTable[P[i].lCursor - 100][ct->nVt] = i; ct = ct->next; }
pt = pt->next; }
if(NULL == pt) {
/*NULL == pt,说明xyz->,用到follow中的符号*/ ct = follow[P[i].lCursor - 100]; while(NULL != ct) {
if(-1 != ct->nVt)
analyseTable[P[i].lCursor - 100][ct->nVt] = i; else /*当含有#号时*/
analyseTable[P[i].lCursor - 100][vtNum] = i; ct = ct->next; } } else {
if(100 <= pt->rCursor) /*不含空的非终结符*/ {
ct = first[pt->rCursor - 100]; while(NULL != ct) {
analyseTable[P[i].lCursor - 100][ct->nVt] = i; ct = ct->next; } }
else /*终结符或者空*/ {
if(-1 == pt->rCursor) /*-1为空产生式时*/ {
ct = follow[P[i].lCursor - 100]; while(NULL != ct) {
if(-1 != ct->nVt)
analyseTable[P[i].lCursor - 100][ct->nVt] = i; else /*当含有#号时*/
analyseTable[P[i].lCursor - 100][vtNum] = i; ct = ct->next; } }
else /*为终结符*/ {
analyseTable[P[i].lCursor - 100][pt->rCursor] = i; } } } } }
/*输出分析表*/ void ShowAT() {
int i,j;
1. printf(\构造预测分析表如下:\\n\
printf(\
for(i = 0; i < vtNum; i++) {
printf(\ }
printf(\
2. printf(\
for(i = 0; i <= vtNum; i++) printf(\ printf(\
3. for(i = 0; i < vnNum; i++)
{
printf(\ for(j = 0; j <= vtNum; j++) {
if(-1 != analyseTable[i][j])
printf(\
else
printf(\ }
printf(\ } }
/*=================主控程序=====================*/ void Identify(char *st) {
int current,step,r; /*r表使用的产生式的序号*/ printf(\的分析过程:\\n\
printf(\步骤\\t分析符号栈\\t当前指示字符\\t使用产生式序号\\n\
step = 0;
current = 0; /*符号串指示器*/ printf(\ ShowStack();
printf(\4. while('#' != st[current])
{
if(100 > analyseStack[topAnalyse]) /*当为终结符时*/ {
if(analyseStack[topAnalyse] == IndexCh(st[current])) {
/*匹配出栈,指示器后移*/ Pop(); current++; step++;
printf(\ ShowStack();
printf(\出栈、后移\\n\ } else {
printf(\不匹配!\ printf(\此串不是此文法的句子!\\n\ return; } }
else /*当为非终结符时*/ {
r = analyseTable[analyseStack[topAnalyse] - 100][IndexCh(st[current])]; if(-1 != r) {
Push(r); /*产生式右部代替左部,指示器不移动*/ step++;
printf(\ ShowStack();
printf(\ } else {
printf(\无可用产生式,此串不是此文法的句子!\\n\ return; } } }
if('#' == st[current]) {
5. if(0 == topAnalyse && '#' == st[current])
{
step++;
printf(\ ShowStack();
printf(\分析成功!\\n\ printf(\是给定文法的句子!\\n\ } else
{ while(topAnalyse > 0)
{ if(100 > analyseStack[topAnalyse]) /*当为终结符时*/ { printf(\无可用产生式,此串不是此文法的句子!\\n\ return; } else
{ r = analyseTable[analyseStack[topAnalyse] - 100][vtNum]; if(-1 != r)
{ Push(r); /*产生式右部代替左部,指示器不移动*/ step++;
printf(\ ShowStack();
if(0 == topAnalyse && '#' == st[current])
{ printf(\分析成功!\\n\ printf(\是给定文法的句子!\\n\ }
else
printf(\ } else
{ printf(\无可用产生式,此串不是此文法的句子!\\n\
return; } } } } } }
/*初始化栈及符号串*/ void InitStack() { int i;
/*分析栈的初始化*/
for(i = 0; i < MaxStLength; i++) st[i] = '\\0';
analyseStack[0] = -1; /*#(-1)入栈*/ analyseStack[1] = 100; /*初始符入栈*/ topAnalyse = 1; }
/*显示符号栈中内容*/ void ShowStack() { int i;
for(i = 0; i <= topAnalyse; i++) { if(100 <= analyseStack[i])
printf(\ else
{ if(-1 != analyseStack[i])
printf(\ else
printf(\ } } }
/*栈顶出栈*/ void Pop()
{ topAnalyse--; }
/*使用产生式入栈操作*/ void Push(int r) { int i;
struct pRNode *pt; Pop();
pt = P[r].rHead;
if(-1 == pt->rCursor) /*为空产生式时*/ return;
topAnalyse += P[r].rLength;
for(i = 0; i < P[r].rLength; i++)
{ /*不为空产生式时*/
analyseStack[topAnalyse - i] = pt->rCursor;/*逆序入栈*/ pt = pt->next;
}/*循环未完时pt为空,则说明rLength记录等出错*/ }
四. 实验结果
五. 实验总结
通过这次的实验,我深入了解了词法分析器和LL(1)文法预测分析法设计和实现,增强了我的自学能力和独立思考能力,也让我对程序设计有了更大的兴趣,自己通过查找资料、复习课本、编程调试,写实验报告等环节,进一步掌握了以前学到的知识,并且还对编译原理应用有了更深入的认识与掌握。在完成这个程序后,真的很开心,也了使我解到编译原理的魅力所在,激发了我要解决更多更难问题的决心。
正在阅读:
LL1语法分析器实验报告01-13
三年级下册第八周班队教案03-24
团委团支部换届选举工作流程图03-08
幼儿园教学活动设计与反思 - 图文12-17
部编版九年级语文下册第三单元9鱼我所欲也同步练习含解析05-05
圆锥摆模型和竖直面内圆周运动04-26
浙江师范大学校史·中卷 志04-30
单片机习题(1)12-20
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 分析器
- 语法
- 实验
- 报告
- LL1
- 八年级下数学分层作业(全学期5章) - 图文
- 职业技术学校年审自查报告
- 浅析农业银行人力资源管理存在的问题及几点建议
- 创设英语教学问题情境,激发学生学习兴趣
- 2019年中国餐厨垃圾处理市场深度调查研究与发展趋势分析报告
- 翻译服务合同范本
- 畅优新课堂秋九年级物理上册3.3连接电路增补练习(新版)教科版
- 7.5 用一元一次不等式解决问题导学案
- 财政部、国家税务总局、中国人民银行关于2011年财税库银税收收入
- 宁波会计从业考试 - 《财经法规》模拟
- 2012年电大会计学《现代管理原理》多选最终整合版
- 河南省实验中学2008 - --2009学年高一下期期中试卷(数学)1
- 曲沃县园区汇报(1)- 复件
- 坚持加快发展推进转型发展
- 新加坡留学:留学新加坡高中一年费用高吗
- 六盘水师院发〔2016〕8号--六盘水师范学院学士学位授予办法
- 来安县小学语文四年级下册《单元质量检测题》(综合练习二)
- 2015年下半年青海省安全工程师《安全生产管理》:企业工伤事故模拟试题
- 南阳理工学院信号与系统题库及答案
- 电控汽油机燃油供给系统工作原理与检修 - 图文