编译原理 LL(1)文法源代码

发布时间：2024-11-25

纯LL1文法源代码,供参考使用

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 50

struct pRNode /*产生式右部结构*/ {

int rCursor;

struct pRNode *next; };

struct pNode {

int lCursor;

int rLength; /*右部长度*/

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;

char st[MaxStLength]; /*要分析的符号串*/

struct collectNode {

int nVt;

struct collectNode *next; };

struct collectNode* first[MaxVnNum + 1]; /*first集*/ struct collectNode* follow[MaxVnNum + 1]; /*follow集*/

纯LL1文法源代码,供参考使用

int analyseTable[MaxVnNum + 1][MaxVtNum + 1 + 1];

int analyseStack[MaxStackDepth + 1]; /*分析栈*/ int topAnalyse; /*分析栈顶*/

void Init();/*初始化*/ int IndexCh(char ch);

void InputVt(); /*输入终结符*/ void InputVn();/*输入非终结符*/

void ShowChArray(char* collect, int num);/*输出Vn或Vt的内容*/ void InputP();/*产生式输入*/

bool CheckP(char * st);/*判断产生式正确性*/ void First(int U);

void AddFirst(int U, int nCh); /*加入first集*/ bool HaveEmpty(int nVn);

void Follow(int V);/*计算follow集*/ void AddFollow(int V, int nCh, int kind);

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);

void main(void) {

char todo,ch;

Init();

InputVn(); InputVt(); InputP();

getchar();

FirstFollow();

printf("所得first集为："); ShowCollect(first);

printf("所得follow集为："); ShowCollect(follow);

纯LL1文法源代码,供参考使用

CreateA T();

ShowA T();

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();

}

void Init()

{

纯LL1文法源代码,供参考使用

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; } }

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; }

纯LL1文法源代码,供参考使用

/*输出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; if('#' != ch) {

if( '#' != (ch = getchar())) {

while('#' != (ch = getchar()))

纯LL1文法源代码,供参考使用

;

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) {

printf("录入错误重新输入！\n"); inErr = 1; } else {

inErr = 0; } } }

/*输入终结符*/ void InputVt() {

int inErr = 1; int n,k; char ch; while(inErr) {

printf("\n请输入所有的终结符，注意："); printf("以#号结束:\n"); ch = ' '; n = 0;

/*初始化数组*/

while(n < MaxVtNum) {

纯LL1文法源代码,供参考使用

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; 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) {

printf("录入错误重新输入！\n"); inErr = 1; } else {

纯LL1文法源代码,供参考使用

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));

纯LL1文法源代码,供参考使用

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; }

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) {

纯LL1文法源代码,供参考使用

if(100 > pt->rCursor) {

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) {

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;

纯LL1文法源代码,供参考使用

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; } } }

bool HaveEmpty(int nVn) {

if(nVn < 100) return false;

struct collectNode *pt; pt = first[nVn - 100]; while(NULL != pt)

纯LL1文法源代码,供参考使用

{

if(-1 == pt->nVt) return true; pt = pt->next; }

return false; }

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) pt = pt->next; if(NULL != pt) {

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 {

while(NULL != pt && HaveEmpty(pt->rCursor)) {

AddFollow(V, pt->rCursor, 1); pt = pt->next; }

if(NULL == pt) {

if(NULL == follow[P[i].lCursor - 100] && P[i].lCursor != V) {

Follow(P[i].lCursor); }

纯LL1文法源代码,供参考使用

AddFollow(V, P[i].lCursor, 0); } else {

AddFollow(V, pt->rCursor, 1); } } } } }

void AddFollow(int V, int nCh, int kind) {

struct collectNode *pt, *qt; int ch; 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集的最后一个元素*/ }

纯LL1文法源代码,供参考使用

pt = pt->next; } } else {

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("\n%c:\t", Vn[i]); while(NULL != pt) {

if(-1 != pt->nVt) {

纯LL1文法源代码,供参考使用

printf(" %c", Vt[pt->nVt]); } else

printf(" #"); pt = pt->next; } i++; }

printf("\n"); }

/*计算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++; } }

/*构造预测分析表*/ 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) {

纯LL1文法源代码,供参考使用

if(-1 != ct->nVt)

analyseTable[P[i].lCursor - 100][ct->nVt] = i; ct = ct->next; }

pt = pt->next; }

if(NULL == pt) {

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) {

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; } }

编译原理 LL(1)文法源代码.doc 将本文的Word文档下载到电脑
下载这篇word文档

    上一篇：怎么把小说下载到iphone

    下一篇：信息中心机房上墙制度

    精彩图片

    猜你喜欢

    热门精选

    经典双语美文：加油为了心中的梦想

    2020-09-14

    美文赏析：花开向暖，素锦留香

    2020-09-14

    经典美文：花开向暖，素锦留香

    2020-09-14

    经典美文：青春如歌，携一份懂得同行

    2020-09-14

    在雨中静听自己的心跳美文

    2020-09-14

    浅谈当今大学教育的含金量双语美文

    2020-09-14

    大家正在看

    土地征收法律意见书一则 2010年上期初三英语教研组工作总 博弈案例分析之百事可乐 控制压力钻井技术在油田高温高压 顺丰速运快递员提成信息化系统方 【城市雕塑论文】现代雕塑造型设 年产10万吨复合肥项目可行性研究 小学一年级数学教学计划-小学数
    × 游客快捷下载通道（下载后可以自由复制和排版）

    限时特价：7 元/份 原价:20元

    支付方式：

    微信支付并下载

    开通VIP包月会员 特价：29元/月

    注：下载文档有可能“只有目录或者内容不全”等情况，请下载之前注意辨别，如果您已付费且无法下载或内容有问题，请联系我们协助你处理。
    微信：fanwen365 QQ：370150219