编译原理实验指导书-2009

<乘型运算符>→*\/ 编译原理实验指导 信息科学与工程学院 计算机系 2009.12.25 实验一 词法程序 一、目的和内容 1．实验目的：通过完成词法分析程序，了解词法分析的过程。 2．实验内容：用C／C++实现对Pascal的子集程序语言的词法识别程序。 3．实验要求：将该语言的源程序，也就是相应字符流转换成内码，并根据需要是否对于标识符填写相应的符号表供编译程序的以后各阶段使用。 二、程序设计语言的描述 程序设计语言的描述采用扩充的BNF表示： <程序>→<程序首部><分程序>． <程序首部>→PROGRAM标识符； <分程序>→[<常量说明部分>][<变量说明部分>][<过程说明部分>]<复合语句> <常量说明部分>→CONST<常量定义>{，<常量定义>}； <常量定义>→标识符=无符号整数 <变量说明部分>→VAR<变量定义>(；<变量定义>)； <变量定义>→标识符{，标识符}：<类型> <类型>→INTEGER|LONG <过程说明部分>→<过程首部><分程序>；{<过程首部><分程序>；} <过程首部>→PROCEDURE标识符；| PROCEDURE标识符(标识符：<类型>)； <语句>→<赋值语句>|<条件语句>|<当型循环语句>|<过程调用语句> |<读语句>|<写语句>|<复合语句>|ε <赋值语句>→标识符：=<表达式> <条件语句>→IF<条件>THEN<语句> <当型循环语句>→WHILE<条件>DO<语句> <过程调用语句>→标识符 | 标识符(<表达式>) <读语句>→READ(标识符，{标识符}) <写语句>→WRITE(<表达式>{，<表达式>}) <复合语句>→BEGIN<语句>{；<语句>}END <条件>→<表达式><关系运算符><表达式> | ODD<表达式> <表达式>→[+|-]<项>{<加型运算符><项>} <项>→<因子>{<乘型运算符><因子>} <因子>→标识符 | 无符号整数 | (<表达式>) <加型运算符>→+|- <乘型运算符>→* | / <关系运算符>→=|<>|<|<=|>|>= 其中：  < >：用左右尖括号括起的字符串表示非终结符号 ：：= ： 定义为 { }：表示该语法成分可以0—n次重复。 [ ]：表示方括号内为可选项，即0或1次。 三、程序设计语言单词的内部编码 如表1-1为词法分析中的内码单词对照表。 表1-1 内部码对照表 内码 单词 内码 单词 内码 单词 内码 单词 1 PROGRAM 2 CONST 3 VAR 4 INTEGER 5 LONG 6 PROCEDURE 7 IF 8 THEN 9 WHILE 10 DO 11 READ 12 WRITE 13 BEGIN 14 END 15 ODD 16 + 17 - 18 * 19 / 20 = 21 <> 22 < 23 <= 24 > 25 >= 26 . 27 . 28 ; 29 : 30 := 31 ( 32 ) 33 无符号整数 34 标识符 35 # 四、词法分析程序的设计思想 为了实现的编译程序实用，这里源程序可采用自由书写格式，即一行内可以书写多个语句，一个语句也可以占领多行书写；标识符的前20个字符有效；整数用2个字节表示；长整数用4个字节表示。这样词法分析程序的主要工作为： （1）从源程序文件中读入字符。 （2）统计行数和列数用于错误单词的定位。 （3）删除空格类字符，包括回车、制表符空格。 （4）按拼写单词，并用（内码，属性）二元式表示。 （5）根据需要是否填写标识符表供以后各阶段使用。 这里采用的编译程序的实现方法是一遍扫描，即从左到右只扫描一次源程序，也就是词法分析作为语法分析的一个子程序。故在编写词法分析程序时，用重复调用词法分析子程序取一单词的方法得到整个源程序的内码流。扫描程序流程图，如图1-1。取单词子程序流程图；如图1-2。取字符和统计字符行列位置子程序；如图1-3。 实验二 语法分析1——递归子程序法 一、目的和内容 1、​ 实验目的：通过完成语法分析程序，了解语法分析的过程和作用 2、​ 实验内容：用递归子程序法实现对pascal的子集程序设计语言的分析程序 3、​ 实验要求：对源程序的内码流进行分析，如为文法定义的句子输出”是”否则输出”否”,根据需要处理说明语句填写写相应的符号表供以后代码生成时使用 二、文法的改变 为适合递归子程序法，对实验一中的文法改写成无左递归和无左共因子的ＢＮＦ如下： <程序>→<程序首部><分程序>。 <程序首部>→PROGRAM标识符； <分程序>→<常量说明部分><变量说明部分><过程说明部分> <复合语句> <常量说明部>→CONST<常量定义><常量定义后缀> |ε <常量定义>→标识符=无符号整数 <常量定义后缀>→，<常量定义><常量定义后缀> |ε <变量说明部分>→VAR<变量定义><变量定义后缀> |ε <变量定义>→标识符<标识符后缀>：<类型>； <标识符后缀>→，标识符<标识符后缀> |ε <变量定义后缀>→<变量定义><变量定义后缀> |ε <类型>→INTEGER | LONG <过程说明部分>→<过程首部><分程序>；<过程说明部分后缀>|ε <过程首部>→PROCEDURE标识符<参数部分>； <参数部分>→(标识符： <类型>)|ε <过程说明部分后缀>→<过程首部><分程序>；<过程说明部分后缀>|ε <语句>→<赋值或调用语句>|<条件语句>|<当型循环语句>|<读语句> |<写语句>|<复合语句>|ε <赋值或调用语句>→标识符<后缀> <后缀>→：=<表达式>|(<表达式>)|ε <条件语句>→IF<条件>THEN<语句> <当型循环语句>→WHILE<条件>DO <语句> <读语句>→READ（标识符<标识符后缀>） <写语句>→WRITE（<表达式><表达式后缀>） <表达式后缀>→，<表过式><表达式后缀>|ε <复合语句>→BEGIN<语句><语句后缀>END <语句后缀>→；<语句><语句后缀>|ε <条件>→<表达式><关系运算符><表达式>|ODD<表达式> <表达式>→+<项><项后缀>|-<项><项后缀>|<项><项后缀> <项后缀>→<加型运算符><项><项后缀>|ε <项>→<因子><因子后缀> <因子后缀>→<乘型运算符><因子><因子后缀>|e <因子>→标识符|无符号整数|（<表达式>） <加型运算符>→+|- <乘型运算型>→*|/ <关系运算符>→ =|<>|<|<=|>|>= 三、非终结符和函数名对照表 为适用递归子程序，表2-1为非终结符和函数名对照表 表2-1 非终符和函数名对照表 非终结符 函数名 非终结符 函数名 <程序> program <程序首部> proghead <分程序> block <常量说明部分> consexpl <常量定义> consdefi <变量说明部分> varexl <常量定义后缀> conssuff <变量定义> vandefi <变量定义后缀> varsuff <>过程说明部分> procdefi <类型> typeil <过程首部> procedh <过程说明部分后缀> procsuff <赋值或调用语句> assipro <语句> sentence <后缀> suffix <条件语句> ifsent <读语句> read <当型循环语句> whilsent <标识符后缀> idsuff <写语句> Write <复合语句> compsent <表达式后缀> Exprsuff <语句后缀> sentsuff <条件> Conditio <项后缀> termsuff <表达式> Express <项> term <因子后缀> Factsuff <参数部分> argument <因子> Factor <加型运算符> addoper <乘型运算符> Muloper <关系运算符> respoper 四、递归子程序的设计思想 为每个非终结符设计一个识别的子程序，寻找该非终结符也就是调用相应的子程序。由于单词在语法分析中作为一个整体，故在语法识别中仅使用其内码。在这里将词法分析作为语法分析的一个子程序，当语法分析需要单词时，就调用相应的词法分析程序获得一个单词。语法分析的作用是识别输入符号串是否是文法上定义的句子，即判断输入符号串是否是满足“程序”定义的要求。也就是当语法识别程序从正常退出表示输入符号串是正确的“程序”；若从出错退出，则输入符号串不是正确的“程序”。出错时，可以根据读字符的位置判断出错的位置。 五、部分子程序流程图 图2-1a表示程序是由首部、分程序和“．”组成的；图2-1b表示程序首部的组成；图2-1c为分程序的语法成分，图2-1d表示语句的组成；图2-1e为因子的构成。 图2-1a 图2-1b 图2-1c 图2-1d 图2-1e 实验三 语法分析2——预测分析法 一、目的和内容 1、实验目的：通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。 2、实验内容：构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序。 3、实验要求：源程序的内码流用预测分析法进行分析。如为文法定义的句子输出“是”，否则输出“否”，并根据需要处理说明语句填写相应的符号表供以后代码生成时使用。 二、文法的改变 由于预测分析和递归子程序都是自顶向下的分析方法，且在实验二中已将它变换成无回溯的和无左公因子的文法。则可直接用实验二中的文法。 三、非终结符的内码表 为了将非终结符和终结符一起存入栈参，将非终结符的内码从128开始标记。其对照表见表3-1。 表3-1 非终结符和内码对照表 内 码 非 终 结 符 内 码 非 终 结 符 内 码 非 终 结 符 128 〈程序〉 129 〈程序首部〉 130 〈分程序〉 131 〈常量说明部分〉 132 〈常量定义〉 133 〈常量定义后缀〉 134 〈变量说明部分〉 135 〈变量定义〉 136 〈变量定义后缀〉 137 〈类型〉 138 〈过程说明部分〉 139 〈过程首部〉 140 〈过程说明部分后缀〉 141 〈语句〉 142 〈赋值或调用语句〉 143 〈后缀〉 144 〈条件语句〉 145 〈当型循环语句〉 146 〈读语句〉 147 〈标识符后缀〉 148 〈写语句〉 149 〈表达式后缀〉 150 〈复合语句〉 151 〈语句后缀〉 152 〈条件〉 153 〈表达式〉 154 〈项后缀〉 155 〈项〉 156 〈因子后缀〉 157 〈因子〉 158 〈参数部分〉 159 〈加型运算符〉 160 〈乘型运算符〉 161 〈关系运算符〉 四、程序设计思想 为了压缩存储，采用一个二维数组存放规则的右部，每个规则对应一个子数组，用0表示每条规则的结束。在预测分析表中用规则的序号代表相应的规则，分析表中的出错用-1表示。由于规则的右部存在相同的符号串，故相同的符号串只要保存一个即可，如ε规则。（这种方法对语法识别没有影响，但不像语义分析和代码生成时，需区分是何种规则的右部）。规则右部符号串编号及内码表示： （1）〈程序首部〉〈分程序〉.　　　　　　　　　　　　　　 129 130 26 0 （2）PROGRAM标识符； 1 34 28 0 （3）<学量说明部分><变量说明部分><过程说明部分><复合语句> 131 134 138 150 0 （4）CONST<常量定义><常量定义后缀>； 2 132 133 28 0 （5）ε 0 （6）标识符=无符号整数 34 20 33 0 （7），<常量定义><常量定义后缀> 27 132 133 0 （8）VAR<变量定义<变量定义后缀>； 3 135 136 0 （9）标识符<标识符后缀>：<类型>； 34 147 29 137 28 0 （10），标识符<标识符后缀> 27 34 147 0 （11）<变量定义><变量定义后缀> 135 136 0 （12）INTEGER 40 （13）LONG 50 （14）<过程首部><分程序>；<过程说明部分后缀> 139 130 28 140 0 （15）PROCGDURE标识符<参数部分>； 6 34 158 28 0 （16）<赋值或调用语句> 142 0 （17）<条件语句> 144 0 （18）<当型循环语句> 145 0 （19）<读语句> 146 0 （20）<写语句> 148 0 （21）<复合语句> 150 0 （22）标识符<后缀> 34 143 0 （23）：=<表达式> 30 153 10 （24）IF <条件>THEN<语句> 7 152 8 141 0 （25）WHILE<条件>DO<>语句  9 152 10 141 0 （26）READ<标识符<标识符后缀> 11 31 34 147 32 0 （27）WRITE（<表达式><表达式后缀>） 12 31 153 149 32 0 （28），<表达式><表达式后缀> 27 153 149 0 （29）BEGIN<语句><语句后缀>END 13 141 151 14 0 （30）；<语句><语句后缀> 28 141 151 0 （31）<表达式><关系运算符><表达式> 153 161 153 0 （32）ODD<表达式> 15 153 0 （33）+<项><项后缀> 16 155 154 0 （34）-<项><项后缀> 17 155 154 0 （35）<项><项后缀> 155 154 0 （36）<加型运算符><项><项后缀> 159 155 154 0 （37）<因子><因子后缀> 157 156 0 （38）<乘型运算符><因子><因子后缀> 160 157 156 0 （39）) 标识符号 34 0 （40）无符号整数 33 0 （41）（<表达式>） 31 153 32 0 （42）无符号整数 26 33 0 （43）+ 16 0 （44）- 17 0 （45）* 18 0 （46）/ 19 0 （47）= 20 0 （48）＜＞ 21 0 （49）＜ 22 0 （50）＜= 23 0 （51）＞ 24 0 （52）＞＝ 25 0 （53）（标识符：〈类型〉） 31 34 29 137 32 0 图3-1为预测分析程序流程图。 图3-1 预测分析程序流程图 五、分析表和程序 在预测分析法中所有预测分析法的总控分析程序都是一样的，主要是分析表不同。在预测分析表中的元素如用规则来表示，则分析表需三维数组，若用该方法表示分析表所需的存储空间较大，为此用规则号表示预测分析表中的元素。另外，一个算法语言的预测分析表中 的元素大多是出错元素，则可用0表示。要在程序中直接用内码表示预测分析表，则该分析表还是很大的，可用(非终结符,终结符,规则号)三元式表示；非终结符和终结符匹配时，用规则号的规则推导。为减少查询分析表的时间，在分析程序初始化时，将三元式（非终结符，终结符，规则号）转换成分析表。最后，由总控程序根据分析表来分析源程序是否是文法上定义的“程序”。 实验四 语义分析和代码生成 一、目的和内容 1、实验目的：通过完成语义分析和代码生成程序，了解语义分析和代码生成与词法分析、语法分析的关系，从而体会编译程序的全过程。 2、实验内容：在语法分析的基础上，配有相应的代码生成语句使源程序生成相应的目标代码（汇编代码）。 3、实验要求：对源程序的内码流进分析语法分析并附有相应的语义子程序制导产生的目标代码。 二、程序设计语言的语义解释 1、程序的数据类型有两种：好integer和long型，和标准Pascal语言一样用两个字节表示integer型，其表示范围为-32768~+32767，而long型用四个字节表示，其表示范围为： -214783648~214783647。 2、相同类型的数据运算其结果为该类型的数据，不同类型的数据运算其结果是多字节的类型，即integer和long型混合运算时结果为long型。 3、比较运算和ODD运算的结果是逻辑值，逻辑值也占两个字节用0表示假，-1表示“真”。 4、不同类型的数据进行赋值时，低字节赋给高字节时，自动补足，高字节赋给低字时，高位部分自动忽略，而不考虚其类型不匹配问题。 5、运算符和优先级 运算符 优先级 # 0 （ 1 入运算栈后 = < > <= >= <> 2 + - 3 * / 4 - (单目) +（单目） 5 （ 6 入运算栈前 另外运算符“）”和“ODD”不需入运算符栈故没有定义优先级。实际上它高于“#”，而和入栈后的“（”优先级一样。 6、输入语句及数据用空格隔开，但输入数据个数不得少于read语句中的变量（否则获得随机值）。 7、对于一个输出语句先自动换行，然后输出其值，对于同一个输出语句中的量，用空格隔开。 8．过程允许递归，允许带一个参数也可不带参数。 9．其他语义规则同标准Pascal语言。 三、语义子程序需考虑的问题 1．标识符表的设计 定义标识符有常量标识符、变量标识符和过程标识符。它们均有符号名，对于常量标识符和变量标识符需要有类型、运行时的地址和定义符号的层数(不同层的同名标识符是不同的对象)，对于过程标识符它分有参过程和无参过程，有参过程还需说明参数在符号表的入口，故标识符表的结构为：符号名、类型、运行时的相对地址、层、属性和参数入口。 2．由于8088指令系统中不提供四字节的乘法和除法指令以及对于integer和long型的输入和输出，故把它们写成相应的子程序并加上一标志。当调用相应的子程序时，就生成相应的子程序。 3．当PROGRAM匹配时，输出汇编语言定义数据段、堆栈段和代码段的首标志。 4．当“．”匹配时，输出数据段、堆栈段和代码段的结束标志。 5．常量说明填写标识符表，分配运行时的地址，产生运行时把常量放入相应地址的指令。 6．变量说明填写标识符表，分配运行时的地址。 7．过程序说明对于过程标识符和形参标识符均填写标识符表，并统计层数和处理相应的子程序的其他部分，生成进入过程后的分配过程的存储空间，指示数据区的低部和顶部，拷贝区头向量的指令，还要注意因为采用的是一遍扫描，当处理过程序头时，尚不能计算出本过程式所需的存储空间，在这里产生一条调用求数据区长度的指令。在处理过程结束时，要产生返回分配数据区的指令，产生求出数据区长度的子程序。另外，在处理本层过程结束后，从标识符表中全部清除属于本层的标识符，以区分下一个并列的子程序的标识符。 8．处理参数时，将参数的入口地址填入过程标识符的参数入口中。 9．在处理分程序时，要区分是0层分程序(即主程序)还是过程，其产生的代码略有不同，还要产生跳过过程代码的指令。 10．将表达式赋给变量的赋值语句根据变量和表达式的类型，产生将运算对象栈中存放的表达式的临时变量地址，取值存入相应的变量指令。 11．过程调用语句，如带有参数应产生将参数的临时变量放入区头向量中参数约定的单元、取新的数据区的低部，拷贝区头向量，和调用相应子程序等指令。 12．只要if语句产生取出条件的逻辑值进行判断的指令为假，跳过相应的语句。 13．while语句先产生标号，然后根据条件判断的指令为假跳出循环，在while语句结束时产生一条无条件转移语句和假转出的标号。 14．read语句先产生将符号串读入缓冲区的指令，然后对于read中的每一个变量调用相应的读数据的子程序。 15．write语句先产生回车指令，然后对于write中的每个表达式调用输出子程序。 16．“(”匹配是入运算符栈，将其运算符的优先级改为1。 17．“)”匹配时生成在运算符栈中全部优先级均大于“(”的运算符，运算指令然后“(”退栈。 18．对于表达式中的常量、常量标识符、变量标识符的匹配时，进入运算对象栈。 19．对于运算符+、-、*、/、+（单目）、-（单目）、=、<、>、<=、>=生成运算符栈中优先级大于等于本运算符优先级的指令，然后将本运算符入栈。 四、证语义子程序的实现方法 采用的方法是在递归子程序识别法的基础上，按制导翻译的原理加上相应的语义动作，由于识别方法本身也是程序逻辑，故在识别程序中直接插入语义分析和代码生成程序代码即可。 语法分析—预测分析法（示例） 一、实验目的和内容 a)​ 实验目的：通过完成预测分析法的语法分析程序，了解预测分析法分析过程 b)​ 实验内容：用C++实现针对LL（1）语言的预测分析程序，该程序能够对输入的语法文件进行分析，自动求得“FIRST”/“FOLLOW”集构造预测分析表，并在实现词法分析的基础上实现语法分析。 c)​ 实验要求：对输入源程序的内码流用“预测分析法”进行分析，输出语法分析结果：错误的个数与错误在源程序中的位置。 二、实验程序设计思想 I ）程序总体方案选择 为实现实验目标，可以有两种选择方案： 1、手工求“FIRST”/“FOLLOW”集并构造预测分析表。这种方法简化了编写程序的过程，但是却增加了人工工作强度，而且容易出错。 2、编写适当的函数，实现“FIRST”/“FOLLOW”集的自动求取，进而构造预测分析表。这种方案虽然在程序编写上有些麻烦，但是却增加了程序的“适应能力”，而且不容易出错。 实验中采用自动求得“FIRST”/“FOLLOW”集构造预测分析表的方案。 II ）文法的处理 实现自动求取“FIRST”/“FOLLOW”集首先要解决文法的输入、存储和处理等问题。 文法的处理过程本身就是一个小型的语法分析程序（只不过文法规则比较简单），其文法规则如下： <文法文件> <终结符定义> <文法定义> <终结符定义> <注释部分>“<<终结符开始>>”<终结符>“<<终结符结束>>” <注释部分> “//” 任意一行字符串 <终结符> 任意满足规定的一行字符串 <文法定义> <注释部分>“<<文法开始>>”<文法>“<<文法结束>>” <文法> <非终结符>“->”<规则右部> <非终结符> “<” 任意满足规定的一行字符串“>” <规则右部> <非终结符><规则右部> | <终结符><规则右部> 对于这个文法的分析不必用预测分析法。利用这个文法的特点： 1、终结符定义和文法定义都有开始和结束标志可以准确定位到定义的开始，而忽略注释部分。 2、每一个非终结符号都有开始（<）结束（>）标志所以可以利用他们取出非终结符 3、每一个非终结符必须出现在文法的左部，由此可以取得所有非终结符 4、每一条文法规则的左右部由“->”分割，由此可以分清文法右部 实验中采用简单的函数对文法定义文件进行了分析，并用“Grammar”类对操作进行了封装。文法被输入到程序后被存储在一个int类型的矩阵（rule）中。由于在预测分析过程中非终结符要与终结符一起入栈，所以在非终结符存储的时候必须考虑到与终结符内码相区别，可以采用限定非终结符内码底线的方法。即定义一个常数：UNFINISH_BASE_INT（由于本次实验的文法数据不是很大，所以这个数被定义为128已经足够了），所有比这个数小的就是终结符的内码，其余内码数字就可以用来表示非终结符以及各种程序中的标志。 在输入文法规则后还要对文法进行适当的处理，因为在预测分析法的栈中出现的非终结符是要用适当的文法规则右部进行替换的，而一个非终结符往往可以对应多条文法右部（他们的关系是并列的“|”），所以必须维护一个文法右部表（存储在int类型的矩阵ruleRight中由“Forecast”类进行管理）以及一个对应关系表（存储在int类型的矩阵linker中由“Forecast”类进行管理）。 如一条文法规则如下 <后缀> -> ":=" <表达式> | "（" <表达式> "）" | null 则应该表示为3条文法右部，并在linker表中表示非终结符〈后缀〉的一行中存入这3条文法右部的序号。 III ）FIRST/FOLLOW集的求取 在用程序求取FIRST集与FOLLOW集的时候有几种方案可以选择： 1、使用递归的方法，采用与手工计算相似的方法，遇到FIRST/FOLLOW集有包含关系，则先求被包含的那个非终结符的FIRST/FOLLOW集，求取之后再将这个非终结符的FIRST/FOLLOW集加到包含它的那个非终结符的FIRST/FOLLOW集中采取的规则是 FIRST集： 若有规则ABC 1如果B为终结符，则将B加入到A的FIRST集中 2如果B为非终结符，则先算出B的FIRST集，并将B的FIRST集加入到A的FIRST集中 3如果B的FIRST集中包含空串（B能推出空串）则将C的FIRST集加入到A的FIRST集中 FOLLOW集： 若有规则ABC 1如果C为终结符，则将C加入到B的FOLLOW集中 2如果C为非终结符，则将C的FIRST集加入到B的FOLLOW集中，并将将A的FOLLOW集加入到C的FOLLOW集中 3如果C的FIRST集中包含空串（C能推出空串）则将A的FOLLOW集加入到B的FOLLOW集中 这种方法编写程序时简单方便，程序可读性好，对于实验所给的文法只有在用第3条规则求FOLLOW集时会产生死循环，但是只要把这条规则放在函数的最后，跳出死循环即可，也不会产生FOLLOW集元素缺失现象。但是这种方法对于一般的文法难以做到FOLLOW集元素不缺失，而且在文法过于复杂时会由于递归层数过大而导致系统堆栈溢出、程序失败。 2、先求取FIRST/FOLLOW集之间的包含/相等 等关系，然后从没有包含其他FIRST/FOLLOW集的非终结符算起，逐步解决。这种方法还是要用到递归，仍然存在递归层数过大的危险，这种方法在求取关系后会留下这些没用的数据，造成没必要的负担。由于关系与FIRST/FOLLOW集是分开求取的，程序会变的庞大复杂。 3、将两种方法结合。FIRST/FOLLOW集之间的包含/相等 等关系在FIRST/FOLLOW集求取过程中同时求取，并逐渐完善，比如加入一个包含关系后就马上完善其余的包含关系：若A包含ABC，B包含BD则A包含ABCD（相等也看成是一种包含关系），若加入一个元素到B的FIRST/FOLLOW集则立即将这个元素加入到A的FIRST/FOLLOW集，并且标记整个“集合群”已经改变。完成一遍后如果发现“集合群”发生了改变，则重新求取一遍，直到“集合群”不再改变。 这种方法的优点是： a、​ 程序复杂度适中 b、​ 不会有元素缺失现象 c、​ 由于整个函数避免了递归，就不会由于递归层数过大而导致系统堆栈溢出、程序失败 d、​ 由于将关系矩阵作为函数的局部元素，计算后也不会产生冗余数据 e、​ 适应能力强，即便输入的文法是左递归的，也能保证FIRST/FOLLOW集的准确 这种方法的缺点是： 由于程序最后一遍运算实际上是在做确认工作，没有加入任何元素。可见程序的运算过程是存在冗余的（但对于实验的文法数据，循环都只运行了2次（包括最后一次校验），可见程序的效率还是令人满意的）。 基于以上分析，实验中采用了第三种方法 IV ）分析结果的表示 对于分析的结果，实验在分析结束后会递交一个分析报告，里面记录了错误的位置和错误的个数，并且可以通过双击分析报告而找到相应的错误的所在位置。 三、实验程序数据 d)​ 程序语法文件 // 每个终结符号占一行 // 第一个终结符必须申明为"无符号整数" // 第二个终结符必须申明为"标识符" // 终结符中不能包含空格和TAB以及其他非打印类字符 // 所有终结符必须申明在"<<终结符开始>>"和"<<终结符结束>>"之间 <<终结符开始>> 无符号整数 标识符 PROGRAM CONST VAR INTEGER LONG PROCEDURE IF THEN WHILE DO READ WRITE BEGIN END ODD + - * / = <> < <= > >= . , ; : := ( ) <<终结符结束>> // <>之间为非终结符符号 // 一条规则用回车结束, // 终结符必须加上""号, // ->区分规则左右部, // 并行(非)终结符用|阁开, // null表示空串 // 空格和TAB添加不限 // 所有文法规则必须申明在"<<文法开始>>"和"<<文法结束>>"之间 // 开始非终结符必须放在最前面 <<文法开始>> <程序> <程序首部> <分程序> "." <程序首部> "PROGRAM" "标识符" ";" <分程序> <常量说明部分> <变量说明部分> <过程说明部分> <复合语句> <常量说明部分> "CONST" <常量定义> <常量定义后缀> | null <常量定义> "标识符" "=" "无符号整数" <常量定义后缀> "," <常量定义> <常量定义后缀> | null <变量说明部分> "VAR" <变量定义> <变量定义后缀> | null <变量定义> "标识符" <标识符后缀> ":" <类型> ";" <变量定义后缀> <变量定义> <变量定义后缀> | null <类型> "INTEGER" | "LONG" <过程说明部分> <过程首部> <分程序> ";" <过程说明部分后缀> | null <过程首部> "PROCEDURE" "标识符" <参数部分> ";" <过程说明部分后缀> <过程首部> <分程序> ";" <过程说明部分后缀> | null <语句> <赋值或调用语句> | <条件语句> | <当型循环语句> | <读语句> | <写语句> | <复合语句> | null <赋值或调用语句> "标识符" <后缀> <后缀> ":=" <表达式> | "(" <表达式> ")" | null <条件语句> "IF" <条件> "THEN" <语句> <当型循环语句> "WHILE" <条件> "DO" <语句> <读语句> "READ" "(" "标识符" <标识符后缀> ")" <标识符后缀> "," "标识符" <标识符后缀> | null <写语句> "WRITE" "(" <表达式> <表达式后缀> ")" <表达式后缀> "," <表达式> <表达式后缀> | null <复合语句> "BEGIN" <语句> <语句后缀> "END" <语句后缀> ";" <语句><语句后缀> | null <条件> <表达式> <关系运算符> <表达式> | "ODD" <表达式> <表达式> "+" <项> <项后缀> | "-" <项> <项后缀> | <项> <项后缀> <项后缀> <加型运算符> <项> <项后缀> | null <项> <因子> <因子后缀> <因子后缀> <乘型运算符> <因子> <因子后缀> | null <因子> "标识符" | "无符号整数" | "(" <表达式> ")" <参数部分> "(" "标识符" ":" <类型> ")" | null <加型运算符> "+" | "-" <乘型运算符> "*" | "/" <关系运算符> "=" | "<>" | "<" | "<=" | ">" | ">=" <<文法结束>> e)​ 终结符号表 1 无符号整数 2 标识符 3 PROGRAM 4 CONST 5 VAR 6 INTEGER 7 LONG 8 PROCEDURE 9 IF 10 THEN 11 WHILE 12 DO 13 READ 14 WRITE 15 BEGIN 16 END 17 ODD 18 + 19 - 20 * 21 / 22 = 23 <> 24 < 25 <= 26 > 27 >= 28 . 29 , 30 ; 31 : 32 := 33 ( 34 ) 35 $ f)​ 非终结符号表 128 程序 129 程序首部 130 分程序 131 常量说明部分 132 常量定义 133 常量定义后缀 134 变量说明部分 135 变量定义 136 变量定义后缀 137 类型 138 过程说明部分 139 过程首部 140 过程说明部分后缀 141 语句 142 赋值或调用语句 143 后缀 144 条件语句 145 当型循环语句 146 读语句 147 标识符后缀 148 写语句 149 表达式后缀 150 复合语句 151 语句后缀 152 条件 153 表达式 154 项后缀 155 项 156 因子后缀 157 因子 158 参数部分 159 加型运算符 160 乘型运算符 161 关系运算符 g)​ 文法右部表 (0) 129 130 28 0 (1) 3 2 30 0 (2) 131 134 138 150 0 (3) 4 132 133 0 (4) 0 (5) 2 22 1 0 (6) 29 132 133 0 (7) 5 135 136 0 (8) 2 147 31 137 30 0 (9) 135 136 0 (10) 6 0 (11) 7 0 (12) 139 130 30 140 0 (13) 8 2 158 30 0 (14) 142 0 (15) 144 0 (16) 145 0 (17) 146 0 (18) 148 0 (19) 150 0 (20) 2 143 0 (21) 32 153 0 (22) 33 153 34 0 (23) 9 152 10 141 0 (24) 11 152 12 141 0 (25) 13 33 2 147 34 0 (26) 29 2 147 0 (27) 14 33 153 149 34 0 (28) 29 153 149 0 (29) 15 141 151 16 0 (30) 30 141 151 0 (31) 153 161 153 0 (32) 17 153 0 (33) 18 155 154 0 (34) 19 155 154 0 (35) 155 154 0 (36) 159 155 154 0 (37) 157 156 0 (38) 160 157 156 0 (39) 2 0 (40) 1 0 (41) 33 2 31 137 34 0 (42) 18 0 (43) 19 0 (44) 20 0 (45) 21 0 (46) 22 0 (47) 23 0 (48) 24 0 (49) 25 0 (50) 26 0 (51) 27 0 h)​ FIRST集 (程序) PROGRAM (程序首部) PROGRAM (分程序) CONST VAR PROCEDURE BEGIN (常量说明部分) 空串 CONST (常量定义) 标识符 (常量定义后缀) 空串 , (变量说明部分) 空串 VAR (变量定义) 标识符 (变量定义后缀) 空串 标识符 (类型) INTEGER LONG (过程说明部分) 空串 PROCEDURE (过程首部) PROCEDURE (过程说明部分后缀) 空串 PROCEDURE (语句) 空串 标识符 IF WHILE READ WRITE BEGIN (赋值或调用语句) 标识符 (后缀) 空串 := ( (条件语句) IF (当型循环语句) WHILE (读语句) READ (标识符后缀) 空串 , (写语句) WRITE (表达式后缀) 空串 , (复合语句) BEGIN (语句后缀) 空串 ; (条件) 无符号整数 标识符 ODD + - ( (表达式) 无符号整数 标识符 + - ( (项后缀) 空串 + - (项) 无符号整数 标识符 ( (因子后缀) 空串 * / (因子) 无符号整数 标识符 ( (参数部分) 空串 ( (加型运算符) + - (乘型运算符) * / (关系运算符) = <> < <= > >= i)​ FOLLOW集 (程序) $ (程序首部) CONST VAR PROCEDURE BEGIN (分程序) . ; (常量说明部分) VAR PROCEDURE BEGIN (常量定义) VAR PROCEDURE BEGIN , (常量定义后缀) VAR PROCEDURE BEGIN (变量说明部分) PROCEDURE BEGIN (变量定义) 标识符 PROCEDURE BEGIN (变量定义后缀) PROCEDURE BEGIN (类型) ; ) (过程说明部分) BEGIN (过程首部) CONST VAR PROCEDURE BEGIN (过程说明部分后缀) BEGIN (语句) END ; (赋值或调用语句) END ; (后缀) END ; (条件语句) END ; (当型循环语句) END ; (读语句) END ; (标识符后缀) : ) (写语句) END ; (表达式后缀) ) (复合语句) END . ; (语句后缀) END (条件) THEN DO (表达式) THEN DO END = <> < <= > >= , ; ) (项后缀) THEN DO END = <> < <= > >= , ; ) (项) THEN DO END + - = <> < <= > >= , ; ) (因子后缀) THEN DO END + - = <> < <= > >= , ; ) (因子) THEN DO END + - * / = <> < <= > >= , ; ) (参数部分) ; (加型运算符) 无符号整数 标识符 ( (乘型运算符) 无符号整数 标识符 ( (关系运算符) 无符号整数 标识符 + - ( j)​ 预测分析表 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 (程序) error error 0 error error error error error error error error error error error error error error error error error error error error error error error error error error error error error error error end (程序首部) error error 1 synch synch error error synch error error error error error error synch error error error error error error error error error error error error error error error error error error error error (分程序) error error error 2 2 error error 2 error error error error error error 2 error error error error error error error error error error error error synch error synch error error error error error (常量说明部分) error error error 3 4 error error 4 error error error error error error 4 error error error error error error error error error error error error error error error error error error error error (常量定义) error 5 error error synch error error synch error error error error error error synch error error error error error error error error error error error error error synch error error error error error error (常量定义后缀) error error error error 4 error error 4 error error error error error error 4 error error error error error error error error error error error error error 6 error error error error error error (变量说明部分) error error error error 7 error error 4 error error error error error error 4 error error error error error error error error error error error error error error error error error error error error (变量定义) error 8 error error error error error synch error error error error error error synch error error error error error error error error error error error error error error error error error error error error (变量定义后缀) error 9 error error error error error 4 error error error error error error 4 error error error error error error error error error error error error error error error error error error error error (类型) error error error error error 10 11 error error error error error error error error error error error error error error error error error error error error error error synch error error error synch error (过程说明部分) error error error error error error error 12 error error error error error error 4 error error error error error error error error error error error error error error error error error error error error (过程首部) error error error synch synch error error 13 error error error error error error synch error error error error error error error error error error error error error error error error error error error error (过程说明部分后缀) error error error error error error error 12 error error error error error error 4 error error error error error error error error error error error error error error error error error error error error (语句) error 14 error error error error error error 15 error 16 error 17 18 19 4 error error error error error error error error error error error error error 4 error error error error error (赋值或调用语句) error 20 error error error error error error error error error error error error error synch error error error error error error error error error error error error error synch error error error error error (后缀) error error error error error error error error error error error error error error error 4 error error error error error error error error error error error error error 4 error 21 22 error error (条件语句) error error error error error error error error 23 error error error error error error synch error error error error error error error error error error error error error synch error error error error error (当型循环语句) error error error error error error error error error error 24 error error error error synch error error error error error error error error error error error error error synch error error error error error (读语句) error error error error error error error error error error error error 25 error error synch error error error error error error error error error error error error error synch error error error error error (标识符后缀) error error error error error error error error error error error error error error error error error error error error error error error error error error error error 26 error 4 error error 4 error (写语句) error error error error error error error error error error error error error 27 error synch error error error error error error error error error error error error error syn