词法分析的目的在于将输入的源代码(一大串字符文本)拆解成一个一个基本组成单元(Token),并且在拆解的过程中,提炼出 Token 的类型(比如:字符串,标识符,数值等)等信息,为后面语法分析打下基础。
在该书中, 通过正则表达式的方式来完成此任务。
为了简单起见,这里我们设定语法规则如下:
类型 | 具体语法规定 |
---|---|
注释 | 以// 开头的内容 |
数值 | 暂定只支持整数,为了简单起见09这样的整数也认为是合法的 |
字符串 | "" 内的内容,支持\\ 、\" 、\n 转义字符 |
标识符 | 以字母或下划线开头,后接字母数字下划线的变量名;各种操作符、标点符号 |
具体正则表达式为:"\\s*((//.*)|([0-9]+)|(\"(\\\\\"|\\\\\\\\|\\\\n|[^\"])*\")|[A-Z_a-z][A-Z_a-z0-9]*|==|<=|>=|&&|\\|\\||\\p{Punct})?";
上述正则表达式与上表中的内容是一一对应的,匹配时首先跳过这一行的空格("\\s*"
),后面的内容都为有效的内容,因此用一个大的括号括起来,便于得到其内容。
在这个大的括号之中:
第一对括号中的内容//.*
用于匹配注释
第二对括号中的内容"[0-9]+"
用来匹配数值类型的 Token;
第三对括号内的内容\"(\\\\\"|\\\\\\\\|\\\\n|[^\"])*\"
用来对匹配字符串类型的 Token,由于字符串本身\
需要转义,正则表达式中的\
同样需要转义,因此这里的\
非常的多,不过还是很容易分析的:\\\\\"
这一部分用来匹配字符串中的\"
,\\\\\\\\
用来匹配字符串中的\\
,\\\\n
用来匹配字符串中的\n
,剩下[^\"]
用来匹配一切非"
字符,至此整个字符串的匹配模式就完成了;
剩下的内容[A-Z_a-z][A-Z_a-z0-9]*|==|<=|>=|&&|\\|\\||\\p{Punct})?
用于匹配标识符,为了简单起见,我们对标识符的定义非常广泛,日后可以更加细化。
整个正则表达式分析完后,对源代码进行词法分析就是对源代码进行正则表达式的模式匹配,通过一行一行地遍历整个源代码,对其中每一行进行单独解析,设置正则式的范围,将该行中所有满足要求的字符串构建成不同类型的 Token,并保存到一个序列中,以便后续语法分析。
词法分析后,我们得到了一系列 Token,但是如何知道哪些 Token 是一句完整的语句呢,他们组成的语句的作用是什么呢?这就需要用到语法分析。语法分析中有一个非常重要的概念:抽象语法树(abstract syntax tree,AST)。将一系列 Token 构建成为一颗抽象语法树就是语法分析的具体作用。
表达式s = 1 + 2
经过上面的词法分析,会得到['s', '=', '1', '+', '2']
这样的一个 Token 序列,其中s
、=
、+
为标识符类型的 Token,1
、2
为数值类型的 Token。
为了表达该表达式的含义,我们将其转换成形如下面展示的一颗抽象语法树:
=
/ \
s +
/ \
1 2
此时我们便可以很清晰的看到:1
和2
是要进行+
运算的,s
和1+2
的结果要进行=
运算。
同样的,只要我们将源代码中的 Token 转换成一颗抽象语法树,那么我们便能得到具体的语句及其语义,因此这一阶段被称为语法分析。
但是,要想将 Token 序列转换成一颗抽象语法树,首先我们得定义我们自己的文法,比如Java
中的if
语句、while
语句等。如何表示定义好的文法呢,这里要用到另一个概念 BNF(巴科斯范式,Backus Normal Form),这是一种用于表示上下文无关文法的语言。
下面是用 BNF 来表示我们的设计好的文法:
primary : "(" expr ")" | NUMBER | IDENTIFIER | STRING
factor : "-" primary | primary
expr : factor {OP factor}
block : "{" [ statement ] { (";" | EOL) [ statement ]}
simple : expr
statement : "if" expr block { "else" block }
| "while" expr block
| simple
program : [ statement ] (";" | EOL)
文法设计好后,只剩下最后一步,但也是最困难的一步,用代码去实现。这里用到了原书作者编写的一个 Parser 类,通过该类可以非常直观的将 BNF 所设计的内容表示出来:
Parser expr0 = rule();
Parser primary = rule(PrimaryExpr.class).or(
rule().sep("(").ast(expr0).sep(")"),
rule().number(NumberLiteral.class),
rule().identifier(Name.class, reserved),
rule().string(StringLiteral.class));
Parser factor = rule().or(rule(NegativeExpr.class).sep("-").ast(primary), primary);
Parser expr = expr0.expression(BinaryExpr.class, factor, operators);
Parser statement0 = rule();
Parser block = rule(BlockStmnt.class)
.sep("{").option(statement0)
.repeat(rule().sep(";", Token.EOL).option(statement0))
.sep("}");
Parser simple = rule(PrimaryExpr.class).ast(expr);
Parser statement = statement0.or(
rule(IfStmnt.class).sep("if").ast(expr).ast(block).option(rule().sep("else").ast(block)),
rule(WhileStmnt.class).sep("while").ast(expr).ast(block),
simple);
Parser program = rule().or(statement, rule(NullStmnt.class)).sep(";", Token.EOL);
到此,语法分析也完成了。
通过上面的语法分析,我们得到了抽象语法树,接下来执行程序就不难了。我们只需要编写一个解释器,从抽象语法树的根节点开始遍历该树直至叶节点,并计算各节点的内容即可。
要想根据得到的抽象语法树来执行程序,各个语法树节点对象的类都需要具备eval
方法。eval
方法将计算与以该节点为根的子树对应的语句、表达式及子表达式,并返回执行结果。因此,只要各个节点都具备eval
方法,调用了根节点对象的eval
方法,就能完整执行该语法树对应的程序。
eval
方法将递归调用该节点的子节点的eval
方法,并根据它们的返回值计算自身的返回值,最后将结果返回给调用者。
举个例子:
表达式13 + 1 * 2
可以得到以下抽象语法树:
+
/ \
13 *
/ \
1 2
当我调用+
节点的eval
方法时,该方法会执行左边子树的eval
方法并获得其结果,即执行13
节点的eval
方法,结果会返回13
,将结果保存下来;接着执行右边子树的eval
方法并获得其结果,即执行*
节点的eval
方法,在执行*
节点的eval
方法时,它又会像执行+
节点的eval
方法那样,去求的左边子树和右边子树的结果,并将其相乘后返回给+
节点;最后,将求得的左子树结果与右子树结果相加并返回。
通过以上的例子不难看出,只要将不同类型的语法树节点的eval
方法各自按需实现,有了整个抽象语法树之后,执行程序非常的简单。