CMM语言解释器构造实践(三)——基于状态转换图的词法分析器

前言

在上篇博客中,我们通过对JavaCC的使用,了解到了编译工具的基本使用方法。在大部分的编译器开发中,开发人员很多情况下是先借助编译工具(如JavaCC、Antlr等),完成词法分析器、语法分析器的自动生成,之后再进行语义分析与其他的后端处理操作,这也大大提高了开发的效率。

正如上文所说,虽然在实际情况中,我们编写词法解析器和语法解析器的情况比较少见,但通过简单的“造轮子”项目,我们可以更好地理解编译器的工作原理。

接下来的两篇文章,就将针对CMM语言进行词法分析器、语法分析器的编写(不借助任何编译工具)。在开发的过程中,在理论知识上,笔者主要依据了龙书的表述,也较多参考了书中的源码。

在词法分析器的编写上,读者也可参考龙书(《编译原理》第二版)2.6章节:词法分析。

项目源码:https://github.com/RMSnow/CMMParser


任务说明

设计并编制调试一个分析单词的词法分析器,功能要求小结如下:

  • 忽略空格、tab键、回车换行等分隔符;
  • 识别不同类型的记号;
  • 识别并忽略注释;
  • 记录下每个记号的行号或位置;
  • 将识别的记号输出;
  • 如果输入串存在词法分析错误,则报错。

从输入的源程序中,识别出各个具有独立意义的记号,包括保留字、标识符、常数、运算符、分隔符等,并依次输出各个记号序列。如果出错(即不是语言可以识别的记号),则输出error。

输入形式:键盘输入或文件输入。
输出结果:呈现出词法分析器对输入内容分析的结果。

即:词法分析程序需要从输入端(控制台或文件)读取若干字符流,对于符合CMM语言语法的字符,能够以词法单元的形式识别,并于控制台输出解析结果。对于其他字符,则会进行相应的出错处理,并提示异常信息。


设计思路

依据面向对象的设计思想,最先应该设计的数据结构,应为CMM语法中涉及到的各类词法单元(Token),整个词法分析程序其实就是在识别各类词法单元

在词法单元设计完成之后,则应编写词法分析程序(Lexer)。对于词法分析程序,其需要进行的工作如下所示:
(1) 跳过空白。即对于空格,\t,\n字符,需要自动跳过;
(2) 判断读入的字符(或字符串)是否为某类词法单元;
(3) 通过若干判断分支,最终得到的返回值即为识别出的一个词法单元.

由此我们可知,词法分析程序每次识别一个词法单元,因此可重复调用词法分析程序,直至其扫描完全部的输入字符。在识别出一个词法单元后,可在控制台输出相应的识别结果。
如,对于语句int a = 0;,最终输出结果<KEYWORD, int> <IDENTIFIER, a> < = > <NUM, 0> < ; >.

除此之外,还应设计相应的出错处理机制,如CMM语言中的标识符必须以字母开头,且不能以下划线结尾,因此对于_aa2_之类的标识符,应辅以相应的报错信息处理。


具体实现

词法单元描述(Token)

词法单元的基类为Token,用tag属性来标识其种类,其他复杂的词法单元都继承自Token。词法单元的类图设计如下:

Token

各个类的说明如下:

  • Token表示运算符号或特殊符号(单目)
  • Word表示关键字与标识符,属性lexme(String)存储其值
  • Num表示数字常量(自然数),value(int)存储其值
  • BinaryOperator表示双目符号,如“>=”、“< >”等,operator(String)存储其值
  • RealNum表示实数,number(Num)存储整数部分,fraction(Num)存储小数部分

词法分析程序(Lexer)

Lexer首先需进行初始化操作,将CMM语言中自定的保留字运算符号存储于Hashtable中,以便后续识别工作的查询。

其次调用scan()方法,对输入字符进行解析,判断字符(或字符串)是否为Token, Word, Num, BinaryOperator, RealNum等词法单元,或为#///*等特殊符号。识别成功后,返回某个词法单元对象。

输入字符流

对于文件输入与控制台输入,Lexer通过自定义CharStream类的readChar()方法,实现每次读入一个字符。
CharStream类拥有readChar()方法,对于文件输入与控制台输入,分别设计FileCharStream类与ConsoleCharStream类,都继承基类CharStream,且实现了对readChar()函数的复写,ConsoleCharStream.readChar()实现对System.in.read()的封装,FileCharStream.readChar()则实现对Reader.read()的封装。

public class CharStream {
    /**
     * 读取字符
     *
     * @return
     * @throws IOException
     */
    public int readChar() throws IOException {
        return 0;
    }
}

public class ConsoleCharStream extends CharStream {
    /**
     * 控制台读取字符
     *
     * @return
     * @throws IOException
     */
    @Override
    public int readChar() throws IOException {
        return System.in.read();
    }
}

public class FileCharStream extends CharStream {
    private Reader reader;

    /**
     * 构造函数
     *
     * @param filename
     * @throws FileNotFoundException
     */
    public FileCharStream(String filename) throws FileNotFoundException {
        File file = new File(filename);
        reader = new InputStreamReader(new FileInputStream(file));
    }

    /**
     * 文件读取字符
     *
     * @return
     * @throws IOException
     */
    @Override
    public int readChar() throws IOException {
        return reader.read();
    }
}

用户可通过命令行参数的选择,进行文件输入或控制台输入的选择。针对命令行参数,分别构建不同的Lexer对象,其分别拥有不同的CharStream成员,实现多态以提高代码复用程度。

异常处理

LexerException类中实现了三个异常处理方法,分别对标识符异常、未定义的符号、未闭合的多行注释进行出错信息打印,并定位出错位置的行号。

/**
 * 异常处理机制
 */
public class LexerException {

    /**
     * 标识符异常
     */
    public static void identifierException() {
        System.out.println();
        System.out.println("[EXCEPTION IN LINE " + LexerEntry.lexer.line + ": THE IDENTIFIER CANNOT BE RECOGNIZED.]");
        System.out.println("[HINT: THE RECOGNIZABLE IDENTIFIER BEGINS WITH A LETTER AND CANNOT END WITH \"_\".]");
        System.out.println();
    }

    /**
     * 未定义的符号
     *
     * @param s
     */
    public static void unknownSymbolException(String s) {
        System.out.println();
        System.out.println("[EXCEPTION IN LINE " + LexerEntry.lexer.line + ": THE SYMBOL \"" + s + "\" CANNOT BE RECOGNIZED.]");
        System.out.println();
    }

    /**
     * 未闭合的多行注释
     */
    public static void unclosedMultiAnnotation() {
        System.out.println();
        System.out.println("[EXCEPTION IN LINE " + LexerEntry.lexer.line + ": \"*/\" IS EXPECTED IN THE FILE.]");
        System.out.println();
    }
}

测试用例

针对CMM语言的特点,设计了如下的用例:

---------------------键盘输入测试用例---------------------

1.无浮点数、无注释时
    1)各个符号单个输入
    if,else,while,read,write,int,real
    +,-,*,/,=,<,>,==,<=,>=,<>,{,},[,]

    2)语句(有空白与无空白)
    int a, b;
    real[] r;
    a = 1;
    read(b);
    r[0] = 0;

    while(a < b){
        if(a == 3){
            r[3] = 3;
        }else if(a >= 5){
            r[5] = 5;
        }else{
            r[7] = (a * 3) - (b / 3);
        }
        a = a + 1;
    }

    write(a, b, r);

    #

    3)出错处理
    a. 不正确的标识符,如_a1aa1b_
    b. 未知单目符号,如$,@

2.注释
1)单行注释
    a. //read(a);
    b. int//double b; a

2)多行注释
    a. [多行注释]
    b. int[多行注释]a;

3.浮点数
1[Num].[Num]
2.[Num]分析为0.[Num]
3[Num].分析为[Num].0

---------------------文件输入测试用例---------------------

1. 同键盘输入

2. 注释
1)单行注释,同键盘输入
2)多行注释,需判断注释符无闭合时的情况

3. 同键盘输入

4. 文件读取结束的判断

5. 行号
1)在控制台输出解析结果,输出时需换行
2)解析错误时,需显示行号

---------------------------------------------------------

实验结果均如预期。


使用说明

CMM

在目前版本的CMM词法分析器中,需满足的词法和语法条件有:

  1. 没有负数,只有正实数与0
  2. 对于实数,共有以下三种形式
    (1)[Num].[Num]
    (2).[Num]分析为0.[Num],但单独的”.”则无法识别
    (3)[Num].分析为[Num].0

系统要求

词法分析器在处理换行符时,要求系统默认的换行符为“\n”,对所有的“\r”或者“\r\n”均未做处理。

png

命令行参数

LexerEntry类为程序入口,其中的主函数对命令行参数作如下要求:

------------------------使用方法------------------------
1.键盘输入:输入命令"scan #"后,在键盘输入代码,"#"为输入结束符
2.读取文件:输入命令"scan [文件名]",如:scan test.txt
-------------------------------------------------------

总结与收获

框架设计

整个词法解析器编写完成后,收获的东西很多。在框架设计上,值得思考与体会的地方也不尽其数,下面列举了一些非常值得品味的point。

  • 词法分析是什么?语法分析是什么?

  • 为什么Lexer的扫描函数scan()要返回Token对象,而不直接用String打印出来

  • 对于双目运算符:
    • 如何设计其数据结构?
    • 如何预读下一字符并进行判断?
  • 通过继承和多态实现代码复用:
    • 词法单元各个类的设计
    • CharStreamFileCharStreamConsoleCharStream的设计
  • Lexer类中peek的灵活使用

基础知识

在Java语言的基础知识方面,以下内容也更需要熟练掌握。

  • charint的转化: 如,Token中只有一个int类型的tag属性,却灵巧的代替了几乎所有词法单元

  • Stringequals()==

  • 异常处理

  • 文件I/O

  • 读取文件内容
    • 按字符读
    • 按字节读
    • 按行读
  • 类与接口

  • 抽象类

  • Hashtable

参考资料

[1]《编译原理》(第2版).张素琴,吕映芝等编著.清华大学出版社.
[2]《编译原理》(第2版).Alfred V.Aho, Monica S.Lam等著.机械工业出版社.
[3]《编译原理实践教程》.胡元义,邓亚玲,胡英著.