--
南京信息工程大学实验（实习)报告
实验(实习)名称 LＬ(1)文法语法分析设计 实验（实习)日期 1１月28日 得分 指导教师 林美华 系 计算机 专业 计算机科学与技术 年级 2011 班次 计科3班 姓名 王欣 学号 20１12３０89１5
一． 实验目的
1．熟悉判断LL（１)文法的方法及对某一输入串的分析过程。 ２．学会构造表达式文法的预测分析表。
二． 实验内容
编写一个语法分析程序,对于给定的输入串，能够判断识别该串是否为给定文法的句型。
三． 实验步骤
从键盘读入输入串,并判断正误;
若无误,由程序自动构造FIRST、FOLLOW集以及ＳELECT集合，判断是否为ＬL（1）文法; 若符合LＬ(1）文法,由程序自动构造LL(1)分析表; 由算法判断输入符号串是否为该文法的句型 【源代码】
#inclｕdｅ ＂stdｉo.h\?＃inｃludｅ \ｔdlib.h\#define MaxRuleNum ８ ＃dｅfiｎe MａxVnＮum 5 ＃defｉｎe MaxＶｔNum 5
#ｄefｉnｅ MaxSｔａｃkDeｐtｈ ２０
#ｄeｆine MaxPLｅngth 20?#ｄefine ＭaxSｔLｅngtｈ 50
ｓtｒｕct ｐRＮoｄe /*产生式右部结构＊/?{? int rCursｏｒ; /*右部序号*/ struct pRNｏｄe *nｅxｔ;?}； sｔrucｔ pNode /＊产生式结点结构*/ {
iｎt lCursor; /＊左部符号序号＊／? int rLeｎgth; ／＊右部长度*/ /*注当rＬenｇtｈ = １ 时,rCursor = －１为空产生式*/ stｒucｔ pRNode *rHｅaｄ; /＊右部结点头指针＊/?};
char Ｖn[MaｘVnNum + 1]; /*非终结符集＊/?ｉnt ｖnNum;?cｈａr Vt[MaxＶtNuｍ + １]； /＊终结符集*/?ｉnt vtＮuｍ;?strucｔ ｐNode P[MaxRuleNum］; ／*产生式*/?ｉｎt PNum; /*产生式实际个数*/ ｃｈar buffｅｒ［MaxPLength ＋ 1]；?char ch; /*符号或strinｇ ｃh;*/?char st[ＭaxStＬength]; /＊要分析的符号串*/
struct coｌlecｔＮｏdｅ ／＊集合元素结点结构＊／?{ int nVt; /*在终结符集中的下标＊／ struｃｔ cｏlｌectＮｏdｅ *next;
--
--
};
strｕct collectNode* fiｒst[MaｘVnNｕm ＋ 1］; ／＊first集*/?sｔrｕct ｃｏlleｃｔNodｅ＊ ｆoｌlow[MaxＶｎNum + 1]； /＊folｌｏw集＊/
inｔ analyseTable［MａxVnNuｍ + 1］［MａxVｔNum ＋ １ + 1］;?／*预测分析表存放为产生式的编号,+1用于存放结束符,多＋１用于存放#(-1)*/
int aｎalyseＳtack[MａｘＳtaｃkDｅｐtｈ ＋ 1］; /＊分析栈*／?int topＡnalyse; ／*分析栈顶*/?/*ｉｎｔ ｒｅverseSｔａck[MaxSｔackDepｔｈ ＋ 1]； /*颠倒顺序栈*/?/＊ｉnt topＲｅverse; /*倒叙栈顶*/ ?voｉｄ Init(）；／*初始化＊/?int InｄexCｈ(char ch);?/*返回Vn在Vn表中的位置+１0０、Vt在Vt表中的位置,-１表示未找到*/?void InｐutVt(）； /*输入终结符*/?ｖoiｄ IｎｐutVｎ()；/*输入非终结符*/?ｖoid ShｏwChＡrray(char* collecｔ, int nuｍ）；/*输出Vn或Ｖt的内容*/
voiｄ InpuｔP();/*产生式输入＊／
boｏl ＣhｅcｋＰ(cｈar * ｓt）;/*判断产生式正确性*/?voｉd Firｓt(ｉnｔ U);/*计算ｆirst集，U－>xｘ...*／?voｉd AdｄＦirst(ｉｎt U, ｉｎt nCｈ)； /*加入ｆiｒst集*／?bｏol HaveＥmpty(ｉnt nＶｎ）； /*判断firsｔ集中是否有空(－1)*/?vｏid Follow(inｔ Ｖ);/*计算follow集*/
voｉd ＡｄｄFolloｗ(int V, ｉnt ｎCh, ｉnt kind)；/*加入foｌlow集,
kinｄ ＝ ０表加入ｆｏｌlow集，kiｎd = １加入ｆｉrｓt集*／?ｖoid ShｏwCollect(struct collectNode **coｌlｅcｔ);/*输出first或ｆollｏｗ集*/
vｏid FirsｔFｏllｏw();/*计算ｆirst和fｏllow*／?ｖoiｄ CreaｔeAT();／＊构造预测分析表＊/?void ShｏｗＡT（);／*输出分析表＊/?vｏｉｄ Identify(chａr *st）;／*主控程序,为操作方便＊/
/*分析过程显示操作为本行变换所用,与教程的显示方式不同*/?ｖｏid InitSｔacｋ();/*初始化栈及符号串*/?void ShowStack();／*显示符号栈中内容*／ void Pop（);/*栈顶出栈*/
ｖoiｄ Push(iｎt r)；/*使用产生式入栈操作*/
#inｃlude \．h\
voｉd ｍａiｎ（void)?{ ｃhar toｄo，ch; Iｎit();
InpｕtVn（）;? InputVt（);? InｐuｔP(); gｅtchar();
ＦirsｔFoｌloｗ();? pｒintf(\所得first集为:\）; SｈowＣollecｔ(ｆirst);
prｉｎｔf(\所得ｆolloｗ集为:\）;? SｈoｗＣollect(folloｗ); CreateＡT（); ＳhｏwＡT(）;
ｔodo = 'y＇;? while('y＇ =＝ tｏｄo) {
printf(\是否继续进行句型分析？(ｙ / n):\? todo = geｔcｈar(); whｉle(＇y' != toｄo && 'n＇ != tｏdｏ)
--
--
{
prｉntf(\ ／ ｎ)? \ todo = geｔcｈar();? } if('ｙ＇ == ｔodo)? ｛
int i；? IniｔStacｋ（);? pｒintｆ(\请输入符号串（以#结束) : \? ch = geｔcｈar();
i = 0;? wｈile('＃' != ch ＆& i < ＭaxStＬength) ｛
if(' ' ！= ch && ＇\\n＇ ！＝ ｃｈ）? { st[i+＋] = ch； }
ｃh = gｅｔchar(）; ｝? iｆ('#' == cｈ ＆& i < MaxStLengｔｈ)?{ ? ｓt[ｉ] = cｈ;? Iｄentｉｆy（sｔ）;
}? elsｅ ? ｐｒinｔf(\输入出错！\\ｎ\? } }
geｔcｈaｒ(); }
void Iniｔ()?{ iｎt i,j;
vnNｕm = 0;? ｖtNuｍ = 0; PNum ＝ 0;
ｆor(i = 0; i <＝ ＭaxVnNuｍ; i++) Ｖn[i] = '\\0＇；
for(i ＝ 0; i <= MaｘVtNuｍ; i++） Ｖt[i] = '\\0';
for(ｉ = 0; ｉ < MaxRulｅＮum; i++) {
Ｐ[ｉ].ｌCｕrｓor ＝ NUＬL;? P[i].rHｅａd = ＮUＬL；? P[i].rＬenｇth = 0; ｝
PNum = ０；
ｆｏr(i = 0; i <＝ ＭaｘPＬengｔh; i+＋)
buffer[i］ = '\\0';? for(i = 0； i ＜ ＭaxVnNｕｍ; i++） {? ｆiｒst[ｉ] = NULL；? ｆｏlloｗ[i］ = NULＬ; }? for(i ＝ 0; i <＝ MaxVnNuｍ； ｉ＋+)?{ ? for(ｊ = 0; j ＜= MaｘVnNum + 1; j+＋)? aｎalysｅTabｌe[i][ｊ] ＝ -１;?}?} ?/＊返回Vn在Vn表中的位置+100、Vt在Vt表中的位置,－1表示未找到＊/ int IndｅxCh(char ch) ｛
iｎｔ n;? ｎ ＝ 0; /*ｉｓ Vn?*／
whilｅ(ｃh !＝ Vn［n] && ＇\\0' != Vn［n]) ｎ+＋;? ｉf('\\0' ！= Vn[n］)? retuｒｎ １00 + ｎ;? n = 0； /*ｉｓ Vｔ?*／? whｉｌe(ch != Vt［n] ＆& '\\0' !＝ Ｖt[n])? n++;? if('\\0' != Ｖ
--
LL1语法分析器实验报告
