要求分析和规格说明.doc

一、 要求分析和规格说明1、 PL语言分析相对于PASCAL和PS语言而言，PL语言是一种定义非常狭窄的小的程序设计语言，它的简单类型仅有整型（integer）和布尔型（Boolean），过程定义不能有参数， a) 符号： 保留字：Boolean Proc array begin call const do end false fi if integer od read skip true write专有符号：- * := , / = ( - | + ) ; & 数字数字是十进制整数，范围从-32767到32767。标识符由字母开头的，后跟0个或多个字母或数字组成。b) 数据类型：PL具有有两种基本数据类型，整型 integer 和布尔类型 Boolean。结构类型只有数组，不可以定义自己新的数据类型。c) 程序结构：得到一个PL程序是后跟有一个句号(圆点)的程序。分程序有定义部分DP和语句部分SP组成: begin DP SP end； 分程序描述了在命名对象上的操作。对象是一个常量、变量或过程（类型由保留字表示）。每个对象有定义说明。不存在标准对象。作用域规则与PS相同。分程序内每个操作产生其内定义的变量的一个新实例。分程序的定义部分是后跟有分号的定义的序列： D1；D2； Dn; 例如： begin const a = 1; $常量部分 integer b; $变量定义 b:=10; $数值输出 end.d) 常量定义一般形式：const = 常量定义说明常量的名字：const n =100e) 变量定义一般形式： 或： array 常量 前者是定义一般变量，后者是定义数组变量。数组的常量必须是自然数1，2，n。它代表要定义的数组的元素个数，而数组的下标是从1开始的。例: integer a,b,c; integer A 10; $定义有10个元素的数组变量APL遵循变量先定义后使用的规则，而且在同一个作用域范围内不允许有相同的变量名。但不同作用域变量名可以相同。也不能用PL的保留字做变量名。f) 过程定义说明一般形式：Proc PL的过程遵循先定义后使用的规则，而且在同一个作用域范围内不允许有相同的过程名。但不同作用域过程名可以相同。也不能用PL的保留字做过程名。Proc write $错误，这是PL的标准过程，不能重定义g) PL的语句空语句:一般形式：skip; 它表示什么也不做。读语句一般形式：read ; 其中 变量访问表 ： , 它是PL的标准过程，也是唯一的一条输入语句。表示输入一个或多个整数并赋值给相应变量。例：read a, b, c;写语句一般形式：write ; 其中 表达式表 ： , 它是PL的标准过程，也是唯一的一条输出语句。表示输出一个或多个由表达式定义的整数。例：write a, b, c*d, 100;赋值语句一般形式： := ; PL的赋值语句具有并行赋值的特点。例：a, b := 1, x+y;它表示依次把右边的表达式的值分别赋给左边对应的变量。上例就是把1赋给变量a， 把x+y的值赋给变量b。过程语句一般形式：call ; 它表示调用用户自己定义过程，PL规定过程必须是先定义后使用的。if语句一般形式：if fi; 其中 警戒命令表 ： 警戒命令： - PL依次检测各警戒命令，如果表达式的值为true则执行相应的语句部分，然后忽略其余警戒命令，执行if后面的语句。如果所有表达式的值均为false这发出“if 语句逻辑错误”的提示并终止程序的执行。例：if ab - t := a; a t := b; fi;do语句一般形式：do do;其中 警戒命令表 ： 警戒命令： - PL依次检测各警戒命令，如果表达式的值为true则执行相应的语句部分，然后重新检测各警戒命令，直到所有表达式的值均为false才继续执行do后面的语句。例：do i 100 - read i ; odh) 程序注释PL的注释以“$”字符开头，直到本行末为止。例如：begin I:=90; $这里也是程序的注释 end.i) 运算PL有下列四种运算与或运算:&： 与运算，只有当两个布尔值均为true结果才为true| ： 或运算，只要其中一个布尔值为true结果就为true关系运算 :PL的关系运算和关系运算符有 运算的结果为布尔值加减运算加减运算 + - 参加运算的两个操作数和结果均为整数。乘除运算乘除运算* / 参加运算的两个操作数和结果均为整数。* : 两个数相乘 /: 两个数相除结果只取整数部分 : 两个数相相除结果只取余数部分非运算运算符 表示把原来的布尔值取反。(3)文法分析：PL的BNF文法: := “.” := “begin” “end” := “;” := | | := “const” “= “ := | “array” “ “” := “integer” | “Boolean” := “,” := “Proc” := “;” := | | | | | | := “skip” := “read” := “,” := “write” := “,” := “:=” := “call” := “if” “fi” := “do” “od” := “” := “-” := := “&” | “|” := := “” := “-” := “+” | “-” := := “*” | “/” | “” := | | “(“ “)” | “” := := “ “” := | | := := “false” | “ture” := | | “_” 从上面的文法中，我们可以得出各语法成分的first和follow集合，这两个集合也是以后进行编译程序编写的关键。First集合beginbeginconst integer Boolean Procconst integer Boolean Procconstinteger Booleaninteger Booleanname arrayProcskip read write name call if doskip read write name call if doskipreadnamewrite- name numeral ( ,namecallifdo- name numeral ( - name numeral ( - name numeral ( & |- name numeral ( - name numeral ( + -name numeral ( * / name numeral ( namename numeralnumeralfalse truenameFollow集合.first(语句部分) first(语句部分) ;first(变量定义) first(过程定义) first(语句部分) follow(定义)first(常量定义) first(过程定义) first(语句部分) follow(定义)first(变量表) follow(变量定义)first(常量定义) first(变量定义) first(语句部分) follow(定义)end;follow(读语句) :=;follow(写语句) follow(赋值语句);fi od follow(警戒命令表), follow(表达式表) - ) first(初等表达式)first(与或运算符) follow(表达式)first(简单表达式)first(关系运算符) follow(初等表达式)first(项)first(加减运算符) follow(简单表达式)first(因子)first(乘除运算符) follow(项), follow(变量访问表) follow(因子)follow(变量访问)follow(常量定义) 2、 PL编译程序的功能要求： (1)分析器读入源程序文件作为输入，逐个扫描字符。识别保留字和专用符号以及名字，把程序正文转化为符号序列，而且用简单值表示符号，定义一个表示这些符号的枚举类型。输出数的时候，在符号名后跟一个整数，即名字索引；是保留字的时候就输出它的顺序值。当扫描器检测到一个不认识的名字时，就输出符号Unknown1。(2)语法分析以PASS1的输出文件作为输入。这个语法分析的过程将识别正确的句子和检测语法错误，根据的文法规则分析程序是否符合Pl文法规则，检查其是否组成PL句子。并做作用域分析，类型分析，并在错误的时候输出错误信息来。最后根据Pl的指令集输出中间代码。(3)代码生成器 代码生成器是为PL计算机生成代码，代码生成有两部分，一个是扩展分析器，输出PL代码，另外一个是汇编器，定义向前引用和代码的优化。代码生成器有4个输出过程，分别输出指令操作码、参数、寻址、以及对应的命令。选择代码优化可以节省更多的空间。(4)解释执行器 解释执行器部分是对所提供的样本程序进行解释执行，前提是前面所有的词法和语法分析、代码生成已经全部通过执行完毕。二、 设计我们的目标是编写一个PL语言的集成IDE环境，它即能编辑PL程序，又可以在集成环境下运行PL程序的目标代码，而且还具应有出错提示等基本功能。1. 总体设计思想我们先来看一下编译程序的一般工作流程。先对高级语言原代码进行词法分析，得到中间代码，然后进行语法分析、语义分析，得到第二个中间代码，接着进行代码优化，得到高效中间代码，再则生成汇编代码，最后是生成可执行的程序代码。我们看到从一个原程序到可执行代码的生成是要经过很多阶段的，所以我们必须用模块化的思想来进行程序设计，不然程序的编写和维护将会变得异常复杂。又由于各功能部分经常是互相调用的，如果用面向过程的思想进行程序设计，那么各函数和过程间的调用次序就变得非常重要了，因为函数和过程必须是先定义后使用的。而且过多的使用全程变量，当程序的复杂性提高时，必将增加程序的出错率。所以我们用面向对象的思想来程序的设计。把每个模块定义成一个类，而由于编译过程的每一步又是在它上一步完成后才能执行的，所以具有一种传递性，这样我们又可以用继承的思想来设计我们的类。模块划分PL编译程序流程词法分析PL原程序语法分析、作用域分析、类型分析及汇编代码生成单词符号序列汇编代码出错处理由于我们的PL语言语法简单，所以我们的编译程序的编译流程可以大大的简化。从下面的流图我们可以看到整个编译流程得到了巨大的简化。首先是省略了代码优化模块，然后是把语法分析、作用域分析、类型分析和汇编代码生成合成在一个模块中，最后把语意分析后的中间代码的生成也省略掉了，而直接生成汇编代码。为了进一步代码的重用性，我们把所有可能重复使用的代码都方在一个单元中ShareCommand。而且定义了一个基类TshareCommand。TshareCommand是实行文件的存取和错误处理。因为这两个处理所以模块都要用到的。把他定义成基类的确是好方法。PSscanTshareCommand所以整个编译程序划分为三个模块，基本处理模块，词法分析模块和语法分析模块（包括代码生成），而每个模块又定义成一个类，分别为TshareCommand、PSscan和Tsyntax。它们的继承关系为：Tsyntax被继承被继承2基本处理模块1文件操作编译程序涉及大量的文件操作，如文件的打开、关闭、读取、写入等等。因此类TshareCommand中有相应的文件操作方法：文件读取操作：procedure TShareCommand.LoadFromFile(FileName: string);文件写入操作：procedure TShareCommand.Emit(Value: integer);2错误处理错误处理涉及的方法有：长度检测：procedure TestLimit(Text1: string); overload;function TestLimit(Length, Maximum: integer):Boolean; overload;错误提示： procedure Error(Kind: TErrorKind); overload; procedure Error(Msg: String); overload;大家可能看有两个TestLimit和Error方法，不要奇怪，这就是面向对象的好处，这里利用了函数名的重载，这样的好处就是对于处理同类信息的方法我们不用定义多个方法名称，这样类的封装性得到了进一步的提高，隐含了更多的细节,提高了系统的可靠性。TshareCommand的完整定义所以TshareCommand的完整定义是：TShareCommand = class PSName: string; LineNo: integer; Emitting, Errors, CorrectLine: Boolean; Input1, Output1, Notes: TextFile; procedure LoadFromFile(FileName: string); procedure TestLimit(Text1: string); overload; function TestLimit(Length, Maximum: integer):Boolean; overload; procedure Emit(Value: integer); procedure Rerun; procedure NewLine(Number: integer); procedure Error(Kind: TErrorKind); overload; procedure Error(Msg: String); overload; private Private declarations public Public declarations end;3。词法分析模块程序编译的第一步就是词法分析，这个任务由类PSscan来完成。他是继承TshareCommand类的，所以他具有了文件操作功能和错误处理功能。我们来看一下他的完整定义。2. PSscan的完整定义 PSScan = class(TShareCommand) procedure Pass1; private Private declarations AlphaNumeric, Digits, EndComment, Invisible, Letters, Separators, SmallLetters, CapitalLetters: TCharSet; ch: char; Characters: integer; Link: TWordPointer; procedure Emit1(Symbol: TSymbolType); procedure Emit2(Symbol: TSymbolType; Argument: integer); procedure BeginLine(Number: integer); procedure EndLine; procedure NextChar; procedure Insert(IsName: Boolean; Text1: string; const Index: integer = -1); procedure Define(IsName: Boolean; Text1: string; Index: integer); procedure Search(Text1: string; var Isname: Boolean; var Index: integer); procedure Initialize; procedure Comment; procedure NextSymbol; public Public declarations end;字符读取词法分析模块逐个字符的读取PL原程序，并用一个控制字符ETX来表示正文的结尾。字符的读取就由方法NextChar负责。它可以跳过除新行符（NL）和正文结束符（ETX）以外的所有不可见字符。扫描对输入的字符进行的处理我们称为扫描。这里我们采用超前读一字符的方法。该功能有NextSymbol负责，具体实现为：启动扫描器时，预先读入原程序的第一个字符每当扫描器识别一个字符为一个特定符号的一部分时，立即读入下一个字符分隔符扫描器跳过每个符号前的任何空格、新行符和注解。分隔符以下列字符开头 Separators := SP, NL, Dollar;在每行末尾，扫描器调用方法EndLine，把行号加1并与符号NewLine一起输出。 while ch in Separators do if ch = SP then NextChar else if ch = NL then begin EndLine; NextChar end else ch = Dollar Comment;注释是以“$”字符开头，直到本行末为止，属于实现起来比较简单procedure TScan.Comment;begin ch = Dollar NextChar; while not (ch in EndComment) do /到本行末尾 NextCharend;专用符号如果读入的是专用符号，如 “”，则立即输出该符号的代码并超前读下一个字符。 Emit1(Plus1); NextChar但对应多字符组成的专用符号，例如 “”就必须如下处理 Nextchar; if ch = then begin Emit1(bracket1); NextChar end else Emit1(LeftBracket1);因子“”和“” 都是以“”开头的，所以必须用超前读下一字符的方法来处理。数字数字的处理只要解决的是数的最大值问题，程序规定数值的绝对值不能超过32767，所以在ShareCommand模块中有一句MaxInt = 32767，具体的算法如下： if ch in Digits then /数字 begin Value := 0; while ch in Digits do begin Digit := ord(ch) - ord(0); if Value = (MaxInt - Digit) div 10 then begin Value := 10 * Value + Digit; NextChar end else begin Error(Numeral3); while ch in Digits do NextChar end end; Emit2(Numeral1, Value) End单词单词的识别，也就是识别保留字和名字。算法如下， if ch in Letters then begin Text1 := ; while ch in AlphaNumeric do /大写小写和数字 begin Text1 := Text1 + ch; NextChar end; Search(Text1, IsName, Index); if IsName then Emit2(Name1, Index) else Emit(Index); end在扫描器输入一个单词时，调用Search查找过程，以便识别他是保留字还是名字。是保留字就输出他的顺序号，是名字就输出符号后跟一个名字索引。由于PL的保留字不多，所以采用线性查找非常理想，而且实现起来也非常简单。在启动扫描器前，首先初始化保留字表，它只是一个简单的指针链，链元素的建立由方法Insert来实现。writearray采用线性查找的符号表方法的调用关系下面我们从整体看看各方法的调用关系。Pass1，主控方法Initialize初始化方法Define， 名字定义BeginLine 开始新行NextChar 读入字符NextSymbol 代码输出EndLine 行结束Search 名字查找Error 错误提示Insert 插入名字Emit2 输出代码Emit 输出代码方法调用关系图4.语法分析模块词法分析结束我们就进而了编译程序的核心模块语法分析模块。这里类Tsyntax是继承类PSscan的，它的完整定义如下3. Tsyntax的完整定义 TSyntax = class(PSScan) SymbolTable: TSymbolTables; Symbol: TSymbolType; LongSymbols, SymbolsSet: TSymbols; SymbolOrd , Argument , LabelNo: integer; /- 以下为作用域分析用 - BlockLevel:integer; Block : TBlockTable; TypeUniversal, TypeInteger, TypeBoolean: TNext; /- procedure Pass2; procedure SLoadFromFile; procedure Init; procedure NextSymbol; procedure Programx(Stop: TSymbols); procedure BlockBody(Stop: TSymbols; var pVarLength, pAddr:integer); procedure Expect(S, Stop: TSymbols); function first(Item:String):TSymbols; function follow(Item:String):TSymbols; procedure DefinePart(Stop :Tsymbols); function Constant(Stop: TSymbols):Integer; procedure SentencesPart(Stop:Tsymbols); procedure SyntaxCheck(Stop: TSymbols); procedure ConstDefine(Stop:Tsymbols); procedure VariableDefine(Stop:Tsymbols); procedure IntAndBool(Typex:TSymbolType; Stop: TSymbols); procedure ProcedureDefine(Stop:TSymbols); procedure SyntaxError(Stop: TSymbols); procedure VarableTable(Typex:TSymbolType; Stop: TSymbols; var pNext:TNext); procedure VarableArray(Typex:TSymbolType; Stop: TSymbols); procedure SkipSentence(Stop: TSymbols); procedure ReadSentence(Stop: TSymbols); procedure WriteSentence(Stop: TSymbols); procedure EvaluateSentence(Stop: TSymbols); procedure ProcedureSentence(Stop: TSymbols); procedure ifSentence(Stop: TSymbols); procedure doSentence(Stop: TSymbols); function VarableAccessTable(Stop: TSymbols):integer; function ExpenssionTable(Stop: TSymbols):integer; procedure alertnessTable(Stop: TSymbols; aBarLab:integer); procedure alertness(Stop: TSymbols; var aErrorLab:integer; aBarLab:integer); procedure expression(Stop: TSymbols); procedure EleExpression(Stop: TSymbols); procedure SimExpression(Stop: TSymbols); procedure Item(Stop: TSymbols); procedure Gene(Stop: TSymbols); procedure VarableAccess(Stop: TSymbols); procedure SubSelector(Stop: TSymbols); /- 作用域分析用 - procedure IsDefine(aName: integer; var aNext: TNext); procedure Search(pName, LevelNo: integer; var Found: Boolean; var aNext: TNext); procedure Define(pName: integer; Kind: TKind; var aNext: TNext); procedure StandardBlock; procedure NewBlock; procedure EndBlock; procedure ExpectName(var pName: Integer; Stop: TSymbols); /- 代码生成用 - function newlabel:integer; procedure DefArg(pLable, pValue:integer); procedure SEmit(AR: array of integer); procedure SaveToFile; private Private declarations VarCount, ExpCount:integer; /- for build code - St : Array TableBottom.TableTop of integer; Address:integer; /语句地址 public Public declarations end;从它的定义的长度我们也见它的复杂性了。为了分析的方便，我们先假设现在只进行语法分析，而不关词法、作用域和汇编代码的生成。下面我们先来看看符号的输入。符号输入符号的输入由方法NextSymbol是实现。他的基本思想是：读入一个字符直到他不是NewLine为止，如果它是名字或数字，就读入他的值。procedure TSyntax.NextSymbol;begin /读一个数字进来 Read(Input1, SymbolOrd); /符号转换,看读进来的是什么符号 /Symbol: TSymbolType; 所有符号的集合 Symbol := TSymbolType(SymbolOrd); while Symbol = NewLine1 do begin /跳过新行 Read(Input1, LineNo); NewLine(LineNo); Read(Input1, SymbolOrd); Symbol := TSymbolType(SymbolOrd); end; /是Name或者是Numeral1则读他的值 if Symbol in LongSymbols then begin Read(Input1, Argument); if Symbol = Name1 then if TSymbolType(Argument) in SymbolsSet then Symbol := TSymbolType(Argument); end; DONE : LongSymbols需要初始化 end;由于现在读入的是词法分析的中间代码，而它们肯定是以EndText结束的，所以，在这里就不必调用函数EOF来确定是否到达输入的末尾。当到达EndText符号时，输入正好结束。分析器的构造现在我们的主要任务是构造一组词法分析的规格，然后用这些规则进行语法的分析。在改造这组规则之前，我们先定义这样一个过程a（E），它检查一个或多个符号，并且判定它们是否构成有语法表达式E描述的句子。如果是，则输入整个句子以及下一个语法单位的头符号，否则在输入若干个符号之后输出语法错误信息。好下面我们看看这组词法分析规则：l 规则1：对于每条BNF规则 N := E，分析器定义一个同名过程l 规则2：对形如F1，F2，Fn的句子序列的识别是按照书写次序每次一个的扫描各个来实现：a（F1F2Fn） a（F1）；a（F2）；a（Fn）；l 规则3：当分析器期待一个后跟Stop符符号S时，它就调用过程Expecta（S，Stop） Expect（S，Stop）l 规则4：为了识别由BNF规则N描述的句子，分析器调用相应的过程N，并用句子的Stop符集作为参数：a(N，Stop) N（Stop）l 规则5：分析器使用下述算法识别形式E的后面跟一个Stop符的句子a( E ) , Stop ) = SyntaxCheck( First(E) + Stop ) if Symbol in First(E) then a(E, Stop)l 规则6：分析器使用下述算法识别形式 E 的后面跟一个Stop符的句子a( E ) , Stop ) = SyntaxCheck( First(E) + Stop ) while Symbol in First(E) do a(E, First(E) + Stop)l 规则7：如果形式T1，T2，Tn的所有句子都是非空的，下述算法将识别形式T1 | T2 | | Tn 的后面跟一个Stop符的句子a(T1 | T2 | | Tn , Stop) = if Symbol in First(T1) then a(T1, Stop) else if Symbol in First(T2) then a(T2, Stop) else if Symbol in First(Tn) then a(Tn, Stop) else SyntaxError（Stop）如果任一Ti句子可能是空的，用SyntaxCheck(Stop)置换算法末尾的错误报告。l 规则8：下述算法识别形式F的后面跟一个Stop符的一个或多个句子a(F F, Stop) = a(F, First(F) + Stop); while Symbol in First(F) do a(F, First(F) + Stop)l 规则9：下述算法识别形式F的一个或多个句子，句子中间有符号s分隔，还有一个Stop符跟在最后a(F sF , Stop) = a(F, s + Stop); while Symbol = s do beginExpect(s, First(F) + s + Stop);a(F, s + Stop); end;这组规则知道后，我们首先来看规则中提到的几个方法，然后再研究如何使用这组规则来进行语法分析。l 期待函数Exoect它的作用前面已经说过了，现在只是给出它完整的定义procedure TSyntax.Expect(S: TSymbols; Stop: TSymbols); /+begin if Symbol in S then NextSymbol /是期望值则读入下一个 else SyntaxError(Stop); /否则语法错误 SyntaxCheck(Stop)end;检查当前符号后，分析器总是确保下一个符号是所期待的Stop符之一。这个任务有SyntaxCheck方法来完成。l 语法检查函数SyntaxCheckprocedure TSyntax.SyntaxCheck(Stop: TSymbols);begin if not (Symbol in Stop) then SyntaxError(Stop)end;一个语法错误之后，分析器跳过输入直到达到Stop符之一为止，而出错信息由SyntaxError来处理。l 出错处理函数SyntaxError procedure TSyntax.SyntaxError(Stop: TSymbols);begin Error(Syntax3); while not (Symbol in Stop) do NextSymbolend;好下面我们来看看如何运用上面的9条规则来构造我们的语法分析器。对于规则1，它只是让我们在编写程序时思路更清晰而已，例如“程序”的分析过程，可定义为procedure TSyntax.Programx;。现在我们来考察一下PL的BNF语法。拿“分程序”来看看 := “begin” “end”这完全复合规则2，所以分程序的分析过程可以写成下面的样子 procedure TSyntax.BlockBody;begin /识别begin Expect(begin1, first(定义部分)+first(语句部分)+end1+Stop); /定义部分 DefinePart(Stop); /语句部分 SentencesPart(Stop); /识别end Expect(end1, Stop);end;我们继续考察其他语法成分，分析它们均可以套用上面的规则。这样按照上面的样子，我们很容易就可以写出一个PL的语法分析的框架来了。那First（s）如何处理呢？其实这就是前面提到的first跟follow集合的问题，幸好我们把它们写成了两个函数，只要直接调用就行了，非常方便。这样看来我们只要套用上面的规则就可以完成语法分析了。情况的确如此！那该阶段没有中间代码输出，我们有如何检查它是否正确呢？语法分析测试当程序能完成语法分析，并报告正确的语法错误，那么我们就假定它是正确的。同样我们用强制分析器执行每条语句至少一次的方法来设计我们的测试用例。同时