LL文法语法分析-编译原理课程设计

1、湖北大学本科课程设计 题 目 LL(1)文法语法分析 课 程 编译原理 姓 名 刘欢 学 号 2007221104210519专业年级 计算机科学与技术2007级 指导教师 张万山 职 称 2010年 1 月 8日摘 要选题要求：根据某一文法编制调试LL(1) 文法语法分分析程序，以便对任意输入的符号串进行分析。本次课程设计的目的主要是加深对预测分析LL(1)文法语法分析法的理解。具体如下：1、对语法规则有明确的定义；2、编写的分析程序能够对给定文法进行正确的语法分析；3、对输入给定的文法，手工计算FIRST、FOLLOW集合和select集合，应能判断识别是否为给定文法的句子，并给出推导过程

2、。4、对输入给定的文法，由程序自动构造FIRST、FOLLOW集合和select集合。5、对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程。【关键词】LL(1)文法 语法分析 FIRST FOLLOW select 目录 TOC o 1-3 h z u HYPERLINK l _Toc250827577 摘 要 PAGEREF _Toc250827577 h I HYPERLINK l _Toc250827578 目录 PAGEREF _Toc250827578 h II HYPERLINK l _Toc250827579 1系统分析 PAGEREF _

3、Toc250827579 h 1 HYPERLINK l _Toc250827580 选题要求 PAGEREF _Toc250827580 h 1 HYPERLINK l _Toc250827581 预期目标 PAGEREF _Toc250827581 h 1 HYPERLINK l _Toc250827582 2系统设计 PAGEREF _Toc250827582 h 2 HYPERLINK l _Toc250827583 基本设计 PAGEREF _Toc250827583 h 2 HYPERLINK l _Toc250827584 程序流程图 PAGEREF _Toc250827584

4、h 4 HYPERLINK l _Toc250827585 3系统实现 PAGEREF _Toc250827585 h 5 HYPERLINK l _Toc250827586 上机编程 PAGEREF _Toc250827586 h 5 HYPERLINK l _Toc250827587 运行结果 PAGEREF _Toc250827587 h 8 HYPERLINK l _Toc250827588 读入ll(1)文法 PAGEREF _Toc250827588 h 9 HYPERLINK l _Toc250827589 优化ll(1)文法 PAGEREF _Toc250827589 h 9

5、HYPERLINK l _Toc250827590 找出各终结符的First和Follow集 PAGEREF _Toc250827590 h 10 HYPERLINK l _Toc250827591 找出各产生式的Select集 PAGEREF _Toc250827591 h 10 HYPERLINK l _Toc250827592 填写分析表 PAGEREF _Toc250827592 h 10 HYPERLINK l _Toc250827593 语法分析 PAGEREF _Toc250827593 h 11 HYPERLINK l _Toc250827594 完成 PAGEREF _Toc

6、250827594 h 11 HYPERLINK l _Toc250827595 4总结与感想 PAGEREF _Toc250827595 h 12 HYPERLINK l _Toc250827596 参考文献 PAGEREF _Toc250827596 h 131系统分析选题要求根据某一文法编制调试LL(1) 文法语法分分析程序，以便对任意输入的符号串进行分析。本次课程设计的目的主要是加深对预测分析LL(1)文法语法分析法的理解。预期目标构造LL(1)文法语法分析程序，任意输入一个文法符号串，并判断它是否为文法的一个句子。程序要求为该文法构造预测分析表，并按照预测分析算法对输入串进行语法分析

7、，判别程序是否符合已知的语法规则，如果不符合（编译出错），则输出错误信息。2系统设计基本设计在这个源程序中涉及到以下种重要数据结构：图1 队列结构图图2 堆栈结构图图3 产生式结构图图4 存储First或Follow集的结构图图5 表结构图程序流程图开始读入ll(1)文法文件，并显示出所有读取的产生式优化并显示新的产生式找出并显示各非终结符的First集找出各产生式的Select集构造并显示分析表进行语法分析，判断是否匹配？结束YN找出并显示各非终结符的Follow集输入待分析的字符串显示分析过程是否继续分析下一条句子？NY3系统实现（出于篇幅考虑，此处仅列出核心语法分析代码）#include

8、 #include #include #define maxlen 13#define idle 5 /用来代表的字符 /*产生式*struct Fl_Node;typedef struct Fl_Node *Fl_PNode;struct Fl_Node/存储FIRST集与FoLLOW集的终结符 char info; Fl_PNode link;struct Jo_F_Node;typedef struct Jo_F_Node *Jo_F_PNode;struct Jo_F_Node/存储FIRST集与FoLLOW集的结点(非终结符) Jo_F_PNode link; char F; Fl_

9、PNode next;struct LinkF_F/存储FIRST集与FoLLOW集的头 Jo_F_PNode knot;typedef struct LinkF_F *PLinkF_F;struct Pr_Node;typedef struct Pr_Node *Pr_PNode;struct Pr_Node/存储产生式 char head; /超能力存储这是个大问题，用到静态存储时，一定要给它分配足够的空间 char infomaxlen+1;/为什么在这里我只定义了9个，在底下它却具有存储11个的能力 Fl_PNode fl; Pr_PNode link;struct Jo_P_Node

10、;typedef struct Jo_P_Node *Jo_P_PNode;struct Jo_P_Node/存储产生式的结点 Jo_P_PNode link; short num; Pr_PNode next;struct LinkLead/产生式结点的头部 Jo_P_PNode knot;typedef struct LinkLead *PLinkLead;/*/*队列*struct Q_Node;typedef struct Q_Node *Q_PNode;struct Q_Node char info; Q_PNode link;struct LinkQueue Q_PNode f;

11、Q_PNode r;typedef struct LinkQueue *PLinkQueue;/*/*堆栈*struct S_Node;typedef struct S_Node *S_PNode;struct S_Node char info; S_PNode link;struct LinkStack S_PNode top;typedef struct LinkStack *PLinkStack;/*/*表格*struct T_Node;typedef struct T_Node *T_PNode;struct T_Node char row; char column; char inf

12、omaxlen; T_PNode down; T_PNode right;struct LinkTable T_PNode tab;typedef struct LinkTable *PLinkTable;/*bool judgeQueue_link(PLinkQueue plqu,char x)/判断字符x有无在队列plqu中 Q_PNode p; p = plqu-f; while(p) if(p-info = x) return true; p = p-link; return false;void push_link(PLinkStack plstack,char x)/进栈 S_PN

13、ode p; p = (S_PNode)malloc(sizeof(struct S_Node); if(p = NULL) printf(空间申请失败!n); else p-info = x; p-link = plstack-top; plstack-top = p; void push_str_link(PLinkStack plstack,char x)/将分析串x存入plstack堆栈中,要求从字符串的尾部开始进栈 short i = 0; S_PNode p; while(xi != 0) i+; while(-i) = 0) p = (S_PNode)malloc(sizeof(

14、struct S_Node); if(p = NULL) printf(空间申请失败!n); else p-info = xi; p-link = plstack-top; plstack-top = p; void print_result(PLinkTable pltable,PLinkStack plst1,PLinkStack plst2) short i=1,k,j; char smaxlen;/ S_PNode p1,p2; void pop_link(PLinkStack plstack); char top_link(PLinkStack plstack); void prin

15、tStackStr(short m,short n); void printConStack_link(PLinkStack plstack); void push_str_link(PLinkStack plstack,char x); printf(步骤 分析栈 );/); p2 = plst2-top; k = 0; while(p2) k+; p2 = p2-link; if(k10) printStackStr(10,k); printf(剩余输入串 推导所用产生式或匹配n); /C语言里允许使用函数名相同,但参数不同的两函数同时存在 while(plst1-top-link | t

16、op_link(plst1) != #) if(itop; j = 0; while(p1) j+; p1 = p1-link; printStackStr(j,12); printf( ); p2 = plst2-top; j = 0; while(p2) j+; p2 = p2-link; if(k10) printStackStr(j,k); else printStackStr(j,10); /插入若干空格（取个） printStack_link(plst2); printf( ); if(top_link(plst1) = top_link(plst2) printf(“%c”匹配,

17、top_link(plst1); pop_link(plst1); pop_link(plst2); else strcpy(s,findTable_link(pltable,top_link(plst1),top_link(plst2); if(s0 = 0) printf(nn有错n); printf(剩余输入串“); printStack_link(plst2); printf(”用此产生式组无法推出nn); return; else if(!strcmp(s,)/注意在这边不能用s0 = 来作为判断条件 printf(%c%c%c%c%c,top_link(plst1),161,250

18、,166,197); /： ： pop_link(plst1); else printf(%c%s,top_link(plst1),s); pop_link(plst1); push_str_link(plst1,s); printf(n); i+; if(top_link(plst1) = #) if(i10) printStackStr(1,k); else printf( ); printf(# 接受nn); else printf(nn在推导过程中出现问题nn); void main() while(true) scanf(%s,s_t); getchar(); t = 0; whil

19、e(s_tt != 0) /判断数组s_t里有无非法字符 if(!judgeQueue_link(plqu2,s_tt) printf(对不起,你所输入的符号串中不能由之前的文件里的文法得出n); break; t+; if(t != 0 & s_tt = 0) break; printf(nn请另输入一个待分析的字符串:n); if(s_tt-1 != #) printf( 你输入的分析字符串没有以“#”作为结束标志；n系统自动在分析字符串后加上“#”nn); push_link(plstack2,#); /将分析串存入plstack2堆栈中 push_str_link(plstack2,s

20、_t); print_result(pltable,plstack1,plstack2); 该程序是在以下编写的，里面没有用到C+的知识，纯C编写的代码.在运行之前，先将要分析的文法写入一个文本文档*.txt里，如：SAABDDiBDDBCEE+CEEC)A*C(注意：只有这里用到两个符号与，其中在特殊符号里、在希腊字母里，此处将上面这样的产生式组存放在eq.txt这个文本文档里作为示例。下面显示语法分析进行个步骤。读入ll(1)文法开始运行后，根据提示输入文件名“”后按Enter键继续，显示如下:优化ll(1)文法按任意键继续，显示如下：找出各终结符的First和Follow集按任意键继续，显示如下：3.2.4找出各产生式的Select集按任意键继续，显示如下：3.2.5填写分析表按任意键继续，显示如下：3.2.6语法分析按提示，输入待分析的句子，按Enter键继续，显示如下：3.2.7完成 按提示，输入y，分析下一条句子；或者输入n，结束，分别显示如下：4总结与感想因为要考试的原因，所有想尽快把这个课程设计做完，可是越急越容易出错，做起来很不顺手，特别是编程的时候，虽然借鉴了几篇类似的试验或课程设计，但完成这一设计仍不是一件简单的事情。在设计过程中主要遇到以下两个问题：1数据结构问题。在此程序中，用到队列，堆栈等形式的数据结构，各节点链接复杂