用某种高级程序设计语言实现文法的等价压缩算法(PASCAL语言实现).docVIP

编译原理实习作业 用某种高级程序设计语言实现 文法的等价压缩算法 （PASCAL语言实现） 二○○一年十月一日 实习作业：用高级程序设计语言实现对文法多余规则的等价压缩 一．相关定义及定理： 给出一个无U：：=U形规则的前提下规则不多余的判别条件： 一个规则U：：=u要是有用的，便得在推导中被应用，即其左部非终结符号U必须在句子的推导中出现，且u能推导到终结符号串。为此，U与u必须分别满足下列条件： 条件1：Z=*xUy，其中x，y∈V，Z为识别符号； 条件2：u=+t，其中t∈VT。 ●判别条件1的加标记算法步骤如下： 步骤1：对规则中识别符号Z加标记； 步骤2：对左部非终结符加有标记的规则，将其右部中出现的一切非终结符号加标记； 步骤3：检查是否一切非终结符号都已加过标记。是，则无多余规则而结束；否，则执行下一步骤； 步骤4：检查最近一次执行步骤2时是否未对任何非终结符号加过标记。如果是这样，该文法中左部非终结符号未加过标记的规则都不满足条件1，这些规则是多余的，结束。否则重复步骤2。 ●判别条件2的加标记算法步骤如下： 步骤1：对u∈V的规则U::=u之左部非终结符号U加标记； 步骤2：对右部仅包含终结符号与已加标记的非终结符号的规则之左部加标记； 步骤3：检查是否已对一切非终结符号加过标记。是，则无多余的规则而结束；否，则执行下一步骤； 步骤4：检查最近一次执行步骤2时是否未对任何非终结符号加过标记。如果是这样，该文法中左部非终结符号未加过标记的规则都不满足条件2，这些规则是多余的，结束。否则重复步骤2。 概括起来，对一个给定的文法进行压缩文法等价变换的规范步骤如下： 展开文法规则，并删除U::=u形规则 判别条件1和2，执行加标记算法 删除不满足条件的无用规则，得到等价的压缩了的文法。 二.PASCAL程序设计语言实现文法压缩算法的功能说明： 文法的存储：对每一个可能包含无用规则的文法G[Z]以数组（grammar类型）形式存储。其中，每一个数组元素都是一条规则，而每一条规则又是一个记录类型（rulers），它包括规则左部（left：字符类型）、规则右部（right：字符串类型）两部分； 加标记算法：对符合条件的非终结符号加标记是采用间接的方法，即：若要对终结符号加标记，则把它存到一个数组B（字符类型）中，以后只要判断该数组中有无某非终结符号便知它加过标记没有。而同样对每个字符是否非终结符号的判断也借助一个数组A（字符类型）来执行； 条件1和2的实现：对一个文法它首先存在一个数组g1（grammar类型）中，对每一个符合条件1的规则都存在另一个数组g2（grammar类型）中，这样也就等于删除了不满足条件1的多余规则；同样在执行条件2后又把所有满足条件2的规则放到g1中去，这样重复直到条件1和2执行过后剩余的有用规则的条数相同为止。 三.设计评价：本设计基本实现了对非压缩文法的等价压缩。但是它只限于文法规则条数不多（这里不超过20条）的情况，并且每次输入都必须先输入要输入的文法包含规则的条数，这一点有待改进。 四.PASCAL语言实现源程序如下： program zipgrammar(input,output); type cc=packed array [1..20] of char; rulers=record left:char; right:string[15]; end; grammar=array [1..20] of rulers; var g1,g2:grammar; a,b:cc; n1,n2,n,v,h,i:integer; gz,ch,ccc,ag:char; procedure new(var g1:grammar;var n1:integer); {输入未压缩文法子过程} var n,x,i,j:integer; a,b,c:char; s,t:boolean; begin writeln; write(How many rulers will you enter?); read(n); writeln(Enter G[Z]:); readln; j:=1; for i