南京信息工程大学实验（实习）报告
实验（实习）名称 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))