编译器一日一练（DIY系列之词法分析）

【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】

        词法分析是编译原理的基础。目前来说，大部分编程语言还是以英文为主。使用英文有几个好处，这主要是因为英文的单词和单词之间是用空格分开来的，不像中文需要用词组来分割。记得读书的时候，有一个编译原理上机作业，就是编写一个词法分析器。如果是纯手工编写词法分析器，那么势必涉及到状态机的知识。然而如果使用javacc来编写，只需要描述清楚规则就可以了。

        目前词法分析涉及到的分词主要有这么几种，一种是关键字，一种是标识符，剩下来的就是各种各样的符号、字符串、数字等等。通常来说，分词就是将一长串的字符串解析成一个一个token。

        当然，除了分词之外，有一些字符也是要过滤的，比如换行、空格、注释等等。

        代码链接：https://github.com/feixiaoxing/DIYCompiler

1、关键字

        关键字比较好理解。就是某个编程语言当中被预留的一些单词。比如c语言里面if、else、for、while、switch、case、goto等等，这些都属于关键字。javacc中一般是这么安排的，

TOKEN: {<IF : "if">}
TOKEN: {<ELSE : "else">}
TOKEN: {<FOR : "for">}
TOKEN: {<WHILE : "while">}
TOKEN: {<DO : "do">}
TOKEN: {<SWITCH : "switch">}
TOKEN: {<CASE : "case">}

2、标识符

        除了关键字之外，接下来就该说说标志符了。标识符通常就是各种各样变量的名字。这个名字一般用于描述全局变量、局部变量、函数名、函数参数、函数调用等等。对于标识符，javacc是这样来描述的，

TOKEN: {<IDENTIFIER: ["a"-"z","A"-"Z","_"](["a"-"z","A"-"Z","_","0"-"9"])*>}

3、其他符号

        在关键字和标识符之后，留下来的就是各种各样的计算符号、数字、字符串和一些特殊付好了。比如，数字一般这么描述，

TOKEN: { <INTEGER: (["0"-"9"])+> }

        计算符号通常这么来描述，

TOKEN: {<ADD : "+">}
TOKEN: {<SUB : "-">}
TOKEN: {<MUL : "*">}
TOKEN: {<DIV : "/">}
TOKEN: {<EQUAL : "=">}

        特殊符号也有一些，比如这些，

TOKEN: {";">}
TOKEN: {"[">}
TOKEN: {"]">}
TOKEN: {"{">}
TOKEN: {"}">}
TOKEN: {"(">}
TOKEN: {")">}

4、待过滤的符号

        在编程代码中，有一些符号是要过滤的，他们不参与最终的代码生成，

SKIP: { <[" ", "\t", "\r", "\n"]> }

        这样，有了上面四种形式的符号，基本的词法分析就差不多了。这里没有描述出来所有的符号，本着用多少记录多少的想法，大家在实际开发中可以根据自己的需要灵活增减。

5、实例

        之前我们谈到了四则运算，这里稍作改变，其实就可以将语法表达式全部用token来表示了，

options {
    STATIC = false;
}
 
PARSER_BEGIN(Parse)
import java.io.*;
public class Parse {
    public static void main(String[] args) {
        for (String arg : args) {
            try {
                System.out.println(evaluate(arg));
            } catch (ParseException ex) {
                System.err.println(ex.getMessage());
            }
        }
    }
 
    public static long evaluate(String src) throws ParseException {
        Reader reader = new StringReader(src);
        return new Parse(reader).expr();
    }
}
PARSER_END(Parse)
 
 
SKIP: { <[" ", "\t", "\r", "\n"]> }
 
TOKEN: { <INTEGER: (["0"-"9"])+> }
 
TOKEN: {<ADD : "+">}
TOKEN: {<SUB : "-">}
TOKEN: {<MUL : "*">}
TOKEN: {<DIV : "/">}
TOKEN: {<EQUAL : "=">}
 
TOKEN: {<IDENTIFIER: ["a"-"z","A"-"Z","_"](["a"-"z","A"-"Z","_","0"-"9"])*>}
 
TOKEN: {<SEMICOLON: ";">}
TOKEN: {<LEFTBRACKETS: "[">}
TOKEN: {<RIGHTBRACKETS: "]">}
TOKEN: {<LEFTBRACE: "{">}
TOKEN: {<RIGHTBRACE: "}">}
TOKEN: {<LEFTPARENTHESES: "(">}
TOKEN: {<RIGHTPARENTHESES: ")">}
 
long expr() throws NumberFormatException :
{
    long value = 0 ;
}
{
	value = main_expr() 
    <EOF>
    { return value ; }
}
 
long main_expr() throws NumberFormatException :
{
    long a ;
    long b ;
    long value = 0 ;
}
{
	a = primary() {value = a;}
    (
	 <ADD> b = primary()
    { 
		value  += b; 
	}|
	 <SUB> b = primary()
    { 
		value -= b; 
	}
	)*
    { return value ; }
}
 
long primary() throws NumberFormatException :
{
    long a ;
    long b ;
    long value = 0 ;
}
{
	a = secondary() {value = a;}
    (
	 <MUL> b = secondary()
    { 
		value  *= b; 
	}|
	 <DIV> b = secondary()
    { 
		value /= b; 
	}
	)*
    { return value ; }
}
 
long secondary() throws NumberFormatException:
{
	Token a;
	long b = 0;
	long value = 0;
}
{
	(
		a = <INTEGER> {value = Integer.parseInt( a.image );} |
		<LEFTPARENTHESES> b =main_expr() <RIGHTPARENTHESES> { value = b;}
	)
	
	{ return value;}
}

        这里有一点需要注意下，如果在语法表达式中需要使用token的时候，应该用<>来表示。此外如果需要解析这个token的时候，可以直接转变为Token，获取对应的信息就可以了。