第1页 / 共23页
第2页 / 共23页
第3页 / 共23页
第4页 / 共23页
第5页 / 共23页
第6页 / 共23页
第7页 / 共23页
第8页 / 共23页
自顶向下的语法分析：LL(1)分析法.doc
《编译原理》课程实验
实验三：自顶向下的语法分析：LL（1）分析法
1、实验目的：用 LL（1）分析法分析高级语言表达式。了解 LL（1）分析器的工作过程
2、实验要求：
文法：无二义性的算术表达式的文法
（1）把词法分析作为语法分析的子程序实现（5 分）
（2）独立的语法分析程序（4 分）
（3）对表达式文法消除左递归、构造 LL（1）分析表
（4）LL（1）分析表可以直接输入（4 分），也可以用程序实现（5 分）
（5）给一个表达式，给出分析过程（分析栈、输入串、所用规则）（4 分）
（6）生成一个棵语法树（5 分）用二叉树的形式表示出来
LL(1)分析表算法:
(1) 构造所有侯选式的 FIRST 集合，构造所有非终结符的 FOLLOW 集合
(2) 对于文法 G 的每个产生式 A→α，执行（3）和（4）
(3) 对于每个终结符 a∈FIRST(α),把 A→α加至 M[A][a]
(4) 若ε∈FIRST(α)，则对于每个终结符 b∈FOLLOW(A),把 A→α加至 M[A][b]
(5) 把所有未定义的 M[A][c] 标上“出错标志”（c∈VT）
/*--------------------声明-----------------------*/
/*
阅读程序请从LL1.h开始。
补充：
程序存在问题：
(1) follow集不能处理：U->xVyVz的情况;
(2) 因本人偷懒，本程序为加入文法判断，故
输入的文法必须为LL(1)文法;
(3) 您可以帮忙扩充：消除左递归，提取公因子等函数
(4) ……
*/
/*-----------------------------------------------*/
#include "LL1.h"
/*-------------------main function--------------------*/
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("\n是否继续进行句型分析？(y / n):");
todo = getchar();
while('y' != todo && 'n' != todo)
{
}
printf("\n(y / n)? ");
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();
}
/*---------------function definition------------------*/
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(" %c ", collect[k++]);
printf("\n");
/*输入非终结符*/
void InputVn()
{
int inErr = 1;
int n,k;
char ch;
while(inErr)
{
printf("\n输入所有的非终结符：");
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符号数目超过限制！\n");
inErr = 1;
continue;
/*正确性确认，正确则，执行下下面，否则重新输入*/
Vn[k] = '\0';
ShowChArray(Vn);
ch = ' ';
while('y' != ch && 'n' != ch)
{
}
if('\n' != ch)
{
}
printf("输入正确确认?(y/n):");
scanf("%c", &ch);
if('n' == ch)
{
}
else
{
}
printf("录入错误重新输入！\n");
inErr = 1;
inErr = 0;
}
}
/*输入终结符*/
void InputVt()
{
int inErr = 1;
int n,k;
char ch;
while(inErr)
{
printf("\n输入所有的终结符：");
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符号数目超过限制！\n");
inErr = 1;
continue;
/*正确性确认，正确则，执行下下面，否则重新输入*/
Vt[k] = '\0';
ShowChArray(Vt);
ch = ' ';
while('y' != ch && 'n' != ch)
{
if('\n' != ch)
{
}
printf("输入正确确认?(y/n):");
scanf("%c", &ch);
}
if('n' == ch)
{
}
else
{
}
printf("录入错误重新输入！\n");
inErr = 1;
inErr = 0;
}
}
/*产生式输入*/
void InputP()
{
char ch;
int i = 0, n,num;
printf("输入文法产生式的个数：");
scanf("%d", &num);
PNum = num;
getchar();
/*消除回车符*/
printf("\n输入文法的%d个产生式,并以回车分隔每个产生式：", num);
printf("\n");
while(i < num)
{
printf("第%d个：", i);
/*初始化*/
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';
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++)
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
