（基于Java）编写编译器和解释器-第二章：初始框架-Part-1

发表于 | 更新于: | 分类于 | 阅读次数:
字数统计: 4,865 字 | 阅读时长 ≈ 20 分钟

本章将会从前一章的概念设计带你到初级的实现过程。你将先为编译器和解释器构造一个灵活的框架，接着将初级版的编译器解释器组件集成到框架中。最后编写端对端的测试用例检验这些框架和组件。

目标和方法

此章的设计方法首先会让你觉得过于繁琐啰嗦，的确，本章结束后将会有一大堆超过你预期数量的代码。但请记你在用早被证明的软件工程法则和优秀面向对象设计构建编译器和解释器。

如在概念设计中描述的那样，编译器和解释器将尽可能复用组件，因只有后端有所不同。在这章中，你将构建一个灵活的框架并首先放置那些已被深度简化的编译器和解释器组件。不过它们足够验证你设计的框架是否恰当即组件能很好的耦合并能协同工作。这个成功前提将会使得从公用前端到编译器解释器后端的端对端执行代码编写，还有后续的增量式组件开发变得简单。

本章的目标是：

  • 一个语言无关的框架，可支持编译器和解释器。
  • 集成进框架前端(front end)的初级版Pascal语言相关组件。
  • 集成进框架后端(back end)的初级版编译器和解释器组件。
  • 通过从公共前端生成源程序清单以及从编译器或解释器后端生成消息，简单的运行端对端测试，测试相关组件。

设计笔记：
不管任何时候开发负责程序如编译器或解释器，成功的首要步骤是：

  • 设计和实现一个合适的框架。
  • 开发能与框架良好集成的初级组件，且这些组件也能良好集成在一起。
  • 通过运行简单端对端代码来测试框架和组件的融合程度。

早期的组件集成是关键，甚至你已经简化了初级组件(没有完善的组件称之为初级组件）也一样。尽可能早的测试矿建和组件以让它们更好的协作。框架和初级组件组成你后续开发的基础。开发将是增量式的进行，代码在每次增量后都能继续工作（附加更多功能）。你该永远基于可运行的代码去构建。

语言无关的框架组件

基于概念设计，框架包含三个包：frontend、intermediate、 backend。

框架组件是用来定义框架且语言无关的接口和类。有些是抽象类。一旦框架组件就绪，你能开发抽象类的Pascal实现（组件语言无关，实现语言相关）。图2-1 展示了使用UML 包和类图的框架组件。
下图在frontend，intermediate，backend包中的语言无关组件一起定义了一个能支持编译器和解释器后续开发的框架。

图2-1

设计笔记：统一建模语言是一个工业级的展示面向对象软件架构和过程的图形化语言。各种图表(序列图，类图等）能表示程序的结构组件之间的静态关系，也能表示组件运行期的动态行为。

前端

在前端包中，语言无关类Paser，Scanner，Token，Source代表框架组件。框架类强制你在忽略具体源语言的情况下，能尽力思考每个前端组件的职责，还有它们之间的交互。图2-2中的UML 类图展示了它们的关系。

图2-2

Parser和Scanner是抽象类；语言相关的子类将实现它们的抽象方法。parser和scanner联系紧密，Parser有一个受保护域(protected field)scanner指向Scanner。Parser从Scanner请求token，所以它依赖Token。Scanner有一个私有域currentToken，它通过受保护域source引用Source，还将source引用传给每个自己构造的token。每个Token也能通过受保护域source拥有Source引用，在它的构造过程中，通过source读取字符。
下面的类图更进一步展示了四个前端框架类。它展示了域，方法和其他的前端类和接口。例如每个Token有一个用TokenType类表示的token类型，EofToken是Token的子类。

图2-3

按照概念设计，parser控制翻译过程，它翻译源程序，所以Parser类有一个抽象方法parser()；语言相关的方法实现将不断的找scanner索取下一个token。Parser的currentToken()和nextToken()仅仅是scanner的代理方法而已(参考代理模式，不过这儿是为了少写点代码）。语言相关的getErrorCount()方法实现返回语法错误数量。

设计笔记：在UML类图中，一个未填充箭头的箭号表示一个类引用或依赖另一个类。虚线箭号(比如从Parser到Token的肩头)表示一个仅仅在方法调用期间(比如Parser的nextToken()方法返回一个Token对象）存在的引用。实线箭号且在出发端有一个空菱形意味着一个类通过在对象生命周期持续的引用，拥有(owns)或聚合(aggregates)另一个类。(假设类A通过引用域ref聚合类B，那么类A的对象a1聚合类B的对象b1的这种关系在a1的生命周期一直存在，聚合相当于包含，a1负责b1的生命周期)。 域名称保存标识箭头的引用（例如，Parser类用它的scanner域维护对Scanner类的引用)。
实心箭号带空箭头（如EofToken类到Token类)表示一个子类到它的父类。
类名称下，一个类图可选择的包含域(field)描述区域和方法描述区域。标识箭号名称的域名不在域描述区域出现(Parser有个域scanner引用类Scanner，它不在Parser的域描述区域出现，在生成代码后就会有）。在域名或者方法名前面的字符表明访问控制。

  • +：public 公共
  • -：private 私有
  • #：protected 受保护
  • ~：package 包权限，即此包中的其它类都可以访问。
    跟在域名或方法名冒号后面的分别是域类型或者返回值类型。为省地方，类图通常不显示构造函数和域名的getter和setter方法。
    抽象类名以斜体出现。抽象方法名还是斜体。

scanner从源程序中抽取token。Scanner类抽象方法extractToken()的语言相关实现将会根据具体语言从Source中读取字符，以便构造Token。Scanner的快捷方法currentChar()和nextChar()会调用Source类中的对应方法(还是代理模式)

Token的域保存有关Token的有用信息，包括类型，文本串（即字面上的字符串），值和它在源程序中的位置（行号和位置【相对于行】)。Token同样有Source类的快捷方法currentChar()和nextChar()。Token类型与具体语言有关。当前的Token类型是一个占位符(因为一个具体类型都没有)。

后面你将会根据具体语言创建语言相关的Token子类。但目前只有语言无关EofToken子类，它表示源文件终止。使用Token子类使得scanner代码更加模块化，因为不同类型Token需要不同计算方式。（原文是算法，我认为谈不上算法）。

Parser

清单2-1 展示了框架抽象类Parser的关键方法。语言相关的Parser子类要实现parse()方法和getErrorCount()，分别用来表示源程序分析过程和返回语法错误。如上文提到的，Parser的currentToken()和nextToken()方法是scanner对应方法的代理。

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
36
37
38
1: /**
 2:  * <p>语言无关的Parser，有子类完成具体语言解析</p>
 3:  */
 4: public abstract class Parser implements MessageProducer
 5: {
 6:     protected static SymTab symTab = null;                  // 生成的符号表
 7:
 8:     protected final Scanner scanner;  // 扫描器SCANNER，Parser找它要token
 9:     protected ICode iCode;      // 语法树根节点。
10:
11:     protected Parser(Scanner scanner)
12:     {
13:         this.scanner = scanner;
14:         this.iCode = null;
15:     }
16:     /**
17:      * 交由子类完成具体语言相关的解析过程，这个方法调用之后将会产生符号表和中间码iCode。
18:      * @throws Exception
19:      */
20:     public abstract void parse()
21:         throws Exception;
22:     /**
23:      * @return 解析过程中的错误数
24:      */
25:     public abstract int getErrorCount();
26:
27:     public Token currentToken()
28:     {
29:         return scanner.currentToken();
30:     }
31:
32:     public Token nextToken()
33:         throws Exception
34:     {
35:         return scanner.nextToken();
36:     }
37:     //.....
38: }

因为前端只会产生一个符号表SymTab，所以符号表在Parser中以symTab域出现。

Source类

清单2-2 展示了框架类Source的关键方法。

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
  1: /**
  2:  * <p>此框架类的每个对象代表一个源文件</p>
  3:  */
  4: public class Source implements MessageProducer
  5: {
  6:     // 行结束符，注意在Windows平台上，默认行结束符是\r\n，
  7:     //如果用记事本之类的写的pascal源程序，可以使用Ultraedit之类的给转成Unix格式的。
  8:     public static final char EOL = '\n';
  9:     //文件结束标识
 10:     public static final char EOF = (char) 0;
 11:     //源程序reader
 12:     private final BufferedReader reader;
 13:     private String line;
 14:     private int lineNum;
 15:     private int currentPos;                   // 当前行相对位置，不是整个文件的offset！！
 16:     public Source(BufferedReader reader)
 17:         throws IOException
 18:     {
 19:         this.lineNum = 0;
 20:         this.currentPos = -2;  // 设置为-2表示文件一行都没有读，后面的判断可以根据是否等于-2读文件第一行。
 21:         this.reader = reader;
 22:         this.messageHandler = new MessageHandler();
 23:     }
 24:
 25:     /**
 26:      * @return 要去读的字符
 27:      * @throws Exception(read过程中的异常)
 28:      */
 29:     public char currentChar()
 30:         throws Exception
 31:     {
 32:         // 第一次读?
 33:         if (currentPos == -2) {
 34:             readLine();
 35:             return nextChar();
 36:         }
 37:
 38:         // 文件结束?
 39:         else if (line == null) {
 40:             return EOF;
 41:         }
 42:
 43:         // 行结束?
 44:         else if ((currentPos == -1) || (currentPos == line.length())) {
 45:             return EOL;
 46:         }
 47:
 48:         // 超过一行，换一行再读
 49:         else if (currentPos > line.length()) {
 50:             readLine();
 51:             return nextChar();
 52:         }
 53:
 54:         // 正常读取当前行的某一列的字符
 55:         else {
 56:             return line.charAt(currentPos);
 57:         }
 58:     }
 59:
 60:     /**
 61:      *位置游标前进一步并返回对应的字符，记住source的位置游标<b>从来不后退，只有向前操作。</b>
 62:      * @return 下一个要读取的字符
 63:      * @throws Exception
 64:      */
 65:     public char nextChar()
 66:         throws Exception
 67:     {
 68:         ++currentPos;
 69:         return currentChar();
 70:     }
 71:
 72:     /**
 73:      * 探测下一字符，位置游标不增加，跟Stack（栈）的Peek方法一样效果。
 74:      * @return 当前位置的字符
 75:      * @throws Exception
 76:      */
 77:     public char peekChar()
 78:         throws Exception
 79:     {
 80:         currentChar();
 81:         if (line == null) {
 82:             return EOF;
 83:         }
 84:
 85:         int nextPos = currentPos + 1;
 86:         return nextPos < line.length() ? line.charAt(nextPos) : EOL;
 87:     }
 88:     /**
 89:      * 读入一行
 90:      * @throws IOException
 91:      */
 92:     private void readLine()
 93:         throws IOException
 94:     {
 95:         line = reader.readLine();
 96:         currentPos = -1;
 97:         //如果读成功，行数+1
 98:         if (line != null) {
 99:             ++lineNum;
100:         }
101:         //每成功读入一行，将当前行数和当前行文本内容以消息方式广播，方便监听器处理。
102:         if (line != null) {
103:             sendMessage(new Message(SOURCE_LINE,
104:                                     new Object[] {lineNum, line}));
105:         }
106:     }
107:     public void close()
108:         throws Exception
109:     {
110:         if (reader != null) {
111:             try {
112:                 reader.close();
113:             }
114:             catch (IOException ex) {
115:                 ex.printStackTrace();
116:                 throw ex;
117:             }
118:         }
119:     }
120:     //more ignored
121: }

构造函数的参数是一个给Source使用的BufferdReader（I/O类用来按字符读取源程序文件）。你将会看到通过源文件创建BufferedReader是件很Easy的事情。你也可通过其它对象如路径串创建BufferedReader。BufferedReader是一个抽象类。你肯定不想Source类操心到底源程序文本内容怎么来的（找bufferedReader即可)。

方法currentChar()干了大部分事情，先前的调用会让它会调用readLine()方法读取第一行，则currentChar()返回这行的第一个字符。在后续的调用中，如果当前位置在行尾，它返回特别的EOL字符；如果已经超过行尾，currentChar再次readLine()返回下一行的第一个字符。如果读到文件末尾，line会是null值，那currentChar()返回一个特殊的EOF字符。其它情况下，此方法currentChar()简单的返回当在当前行currentPos位置的字符。

方法nextChar()将当前行的currentPos位置前进一步，接着调用chrrentChar()去返回下一个字符。(注意位置指针前移了)

假设源文件当前行包含ABCDE五个字符且currentPos是0。那么按如下顺序调用currentChar()和nextChar()，每次调用返回字符如下标：

1
2
3
4
5
6
7
8
1: currentChar() ⇒ 'A'
2:  nextChar()    ⇒ 'B'
3:  nextChar()    ⇒ 'C'
4:  nextChar()    ⇒ 'D'
5:  currentChar() ⇒ 'D'
6:  currentChar() ⇒ 'D'
7:  nextChar()    ⇒ 'E'
8:  nextChar()    ⇒ EOL

nextChar()　“吞噬”当前字符（将currentPos增1使其指向下一个字符），但currentChar()不是。有时候你需要调用nextChar()吞噬当前字符，但不用它返回的字符。你将会在后面和下章看到怎么使用这两个方法。

方法peekChar() “向前探测”（后续将简称前探）挨着当前字符的下一个字符，此操作不吞噬当前字符。下章中此方法将会区分单个Pascal Token “3.14”和三个Token “3..14.”。注意peekChar在当前位置处于行尾或者超过行尾是，不会读下一行，它总会返回EOL字符，这不会有啥问题。

在更新域line同时，方法readLine()会把lineNum加1且设置currentPos为0。

Scanner类

清单2-3 展示了框架抽象类Scanner。语言相关的子类将会实现extractMethod方法。Parser调用其nextToken() 方法，而nextToken()方法调用extractToken()去设置和返回私有域currentToken的值。快捷方法currentChar()和nextChar()来自于Source类对应的方法。
清单2-3 抽象类Scanner

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 1: /**
 2:  * <p>语言无关的scanner，产生Token</p>
 3:  */
 4: public abstract class Scanner
 5: {
 6:     protected Source source;
 7:     private Token currentToken;  //当前Token
 8:     public Scanner(Source source)
 9:     {
10:         this.source = source;
11:     }
12:     public Token currentToken()
13:     {
14:         return currentToken;
15:     }
16:
17:     /**
18:      * 以source中的char序列模式抽取token
19:      * @return 下一个token
20:      * @throws Exception
21:      */
22:     public Token nextToken()
23:         throws Exception
24:     {
25:         currentToken = extractToken();
26:         return currentToken;
27:     }
28:
29:     /**
30:      * 因为每个源语言的Token构成方式不一样，所以这个具体语言的子类去实现。
31:      * @return 语言相关的Token
32:      * @throws Exception
33:      */
34:     protected abstract Token extractToken()
35:         throws Exception;
36:
37:    /**
38:     * source的一个快捷方法，可让子类比不依赖source
39:     * @return 要读取的字符
40:     * @throws Exception
41:     */
42:     public char currentChar()
43:         throws Exception
44:     {
45:         return source.currentChar();
46:     }
47:     /**
48:      * source的一个快捷方法，可让子类比不依赖source
49:      * @return 下一个要读取的字符
50:      * @throws Exception
51:      */
52:
53:     public char nextChar()
54:         throws Exception
55:     {
56:         return source.nextChar();
57:     }
58: }

Token类

代码清单2-4 展示了Token类的关键方法

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 1: /**
 2:  * <p>Scanner扫描返回的最小语法单元，也是个比不可少的框架类</p>
 3:  */
 4: public class Token
 5: {
 6:     protected TokenType type;  // 语言相关的Token类型
 7:     protected String text;     // 字面文本
 8:     protected Object value;    // 值，如果是一些常量，直接可以算出值来的
 9:     protected final Source source;   // source
10:     protected int lineNum;     // 所在行
11:     protected int position;    // Token第一个字符所在的位置，即行中列位置
12:     public Token(Source source)
13:         throws Exception
14:     {
15:         this.source = source;
16:         this.lineNum = source.getLineNum();
17:         this.position = source.getPosition();
18:         extract();
19:     }
20:
21:     /**
22:      * 当前为演示框架组件，每次都返回一个字符的Token，实际不是这样的，后面章节会改。<br>
23:      * 但是吞噬原理是一样的，每当Token构成完之后，都把位置游标前移一步。
24:      * @throws Exception
25:      */
26:     protected void extract()
27:         throws Exception
28:     {
29:         text = Character.toString(currentChar());
30:         value = null;
31:         //吞噬&前进
32:         nextChar();
33:     }
34:
35:     protected char currentChar()
36:         throws Exception
37:     {
38:         return source.currentChar();
39:     }
40:
41:     protected char nextChar()
42:         throws Exception
43:     {
44:         return source.nextChar();
45:     }
46:
47:     protected char peekChar()
48:         throws Exception
49:     {
50:         return source.peekChar();
51:     }
52: }

根据概念设计，scanner构造出token然后把它们交给parser。因为TokenType是一个接口，你能设置Token的类型(域type)为一个语言相关的值。下章将会演示scanner如何根据当前字符（源文件中），也就是token的首字符，判定要构造的下一个Token的类型。例如，如果首字符为数字，则下一个token为number类型；如果为字母，则下一个token可以是标识符(ID)或关键字，因为你用不同Token子类来表示不同Token类型，scanner将会根据首字符调用Token子类相应的构造函数。

构造函数调用extract()方法去实际构造一个Token。方法(extract)名意味着此方法将会从source中读取字符来抽取token。Token子类根据语言相关的token类型逻辑实现extract方法。Token类提供了一个默认的单字符Token实现。除少数情况，extract()实现会吞噬token字符，而把行的当前位置到Token尾字符的下一个位置（假设when i < k 抽取到Token when，那么首字符为w，尾字符为n，则当前行位置会定位到 i，因为一般空格会被忽略）。
调用extract方法之前，构造函数设置token文本所在行和首字符行中位置。比如关键字BEGIN的文本串可为”begin”（Pascal大小写不敏感），如果文本begin在第11到15位置，那么首字符位置为11，在extract方法返回后，当前位置为16。(15的下一个）

有些Token有值（一般为常量Token)。比如一个数字token的文本是”3.14159”则值与Pi近似。

跟Scanner类一样，Token类同样是调用source对象响应方法，实现了currentChar()和nextChar()和peekChar()。

清单2-5 展示了TokenType标记接口。语言相关的Token类型将会用到实现接口。（标记接口不定义任何方法，它主要用来标识实现了此接口的类。比如所有实现了TokeType接口被认为是Token类型，这在JDK中就有，比如有名的java.io.Serializable类)

清单2-5：TokenType接口

1
2
3
4
5
6
7
8
1: package wci.frontend;
2:
3: /**
4:  * <p>Token类型，此章没有任何具体类型实现，仅仅是个为演示框架的占位类</p>
5:  */
6: public interface TokenType
7: {
8: }

清单2-6 暂时了语言无关的EofToken子类。因为它仅仅表示文件结束，所以覆盖extract方法后啥事都没干。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 1: package wci.frontend;
 2:
 3: /**
 4:  * <p>表示文件结束的特殊Token</p>
 5:  */
 6: public class EofToken extends Token
 7: {
 8:     public EofToken(Source source)
 9:         throws Exception
10:     {
11:         super(source);
12:     }
13:     protected void extract(Source source)
14:         throws Exception
15:     {
16:     }
17: }

SupriseMF wechat
欢迎关注微信订阅号【星球码】，分享学习编程奇淫巧技~
喜欢就支持我呀(*^∇^*)~

热评文章