LL语法分析程序设计.doc

实验二 LL（1）语法分析程序设计 【实验目的】 1．熟悉判断LL（1）文法的方法及对某一输入串的分析过程。 2．学会构造表达式文法的预测分析表。 【实验内容】 编写一个语法分析程序，对于给定的输入串，能够判断识别该串是否为给定文法的句型。 【实验步骤和要求】 从键盘读入输入串，并判断正误； 若无误，由程序自动构造FIRST、FOLLOW集以及SELECT集合，判断是否为LL（1）文法； 若符合LL（1）文法，由程序自动构造LL（1）分析表； 由算法判断输入符号串是否为该文法的句型。（可参考教材96页的例题1） 【说明】 语法分析主要是将从词法分析那里得来的记号构成一棵语法树。例SHMA#?adbe#??S-aH?H-aMd?H-d?M-Ab?M-?A-aM?A-e?分析例句：aaabd#??/*-------------------LL(1)语法分析--------------------*/#include stdio.h#include stdlib.h #define MaxRuleNum 8#define MaxVnNum 5#define MaxVtNum 5#define MaxStackDepth 20#define MaxPLength 20#define MaxStLength 50struct 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(s