编译原理实验指导书最终

1、编译方法实验指导书柴本成 赵晨 编写浙江万里学院2010.01目 录实验一 有限自动机的构造与实现1实验二 词法分析器的设计3实验三 语法分析递归下降分析器5实验四 LL(1)文法预测分析表的实现6附 录9附录一 实验结果的提交与检查9附录二 实验报告参考格式9附录三 Visual C+上机环境简介10附录四 参考程序13实验一 有限自动机的构造与实现一、 实验目的1、 正确理解正规式和正规集以及有限自动机的定义；2、 熟练掌握用状态转换图表示有限自动机的方法。二、 实验预习提示1、 正规表达式就是一种形式化的表示法，它可以表示单词符号的结构，从而精确地定义单词符号集。正规表达式简称为正规式，

2、它表示的集合即为正规集。2、 状态转换图是一张当输入不同内容时选择不同分析路径的有向图。一个状态转换图可用于识别一定的字符串。3、 有限自动机（FA）是更一般化的状态转换图，可用来识别正规集；分为DFA和NFA两种。三、 实验内容构造识别如下字符串的状态转换图，并将其编程实现。1、 识别标识符(以字母开始由字母和数字构成的字符串，要求长度不超过10)；参考程序：#include <iostream.h>#include <string.h>/字符串处理的头文件/判断一个字符是不是字母bool Isletter(char ch)if(ch>='a'

3、&& ch<='z' | ch>='A' && ch<='Z')return true;return false;/判断一个字符是不是数字bool IsDigit(char ch)if(ch>='0' && ch<='9')return true;return false;/判断一个字符串是不是标识符bool IsId(char *str)if(!Isletter(str0)return false;int l=strlen(str);/

4、计算字符串的长度for(int i=1;i<l;i+)if(Isletter(stri) | IsDigit(stri)continue;/如果是字母或数字就继续循环elsereturn false;/否则，返回不是字符串return true;void main()char *str="1abc"/初始化字符串，也可键盘输入if(IsId(str)cout<<"accept!"<<endl;else cout<<" not accept!"<<endl;2、 识别实数(要求正负号

5、可有可无，长度不超过20，不要求识别用科学记数法表示的实数)。3、 （选做）识别实数（包含科学计数法）。四、 实验要求1、 编程语言可用C/C+中任意一种；2、 自行设计测试数据对程序进行测试，对输入的字符串（以#作为结束符）如果能识别，则显示“接受”，否则，显示“不接受”；3、 书写实验报告；实验报告的格式可参见附录实验报告参考格式。实验二 词法分析器的设计一、 实验目的通过设计编制调试一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、

6、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）二、实验预习提示1. 词法分析器的功能和输出格式词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示成以下的二元式(单词种别码，单词符号的属性值)。本实验中，采用的是一类符号一种别码的方式。2. 单词的BNF表示<标识符>-> <字母><字母数字串><字母数字串>-><字母><字母数字串>|<数字><字母数字串>|<下划线

7、><字母数字串>|<无符号整数>-> <数字><数字串><数字串>-> <数字><数字串> |<加法运算符>-> +<减法运算符>-> -<大于关系运算符>-> ><大于等于关系运算符>-> >=3. “超前搜索”方法词法分析时，常常会用到超前搜索方法。如当前待分析字符串为“a>+”,当前字符为>，此时，分析器到底是将其分析为大于关系运算符还是大于等于关系运算符呢？显然，只有知道下一个字符是什么才能

8、下结论。于是分析器读入下一个字符+，这时可知应将>解释为大于运算符。但此时，超前读了一个字符+，所以要回退一个字符，词法分析器才能正常运行。在分析标识符，无符号整数等时也有类似情况。三、实验过程和指导 （一）准备：1. 阅读课本有关章节，花一周时间明确语言的语法，写出基本保留字、标识符、常数、运算符、分隔符和程序例。2. 初步编制好程序。3. 准备好多组测试数据。（二）上课上机：将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。（2，”main”）（5，”（“）（5，”）“）（5，”“）（1，”int”）（2，”a”）（5，”,”）（2，”b”）（5，”;”）（2，”a”

9、）（4，”=”）（3，”10”）（5，”;”）（2，”b”）（4，”=”）（2，”a”）（4，”+”）（3，”20”）（5，”;”）（5，”“）（三）程序要求：程序输入/输出示例：如源程序为C语言。输入如下一段：main()int a,b;a = 10; b = a + 20;要求输出如右图。具体要求如下：1. 识别保留字：if、int、for、while、do、return、break、continue等2. 其他的都识别为标识符；3. 常数为无符号整形数；4. 运算符包括：+、-、*、/、=、>、<、>=、<=、!=5. 分隔符包括：,、;、(、)（四）程序思路（仅

10、供参考）：1. 定义部分：定义常量、变量、数据结构。2. 初始化：从文件将源程序全部输入到字符缓冲区中。3. 取单词前：去掉多余空白。4. 取单词后：去掉多余空白（可选，看着办）。5. 取单词：利用实验一的成果读出单词的每一个字符，组成单词，分析类型。（关键是如何判断取单词结束？取到的单词是什么类型的单词？）6. 显示结果。（五）练习该实验的目的和思路：程序开始变得复杂起来，可能是大家以前编过的程序中最复杂的，但相对于以后的程序来说还是简单的。因此要认真把握这个过渡期的练习。程序规模大概为200行。本实验和以后的实验相关。通过练习，掌握对字符进行灵活处理的方法。（六）为了能设计好程序，注意以下

11、事情：1. 模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。2. 写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。3. 编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。三、上交：1. 程序源代码（通过网络提交），详细提交方式见附录。2. 已经测试通过的测试数据3组（全部存在一个文本文件中通过网络提交，以“第一组输入/输出/第二组输入/输出/第三组输入/输出”的顺序存放）；3. 实验报告：参考格式见附录实验三 语法分析递归下降分析器一、 实验目的通过完成语法分析递归下降分析器的程序，了解语法分析之一递归下降分析法的过程和作用。为每个非终结符设计一

12、个识别的子程序，寻找该非终结符也就是调用相应的子程序。由于单词在语法分析中作为一个整体，故在语法识别中仅使用其内码。在这里将词法分析作为语法分析的一个子程序，当语法分析需要单词时，就调用相应的词法分析程序获得一个单词。语法分析的作用是识别输入符号串是否是文法上定义的句子，即判断输入符号串是否是满足“程序”定义的要求。也就是当语法识别程序从正常退出表示输入符号串是正确的“程序”；若从出错退出，则输入符号串不是正确的“程序”。出错时，可以根据读字符的位置判断出错的位置。二、实验预习提示在不含左递归和每个非终结符的所有候选终结首符集都两两不相交的条件下，通过构造一个不带回溯的自上而下的分析程序，这个

13、分析程序是由一组递归过程（或函数）组成，每个过程（或函数）对应文法的一个非终结符。对于文法：三、实验内容设计对应该文法的递归下降分析器（参考教材P46的代码），并将递归函数的调用栈的形式模拟来分析输入串 的语法分析过程；在此，“”为输入串的分隔符。进行语法分析时，首先将“”和文法开始符号E压入栈终，当语法分析进行到栈中仅剩“”而输入串扫描指针已指向输入串尾部的“”时，则语法分析成功，分析过程参见教材图312所示。实验四 LL(1)文法预测分析表的实现一、实验目的 通过本次实验，使学生对自顶向下语法分析的基本概念、基本原理、基本方法等充分理解并掌握预测分析方法。二、实验主要内容 1. 给定无左递

14、归和无回溯的文法，计算FIRST集合和FOLLOW集合，并构造出预测分析表。文法如下：（在这里用e来表示空串）E->TAA->+TAA->eT->FBB->*FBB->eF->(E)F->i2. 根据预测分析表，判断该文法是否为LL(1)文法。三、实验过程和指导对给定的无左递归和无回溯的上下文无关文法，按以下步骤执行：1. 构造First集合对文法中的每一个非终结符X构造FIRST(X)，其方法是连续使用下述规则，直到每个集合的FIRST不再增大为止。(注：对终结符a而言，FIRST(a)=a，因而无需构造。)1) 若有产生式Xa，且aVT ，则

15、把a加入到FIRST(X)中；若存在X，则将也加入到FIRST(X)中。2) 若有XY，且YVN，则将FIRST(Y)中的所有非元素(记为“”)都加入到FIRST(X)中；若有XY1Y2Yk，且Y1Yi1都是非终结符，而Y1Yi1的候选式都有存在，则把FIRST(Yj)的所有非元素都加入到FIRST(X)中(j=1,2,i)；特别是当Y1Yk均含有产生式时，应把也加到FIRST(X)中。2. 构造FOLLOW集合对文法GS的每个非终结符A构造FOLLOW(A)的方法是连续使用下述规则，直到每个FOLLOW不再增大为止。1) 对文法开始符号S，置#于FOLLOW(S)中(由语句括号“#S#”中的

16、S#得到)。2) 若有AB(可为空)，则将FIRST()加入到FOLLOW(B)中。3) 若有AB或AB，且(即FIRST()，则把FOLLOW(A)加到FOLLOW(B)中(此处的也可为空)。 3. 构造预测分析表M1) 对文法GS的每个产生式A执行以下2)、3)步。2) 对每个终结符aFIRST(A)，把A加入到MA,a中，其中为含有首字符a的候选式或为惟一的候选式。3) 若FIRST(A),则对任何属于FOLLOW(A)的终结符b，将A加入到MA,b中。4) 把所有无定义的MA,a标记为“出错”。 4. 判断该文法是否为LL(1)文法若预测分析表M无多重定义，则该文法为LL(1)文法；否

17、则，该文法不是LL(1)文法。四、实验提示1. 为了简化实验过程，我们这里假定要分析的文法都是无左递归的；即我们编程序时无需考虑文法是否左递归了。下面给出文法结构体和文法符号集合的程序定义#define MAX_GRAM_LEN 255/文法符号的最大长度#define MAX_ELE_NUM 40/文法符号的最大个数#define MAX_GRAM_ELE_NUM 300/所有文法符号的个数/-定义文法结构体 -typedef structchar mSetenceMAX_GRAM_LEN;grammerElement;grammerElement GrammerSetMAX_GRAM_EL

18、E_NUM;/定义文法符号的结构体typedef structint len;char eleMAX_ELE_NUM;simpleGroup;simpleGroup groupFirstMAX_ELE_NUM;/ First集simpleGroup groupFollowMAX_ELE_NUM;/ Follow集int grammerNum;/文法符号个数char VTSetMAX_ELE_NUM;/ 终结符char VNSetMAX_ELE_NUM;/ 非终结符int VNProduceZMAX_ELE_NUM;/ 产生式int vtSetLen;/终结符的个数int vnSetLen;/非

19、终结符的个数char startedSign;/开始符号2. 为了便于分析程序，在实验中要求把分析的文法保存在一个文本文件中，同时输出的结果也保存在一个文本文件中。3. 在附录中，我们给出了求First集的参考程序。大家可以参考该程序，并在此基础上写出求Follow集以及构造分析表的程序。附 录附录一 实验结果的提交与检查1. 提交实验结果每个实验的结果包括两项：实验报告和程序源代码。实验报告中请写明姓名、班号、学号、Email等个人信息，以便遇到问题时老师可以及时与你联系。实验报告的格式可参见实验报告参考格式，也可自行拟定报告的格式，但要求实验报告中至少包含如下内容：实验题目及内容，所用的状

20、态转换图，主要数据结构的设计，重要算法的流程，关键的代码段及注释，所用的测试数据及测试结果，以及实验中遇到的问题和解决方法。请把实验的结果放入一个目录中，并将上述所有的文件打包成rar文件，文件名为“自己的学号.rar”，例如“01001.zip”，通过ftp或Email提交。2. 检查方式与评分标准在大家提交实验后，我们将对提交的程序进行测试。评分的主要标准是实验报告以及程序输出与标准输出相符合的程度。附录二 实验报告参考格式以实验二（词法分析器的设计为例），实验报告格式如下：一、实验目的与任务编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运

21、算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）二、实验步骤1. 仔细阅读实验要求和书上的相关内容，写出基本保留字、标识符、常数、运算符、分隔符和要测试的程序例。（在这里写出基本保留字、标识符、常数、运算符、分隔符和要测试的程序实例）2. 程序的功能描述。（在这里描述你的程序的功能）3. 程序的模块描述。（在这里写出：重要的全局变量及其用途，主要函数的定义、功能、参数与返回值的含义）4. 关键程序代码（在这里写出：实验中关键的程序代码，不用把所有代码都写上）三、实验总结（可以从以下几个方面来总结：你在编程过程中花时多

22、少？时间是怎么分配的？多少时间在思考问题？遇到了哪些难题？你是怎么克服的？你对你的程序的评价？你的收获有哪些？）附录三 Visual C+上机环境简介上机实验环境亦可选择Microsoft Visual C+（以下简称VC）。VC是美国微软公司生产的基于其Windows系统的软件开发工具。它具有使用灵活，并与32位Windows内核（使用于Windows 2000/Windows XP）高度兼容的特点，从而被Windows程序员们广泛使用。同时，VC同样可以加工处理C语言程序，与标准的ANSI C语言兼容。VC提供了一种控制台操作方式，初学者使用它应该从这里开始。下面我们将对使用VC编写简单的

23、控制台程序作一个最初步的介绍。一、控制台程序简介Win32控制台程序(Win32 Console Application)是一类Windows程序，它不使用复杂的图形用户界面，程序与用户交互时通过一个标准的正文窗口，通过几个标准的输入输出流（I/O Streams）进行。它们分别是stdin（标准输入），stdout（标准输出）以及stderr（标准错误输出）。这些流都是ANSI C语言标准库提供的，通过printf()等函数可以访问这些流。一个最简单的控制台程序如下：/* hello.c */#include<stdio.h>/* 包含使用标准输入输出的头文件声明 */int m

24、ain()/* 主函数 */    printf(“Hello, World!n”);/* 向标准输出stdout输出一个字符串 */    return 0;/* 主函数返回 */该程序的运行结果如图3-4所示。  图3-4 控制台程序运行结果图中显示的黑色窗口称为控制台窗口，程序的输入、输出均在这个窗口中进行。二、使用VC编写控制台程序很简单，只需要按照下面几个步骤进行：1. 打开MSVC集成开发环境。双击桌面或“开始”菜单中的Microsoft Visual C+6.0，不久将看到VC的编辑窗口，如图3-5：图3-5

25、VC启动界面2. 选择菜单“File | New”,在弹出的对话框中 1) 单击上方的选项卡“File”，2) 选择“C+ Source File”， 3) 在“File name”一栏中填写文件名例如hello.c，4) 在“Location”一栏中填写你想把文件存放的位置（目录）。然后按“OK”。见图3-6。 注意： 第3）步中一定写明扩展名“.c”（不要用“.cpp”。那样VC将按C+的方式编译，C+与C有一些的不兼容性）； 第4）步中指定你自己的目录，不要使用系统的缺省目录或者随便放在根目录或者其他的目录下。 图3-6 应用程序向导主界面3. 在右侧的窗口中键入程序的内容，然后点击图标

26、存盘。进入VC编辑界面，如图3-7。图3-7 VC编辑界面4. 试编译。点击图标，或者选择菜单“Build | Build”（启动程序加工，这样系统将连续进行编译和连接操作。另一种更稳妥的方式是先做编译，检查无误后再做连接）。这时VC将弹出一个对话窗口，说明这个命令需要一个工程（Project），问：是否创建一个默认的工程？点击“Yes”。如图3-8所示。 图3-8 是否创建一个工程5. 编辑器中编译窗口开始显示编译的结果。如果显示“hello.exe - 0 error(s), 0 warning(s)”， 则表示编译已经通过！ 6. 点击快捷工具栏上的红色的感叹号（或者选择菜单“Build

27、 | Execute”或按Ctrl-F5），查看运行结果（VC将自动打开一个显示结果的窗口，如上图3-4所示）。   三、如何调试程序利用VC编写程序，还需要学会如何调试程序。我们都会发现，在编写较长的程序时，能够一次成功而不含有任何错误决非易事（当然，鼓励同学们以此为目标，进行长期大量的练习）。对于程序中的错误，VC提供了易用且有效的调试手段。在工具栏上单击鼠标右键，在弹出的菜单中对“Debug”项打勾，发现如图3-9所示的许多按钮。其中，较常用的工具有：单步跟踪进入子函数（Step Into），单步跟踪跳过子函数（Step Over），运行至当前函数的末尾（Step Out）以及

28、观察变量的值（Watch）等，这些VC中常用的调试功能详见有关参考文献。图3-9 VC调试工具条附录四 参考程序1.词法分析器的设计-参考程序/*cifa fenxi chengxu*/#include <stdio.h>#include "stdlib.h"#include <string.h>#define N 100/定义要分析的标识符或常数的最大个数#define M 20/标识符的长度char *sourceFile="1.txt"/定义进行词法分析的源文件char *key8="if","

29、else","for","while","do","return","break","continue"/关键字char *border6=",","","","","(",")"/界符定义char *arithmetic4="+","-","*","/"/算术运算符定

30、义char *relation6="<","<=","=",">",">=","<>" /关系运算符定义char *constsN;/常数定义char *labelN;/标识符int constnum=0,labelnum=0;/constnum-常数个数;labelnum-标识符个数/判断一个字符是不是字母int Isletter(char ch)if(ch>='a' && ch<='z

31、' | ch>='A' && ch<='Z')return 1;return 0;/判断一个字符是不是数字int IsDigit(char ch)if(ch>='0' && ch<='9')return 1;return 0;/判断单词符号类型int search(char searchchar,int wordtype)int i=0;switch (wordtype) case 1:for (i=0;i<=7;i+) if (strcmp(keyi,sear

32、chchar)=0)/返回具体的关键字 return(i+1); case 2:for (i=0;i<=5;i+) if (strcmp(borderi,searchchar)=0)/返回具体的界符 return(i+1); return(0); case 3:for (i=0;i<=3;i+) if (strcmp(arithmetici,searchchar)=0)/返回具体的算术运算符 return(i+1); return(0); case 4:for (i=0;i<=5;i+) if (strcmp(relationi,searchchar)=0)/返回具体的关系运

33、算符 return(i+1); return(0); case 5:for (i=0;i<=constnum;i+) if (strcmp(constsi,searchchar)=0)/返回具体的整型常数 return(i+1); constsi-1=(char *)malloc(sizeof(searchchar);strcpy(constsi-1,searchchar);constnum+;return(i); case 6:for (i=0;i<labelnum;i+) if(labeli!=NULL) if (strcmp(labeli,searchchar)=0)/返回标

34、识符 return(i+1); labeli-1=(char *)malloc(sizeof(searchchar);strcpy(labeli-1,searchchar);labelnum+;return(i); return -1;/标识符或关键字char alphaprocess(char buffer,FILE* fp)int atype;int i=-1;char alphatpM;while (Isletter(buffer)|(IsDigit(buffer)alphatp+i=buffer;buffer=fgetc(fp);alphatpi+1='0'if (at

35、ype=search(alphatp,1)/输出关键字printf("%s (1,%d)n",alphatp,atype-1);elseatype=search(alphatp,6);/输出标识符printf("%s (6,%d)n",alphatp,atype-1);return(buffer);/常数处理char digitprocess(char buffer,FILE* fp)int i=-1;char digittpM;int dtype;while (IsDigit(buffer)digittp+i=buffer;buffer=fgetc(f

36、p);digittpi+1='0'dtype=search(digittp,5);/输出整型常数printf("%s (5,%d)n",digittp,dtype-1);return(buffer);/其它处理(运算符,界符等)char otherprocess(char buffer,FILE* fp)int i=-1;char othertpM;int otype,otypetp;othertp0=buffer;othertp1='0'if (otype=search(othertp,3)printf("%s (3,%d)n&q

37、uot;,othertp,otype-1);buffer=fgetc(fp);goto out;if (otype=search(othertp,4)buffer=fgetc(fp);othertp1=buffer;othertp2='0'if (otypetp=search(othertp,4)printf("%s (4,%d)n",othertp,otypetp-1);goto out;elseothertp1='0'printf("%s (4,%d)n",othertp,otype-1);goto out;if (b

38、uffer=':')buffer=fgetc(fp);if (buffer='=')printf(":= (2,2)n");buffer=fgetc(fp);goto out; else if (otype=search(othertp,2) printf("%s (2,%d)n",othertp,otype-1); buffer=fgetc(fp); goto out; if (buffer!='n')&&(buffer!=' ') printf("%c erro

39、r,not a wordn",buffer); buffer=fgetc(fp);out: return(buffer);void main()int i;FILE *fp;/文件指针,指向要分析的源程序char cbuffer;/保存最新读入的字符for (i=0;i<=N;i+)labeli=NULL;/初始化标识符constsi=NULL;/初始化常数;if (fp=fopen(sourceFile,"rb")=NULL)/判断源文件是否存在printf("文件%s不存在",sourceFile);elsecbuffer = fge

40、tc(fp);/读入字符while (cbuffer!=EOF)/如果文件没有结束,就一直循环if (Isletter(cbuffer)/若为字母cbuffer=alphaprocess(cbuffer,fp);else if (IsDigit(cbuffer)/若为数字cbuffer=digitprocess(cbuffer,fp);else cbuffer=otherprocess(cbuffer,fp);printf("overn");getchar();2. LL(1)文法预测分析表的实现-参考程序/*程序说明*grammer.txt用于输入相应的文法，第一行字母表

41、示起始字符。*/#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX_GRAM_LEN 255/文法符号的最大长度#define MAX_ELE_NUM 40/文法符号的最大个数#define MAX_GRAM_ELE_NUM 300/所有文法符号的个数/-文件指针-FILE* grammerFile;char* grammerFileName="grammer.txt"/输入文法文件FILE* testFile;char* testFileName=&qu

42、ot;outputData.txt"/输出文件/-文法结构体 -typedef structchar mSetenceMAX_GRAM_LEN;grammerElement;grammerElement GrammerSetMAX_GRAM_ELE_NUM;typedef structint len;char eleMAX_ELE_NUM;simpleGroup;simpleGroup groupFirstMAX_ELE_NUM;/ First集simpleGroup groupFollowMAX_ELE_NUM;/ Follow集int grammerNum;/文法符号个数char

43、 VTSetMAX_ELE_NUM;/ 终结符char VNSetMAX_ELE_NUM;/ 非终结符int VNProduceZMAX_ELE_NUM;/ 产生式int vtSetLen;int vnSetLen;char startedSign;/开始符号voidreadInGrammer();void cal_first_set();/计算First集void main()/首先读入文法文件if(grammerFile=fopen(grammerFileName,"rb")=NULL)printf("open file:grammerFile error.n

44、");return;if(testFile=fopen(testFileName,"wb")=NULL)printf("open file:testFile error.n");return;readInGrammer();/计算First集,Follow集cal_first_set();/GrammerSetcal_follow_set();/GrammerSetfclose(grammerFile);fclose(testFile);getchar();/从文件中读入文法void readInGrammer()char tmpChar;ch

45、ar tmpStrMAX_GRAM_LEN;int tmpIndex;int vtIndex,vnIndex;int i,j;tmpIndex=0;vtIndex=0;vnIndex=0;fscanf(grammerFile,"%crn",&startedSign);while(!feof(grammerFile)if(fscanf(grammerFile,"%c->%srn",&tmpChar,&tmpStr)!=2)break;GrammerSettmpIndex.mSetence0=tmpChar;GrammerSet

46、tmpIndex.mSetence1='0'strcat(GrammerSettmpIndex.mSetence,tmpStr);tmpIndex+;for(i=0;i<vnIndex;i+)if(tmpChar=VNSeti)break;if(i=vnIndex)/新的文法符号;VNSetvnIndex=tmpChar;vnIndex+;i=0;while(tmpStri!='0')if(!(tmpStri>=65&&tmpStri<=90)/不是大写字母(不是非终结符)for(j=0;j<vtIndex;j+)if(t

47、mpStri=VTSetj)break;if(j=vtIndex) /新的文法符号VTSetvtIndex=tmpStri;vtIndex+;i+;VTSetvtIndex='0'VNSetvnIndex='0'vtSetLen=vtIndex;vnSetLen=vnIndex;grammerNum=tmpIndex;/计算First集合void cal_first_set()int i,j,k;int* relationMatrix;int matrixSize;int vnIndex;int rowIndex,colIndex;matrixSize=vnSe

48、tLen+vtSetLen;relationMatrix=(int*)malloc(sizeof(int*)*matrixSize);for(i=0;i<matrixSize;i+)relationMatrixi=(int*)malloc(sizeof(int)*matrixSize);if(relationMatrix=NULL)printf("in cal_first_set,mem apply failure.n");return;for(i=0;i<matrixSize;i+)for(j=0;j<matrixSize;j+)relationMatrixij=0;/创建一个图vnIndex=0;for(i=0;i<grammerNum;i+)if(GrammerSeti.mSetence0!=VNSetvnIndex)vnIndex+;j=1;while(GrammerSeti.mSetencej!='0')/A->Beta , Beta是非终结符if(GrammerSeti.mSetencej>=65&&GrammerSeti.mSetencej<=90)for(k=0;k<vnSetLen;k+)/找到相应的非终结符if(VNSetk=Gramme