(基于Java)编写编译器和解释器-第9章:解析声明-第一部分(连载)

时间:2021-08-01 17:09:05

本章你将会解析声明(declarations)。因为所有申明的信息都会放到符号表,所以这章也是第4章的一个延续。

==>> 本章中文版源代码下载:svn co http://wci.googlecode.com/svn/branches/ch9/ 源代码使用了UTF-8编码,下载到本地请修改!

目标与方法

本章有以下目标:

  • 前端处理Pascal常量定义类型定义变量声明类型说明的解析器。
  • 在符号表中加入类型信息。

方法将是开发新的类表现Pascal类型信息,并分别放在intermediate,intermediate.symtabimpl和intermediate.typeimpl包中。为验证你的代码,你会扩展第4章开发的使用工具CrossReferencer使之包含类型信息。

程序语言的申明对解析来说通常是最难搞的一些语句,因为:

  • 声明语句语法本身可以很难。
  • 声明通常包含递归定义。
  • 你得hold住各式各样的信息。
  • 你得在符号表放置很多很多很多的东西。

Pascal声明(Declarations)

Pascal申明包含四个部分(本书不处理标识申明label delcaration,因为去掉了goto,也不处理集合和指针类型,这留给你实践吧)。每个部分都可以没有但它们的顺序不能乱,分别是:常量定义部分(constant),类型定义部分(type),变量申明部分以及过程和函数申明(procedure and function)部分。这章只讲前三部分,你会在11章中解析过程和函数申明。语法图9-1显示出Pascal申明有一个相对来说比较明了的语法。

图9-1:Pascal声明语法

(基于Java)编写编译器和解释器-第9章:解析声明-第一部分(连载)
留意常量和类型是“定义”的,而变量,过程以及函数是“声明”的。我们把定义和声明语句统称为“声明”(declarations)。

一个Pascal常量定义由1个标识符紧接着等于号"="和一个常量组成。看下面的常量定义部分的例子:

   1: CONST
   2:     factor = 8;
   3:     epsilon = 1.0e-6;
   4:     ch = 'x';
   5:     limit = -epsilon;
   6:     message = 'Press the OK button to confirm your selection.';

一个Pascal类型定义包含一个标识符,然后是一个等于号"="加一个类型说明(type specification)。一个简单的类型说明可以是先前定义过的类型标识符,一个枚举类型说明,一个其基础类型为枚举类型的子界(subrange)说明或一个非实(non-real,意思实际上是非浮点数,只是整数)标量类型。下面是类型定义部分的例子:

   1: TYPE
   2:     range1 = 0..factor; {subrange of integer}
   3:     range2 = 'a'..'q';  {subrange of char}
   4:     range3 = range1;    {type identifier}
   5:  
   6:     grades  = (A, B, C, D, F);  {enumeration}
   7:     passing = A..D;             {subrange of enumeration}
   8:  
   9:     week    = (monday, tuesday, wednesday, thursday, friday, saturday, sunday);
  10:     weekday = monday..friday;
  11:     weekend = saturday..sunday;
一个数组类型说明有一个索引类型和一个元素类型。索引类型必须是一个子界或枚举类型,元素类型可以是任何Pascal类型。数组可以使多维的。看数组类型定义的例子:
   1: ar1 = ARRAY [grades] OF integer;
   2: ar2 = ARRAY [(alpha, beta, gamma)] OF range2;
   3: ar3 = ARRAY [weekday] OF ar2
   4: ar4 = ARRAY [range3] OF (foo bar, baz);
   5: ar5 = ARRAY [range1] OF ARRAY [range2] OF ARRAY[c..e] OF enum2;
   6: ar6 = ARRAY [range1, range2, c..e] OF enum2;

上面可以看到ar5和ar6两种等效的定义多维数组的方式。每一维可以象ar5一样显式指定,或者象ar6的把维度值合并在一起(也就是C,Java等语言的方式)。

Pascal字符串类型是一个字符数组,且其索引类型是一个最小值为1的整数子界(subrange)。下面的类型str是一个长度为10的字符串(这个我估计用的很少吧,定长字符串,很恶心的)。

   1: str = ARRAY [1..10] OF char;

一个Pascal记录(record)类型说明由包含在关键字RECORD和END之间的域申明构成。每个记录域(record field)可以是任何Pascal类型,包括其它的记录类型。一个冒号将域标识符列表与其类型隔开。(Pascal记录类型和C语言的Struct类型很像,但是本书不处理记录类型的变种和WITH语句)。举两个例子:

   1: rec1 = RECORD
   2:            i : integer;
   3:            r : real;
   4:            b1, b2 : boolean;
   5:            c : char
   6:        END;

第二个:

   1: rec2 = RECORD
   2:               ten : integer;
   3:               r : rec1;
   4:               a1, a2, a3 : ARRAY [range3] OF range2;
   5:           END;

注意rec2的域r的类型是记录类型rec1

Pascal变量申明语法与记录域的申明类似,看变量申明部分的例子:

   1: VAR
   2:     var1 : integer;
   3:     var2, var3 : range2;
   4:     var4 : ar2
   5:     var5 : rec1;
   6:     direction : (north, south, east, west);

Pascal支持匿名(unnamed type)类型。在上面演示过的类型ar2,它的索引类型就是一个匿名枚举类型。同理,在类型ar5和ar6的定义中,第三维的索引类型是一个匿名子界类型。记录类型rec2的域a1,a2,a3的类型是一个匿名数组类型。变量direction的类型是一个匿名枚举类型。

类型和符号表

你将要编写的类型说明解析器将会在符号表中放入类型信息。

设计笔记

就像你在第4章做的那样,我们再一次从概念层面上着手。首先,设计一组语言无关的接口,将类型说明简单当成一个属性集合。在这些属性中,一个类型说明有一个格式,或许还有一个类型标识符。之后,开发Pascal相关的接口实现。

类型说明接口

图9-2 展示了intermediate包中相关接口TypeSpec,TypeForm,TypeKey的UML类图。

方法getForm()返回类型的格式,诸如标量,数组,和记录。方法getIdentifier()返回类型标识符对应的符号表项,或者null值假如类型匿名。所有其它的类型说明信息象属性值一样通过setAttribute()和getAttribute()方法存取。方法isPascalString()标识当前类型是否一个Pascal字符串。baseType()方法如果当前类型是子界类型则返回其基础类型,否则返回它本身。

(基于Java)编写编译器和解释器-第9章:解析声明-第一部分(连载)

清单9-1,9-2,9-3 分别展示TypeSpec,TypeForm和TypeKey的内容,请参考源代码对应类,这里不再显示

Pascal类型说明实现

前面提到,一个Pascal类型的格式可以是标量,枚举,子界,数组或者记录。下面的表格展示了对每一种类型格式来说,解析器该抽取什么样的类型说明信息。

类型格式 类型说明信息(要抽取的)
标量
枚举 枚举常量标识符列表
子界 基础类型
  下界值
  上界值
数组 索引类型
  最小索引值
  最大索引值
  元素类型
  元素数量
记录 一个独立的符号表服务于记录域的标识符

类型说明信息都以属性方式存取。

清单9-4 展示了包intermediate.typeimpl中的枚举类型(注意,这个是Java的) TypeFormImpl即Pascal的TypeForm接口实现。它的枚举值对应上表中的第一列。

   1: public enum TypeFormImpl implements TypeForm
   2: {
   3:     SCALAR /*标量*/,
   4:     ENUMERATION/*枚举*/, 
   5:     SUBRANGE/*子界*/, 
   6:     ARRAY /*数组*/, 
   7:     RECORD/*记录*/;
   8:  
   9:     public String toString()
  10:     {
  11:         return super.toString().toLowerCase();
  12:     }
  13: }

清单9-5 展示了包intermediate.typeimpl中的枚举类型TypeKeyImpl即接口TypeKey的Pascal相关实现。其枚举值对应上表中的第二列。

   1: public enum TypeKeyImpl implements TypeKey
   2: {
   3:     //枚举的属性
   4:     ENUMERATION_CONSTANTS,
   5:  
   6:     // 子界的属性
   7:     SUBRANGE_BASE_TYPE/*基础类型*/, SUBRANGE_MIN_VALUE/*下界*/,
   8:     SUBRANGE_MAX_VALUE/*上界*/,
   9:  
  10:     // 数组属性
  11:     ARRAY_INDEX_TYPE/*索引类型*/, ARRAY_ELEMENT_TYPE/*元素类型*/,
  12:     ARRAY_ELEMENT_COUNT/*元素个数*/,
  13:  
  14:     // 记录
  15:     RECORD_SYMTAB /*记录对应的符号表*/
  16: }

就如你在前面针对符号表项(第四章)和分析树节点(第五章)做的那样,将每种类型说明(TYpe SPecification)实现成哈希表可带来极大方便。清单9-6 展示了包intermediate.typeimpl中的类TypeSpecImpl的关键方法,它是TypeSpec接口的Pascal相关实现。更详细参见源代码。

   1: public class TypeSpecImpl
   2:     extends HashMap<TypeKey, Object>
   3:     implements TypeSpec
   4: {
   5:     private TypeForm form; //对应格式
   6:     private SymTabEntry identifier;  //类型标识符
   7:  
   8:     public TypeSpecImpl(TypeForm form)
   9:     {
  10:         this.form = form;
  11:         this.identifier = null;
  12:     }
  13:     //特殊的对String的处理
  14:     public TypeSpecImpl(String value)
  15:     {
  16:         this.form = ARRAY;
  17:  
  18:         TypeSpec indexType = new TypeSpecImpl(SUBRANGE);
  19:         indexType.setAttribute(SUBRANGE_BASE_TYPE, Predefined.integerType);
  20:         indexType.setAttribute(SUBRANGE_MIN_VALUE, 1);
  21:         indexType.setAttribute(SUBRANGE_MAX_VALUE, value.length());
  22:  
  23:         setAttribute(ARRAY_INDEX_TYPE, indexType);
  24:         setAttribute(ARRAY_ELEMENT_TYPE, Predefined.charType);
  25:         setAttribute(ARRAY_ELEMENT_COUNT, value.length());
  26:     }
  27:  
  28: //一个Pascal String首先必须得是个数组(注意char和int的互转)
  29:     public boolean isPascalString()
  30:     {
  31:         if (form == ARRAY) {
  32:             TypeSpec elmtType  = (TypeSpec) getAttribute(ARRAY_ELEMENT_TYPE);
  33:             TypeSpec indexType = (TypeSpec) getAttribute(ARRAY_INDEX_TYPE);
  34:  
  35:             return (elmtType.baseType()  == Predefined.charType) &&
  36:                    (indexType.baseType() == Predefined.integerType);
  37:         }
  38:         else {
  39:             return false;
  40:         }
  41:     }
  42:  
  43:     /**
  44:      * @return 是子界则返回基类型,否则返回本身
  45:      */
  46:     public TypeSpec baseType()
  47:     {
  48:         return form == SUBRANGE ? (TypeSpec) getAttribute(SUBRANGE_BASE_TYPE)
  49:                                 : this;
  50:     }
  51: }

这儿有两个构造函数。第一个给定一个格式创建一个“空”TypeSpec对象。第二个构造函数为一个String(Java的)对象创建相应的TypeSpec对象。本章开头说过,一个Pascal 字符串类型是一个带 子界索引类型的字符数组,就象isPascalString()方法验证的那样。此构造函数创建一个带整数子界索引类型且值范围从1到字符串(Java的)长度的字符数组。

图9-3 展示了针对几个Pascal类型定义样例其中符号表项和TypeSpec对象之间的关系。值得留意的有:

  • 类型标识符的符号表项指向相应的TypeSpec对象,而它反过来指向这个符号表项。不过匿名类型的类型说明(比如图中的匿名数组索引类型)没有指向任何符号表项。
  • 枚举类型说明的ENUMERATION_CONSTANTS属性是其常量标识符所对应的符号表项形成的数组列表。
  • 字节类型说明有SUBRANGE_MIN_VALUE和SUBRANGE_MAX_VALUE属性,它的SUBRANGE_BASE_TYPE属性值为其基本类型说明。
  • 数组类型说明的ARRAY_INDEX_TYPE和ARRAY_ELEMENT_TYPE属性分别是数组索引和数组元素的类型说明。
  • 记录类型说明的RECORD_SYMTAB属性指向包含此记录域标识符的符号表

(基于Java)编写编译器和解释器-第9章:解析声明-第一部分(连载)

图9-3:各种类型定义下SymTabEntry对象(淡灰色)和TypeSpec对象(暗灰色)。TypeKeyImpl属性键名以斜体大写呈现。

类型工厂

清单9-7 展示了包intermediate中的类TypeFactory,它创建TypeSpec对象。它有两个静态方法为别对应TypeSpecImpl的不同构造函数

设计笔记

此时再次使用“工厂方法”设计模式,使得类型说明客户端保持对具体类型说明实现的松耦合。


清单9-7 类型工厂的代码

   1: public class TypeFactory
   2: {
   3:     public static TypeSpec createType(TypeForm form)
   4:     {
   5:         return new TypeSpecImpl(form);
   6:     }
   7:  
   8:     public static TypeSpec createStringType(String value)
   9:     {
  10:         return new TypeSpecImpl(value);
  11:     }
  12: }

作用域(scope)和符号表堆栈

作用域(scope)指的是源程序的某部分,在此范围内,某些标识符能被使用(换句话说,是程序中使得哪些标识符生效的任何位置)。也可以说任何一个标识符都有一个作用域或属于一个作用域。作用域与嵌套层次和符号表堆栈(第四章有给过简要介绍)关系紧密。

Pascal有很多命名语言预定义元素的标识符,比如各种类型如integer、real、boolean、char和布尔常量true和false。在后面章节中,你将会碰到命名预定义函数的标识符如writeln。默认情况下,预定义的全局标识符的作用域是整个程序(程序可以有1个或多个文件构成)。他们被隐式的定义在嵌套层0作用域即全局作用域。程序的名字同样在这个嵌套层定义。

本章之前你仅仅碰到过只有一个符号表的符号表堆栈,它在嵌套层0,也就是把所有的标识符都当作了全局标识符。实际上在一个程序的最顶层定义的所有标识符(常量名,类型,变量,函数过程等)是在嵌套层1即程序域(program scope)。(目前有两个作用域了,一个全局作用域 global scope,一个程序作用域 program scope)

每一个Pascal记录定义为它的域标识符创建一个新的作用域。这个新域的嵌套层次比记录定义本身所在的作用域层次高一级。嵌套的记录定义创建更高的嵌套层级。类似的你将在第11章看到,每一个声明过的Pascal过程或函数创建的新作用域嵌套层次取决于函数的嵌套深度。

标识符可以被嵌套作用域重定义(也就是覆盖)。例如,一个程序可能定义了名为str,类型为string的标识符。但程序还可有一个记录(record)定义了str为一个域(field)的名字。在记录的嵌套域中,作为域重定义的str有效,而外部程序域中的str定义被隐藏。但是在记录之外,也就是程序域中,str的定义是作为一个字符串类型应用的。

这个讨论带来两个重要问题:

  • 每个作用域必须有它自己单独的符号表。对于全局标识符在嵌套层0上有一个符号表。程序作用域也有一个符号表在层级1存储它包含的标识符。每个记录定义有一个符号表存储她的域标识符。每个函数(routing,包含过程和函数)针对它的标识符都有独立的符号表。
  • 当解析器从上直下分析源程序时,它将进入和退出作用域(比如进入一个函数,返回一个函数),所以这些作用域最好将在符号表上维护。每次解析器进入一个作用域,它必须把此域的符号表放如堆栈,且将嵌套层次加1。当解析器退出此作用域时,它必须将堆栈上的此域对应的符号表弹出,且将嵌套层次减1。符号表堆栈将随着解析器进入更深的嵌套而增长。

图9-4 演示了符号表堆栈的概念,解析之前的符号表堆栈已经随着RECORD类型形成(注意这个RECORD是源程序中RECORD字符,意思是到RECORD这已经形成了堆栈的层级关系)。预定义的全局标识符如integer、real、程序名称Test在层级0的符号表。程序作用域定义的标识符比如epsilon和rec在层级1的符号表。RECORD类型说明推入一个层级为2的新符号表到堆栈上,它包含域标识符a,x,y,z,这个符号表在解析器完成RECORD类型解析之后将会被弹出。

(基于Java)编写编译器和解释器-第9章:解析声明-第一部分(连载)
第4章中已经编写了包intermediate中的接口SymTabStack。现在加几个新的方法用来推入(push)和弹出符号表,以及存取程序标识符,就如清单9-8显示的那样。

   1: /**
   2:  * 存取程序标识符
   3:  * @param entry
   4:  */
   5: public void setProgramId(SymTabEntry entry);
   6: public SymTabEntry getProgramId();
   7: /**
   8:  * 推入一个新的符号表
   9:  * @return 刚创建的
  10:  */
  11: public SymTab push();
  12: /**
  13:  * 推入一个已存在的符号表
  14:  * @param symTab
  15:  * @return
  16:  */
  17: public SymTab push(SymTab symTab);
  18: /**
  19:  * 弹出符号表,层级减1
  20:  * @return
  21:  */
  22: public SymTab pop();

方法setProgramId()和getProgramId针对的是主程序标识符对应的符号表项。方法push()和pop()分别从符号表堆栈上推入和弹出符号表。这儿有两个push方法,一个创建一个新的符号表而另外一个推入现存符号表。

包intermediate.symtabimpl中的类SymTabStackImpl必须包含一个新的域:

//主程序标识符的符号表项
private SymTabEntry programId;
清单9-9 展示了类SymTabStackImpl中的新方法push()和pop()的实现,还有一个新版本的lookup()方法。
   1: public SymTabEntry lookup(String name)
   2:  {
   3:       SymTabEntry foundEntry = null;
   4:       // 搜索当前及更高层级(父层级)
   5:       for (int i = currentNestingLevel; (i >= 0) && (foundEntry == null); --i)
   6:       {
   7:           foundEntry = get(i).lookup(name);
   8:       }
   9:  
  10:       return foundEntry;
  11:  }
  12:  @Override
  13:  public SymTabEntry getProgramId() {
  14:      return this.programId;
  15:  }
  16:  @Override
  17:  public void setProgramId(SymTabEntry entry) {
  18:      this.programId = entry;        
  19:  }
  20:  public SymTab push()
  21:  {
  22:      SymTab symTab = SymTabFactory.createSymTab(++currentNestingLevel);
  23:      add(symTab);
  24:  
  25:      return symTab;
  26:  }
  27:  public SymTab push(SymTab symTab)
  28:  {
  29:      ++currentNestingLevel;
  30:      add(symTab);
  31:  
  32:      return symTab;
  33:  }
  34:  public SymTab pop()
  35:  {
  36:      SymTab symTab = get(currentNestingLevel);
  37:      remove(currentNestingLevel--);
  38:  
  39:      return symTab;
  40:  }
两个push()方法都会增加提高嵌套层级而pop()方法降低层级。方法lookup现在不仅搜索当前作用域,如有必要还包括父作用域( 包含此所用域的更大一级的作用域)。它从栈订的符号表里开始搜索某个标识符,一直到包含这个标识符的符号表位置,或者找不到返回。换句话说,方法先在当前作用域搜寻这个标识符,如有必要,一级一级的扩散它的作用域范围( 直到全局作用域,即嵌套层级为0的那个)。