(基于Java)编写编译器和解释器-第3章:扫描-第一部分(连载)

时间:2022-12-03 17:08:36

扫描器(Scanner,词法分析器)是编译器/解释器前端的一个组件,用来执行读取源程序,将程序分成Token等语法动作。解析器(语法分析器)每次需要从源程序获取Token时就会调用扫描器。本章你将会为Pascal Token设计和开发一个扫描器。

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

目标和方法

前面章节中,你已在前端实现一个语言无关的Scanner框架类和一个初级版本与Pascal有关的框架子类PascalScanner。本章的目标是完成Pascal扫描器的设计与开发并测试它。扫描器将能够:

  • 从源程序中抽取Pascal单词,数字,字符串以及特殊符号Token(比如+,:= 等)。
  • 判断一个单词Token是一个标识符(identifier,一般标识变量名称,程序名称,过程/函数名称等)还是一个Pascal关键字(reserved word)。
  • 计算数字token的值并判断它是一个整数还是实数(real,包含小数点)。
  • 处理语法错误。

本章的方法是开发一系列可被PascalScanner创建的Pascal token子类。你将创建一个框架类Token的子类PascalToken并接着开发PascalToken的子类用来表示Pascal单词,数字,特殊符号token等。你会定义Pascal Token类型并实现上一章的TokenType接口。

图3-1 概括了我们的扫描器设计

图3-1:Pascal相关的Scanner和Token类

(基于Java)编写编译器和解释器-第3章:扫描-第一部分(连载)灰色部分表示你已在frontend包中实现的语言无关的框架类。现在你将完成frontend.pascal包中的Pascal子类。你也将创建frontend.pascal.tokens包用来容纳PascalToken子类。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

设计笔记

定义将单个的Pascal Token类型子类分开是策略设计模式的另一个例子。这儿的策略是从源文件中创建各种token类型的算法。在每个子类封装自己策略(通过extract()方法实现)使得代码更加模块化,也使得扫描器能够更容易的选择合适的token类型去创建。所有token子类将继承自PascalToken类,而PascalToken继承自语言无关的Token类。

图3-1 也演示了上一章开始处提到的设计准则:永远基于可运行代码进行构建。此时你正在给早些时候开发的框架添加子类。

就如第一章提到的,扫描器也称词法分析器,它的扫描操作也称词法分析。Token同样有另一个名字:Lexeme(词单位)

程序-3:Pascal分词器

从frontend.pascal包中,上一章开发的解析器子类PascalParserTD开始,扩展它的parser方法以便练习和测试整个Pascal扫描器。尽管你还没有编写它需要的各种token子类,parser方法还是展示了怎样扫描各种Pascal Token并处理错误。见清单3-1。

清单3-1:PascalParserTD类中的Parse和getErrorCount方法

   1: public class PascalParserTD extends Parser {
   2:  
   3:     private PascalErrorHandler errorHandler = new PascalErrorHandler();
   4:  
   5:     public PascalParserTD(Scanner scanner) {
   6:         super(scanner);
   7:     }
   8:  
   9:     /**
  10:      * Pascal的解析过程,产生Pascal相关的iCode和symbol table
  11:      */
  12:     public void parse() throws Exception {
  13:         Token token;
  14:         long startTime = System.currentTimeMillis();
  15:  
  16:         try {
  17:             while (!((token = nextToken()) instanceof EofToken)) {
  18:                 TokenType tokenType = token.getType();
  19:                 if (tokenType != PascalTokenType.ERROR) {
  20:                     sendMessage(new Message(MessageType.TOKEN,
  21:                             new Object[] { token.getLineNumber(),
  22:                                     token.getPosition(), token.getType(),
  23:                                     token.getText(), token.getValue() }));
  24:                 } else {
  25:                     // 留意当token有问题是,它的值表示其错误编码
  26:                     errorHandler.flag(token,
  27:                             (PascalErrorCode) token.getValue(), this);
  28:                 }
  29:             }
  30:             // 发送编译摘要信息
  31:             float elapsedTime = (System.currentTimeMillis() - startTime) / 1000f;
  32:             sendMessage(new Message(PARSER_SUMMARY, new Number[] {
  33:                     token.getLineNumber(), getErrorCount(), elapsedTime }));
  34:         } catch (IOException e) {
  35:             errorHandler.abortTranslation(PascalErrorCode.IO_ERROR, this);
  36:         }
  37:     }
  38:  
  39:     public int getErrorCount() {
  40:         return errorHandler.getErrorCount();
  41:     }
  42: }

(对比第二章,注意黑体部分为新增内容

parse()方法遍历成功从扫描器(scanner)调用nextToken()获得的每一个token。针对每个token发送一个TOKEN消息给所有监听器,消息明示token的类型,文本串,行号和起始位置。消息包含整数,实数以及字符串token的值。然而,如果有错,方法将错误处理转交给errorHandler,一个PascalErrorHandler对象。

我们约定TOKEN消息的格式如下:

  • token.getLineNumber():行位置
  • token.getPosition():起始位置,token字一个字符的位置。
  • token.getType():token类型
  • token.getText():token文本
  • token.getValue():token值

清单3-1 也展示了新版方法getErrorCount(见第40行),它现在返回错误处理器errorHandler中的语法错误(这个Parser把分词的词法错误也算作语法错误了??应该词法错误是词法错误,语法错误是语法错误)。

主程序Pascal类中的私有内部类PascalMessageListener监听来自Parser的消息。前章它可处理PARSER_SUMMARY消息。现在将TOKEN和SYNTAX_ERROR消息处理也加上。见清单3-2:

清单3-2:Pascal主类中的ParserMessageListener增加TOKEN和SYNTAX_ERROR处理

   1: private static final String TOKEN_FORMAT = ">>> %-15s %03d行 %2d列, 内容为\"%s\"";
   2: private static final String VALUE_FORMAT = ">>>                 值等于%s";
   3: private static final int PREFIX_WIDTH = 5;
   4:  
   5: /**
   6:  * Parser的监听器,监听来自Parser解析过程中产生的消息,还是Observe模式
   7:  */
   8: private class ParserMessageListener implements MessageListener {
   9:     public void messageReceived(Message message) {
  10:         MessageType type = message.getType();
  11:  
  12:         switch (type) {
  13:         case TOKEN: {
  14:             Object body[] = (Object[]) message.getBody();
  15:             int line = (Integer) body[0];
  16:             int position = (Integer) body[1];
  17:             TokenType tokenType = (TokenType) body[2];
  18:             String tokenText = (String) body[3];
  19:             Object tokenValue = body[4];
  20:  
  21:             System.out.println(String.format(TOKEN_FORMAT, tokenType, line,
  22:                     position, tokenText));
  23:             if (tokenValue != null) {
  24:                 if (tokenType == PascalTokenType.STRING) {
  25:                     tokenValue = "\"" + tokenValue + "\"";
  26:                 }
  27:  
  28:                 System.out.println(String.format(VALUE_FORMAT, tokenValue));
  29:             }
  30:  
  31:             break;
  32:         }
  33:  
  34:         case SYNTAX_ERROR: {
  35:             Object body[] = (Object[]) message.getBody();
  36:             int lineNumber = (Integer) body[0];
  37:             int position = (Integer) body[1];
  38:             String tokenText = (String) body[2];
  39:             String errorMessage = (String) body[3];
  40:  
  41:             int spaceCount = PREFIX_WIDTH + position;
  42:             StringBuilder flagBuffer = new StringBuilder();
  43:  
  44:             //下一行跳到token出现的位置
  45:             for (int i = 1; i < spaceCount; ++i) {
  46:                 flagBuffer.append(' ');
  47:             }
  48:  
  49:             //尖括号指出问题token
  50:             flagBuffer.append("^\n*** ").append(errorMessage);
  51:  
  52:             if (tokenText != null) {
  53:                 flagBuffer.append(" [在 \"").append(tokenText)
  54:                         .append("\" 处]");
  55:             }
  56:  
  57:             System.out.println(flagBuffer.toString());
  58:             break;
  59:         }
  60:         //其它处理省略
  61:         }
  62:     }
  63: }

messageRecieved()方法遵循PascalParserTD类生成的TOKEN消息格式约定,也遵循PascalErrorHandler类生成的SYNTAX_ERROR消息格式约定(下面会讲)。如碰到SYNTAX_ERROR消息,方法显示一个^字符指向出错Token的首字符以及一条错误信息。

可以运行命令 java -classpath classes Pascal compile scannertest.txt 看分词效果,scannertest.txt参见源代码根目录下的同名文件,这儿就不显示了。

清单3-4 展示了Pascal分词功能的输出。每行之前有一个三位数字长的行号,接着是每一行的token,在行之前用>>>标识。每个单词token不是一个标识符就是一个关键字,整数和实数 token有值,字符串同样有值(值就是这个字串)。

清单3-4:分词器输出

001 {This is a comment.}
002
003 {This is a comment
004 that spans several
005 source lines.}
006
007 Two{comments in}{a row} here
>>> IDENTIFIER 007行 0列, 内容为"Two"
>>> IDENTIFIER 007行 24列, 内容为"here"
008
009 {Word tokens}
010 Hello world
>>> IDENTIFIER 010行 0列, 内容为"Hello"
>>> IDENTIFIER 010行 6列, 内容为"world"
011 begin BEGIN Begin BeGiN begins
>>> BEGIN 011行 0列, 内容为"begin"
>>> BEGIN 011行 6列, 内容为"BEGIN"
>>> BEGIN 011行 12列, 内容为"Begin"
>>> BEGIN 011行 18列, 内容为"BeGiN"
>>> IDENTIFIER 011行 24列, 内容为"begins"
012
013 {String tokens}
014 'Hello, world.'
>>> STRING 014行 0列, 内容为"'Hello, world.'"
>>> 值等于"Hello, world."
015 'It''s Friday!'
>>> STRING 015行 0列, 内容为"'It''s Friday!'"
>>> 值等于"It's Friday!"
016 ''
>>> STRING 016行 0列, 内容为"''"
>>> 值等于""
017 ' '' '' ' ''''''
>>> STRING 017行 0列, 内容为"' '' '' '"
>>> 值等于" ' ' "
>>> STRING 017行 12列, 内容为"''''''"
>>> 值等于"''"
018 'This string
019 spans
020 source lines.'
>>> STRING 018行 0列, 内容为"'This string spans source lines.'"
>>> 值等于"This string spans source lines."
021
022 {Special symbol tokens}
023 + - * / := . , ; : = <> < <= >= > ( ) [ ] { } } ^ ..
>>> PLUS 023行 0列, 内容为"+"
>>> MINUS 023行 2列, 内容为"-"
>>> STAR 023行 4列, 内容为"*"
>>> SLASH 023行 6列, 内容为"/"
>>> COLON_EQUALS 023行 8列, 内容为":="
>>> DOT 023行 11列, 内容为"."
>>> COMMA 023行 13列, 内容为","
>>> SEMICOLON 023行 15列, 内容为";"
>>> COLON 023行 17列, 内容为":"
>>> EQUALS 023行 19列, 内容为"="
>>> NOT_EQUALS 023行 21列, 内容为"<>"
>>> LESS_THAN 023行 24列, 内容为"<"
>>> LESS_EQUALS 023行 26列, 内容为"<="
>>> GREATER_EQUALS 023行 29列, 内容为">="
>>> GREATER_THAN 023行 32列, 内容为">"
>>> LEFT_PAREN 023行 34列, 内容为"("
>>> RIGHT_PAREN 023行 36列, 内容为")"
>>> LEFT_BRACKET 023行 38列, 内容为"["
>>> RIGHT_BRACKET 023行 40列, 内容为"]"
>>> RIGHT_BRACE 023行 46列, 内容为"}"
>>> UP_ARROW 023行 48列, 内容为"^"
>>> DOT_DOT 023行 50列, 内容为".."
024 +-:=<>=<==.....
>>> PLUS 024行 0列, 内容为"+"
>>> MINUS 024行 1列, 内容为"-"
>>> COLON_EQUALS 024行 2列, 内容为":="
>>> NOT_EQUALS 024行 4列, 内容为"<>"
>>> EQUALS 024行 6列, 内容为"="
>>> LESS_EQUALS 024行 7列, 内容为"<="
>>> EQUALS 024行 9列, 内容为"="
>>> DOT_DOT 024行 10列, 内容为".."
>>> DOT_DOT 024行 12列, 内容为".."
>>> DOT 024行 14列, 内容为"."
025
026 {Number tokens}
027 0 1 20 00000000000000000032 31415926
>>> INTEGER 027行 0列, 内容为"0"
>>> 值等于0
>>> INTEGER 027行 2列, 内容为"1"
>>> 值等于1
>>> INTEGER 027行 4列, 内容为"20"
>>> 值等于20
>>> INTEGER 027行 7列, 内容为"00000000000000000032"
>>> 值等于32
>>> INTEGER 027行 29列, 内容为"31415926"
>>> 值等于31415926
028 3.1415926 3.1415926535897932384626433
>>> REAL 028行 0列, 内容为"3.1415926"
>>> 值等于3.1415925
>>> REAL 028行 11列, 内容为"3.1415926535897932384626433"
>>> 值等于3.1415927
029 0.00031415926E4 0.00031415926e+00004 31415.926e-4
>>> REAL 029行 0列, 内容为"0.00031415926E4"
>>> 值等于3.1415925
>>> REAL 029行 17列, 内容为"0.00031415926e+00004"
>>> 值等于3.1415925
>>> REAL 029行 39列, 内容为"31415.926e-4"
>>> 值等于3.1415925
030 3141592600000000000000000000000e-30
>>> REAL 030行 0列, 内容为"3141592600000000000000000000000e-30"
>>> 值等于3.1415925
031
032 {Decimal point or ..}
033 3.14 3..14
>>> REAL 033行 0列, 内容为"3.14"
>>> 值等于3.14
>>> INTEGER 033行 6列, 内容为"3"
>>> 值等于3
>>> DOT_DOT 033行 7列, 内容为".."
>>> INTEGER 033行 9列, 内容为"14"
>>> 值等于14
034
035 {Bad tokens}
036 123e99 123456789012345 1234.56E. 3. 5.. .14 314.e-2
^
*** 实数操作范围 [在 "123e99" 处]
^
*** 整数超过范围 [在 "123456789012345" 处]
^
*** 无效数值 [在 "1234.56E" 处]
>>> DOT 036行 33列, 内容为"."
^
*** 无效数值 [在 "3." 处]
>>> INTEGER 036行 40列, 内容为"5"
>>> 值等于5
>>> DOT_DOT 036行 41列, 内容为".."
>>> DOT 036行 45列, 内容为"."
>>> INTEGER 036行 46列, 内容为"14"
>>> 值等于14
^
*** 无效数值 [在 "314." 处]
>>> IDENTIFIER 036行 54列, 内容为"e"
>>> MINUS 036行 55列, 内容为"-"
>>> INTEGER 036行 56列, 内容为"2"
>>> 值等于2
037 What?
>>> IDENTIFIER 037行 0列, 内容为"What"
^
*** 非法字符 [在 "?" 处]
038 'String not closed
^
*** 意外的终止符 [在 "'String not closed " 处]

----------代码解析统计信--------------
源文件共有 38行。
有 7个语法错误.
解析共耗费 0.06秒.

----------编译统计信--------------
共生成 0 条指令
代码生成共耗费 0.00秒
Pascal扫描器需要处理一些有挑战的情况。清单3-4的例子包含行011(Pascal大小写不敏感),行015、016、017(紧挨的一对单引号)和行033(区分小数点 "." 和表示数字范围的 ".."。行036、037、038演示了一些简单错误处理。扫描器用^号指向有问题Token的首字符,再加一条错误信息来标记每一个语法错误。

语法错误处理

解析器必须处理源程序中的语法错误。错误处理分三步骤:
  • 检测(Detection):检测存在的语法错误。
  • 标记(Flagging):通过指出错误位置或高亮错误处文本,还有显示一个错误描述信息来标识一个错误。
  • 恢复(Recovery):略过错误继续解析。
现在的错误恢复很simple:从当前字符往前探,尝试构造下个token( 当然还有个弱智但有用的错误恢复方法那就是碰到第一个错误,解析器就推出。不过我看好你能做的更好喔!)。
清单3-1 展示了PascalParserTD将错误处理交由PascalErrorHandler代理。清单3-5 展示了此代理类的关键方法,errorCount的getter没显示。
   1: public class PascalErrorHandler
   2: {    
   3:     //能忍受的最大错误数
   4:     private static final int MAX_ERRORS = 25;
   5:     //错误计数
   6:     private static int errorCount = 0;  
   7:     /**
   8:      * 标记错误Token
   9:      * @param token 有错误的token
  10:      * @param errorCode 错误编码
  11:      * @param parser 解析器
  12:      */
  13:     public void flag(Token token, PascalErrorCode errorCode, Parser parser)
  14:     {
  15:         // 通知解析器的监听器
  16:         parser.sendMessage(new Message(SYNTAX_ERROR,
  17:                                        new Object[] {token.getLineNumber(),
  18:                                                      token.getPosition(),
  19:                                                      token.getText(),
  20:                                                      errorCode.toString()}));
  21:  
  22:         if (++errorCount > MAX_ERRORS) {
  23:             abortTranslation(TOO_MANY_ERRORS, parser);
  24:         }
  25:     }
  26:  
  27:    /**
  28:     * 通知解析器的监听器,然后终止翻译,
  29:     * @param errorCode 错误编码
  30:     * @param parser 解析器
  31:     */
  32:     public void abortTranslation(PascalErrorCode errorCode, Parser parser)
  33:     {
  34:         String fatalText = "FATAL ERROR: " + errorCode.toString();
  35:         parser.sendMessage(new Message(SYNTAX_ERROR,
  36:                                        new Object[] {0,
  37:                                                      0,
  38:                                                      "",
  39:                                                      fatalText}));
  40:         System.exit(errorCode.getStatus());
  41:     }
  42: }

flag()方法创建一条消息并发送给解析监听器。我们约定SYNTAX_ERROR消息格式为:

  • token.getLineNumber():所在行
  • token.getPosition():首字符位置
  • token.getText():字面文本
  • errorCode.toString():语法错误描述

abortTranslation()方法遇到致命错误会被调用。它传给System.exit()函数一个退出状态,而此函数会终止程序。

设计笔记

通过将错误交由PascalErrorHandler处理,解析过程和错误处理达到松耦合。这使得你以后在不用修改解析代码的情况下,可修改错误处理代码。代理有助于限定每个类的职责。解析器只需要关注解析过程而错误处理类仅需关注错误处理。

类PascalErrorCode(参考源代码)中每个枚举值表示一个错误代码,每个错误码有一个描述。比如错误码RANGE_INTEGER的描述是“整数超过范围”。表示致命错误的错误码有一个非零的退出状态。比如,错误码IO_ERROR有退出状态-101。

解析器如何知道有错误发生了?规则如下:

  • 如果一个Pascal Token子类(比如PascalNumberToken)的实例(对象)发现一条语法错误,它将会把自己的类型域设置为PascalTokenType的枚举值ERROR,并且把值域设置为相应的PascalErrorCode枚举值。
  • 如果扫描器(scanner)发现一条语法错误(比如不能成为某个有效Pascal token首字符的非法字符),它将会创建一个PascalErrorToken。

类PascalErrorToken(参考源代码)扩展了PascalToken。它覆盖了extract方法并没有做什么操作。

清单3-4 展示了一些错误处理例子:

 

   1: 035 {Bad tokens}
   2: 036 123e99  123456789012345  1234.56E.  3.  5..  .14  314.e-2
   3:     ^
   4: *** 实数操作范围 [在 "123e99" 处]
   5:             ^
   6: *** 整数超过范围 [在 "123456789012345" 处]
   7:                              ^
   8: *** 无效数值 [在 "1234.56E" 处]
   9: >>> DOT             036行 33列, 内容为"."
  10:                                         ^
  11: *** 无效数值 [在 "3." 处]
  12: >>> INTEGER         036行 40列, 内容为"5"
  13: >>>                 值等于5
  14: >>> DOT_DOT         036行 41列, 内容为".."
  15: >>> DOT             036行 45列, 内容为"."
  16: >>> INTEGER         036行 46列, 内容为"14"
  17: >>>                 值等于14
  18:                                                       ^
  19: *** 无效数值 [在 "314." 处]
  20: >>> IDENTIFIER      036行 54列, 内容为"e"
  21: >>> MINUS           036行 55列, 内容为"-"
  22: >>> INTEGER         036行 56列, 内容为"2"
  23: >>>                 值等于2
  24: 037 What?
  25: >>> IDENTIFIER      037行  0列, 内容为"What"
  26:         ^
  27: *** 非法字符 [在 "?" 处]
  28: 038 'String not closed
  29:     ^
  30: *** 意外的终止符 [在 "'String not closed " 处]

怎样扫描Token

假设有个Pascal程序包含这行代码:

   1: IF (index >= 10) THEN

扫描器该如何扫描和提取此行中的Token?假定这行开头有四个空格的缩进,当前行下标为0,由下图套在第一个字符上的黑框指明。

(基于Java)编写编译器和解释器-第3章:扫描-第一部分(连载)

扫描器扫描字符,跳到第一个非空白字符。现在当前位置的字符是I

(基于Java)编写编译器和解释器-第3章:扫描-第一部分(连载)

因为字符'I'是一个字母,这相当于告诉扫描器接下来的Token将会是一单词(Word Token)。扫描器扫描并拷贝字符,直到当前字符不能构成单词(这儿是空格)从而完成单词Token的提取。扫描器判断这个单词是关键字IF。扫描器创建此单词token之后,当前字符是F后面的空格。

(基于Java)编写编译器和解释器-第3章:扫描-第一部分(连载)

扫描器还是扫描并跳过token之间的任何空格。

(基于Java)编写编译器和解释器-第3章:扫描-第一部分(连载)

这个字符'('等于告知扫描器下一个肯定是一个特殊符号token。这番提取之后,当前字符是i :

(基于Java)编写编译器和解释器-第3章:扫描-第一部分(连载)

字符i 使得扫描器知道下一个肯定是个单词token。跟前面一样,扫描器扫描并拷贝字符知道不能构成一个单词为止。扫描器断定单词index是一个标识符。当前字符现在时x后面的空格

(基于Java)编写编译器和解释器-第3章:扫描-第一部分(连载)

扫描器扫描,跳过空格

(基于Java)编写编译器和解释器-第3章:扫描-第一部分(连载)

见到 >,提取一个 >= 特殊符号token。(大于等于 比较符)

(基于Java)编写编译器和解释器-第3章:扫描-第一部分(连载)

接着扫描和跳过空格后:

(基于Java)编写编译器和解释器-第3章:扫描-第一部分(连载)

扫描器看到 1,知道接下来是数字token,于是扫描并拷贝直到当前字符不能构成一个数字为止,这儿这个字符是 )。扫描器判定数字是一个整数,于是计算其值为10。

(基于Java)编写编译器和解释器-第3章:扫描-第一部分(连载)

符号 ) 使得扫描器去提取另一个特殊符号token:

(基于Java)编写编译器和解释器-第3章:扫描-第一部分(连载)

仍然是扫描并跳过空格

(基于Java)编写编译器和解释器-第3章:扫描-第一部分(连载)

字符 T 使得扫描器去提取一个单词token。

(基于Java)编写编译器和解释器-第3章:扫描-第一部分(连载) 扫描器断定THEN是一个关键字

扫描这整行过后,扫描器提取了如下token:

类型 字面文本
单词(关键字) IF
特殊符号 (
单词(ID) index
特殊符号 >=
数字(整数) 10
特殊符号 )
单词(关键字) THEN

>>> 继续第三章