Note: 所有代码、定义、术语命名都参考 Nora Sandler 的书籍 Write a C Compiler
Lexer
这部分没新增什么东西，只需要 $3$ 个 token 类型即可。
| 字符序列 |
运算符名称 |
语义说明 |
~ |
Bitwise complement |
按位取反 |
- |
Negation |
算数负号 |
-- |
Decrement |
自减运算符 |
注意到我们新增了 -- 运算符的解析。这是因为目前编译器只支持常量，而 --2 这样的表达式是非法的，我们应在解析阶段报错。如果我们不解析 --，编译器会将 --2 识别为 -(-2) 造成语义上的错误。所以在 Lexer 阶段我们会解析 -- 运算符，但在后续阶段，我们会忽略它。
对应的正则表达式和上一章中的标点符号 ;, ( 一致，这里不做赘述。
Implementation
lib/token.ml:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| type t =
| Identifier of string
| Constant of int
| KWInt
| KWReturn
| KWVoid
| OpenParen
| CloseParen
| OpenBrace
| CloseBrace
| Semicolon
| Tilde
| Hyphen
| DoubleHyphen
|
lib/lexer.ml:
1
2
3
4
5
6
7
8
9
10
11
12
13
| let match_rules =
[
generate_rule {_|[A-Za-z_][A-Za-z0-9_]*\b|_} convert_identifier;
generate_rule {_|[0-9]+\b|_} convert_constant;
generate_rule {_|\(|_} (convert_literal T.OpenParen);
generate_rule {_|\)|_} (convert_literal T.CloseParen);
generate_rule {_|\{|_} (convert_literal T.OpenBrace);
generate_rule {_|\}|_} (convert_literal T.CloseBrace);
generate_rule ";" (convert_literal T.Semicolon);
generate_rule "-" (convert_literal T.Hyphen);
generate_rule "--" (convert_literal T.DoubleHyphen);
generate_rule "~" (convert_literal T.Tilde);
]
|
Parser
更新新的 AST 定义：
1
2
3
4
5
| program = Program(function_definition)
function_definition = Function(identifier name, statement body)
statement = Return(exp)
exp = Constant(int) | Unary(unary_operator, exp)
unary_operator = Complement | Negate
|
为 exp 新增了 Unary 的定义，表示一元操作表达式，由一个 unary-operator 和 exp 组成。
注意现在 exp 的定义是递归的：一个 Unary 内部可能包含另一个 exp。
新定义了 unary_operator 结点，值 Complement 对应 ~ 运算符，值 Negate 对应 - 运算符。
更新后的形式文法：
1
2
3
4
5
6
7
| <program> ::= <function>
<function> ::= "int" <identifier> "(" "void" ")" "{" <statement> "}"
<statement> ::= "return" <exp> ";"
<exp> ::= <int> | <unop> <exp> | "(" <exp> ")"
<unop> ::= "-" | "~"
<identifier> ::= ? An identifier token ?
<int> ::= ? A constant token ?
|
新增 exp 的产生式规则 <unop> <exp> 和 "(" <exp> ")"。 AST 中不保留括号信息，1、（1) 和 ((((((((1))))))) 在 AST 中均表示为 Constant(1)。注意并没有给出 递减操作符号 -- 的产生式规则，如果遇到 Token.DoubleHyphen 应报错。
<unop> 对应 AST 中的 unary_operator 类型。
对应 parser_exp 的伪代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| parse_exp(tokens):
next_token = peek(tokens)
if next_token is an int:
--snip--
else if next_token is "~" or "-":
operator = parse_unop(tokens)
inner_exp = parse_exp(tokens)
return Unary(operator, inner_exp)
else if next_token == "(":
take_token(tokens)
inner_exp = parse_exp(tokens)
expect(")", tokens)
return inner_exp
else:
fail("Malformed expression")
|
其中的 peek 函数作用为：查看下一个 token 但不消耗它。用以决定应用哪条产生式规则。如果为 一元操作符，首先解析操作符类型，并递归调用 parse_exp 解析操作数，最后构造 Unary 结点。
如果为括号表达式，则首先消耗左括号，递归解析内部表达值，并验证右括号存在。不创建新结点，直接返回内部表达式。
Implementation
lib/Tok_stream.ml
1
2
3
4
| let peek tokens =
match Stream.peek tokens with
| Some token -> token
| None -> raise End_of_stream
|
lib/parser.ml
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
let parse_unop tokens =
match Tok_stream.take_token tokens with
| T.Tilde -> Ast.Complement
| T.Hyphen -> Ast.Negate
| other -> raise_error ~expected:(Name "a unary operator") ~actual:other
let rec parse_exp tokens =
match Tok_stream.peek tokens with
| T.Constant _ -> parse_int tokens
| T.Tilde | T.Hyphen ->
let opera = parse_unop tokens in
let inner_exp = parse_exp tokens in
Unary (opera, inner_exp)
| T.OpenParen ->
let _ = Tok_stream.take_token tokens in
let expr = parse_exp tokens in
expect T.CloseParen tokens;
expr
| other -> raise_error ~expected:(Name "an expression") ~actual:other
|