编译器开发从零单排(2)
NaiveCompiler 前端设计
NaiveCompiler 的前端实现主要在 c_parser.py 文件中， 其中词法分析由 Lexer 类实现， 语法分析由 Parser 类实现，生成的结果为 ast（语法树），定义于 c_ast.py。
其中 Lexer 和 Parser 类使用了 PLY 库，即 lex、yacc 的 python 实现。
本系列不涉及编译原理的原理细节，主要记录实践的方法和工具。如果你对编译器原理不熟悉的话，推荐阅读
《编译原理》（龙书）
lex & yacc
parsing techniques
以及 PLY 的文档 和 pycparser 的源码。
为了方便理解，接下来的内容都基于一个简单的 c 源码: test.c
test.c
int main() {
int x = 1;
int y = 2;
return x + y;
}
Lexical Analysis(词法分析)
基本概念
词法分析是编译器的第一个步骤，读入字符流（源代码）分离为单词（token）序列。对于每个 token，词法分析器生成 (token-name, attribute-value) 形式的输出。
例如
x = y + 1
经过 tokenizer 处理后得到的 token 如下
'x','=', 'y','+','1'
而 token 通常需要定义一个名字用于区分其类型
例如
'ID', 'EQUALS', 'PLUS', 'NUMBER'
('ID','x'), ('EQUALS','='), ('ID','y'),
('PLUS','+'), ('NUMBER','1')
常用的词法分析器生成工具为 flex，指定关键字和 token 的正则表达式即可将源码分离为 token 流。
当然，我们也可以手动构造一个自动机来识别 token，具体的例子可以参考我以前在学校上编译原理课时的课后作业 scanner.c。
ch = getc(fin);
while(ch != EOF)
{
while(ch == ' '||ch == '\n' ||ch == '\t'||ch == '\r')
{
if(ch == '\n')
linenum++;
ch = getc(fin);
}
if (isalpha(ch))
{
token[0] = ch;
i = 1;
ch = getc(fin);
while(isalnum(ch))
{
token[i++] = ch;
ch = getc(fin);
}
token[i] = '\0';
n = 0;
while((n<keywordSum)&&strcmp(token,keyword[n]))
n++;
if (n >= keywordSum)
fprintf(fout,"%s\t%s\n","ID",token);
else
fprintf(fout,"%s\t%s\n",token,token);
}
/* numbers */
else if (isdigit(ch))
{
token[0] = ch;
i = 1;
ch = getc(fin);
while(isdigit(ch))
{
token[i++] = ch;
ch = getc(fin);
}
token[i] = '\0';
fprintf(fout,"%s\t%s\n","NUM",token);
}
/* {}*();,: */
else if (strchr(singleword,ch) > 0)
{
token[0] = ch;
token[1] = '\0';
ch = getc(fin);
fprintf(fout,"%s\t%s\n",token,token);
}
....
scanner 预先读取一个字符，判断当前缓冲区中的字符串是否满足预先定义的 token 中的某一种，满足则输出 token 并继续解析。
clang 的 Lexer
clang 的 Lexer 为手工编写，位于 /inclue/clang/Lex/Lexer.h，其实现位于/lib/Lex/Lexer.cpp。Token 定义于 /inclue/clang/Lex/Token.h。
以 test.c 为例， 使用 clang 命令行 dump token 输出如下
$ clang -Xclang -dump-tokens test.c
int 'int' [StartOfLine] Loc=<test.c:1:1>
identifier 'main' [LeadingSpace] Loc=<test.c:1:5>
l_paren '(' Loc=<test.c:1:9>
r_paren ')' Loc=<test.c:1:10>
l_brace '{' [LeadingSpace] Loc=<test.c:1:12>
int 'int' [StartOfLine] [LeadingSpace] Loc=<test.c:2:5>
identifier 'x' [LeadingSpace] Loc=<test.c:2:9>
equal '=' [LeadingSpace] Loc=<test.c:2:11>
numeric_constant '1' [LeadingSpace] Loc=<test.c:2:13>
semi ';' Loc=<test.c:2:14>
int 'int' [StartOfLine] [LeadingSpace] Loc=<test.c:3:5>
identifier 'y' [LeadingSpace] Loc=<test.c:3:9>
equal '=' [LeadingSpace] Loc=<test.c:3:11>
numeric_constant '2' [LeadingSpace] Loc=<test.c:3:13>
semi ';' Loc=<test.c:3:14>
return 'return' [StartOfLine] [LeadingSpace] Loc=<test.c:4:5>
identifier 'x' [LeadingSpace] Loc=<test.c:4:12>
plus '+' [LeadingSpace] Loc=<test.c:4:14>
identifier 'y' [LeadingSpace] Loc=<test.c:4:16>
semi ';' Loc=<test.c:4:17>
r_brace '}' [StartOfLine] Loc=<test.c:5:1>
eof '' Loc=<test.c:5:2>
NaiveCompiler 中的 lex
使用 PLY 的 lex 模块，可以参考 naivecompiler 中的 c_parser.py, 第一步需要定义一个 Lex 类，进行初始化，接下来定义的内容都需要放在这个类中。
from ply import lex
from ply.lex import TOKEN
class Lexer(object):
def __init__(self, **kwargs):
self.lexer = lex.lex(object=self, **kwargs)
其中 self.lexer 变量实例化了 lex 对象，并将 self 即 Lexer 类自身作为参数传给了 lex 实例，这样 lex 将识别并使用 Lexer 类中特定的成员函数和成员变量。
然后第一步需要定义语言涉及到的 token，以 naivecompiler 为例，涉及到的 token 如下
tokens = (
"ID", "INT_CONST", "FLOAT_CONST", "CHAR_CONST", "NORMALSTRING",
"IF", "ELSE", 'WHILE', 'RETURN', 'BREAK', 'CONTINUE',
"PLUS", "MINUS", "TIMES", "DIVIDES", "EQUALS", "GT", "LT", "LAND", "LOR",
"BAND",
'INT','CHAR', 'FLOAT',
"GE", 'LE', 'NE', 'EQ',
"LBRACE", "RBRACE", "LBRACKET", "RBRACKET", "LPAREN","RPAREN","SEMI","COMMA","VOID",
"COMMENTS",
"EXTERN", "STATIC"
)
将 token 元组赋值给 Lexer 类中的 tokens 变量，ply 的 lex 模块会自动处理。C 语言中的 token 包括：变量名、数字、字符串常量、关键字和各种符号等等。
接下来定义每个 token 的正则表达式，以 t_ + token 的名字命名，放在 Lexer 类中(Python 中在类里生命的变量都在同一个作用域里，即该类自身,可以用在成员函数中以 self.变量名 的方式访问)
t_INT_CONST = r'[0-9]+'
t_PLUS = r'\+'
t_MINUS = r'-'
t_TIMES = r'\*'
t_BAND = r'&'
t_DIVIDES = r'/'
t_EQUALS = r'='
t_GT = r'>'
t_LT = r'<'
t_GE = r'>='
t_LE = r'<='
t_EQ = r'=='
t_NE = r'!='
t_LBRACE = r'\{'
t_RBRACE = r'\}'
t_LBRACKET = r'\['
t_RBRACKET = r'\]'
t_LPAREN = r'\('
t_RPAREN = r'\)'
t_SEMI = r';'
t_COMMA = r','
....
# Ignored characters
t_ignore = " \t"
其中 t_ignore 是一个特殊的变量，赋值给该变量的字符会被 Lexer 忽略，在 naivecompiler 中忽略的字符为空格和制表符。
identifier = r'[a-zA-Z_][0-9a-zA-Z_]*'
@TOKEN(identifier)
def t_ID(self, t):
if t.value in self.keywords:
t.type = self.keywords[t.value]
return t
除了以定义 t_<TOKEN> 成员变量的方式来定义 TOKEN 的正则以外，还可以定义 t_<TOKEN> 成员函数，并通过 @TOKEN(pattern) 装饰符的方式定义其正则，其中 pattern 是对应的正则的内容。上面的例子中，以 identifier 变量定义了 “变量名” TOKEN 的正则。
def t_COMMENTS(self, t):
r'\/\*(.*\n)*.*\*\/'
pass
def t_newline(self, t):
r'\n+'
t.lexer.lineno += t.value.count("\n")
除了用装饰符来定义正则，还可以在成员函数的第一行指定其正则。例如上面的 t_COMMENTS 函数，识别出注释后忽略该 TOKEN。以及 t_newline 函数识别换行符，并将文件行数信息返回给 lexer。
PLY 的 lex 库中还有一个比较重要的函数为 t_error， lex 中遇到的不满足上面 TOEKN 定义的错误字符会回调该函数。
def t_error(self, t):
print("Illegal character '%s'" % t.value[0])
t.lexer.skip(1)
我们可以在该函数中打印出错误的字符并指定 lexer 忽略这些字符。
在定义好我们的 Lexer 后，可以使用下面的函数测试其效果。
# Test it output
def test(self, data):
self.input(data)
while True:
tok = self.token()
if tok:
print(tok)
else:
break
以 test.c 为例，得到的结果如下:
LexToken(INT,'int',1,0)
LexToken(ID,'main',1,4)
LexToken(LPAREN,'(',1,8)
LexToken(RPAREN,')',1,9)
LexToken(LBRACE,'{',1,11)
LexToken(INT,'int',2,17)
LexToken(ID,'x',2,21)
LexToken(EQUALS,'=',2,23)
LexToken(INT_CONST,'1',2,25)
LexToken(SEMI,';',2,26)
LexToken(INT,'int',3,32)
LexToken(ID,'y',3,36)
LexToken(EQUALS,'=',3,38)
LexToken(INT_CONST,'2',3,40)
LexToken(SEMI,';',3,41)
LexToken(RETURN,'return',4,47)
LexToken(ID,'x',4,54)
LexToken(PLUS,'+',4,56)
LexToken(ID,'y',4,58)
LexToken(SEMI,';',4,59)
LexToken(RBRACE,'}',5,61)
Syntax Analysis(语法分析)
基本概念
语法分析是编译器的第二个步骤，语法分析器(Parser)读取词法分析产生的 TOKEN 流，生成语法树(AST)。Parser 中通常使用 BNF 来定义上下文无关文法，通过定义的文法生成 NFA 读取 TOKEN 并生成 AST。
使用 BNF 定义的语言通常会定义一系列如下的文法
<symbol> ::= __expression__
其中 Symbol 为非终结符号。 expression 由一个或多个由 '|' 分割的 symbol 序列组成。从未出现在左边的符号为“终结符”
Parser 按解析 token 的顺序可以分为自顶向下和自低向上两种。
其中自顶向下又有 LL Parser (需要消除左递归)和 递归下降 (可能需要回溯)两种。
LL Parser 一般为手工编写，从左至右按顺序读取 TOKEN，处理没有歧义的上下无关文法定义的语言。根据其提前读取的 TOEKN 个数(k)称为 LL(k) Parser, 最常见的即是 LL(1) Parser。简单的 LL(1) Parser 可以参考我以前在学写的课后作业– parser.c
其定义的部分语法如下:
<program>→{<declaration_list><statement_list>}
<declaration_list>→<declaration_list>’
<declaration_list>’→ int ID <declaration_list>’ | ε
其中 ε 表示空字符串，代表 declaration_list 结束。
根据语法可以构造如下的自动机:
其部分代码如下:
int program()
{
int es;
fscanf(fp,"%s %s\n",&token,&token1);
printf("%s %s\n", token,token1);
if(strcmp(token,"{"))
{
printf("lack { !\n");
return 1;
}
fscanf(fp,"%s %s\n",&token,&token1);
printf("%s %s\n", token,token1);
if ((es = declaration_list()) !=0)
return es;
if ((es = statement_list()) !=0)
return es;
if(strcmp(token, "}"))
{
printf("lack } ! in program\n");
return 2;
}
return 0;
}
/*
<declaration_list>→<declaration_list>’
<declaration_list>’→ int ID <declaration_list>’ | ε*/
int declaration_list()
{
return declaration_list2();
}
int declaration_list2()
{
int es;
if(strcmp(token,"int")==0)
{
if ((es = declaration_stat()) != 0)
return es;
if ((es = declaration_list2()) != 0)
return es;
}
return 0;
}
int declaration_stat()
{
fscanf(fp,"%s %s\n",&token,&token1);
printf("%s %s\n", token,token1);
if(strcmp(token,"ID"))
{
printf("lack identifier\n");
return 3;
}
fscanf(fp,"%s %s\n",&token,&token1);
printf("%s %s\n", token,token1);
if(strcmp(token,";"))
{
printf("lack semicolon - ; !\n");
return 4;
}
fscanf(fp,"%s %s\n",&token,&token1);
printf("%s %s\n", token,token1);
return 0;
}
可以看到代码中严格按照上图中定义的 DFA 实现，每次预读下一个 TOKEN，判断当前状态是否符合语法。
而自低向上的 Parser 为各类 LR Parser。如 LR(k)、SLR 以及 LALR 等等。
YACC 使用的便是 LR 算法，即从左至右读取 token，根据语法生成的自动机决定是否将 token 放入栈中，如果栈顶的元素满足一个语法(grammer)右侧的定义则将栈中的元素按规则替换为语法左侧定义的内容，再继续解析剩下的 token。这种方法又叫 shift-reduce parsing。
根据 PLY 的文档，YACC 解析表达式 3 + 5 * (10 - 20) 的过程如下:
Step Symbol Stack Input Tokens Action
---- --------------------- --------------------- -------------------------------
1 3 + 5 * ( 10 - 20 )$ Shift 3
2 3 + 5 * ( 10 - 20 )$ Reduce factor : NUMBER
3 factor + 5 * ( 10 - 20 )$ Reduce term : factor
4 term + 5 * ( 10 - 20 )$ Reduce expr : term
5 expr + 5 * ( 10 - 20 )$ Shift +
6 expr + 5 * ( 10 - 20 )$ Shift 5
7 expr + 5 * ( 10 - 20 )$ Reduce factor : NUMBER
8 expr + factor * ( 10 - 20 )$ Reduce term : factor
9 expr + term * ( 10 - 20 )$ Shift *
10 expr + term * ( 10 - 20 )$ Shift (
11 expr + term * ( 10 - 20 )$ Shift 10
12 expr + term * ( 10 - 20 )$ Reduce factor : NUMBER
13 expr + term * ( factor - 20 )$ Reduce term : factor
14 expr + term * ( term - 20 )$ Reduce expr : term
15 expr + term * ( expr - 20 )$ Shift -
16 expr + term * ( expr - 20 )$ Shift 20
17 expr + term * ( expr - 20 )$ Reduce factor : NUMBER
18 expr + term * ( expr - factor )$ Reduce term : factor
19 expr + term * ( expr - term )$ Reduce expr : expr - term
20 expr + term * ( expr )$ Shift )
21 expr + term * ( expr ) $ Reduce factor : (expr)
22 expr + term * factor $ Reduce term : term * factor
23 expr + term $ Reduce expr : expr + term
24 expr $ Reduce expr
25 $ Success!
Clang 中的 Parser
Clang 中使用的是手工编写的自顶向下的递归下降 Parser。
以 test.c 为例， 使用 clang 命令行 dump ast 的方法参考 dump_ast.sh, 输出如下
$ clang -Xclang -ast-dump -fsyntax-only test.c
...
`-FunctionDecl 0x7fffee2c5ec0 <test.c:1:1, line:5:1> line:1:5 main 'int ()'
`-CompoundStmt 0x7fffee2c61c0 <col:12, line:5:1>
|-DeclStmt 0x7fffee2c6038 <line:2:5, col:14>
| `-VarDecl 0x7fffee2c5fb8 <col:5, col:13> col:9 used x 'int' cinit
| `-IntegerLiteral 0x7fffee2c6018 <col:13> 'int' 1
|-DeclStmt 0x7fffee2c60e8 <line:3:5, col:14>
| `-VarDecl 0x7fffee2c6068 <col:5, col:13> col:9 used y 'int' cinit
| `-IntegerLiteral 0x7fffee2c60c8 <col:13> 'int' 2
`-ReturnStmt 0x7fffee2c61a8 <line:4:5, col:16>
`-BinaryOperator 0x7fffee2c6180 <col:12, col:16> 'int' '+'
|-ImplicitCastExpr 0x7fffee2c6150 <col:12> 'int' <LValueToRValue>
| `-DeclRefExpr 0x7fffee2c6100 <col:12> 'int' lvalue Var 0x7fffee2c5fb8 'x' 'int'
`-ImplicitCastExpr 0x7fffee2c6168 <col:16> 'int' <LValueToRValue>
`-DeclRefExpr 0x7fffee2c6128 <col:16> 'int' lvalue Var 0x7fffee2c6068 'y' 'int'
NaiveCompiler 中的 Parser
使用 PLY 的 parser(yacc) 模块，可以参考 naivecompiler 中的 c_parser.py, 第一步需要定义一个 Parser 类，在初始化该类时同时初始化 Lexer，并获取 Lexer 的 tokens。参考 PLY 的文档
class Parser(object):
def __init__(self):
self.lex = Lexer()
self.tokens = self.lex.tokens
self.parser = yacc.yacc(module=self)
def parse(self, text):
return self.parser.parse(input=text, lexer=self.lex)
然后根据 PLY yacc 的文档，需要将语法(grammar rule)定义为一个个的 Python 函数，格式如下:
def p_declstmt(self, p):
""" declstmt : declaration SEMI
"""
# ^ ^ ^
# p[0] p[1] p[2]
#decls = DeclarationList(p[1])
p[0] = DeclStmt(p[1])
函数以 p_ 开头，其文档字符串(docstring)为该函数对应的语法(grammar)。每个函数只有一个参数 p 为语法对应的各个符号(Symbol)的序列，根据定义的语法，通过 p[0] 可以获取到语法冒号左边对应的符号，p[1] 取到 declaration 对应的递归的语法表示的数据， p[2] 取到的为 SEMI TOKEN 字符。
PLY 的 yacc 模块中，第一个定义语法的函数决定了语法的起始符号，在 NaiveCompiler 中为 translation_unit， yacc 模块会根据定义的语法调用对应的语法处理函数，直到没有新的输入， parser 停止工作，并返回最终的结果(为起始语法中的最左符号)，在这里为 translation_unit 的 p[0] 即 AST。
def p_translation_unit(self, p):
''' translation_unit : external_decl
| translation_unit external_decl
'''
if len(p) == 2:
p[0] = AST(p[1])
elif len(p) == 3:
p[1].l.append(p[2])
p[0] = p[1]
else:
logging.error("empty ast")
多个 Grammar Function 可以通过 | 组合在一起。如上面的
def p_external_decl(self, p):
''' external_decl : funcdef
| declstmt
'''
p[0] = p[1]
也可以由多个函数来定义，如上面的 p_funcdecl 和 p_funcdecl2。
NaiveCompiler 所支持的语法为 C 语言的部分子集，其语法定义可以参考 The C Programming Language 的附录，以及 pycparser 的源码。
NaiveCompiler 中的 AST
通常编译器先将源码解析为 Parser Tree，再通过 Visitor 模式遍历生成对应的语法树(AST)。NaiveCompiler 使用 PLY 中的 YACC 模块，在解析的过程中边解析边构建了语法树。
NaiveCompiler 中 AST 定义于 c_ast.py 中。语法树本身的数据结构就是树，其节点定义如下。
class ASTNode(object):
attr_names = ()
def __init__(self):
self.node_name = "ASTNode"
def show(self, buf=sys.stdout, offset=0):
buf.write(' '*offset + self.__class__.__name__+ ': ')
if self.attr_names:
nvlist = [(n, getattr(self,n)) for n in self.attr_names]
attrstr = ', '.join('%s=%s' % nv for nv in nvlist)
buf.write(attrstr)
buf.write('\n')
for child in self.children():
child.show(offset = offset + 2)
def children(self):
raise NotImplementedError
每一个语法树节点都包含其属性和子节点(可能为空)。show 函数定义了该节点如何打印。
语法树的根节点为 AST 节点，在 c_paser.py 中 Parser 最后返回的即为该对象。
class AST(ASTNode):
def __init__(self, trans_unit):
self.l = [trans_unit]
def children(self):
return self.l
def p_translation_unit(self, p):
''' translation_unit : external_decl
| translation_unit external_decl
'''
if len(p) == 2:
p[0] = AST(p[1])
elif len(p) == 3:
p[1].l.append(p[2])
p[0] = p[1]
else:
logging.error("empty ast")
可以看到 Parser 中第一个定义的语法函数即为 p_translation_unit，其中 translation_unit 为语法规则中最左侧的符号， 所以该函数返回的对象，即 p[0]=AST 为 Parser 的最终结果。
同时在该函数中也可以看到，当右边的符号只有一个时，p[1] 对应 external_decl ，可以传入 AST 的 init 函数，初始化 AST 对象。
def p_external_decl(self, p):
''' external_decl : funcdef
| declstmt
'''
p[0] = p[1]
def p_funcdecl(self, p):
''' funcdecl : storage type methodsymbol LPAREN param_list RPAREN'''
p[0] = FuncDecl(p[2], p[3], p[5], p[1])
def p_funcdecl_2(self, p):
''' funcdecl : type methodsymbol LPAREN param_list RPAREN'''
p[0] = FuncDecl(p[1], p[2], p[4])
而 external_decl 可以 resolve 到 declstmt 最后到 funcdecl，所以自顶向下观察的话， AST 的子节点的可能为 FuncDecl。
NaiveCompiler 中，使用 python compiler.py --show-ast test.c 可以打印出源码对应的语法树，以上面的 test.c 为例，打印的语法树如下:
----------- show ast ------------
AST:
FuncDef: return_type=int, storage=extern
MethodSymbol: name=main
DeclarationList:
StmtList:
DeclStmt:
TypeDecl: _type=int, storage=auto
VariableSymbol: name=x
Const: _type=int, val=1
DeclStmt:
TypeDecl: _type=int, storage=auto
VariableSymbol: name=y
Const: _type=int, val=2
ReturnStmt:
BinaryOp: op=+
VariableSymbol: name=x
VariableSymbol: name=y