编译课程设计报告

1、编译原理课程设计LL(1)文法判定 -c语言实现专业班号_计算机021_学生姓名_3122020130_指导教师_齐林海_2006年 3 月 6 日目 录第一章前言11.1 LL(1)文法概述11.2 设计思想概述1第二章语言文法规则12.1 语言的词法规则12.2 语言的语法规则2第三章程序设计23.1 词法分析程序的实现23.1.1 文法输入规则23.1.2 数据结构23.1.3 程序流程43.2 求解FIRST集、FOLLOW集和SELECT集的实现53.2.1 求出能推出的非终结符53.2.2 求解产生式的右部的FIRST集63.2.3 求解非终结符的FOLLOW集73.2.4 求解产

2、生式的SELECT集73.3 判定是否是LL(1)文法的实现73.4 预测分析表的生成实现73.5 判定给定符号串是否是文法中的句子的实现8第四章系统运行及测试94.1 运行和安装环境94.2 系统运行94.2 系统测试94.2.1 测试一94.2.2 测试二10第五章结论115.1 系统结论115.2 存在的不足12参考文献12附录13源程序13第一章 前 言本设计使用C语言实现了对简单方法描述的LL(1)文法的判定。该设计程序实现了：分别求出每一产生式的右部的FIRST 集、每一个非终结符的FOLLOW集和每一产生式的SELECT集；判定是否是LL(1)文法；画出预测分析表；对给定的符号串

3、判定是否是文法中的句子，分析过程用计算机打印出来。1.1 LL(1)文法概述LL(1)文法是一种2型文法，由它所描述的语言可以使用自顶向下语法分析方法进行语法分析。LL(1)文法的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第二个L表明分析过程中将用最左推导，1表明只需向右看一个符号便可决定如何推导即选择哪一个产生式（规则）进行推导。一个上下文无关文法（即2型文法）是LL（1）文法的充分必要条件是，对每个非终结符A的两个不同产生式，A，A，满足SELECT（A）SELECT（A）= ø其中、不同时能1。1.2 设计思想概述首先对输入的文法进行词法分析，识别出所有的文法符号（

4、终结符和非终结符）并对其编码生成相应ID，同时用单链表型数据结构存储单个产生式，产生式的文法符号在单链表中以其相应ID表示，即所有的产生式以规定形式存储在一个单链表集中。第二步，针对单链表型数据结构，设计相应算法计算出每一个表达式右部的FIRST 集、每一非终结符的FOLLOW集和每一产生式的SELECT集，其结果均以单链表集的形式存储。最后，由求出的SELECT集经由相应算法判定出该输入文法是否为LL(1)文法，若是，则在屏幕上输出预测分析表，并对给定的符号串判定是否是文法中的句子，分析过程用计算机打印出来。第二章 语言文法规则2.1 语言的词法规则为简单起见，本设计规定非终结符集VN为所有

5、大写字母的集合，终结符集VT为所有小写字母、数字和四则运算符号的集合，取所有文法符号均为单个字符。2.2 语言的语法规则由2型文法的定义，定义如下：设G=（VN，VT，P，S），若P中的每一个产生式满足： 是一非终结符， (VNVT)*则此文法称为2型的或上下文无关的1。规定产生式的左部必须为非终结符。第三章 程序设计3.1 词法分析程序的实现3.1.1 文法输入规则源文法的输入采用文件输入的方式，每读入一个字符就进行文法符号的判定、记录和编码，同时对产生式以特定格式存储。文件中源产生式的书写格式规定如下：格式为“左部>右部”，左部为一非终结符，右部的文法符号之间不允许有空格，右部结束后

6、直接回车或文件结束，规定文件的第一个字符为文法的开始符号；格式中使用“>”而非“->”的原因在于简化词法分析，可以避免在读入字符“-”时的分情况处理（因为“-”也是一个终结符）。举例如下：/*file:e:demo1.dat参考文献1例5.5*/S>ABS>bCA>&A>bB>&B>aDC>ADC>bD>aSD>c3.1.2 数据结构对非终结符和终结符分别采用以下的数据结构存储：typedef struct Vn_struunsigned int ID;char Nch;unsigned int ifget

7、null;Vn_type;Vn_type Vn100;int Vn_ID_next;以上为非终结符的存储结构，对非终结符采用结构体数组存储。结构体中ID存储非终结符的编码（关于编码，程序中规定非终结符的编码从200开始，第一个被“发现”的非终结符被编码为200，按照被“发现”顺序依次编码为201,202,程序最多允许100个非终结符，即编码范围在200299之间。对于终结符，采用同样的规则对其编码，编码范围在300399之间），Nch存储其字符，ifgetnull指示该终结符能否推出，用于对三个集合的求解过程中。Vn存储所有的非终结符。Vn_ID_next指示下一个可用的非终结符的编码值，初始

8、为200。typedef struct Vt_struunsigned int ID;char Tch;Vt_type;Vt_type Vt100;int Vt_ID_next;以上为终结符的存储结构，在结构体中，ID存储其编码，Tch存储其字符。所有终结符存储在Vt中。Vt_ID_next提示下一个可用的终结符的编码值。需要指出的是，出于降低程序复杂度的考虑，（程序中以&指代）和#均被以终结符的身份处理。如前所述，分析所得的文法存储在单链表集中。链表的结点结构如下：typedef struct IDNodeunsigned int ID;struct IDNode *next;IDN

9、ode;结点中存储文法符号的编码和指向下一结点的指针。单链表集用IDNode*指针数组表示，即：IDNode *ppro100;词法分析的结果，即第i个产生式转存为单链表的规则如下：左部作为第一个结点，该结点的地址存储在pproi中，即第i个产生式的首结点地址存储在ppro的第i个元素中,右部第一个符号作为第二个结点，向右依次将右部所有文法符号对应的结点加入到单链表的尾部。例如：S>ABS>bC存储方法为如图3-1所示ppro0ppro1ppro2200201202 NULL200300300 NULL 100 101 102 100 200 103 图3-1（假定S、A、B、C、

10、b的编码分别为100、101、102、103、200）3.1.3 程序流程词法分析由函数File_Input (FILE *fp)实现，具体实现见附录源程序。以下是程序的流程图：否从文件中读入一个字符否否是检查Vn中是否存在此符号,若无,填之是准备在pproi+1中填入结点若字符不是>判定为终结符检查Vt中是否存在此符号,若无,填之在pproi中填入代表该字符的结点读入下一个字符是结束是否为非终结符是否为EOF文件结束符是否为回车换行图3-23.2 求解FIRST集、FOLLOW集和SELECT集的实现存储FIRST集、FOLLOW集和SELECT集的数据结构采用如图3-1的单链表集，分

11、别命名为FirstRight、Follow和Select，在这里，每个结点的ID必然大于等于300，因为这些集合的元素都必然是终结符。每个单链表中的结点将按其ID的大小顺序由小到大排列。需要指出的是，对三个集合的求解在算法上是对单链表集ppro进行若干种链表操作的组合，故具体过程（分别由getFirstVn()、getFirstRight()、etFollow()和getSelect()实现）不再给出，下面给出的是逻辑算法。3.2.1 求出能推出的非终结符算法如下：1) 将结构体数组Vn中对应每一非终结符的能否推出的标记ifgetnull（如前所述，ifgetnull为结构体变量Vn_type

12、的成员变量，见3.1.2）置初值“未定”即2。2) 扫描方法中的产生式（程序中的扫描对象为ppro的拷贝pprotemp）。a) 删除所有右部含有终结符的产生式，若这使得以某一非终结符为左部的所有产生式都被删除，则将数组中对应该非终结符的标记值改为“否”，说明该非终结符不能推出。（在程序中的操作为：删除含有ID大于或等于300的结点的单链表，若这使得表示某一非终结符为左部的产生式的所有单链表都被删除，则将Vn中对应的ifgetfull置为0）b) 若某一非终结符的某一产生式右部为,则将数组中对应该非终结符的标志置为“是”，并从文法中删除该非终结符的所有产生式。（程序中的操作为：删除含有对应的I

13、D的结点的单链表，置该单链表的第一个结点所表示的非终结符对应的Vn中元素的ifgetnull为1，并从pprotemp删除所有以该非终结符对应的结点为第一结点的单链表。）3) 扫描产生式右部的每一符号a) 若所扫描到的非终结符号在数组中对应的标志是“是”，则删去该非终结符，若这使产生式右部为空，则对产生式左部的非终结符在数组中对应的标志改为“是”，并删除该非终结符为左部的所有产生式。（程序中的操作为：若所扫描到的结点所表示的非终结符号的ifgetnull被标记为1,则删去该结点，若这使该单链表只剩一个结点，则标记该产生式左部的非终结符的ifgetnull为1，并删除pprotemp中所有以该非

14、终结符对应的结点为第一结点的单链表）b) 若所扫描到的非终结符号在数组中对应的标志是“否”，则删去该产生式，若这使产生式左部非终结符的有关产生式都被删去，则把在数组中该非终结符对应的标志改为“否”。（程序中的操作为：删除含有对应的ifgetnull=0的结点的单链表，若这使表示产生式左部非终结符的有关产生式的单链表都被删去，则把左部非终结符对应的ifgetnull置为0。）4) 重复3），直到扫描完一遍文法的产生式，数组中非终结符对应的特征再没有改变为止。（程序中设置了标志变量ifVnChanged用以标识非终结符对应的特征有没有改变。）1该过程由函数getNULLVn()实现，由于对存储文法

15、的链表有删除操作，为保护数据，函数开始时先从ppro拷贝了一个临时单链表集pprotemp,所有删除操作均在后者中进行，并在程序结束时释放了pprotemp的地址空间。函数的结果存储在Vn中。3.2.2 求解产生式的右部的FIRST集首先，计算每个文法符号的FIRST集。由定义：FIRST（）=a|a,aVT，a、V*，若，则规定FIRST（）对每一文法符号XV计算FIRST（X）。a) 若XVT，则FIRST（X）=Xb) 若XVN，且有产生式Xa，aVT则aFIRST（X）c) 若XVN，X，则FIRST（X）d) 若XVN，Y1，Y2，Yi都VN，而有产生式XY1Y2Yn。当Y1，Y2，

16、Yi-1都时，（其中1in），则FIRST（Y1）-，FIRST（Y2）-，FIRST（Yi-1）-，FIRST（Yi）都包含在FIRST（X）中。e) 当d)中所有Yi ，（i=1，2，n）则FIRST（X）=FIRST（Y1）FIRST（Y2）FIRST（Yn）。反复使用上述(b)(e)步直到每个符号的FIRST集合不再增大为止。求出每个文法符号的FIRST集合后也就不难求出一个符号串的FIRST集合。若符号串V*，=X1X2Xn，当X1不能，则置FIRST（）=FIRST（X1）。若对任何j(1ji-1,2in)，FIRST（Xj）则FIRST（）=（FIRST（Xj）-）FIRST（X

17、i）当所有FIRST（Xj）(1jn)都含有时，则FIRST（）=（FIRST（Xj）1。由此算法可计算出各文法符号的FIRST集和各产生式的右部的FIRST集，分别存储在FirstVn和FirstRight中。定义如下：/*LL(1).h*/IDNode *FirstVn100; IDNode *FirstRight100;该过程分别由函数getFirstVn()和getFirstRight()实现，两者又调用了两个链表操作函数insert2link()和add2link()以及一个辅助函数getFirstExp()来实现具体功能，后三都的功能分别为插入结点到单链表、拷贝单链表到另一单链表、

18、得到任意字符串的FIRST集。详见附录源程序。3.2.3 求解非终结符的FOLLOW集算法如下：对文法中每一AVN计算FOLLOW(A)a) 设S为文法中开始符号，把#加入FOLLOW（S）中。b) 若AB是一个产生式，则把FIRST（）的非空元素加入FOLLOW（B）中。如果则把FOLLOW（A）也加入FOLLOW（B）中。c) 反复使用（b）直到每个非终结符的FOLLOW集不再增大为止1。由此算法可计算出非终结符号的FOLLOW集，存储在Follow中。定义如下：/*LL(1).h*/IDNode *Follow100;该过程由函数getFollow()实现。函数中调用getFirstEx

19、p()取得“FIRST（）的非空元素”；调用add2link()“把FOLLOW（A）也加入FOLLOW（B）中”。详见附录源程序。3.2.4 求解产生式的SELECT集计算SELECT集的算法如下：对于任一产生式，若其左部的非终结符号不能推出，则其SELECT集等于右部的FIRST集；反之，SELECT集等于右部的FIRST集的非空元素与左部的非终结符的FOLLOW集的所有元素组成的集合。该过程由函数getSelect()实现。计算出的表达式的SELECT集存储在Select中。定义如下：/*LL(1).h*/IDNode *Select100;3.3 判定是否是LL(1)文法的实现如“1.

20、1 LL(1)文法概述”中所述，一个上下文无关文法是否是LL(1)文法关键在于每个非终结符的两个不同产生式的SELECT集是否存在交集，若存在则不是LL(1)文法，反之则可以判定该输入文法是LL(1)文法。该过程由函数judgeLL1()实现。3.4 预测分析表的生成实现预测分析表可用一个矩阵M(或称二维数组)表示。矩阵的元素MA,a中的下标A表示非终结符,a为终结符或句子括号“#”,矩阵元素MA,a中的内容为一条关于A的产生式,表明当用非终结符A向下推导时,面临输入符a时,所应采取的候选产生式,当元素内容无产生式时,则表明用A为左部向下推导时遇到了不该出现的符号,因此元素内容为转身出错处理的

21、信息1。算法如下：对每个终结符或“#”号用a表示。aSELECT(A),则把的头指针放入MA,a中。把无定义的MA,a置为NULL空指针。该过程由函数getpa_table()实现，该函数以Select为输入数据，计算所得分析表存储在结构体pa_table的变量中。pa_table的定义如下：/*LL(1).h*/typedef struct pa_tableIDNode *ptb;int *row_info,*col_info;int row_num,col_num;pa_table;3.5 判定给定符号串是否是文法中的句子的实现预测分析程序的工作过程用示意图3-3表示图3-3 第四章 系统

22、运行及测试4.1 运行和安装环境Windows XP Professional + Turbo C2.04.2 系统运行a) 首先将所需判定的文法按“3.1.1 文法输入规则”中的要求写入自定义的文件中，该文件称作文法文件。b) 运行程序LL1.exe,按照屏幕提示，输入文法文件的路径和文件名。c) 程序将一步步进行LL(1)文法的判定。d) 若判定为LL(1)文法，则输出预测分析表，并提示输入符号串进行语法分析。4.2 系统测试4.2.1 测试一测试文法一的测试数据如下:S->ABS->bCA->A->bB->B->aDC->ADC->bD-&

23、gt;aSD->c图4-1、图4-2、图4-3分别是程序计算FIRST集、FOLLOW集和SELECT集的运行截图（符号“由“&”代替）。图4-1图4-2 图4-3图4-4是程序根据得到的SELECT集判定输入文法是否为LL(1)文法的运行截图。图4-4如图4-4所示，经程序判定，该输入文法不是LL(1)文法。4.2.2 测试二测试文法二的测试数据如下:E->TDD->+TDD->T->FSS->*FSS->F->iF->(E)图4-5、图4-6、图4-7分别是程序计算FIRST集、FOLLOW集和SELECT集的运行截图（符号“由

24、“&”代替）。图4-5图4-6图4-7图4-8是程序根据得到的SELECT集判定输入文法是否为LL(1)文法的运行截图。图4-8如图4-8所示，经程序判定，该输入文法是LL(1)文法。根据屏幕提示，输入符号串i+i*i#，由程序判定是否是文法中的句子，分析过程在打印在屏幕上，如图4-9所示。图4-9如图中最后一行所示， i+i*i#是该文法的句子。测试完毕。第五章 结 论5.1 系统结论本设计用C语言成功实现了对LL(1)文法的判定，达到了课程设计题目中的所有要求，并且操作简单、易上手，输出结果清晰明了，可以作为编译原理初学者的学习工具，也可以作为编译原理课上的演示程序。本设计的设计亮

25、点在于使用单链表集存储关键数据，实现了判定过程的高效率；同时针对链表操作的复杂和易出错的特点，设计者设计出了几个基本却功能强大的链表操作函数，如insert2link()、add2link()，提供给各主要函数调用。这样的做法，既提高的程序的开发效率和运行效率，又增强了程序运行的稳定性，此外，还大大提高了程序的可重用性。除了高标准的完成了设计要求，在这次课程设计中，设计者对编程技术也有了更进一步的理解和体会，并借此机会大大提高了对C语言的驾驭能力，可谓受益匪浅。希望以后能有更多的机会得以锻炼和施展才能。5.2 存在的不足当然，由于能力所限，本设计也有一些不足：其一，没有实现实时输入文法，只采用

26、了文件输入；其二，对于文法的要求过于苛刻，文法符号只能由一位字符构成；其三，程序中过多地采用了全局变量，模块化的程度太低；其四，程序几乎处理错误能力很低，遇非规则输入则死机。总的来说，虽然这些不足不影响程序对LL(1)文法判定的演示和教学效果，但是其判定功能却因为这些不足而被大大削弱。有时间的话，设计者会对该程序做进一步的改进。参考文献1 吕映芝,张素琴,蒋维杜.编译原理.第1版.北京:清华大学出版社,1998附 录源程序#include "stdlib.h"#include "stdio.h"#include <string.h> #inc

27、lude "e:ll1.h"#include "dir.h"/*#define DEBUG*/void initiate()int i;Line_Num = -1;/*special used in input*/Vn_ID_next = 100; /*Vn 100.199*/Vt_ID_next = 200; /*Vt 200.299*/for (i=0;i<100;i+)pproi=NULL;Vni.ifgetnull = UNCERTAIN;FirstVni = NULL;FirstRighti = NULL;Followi = NULL;S

28、electi = NULL;int getVnID(char ch)/*get the ID of Vn according to itselt*/int i=0;for (;i<Vn_ID_next-100;i+)if (Vni.Nch=ch) return Vni.ID;return 0;int getVtID(char ch)/*get the ID of Vt according to itselt*/int i=0;for (;i<Vt_ID_next-200;i+)if (Vti.Tch=ch) return Vti.ID;return 0;int getID(char

29、 ch)/*get the ID of V*/int i;i = getVnID(ch);if(i=0) i = getVtID(ch);return i;int SeekoverVn(char ch) /*scan vn, if ch in,then return its id,else return Vn_ID_next*/int i=0,r = Vn_ID_next;for (;i<Vn_ID_next-100;i+)if (ch = Vni.Nch)r = Vni.ID;break;return r;int SeekoverVt(char ch) /*scan vt, if ch

30、 in,then return its id,else return Vt_ID_next*/int i=0,r = Vt_ID_next;for (;i<Vt_ID_next-100;i+)if (ch = Vti.Tch)r = Vti.ID;break;return r;Status File_Input (FILE *fp) /*read file fp points to, get all fags,and transform the oriental words to the form that the syntax analyser can read which is st

31、ored in ppro*/char ch;int idcurrent;int ifavailable;/*notes whether to be transformed*/IDNode *pnewnode = NULL; /*pointer to the last node*/IDNode *pt;/*temp pointer*/Line_Num = -1;ch = fgetc(fp);while (ch != EOF)ifavailable = 0;/*to get ready*/if (ch='|')/*for example S->AB|bC,'|'

32、; means a new expression*/ifavailable = 1;/*notes to be transformed*/idcurrent = pproLine_Num->ID;/*left part*/pnewnode = NULL;/*a new expression*/elseif (ch>='A') && (ch<='Z')idcurrent = SeekoverVn(ch); /*get the id of ch*/if (idcurrent=Vn_ID_next)VnVn_ID_next-100.I

33、D = Vn_ID_next;/*add it in Vn*/VnVn_ID_next-100.Nch = ch;Vn_ID_next+;ifavailable = 1;/*notes to be transformed*/elseif (ch='n')/*carriage return*/pnewnode = NULL;elseif(ch!='>') idcurrent = SeekoverVt(ch); /*get the id of ch*/if (idcurrent = Vt_ID_next)VtVt_ID_next-200.ID = Vt_ID_

34、next;/*add it in Vt*/VtVt_ID_next-200.Tch = ch;Vt_ID_next+;ifavailable = 1;if (ifavailable)/*to be transformed*/pt = CreateNewIDNode;pt->ID= idcurrent; pt->next= NULL;if (pnewnode = NULL) /*notes CR*/Line_Num+;pproLine_Num = pnewnode = pt;else pnewnode->next = pt;pnewnode = pt;ch = fgetc(fp

35、);return OK;Status File_Print (FILE *fp) /*print the file onto the screen*/char ch;printf("File Content: (Press any key to continue.)n");getch();ch = fgetc(fp);while (ch!= EOF)printf("%c",ch);ch = fgetc(fp);printf("nPress any key to continue.n");getch();#ifdef DEBUGvoid

36、 debugprint()int i;IDNode *pt;for (i=0;i<Vn_ID_next-100;i+) printf (" %c ",Vni.Nch);printf ("n");for (i=0;i<Vn_ID_next-100;i+) printf ("%d ",Vni.ID);printf("n");for (i=0;i<Vt_ID_next-200;i+) printf (" %c ",Vti.Tch);printf("n");for

37、(i=0;i<Vt_ID_next-200;i+) printf ("%d ",Vti.ID);printf("n");for(i=0;i<=Line_Num;i+)pt = pproi;printf("%d.",i);while(pt)printf("%d-",pt->ID);pt=pt->next;printf("ENDn");#endifint insert2link(IDNode *pdes,IDNode *pNode,int iffreeit)/*insert

38、pNode to *pdes,with the order small to large*/*no same 2, if can't insert,according to iffreeit,free pNode or not, and return 0,else return 1*/IDNode *ptd1,*ptd2,*pt=pNode;int cID;if(!iffreeit) /*if iffreeit=0,it means this node is in another link,i can't change it,so copy a new one*/pt = Cr

39、eateNewIDNode;pt->ID=pNode->ID;pt->next = NULL;/*to avoid error*/if(*pdes = NULL)/*insert directly*/*pdes = pt;return 1;elseif(pt->ID<=(*pdes)->ID)/*at the head*/if(pt->ID!=(*pdes)->ID)pt->next = *pdes;*pdes = pt;return 1;elseif(iffreeit) free(pt);return 0;elseptd1 = *pdes

40、; ptd2 = ptd1->next;if(ptd2) cID = ptd2->ID;else cID = -1; /*if at the tail*/while(ptd2&&(pt->ID>cID)ptd1 = ptd2; ptd2 = ptd2->next;if(ptd2) cID = ptd2->ID;else cID = -1;if(pt->ID!=cID)pt->next = ptd2; ptd1->next = pt;return 1;else if(iffreeit) free(pt);return 0;in

41、t add2link(IDNode *pdes,IDNode *psrc,int ifdelsrc,int ifcopyNULL)/*the return value notes if the *pdes is changed*/int mark=0,NULLID=getVtID('&');/*return value*/IDNode *ps = psrc,*pt;while(ps)if(ifcopyNULL|(ps->ID!=NULLID)/*about '&'*/if(ifdelsrc) pt=ps;else pt = CreateNe

42、wIDNode;pt->ID = ps->ID;ps = ps->next;pt->next=NULL;mark=insert2link(pdes,pt,1)|mark;/*make sure mark is in the right*/else ps = ps->next;return mark;void DeleteLink(IDNode *p)/*delete the link that p points to*/IDNode *pt;while(p)pt=p;p = p->next;free(pt);void DeleteAllVnExp(IDNod

43、e *pprotemp,int VnID)/*delet all Vn's expression*/IDNode *pt;int i;for(i=0;i<=Line_Num;i+)pt=*(pprotemp+i);if(pt&&(pt->ID=VnID)DeleteLink(pt);*(pprotemp+i)=NULL;void PrintLink(IDNode *pt,char ins)/*print Link,use ins to divide each character,if ins=0,the result will be consistant*/

44、int num;char ch;while(pt)num = pt->ID;if(num>=200) ch = Vtnum-200.Tch;else ch = Vnnum-100.Nch;printf("%c",ch);if(ins&&pt->next) printf("%c",ins);pt = pt->next;int CheckVnNoExist(IDNode *pprotemp,int VnID)/*check whether Vn's expression exists.if no,mark it

45、 NO*/IDNode *pt;int i;for(i=0;i<=Line_Num;i+)pt=*(pprotemp+i);if(pt&&(pt->ID=VnID)return 0;return 1;IDNode* getFirstExp(IDNode *pExp,int *ifgetnull)/*get First set of one expression that pExp points to,with no '&' in the return link*/*ifgetnull returns whether the exp can =

46、> &*/IDNode *phead=NULL;/*point to the new created link*/IDNode *pt;while(1)if(!pExp)/*get to the tail*/*ifgetnull = 1;return phead;elseif(pExp->ID>=200)pt = CreateNewIDNode;pt->ID = pExp->ID;pt->next = NULL;insert2link(&phead,pt,1);*ifgetnull=0;if (pExp->ID=getVtID('

47、;&') *ifgetnull = 1;/*in case that S->&*/return phead;else/*Vn*/add2link(&phead,FirstVnpExp->ID-100,0,0);if(VnpExp->ID-100.ifgetnull)pExp = pExp->next;else*ifgetnull = 0;return phead;/*while*/int ifCross(IDNode *p1,IDNode *p2)/*judge if p1 p2 has the same node,if has then

48、 print out in the form of .,.,.*/IDNode *pt1=p1,*pt2=p2;int ID1,ID2,mark=0,r=0;/*mark notes if it's the first same character,used to control if print out ','*/while(pt1)ID1 = pt1->ID;while(pt2)ID2 = pt2->ID;if(ID1=ID2) if(mark) printf(",");/*if not the first, print ',

49、'*/else printf("");printf("%c",VtID1-200.Tch);mark = 1;r = r|1;/*r stores the result*/pt2 = pt2->next;pt1 = pt1->next;if(r) printf("");/*if not LL(1),print the remaining ''*/return r;void getNULLVn()/*to decide the Vn that can deduct,the result is stor

50、ed in Vn &*/int i,j,LeftID;IDNode *pprotemp=(IDNode*)malloc(sizeof(IDNode*)*(Line_Num+1);IDNode *pt1,*pt2;/*temp pointers*/int ifVnChanged; /*mark whether the ifgetnull changes in stage 3*/char ch; /*for printing*/for(i=0;i<=Line_Num;i+)*(pprotemp+i)=NULL;/*Copy PProArray*/for(i=0;i<=Line_

51、Num;i+)pt1=pproi;*(pprotemp+i) = pt2 = CreateNewIDNode;pt2->ID = pt1->ID;pt2->next = NULL;while(pt1->next!=NULL)pt1 = pt1->next;pt2->next = CreateNewIDNode;pt2 = pt2->next;pt2->ID = pt1->ID;pt2->next = NULL;/*#ifdef DEBUGfor(i=0;i<=Line_Num;i+)pt1 = pprotempi;printf(

52、"%d.",i);while(pt1)printf("%d-",pt1->ID);pt1=pt1->next;printf("ENDn");#endif*/*The second stage*/for(i=0;i<=Line_Num;i+)pt1 = *(pprotemp+i);if(pt1) /*in case that this link was deleted*/LeftID = pt1->ID;pt2 = pt1->next; /*point to the right part*/if(pt2-&

53、gt;ID = getVtID('&')VnLeftID-100.ifgetnull = YES;DeleteAllVnExp(pprotemp,LeftID);/*delet all Vn's expression*/elsewhile(pt2)if(pt2->ID >= 200) /*Vt*/DeleteLink(pt1); /*Free all nodes*/*(pprotemp+i)=NULL;if (CheckVnNoExist(pprotemp,LeftID) /*check whether Vn's expression exists if no,mark it NO*/VnLeftID-100.ifgetnull=NO;break;/*stop while*/pt2 = pt2->next;/*#ifdef DEBUGfor(j=0;j<=Line_Num;j+)pt1 = pprotempj;printf("%d.",