本系列的原始英文教程地址：https://ruslanspivak.com/lsbasi-part9/
本文的代码和原作的可能略有出入，因为是博主一行一行敲出来的，原作者也鼓励大家亲自动手实现一遍，才能真正理解编译器与解释器的真谛！因此建议大家来理解了思路之后，从最基本的计算器开始写起：支持10以内加法 => 支持任意整数加法 => 任意整数加减法 => 任意整数加减乘除 => 支持括号 => 支持一元运算 => 支持变量 => 支持关键字 => … 一路下来真的收获满满！
本文开始正式进行程序语言解释器的开发，目标语言为 pascal！实现对如下代码的解析与执行：
BEGIN
BEGIN
number := 2;
a := number;
b := 10 * a + 10 * number / 4;
c := a - - b
END;
x := 11;
END.
有了前面一系列文章的铺垫，在上一篇的支持变量的多行程序解释器的基础之上，实现起来真的很简单，语法规则中无非是增加了关键字 （BEGIN，END，DOT）
program : compound_statement DOT
compound_statement : BEGIN statement_list END
statement_list : statement
| statement SEMI statement_list
statement : compound_statement
| assignment_statement
| empty
assignment_statement : variable ASSIGN expr
empty :
expr: term ((PLUS | MINUS) term)*
term: factor ((MUL | DIV) factor)*
factor : PLUS factor
| MINUS factor
| INTEGER
| LPAREN expr RPAREN
| variable
variable: ID
实现效果如下：
srcCode>
.......> BEGIN
.......> BEGIN
.......> number := 2;
.......> a := number;
.......> b := 10 * a + 10 * number / 4;
.......> c := a - - b
.......> END;
.......> x := 11;
.......> END.
.......>
{'number': 2, 'a': 2, 'b': 25.0, 'c': 27.0, 'x': 11}
程序解释器 Version 14
import json
import copy
NUMBER, PLUS, MINUS, MUL, DIV, LPAR, RPAR, EOF = 'NUMBER', 'PLUS', 'MINUS', 'MUL', 'DIV', '(', ')', 'EOF'
SEMI = 'SEMI'
ASSIGN = 'ASSIGN'
ID = 'ID'
DOT = 'DOT'
BEGIN = 'BEGIN'
END = 'END'
class AST:
pass
class CompoundStatement(AST):
def __init__(self, node_type, statement_list):
self.type = node_type
self.children = statement_list
def __repr__(self):
return f'{{"type":"{self.type}", "children":{self.children}}}'
__str__ = __repr__
class BinOp(AST):
def __init__(self, node_type, left_node, right_node):
self.type = node_type
self.left_node = left_node
self.right_node = right_node
def __repr__(self):
return f'{{"type":"{self.type}", "left":{self.left_node}, "right":{self.right_node}}}'
__str__ = __repr__
class UniOp(AST):
def __init__(self, node_type, child_node):
self.type = node_type
self.child_node = child_node
def __repr__(self):
return f'{{"type":"{self.type}", "child":{self.child_node}}}'
__str__ = __repr__
class Leaf(AST):
def __init__(self, node_type, value):
self.type = node_type
self.value = value
def __repr__(self):
return f'{{"type":"{self.type}", "value":{self.value}}}'
__str__ = __repr__
class Token:
def __init__(self, token_type, value):
self.type = token_type
self.value = value
def __repr__(self,):
return f'Token({self.type}, {self.value})'
class Lexer:
reserved_words = [BEGIN, END]
def __init__(self, text):
self.text = text
self.pos = 0
self.current_char = self.text[self.pos]
def copy(self,):
l = Lexer(self.text)
l.pos = self.pos
def peek(self):
if 1 + self.pos >= len(self.text):
return None
return self.text[self.pos + 1]
def error(self, msg=''):
raise Exception(f'Lexer Error! {msg}')
def advance(self):
self.pos += 1
if self.pos >= len(self.text):
self.current_char = None
else:
self.current_char = self.text[self.pos]
def skip_space(self):
blank_chars = [' ', 'n', 't']
if self.current_char in blank_chars:
while self.current_char in blank_chars:
self.advance()
def _id(self,):
var_id = ''
while self.current_char is not None and self.current_char.isalnum():
var_id += self.current_char
self.advance()
if var_id.upper() in self.reserved_words:
return Token(var_id.upper(),var_id.upper())
return Token(ID, var_id)
def get_next_token(self, ):
self.skip_space()
if self.current_char is None:
return Token(EOF, None)
if self.current_char.isdigit():
number = ''
while self.current_char is not None and self.current_char.isdigit():
number += self.current_char
self.advance()
return Token(NUMBER, int(number))
if self.current_char.isalpha():
return self._id()
if self.current_char == '+':
self.advance()
return Token(PLUS, '+')
if self.current_char == '-':
self.advance()
return Token(MINUS, '-')
if self.current_char == '*':
self.advance()
return Token(MUL, '*')
if self.current_char == '/':
self.advance()
return Token(DIV, '/')
if self.current_char == '(':
self.advance()
return Token(LPAR, '(')
if self.current_char == ')':
self.advance()
return Token(RPAR, ')')
if self.current_char == ';':
self.advance()
return Token(SEMI, ';')
if self.current_char == ':' and self.peek() == '=':
self.advance()
self.advance()
return Token(ASSIGN, '=')
if self.current_char == '.':
self.advance()
return Token(DOT, '.')
self.error(f'current_char: {self.current_char}')
class Parser:
"""
statement_list: (statement SEMI)*
statement: assign_statement | expr | empty
empty:
assign_statement: VAR ASSIGN expr
expr: term((PLUS|MINUS)term)*
term: factor(MUL|DIV)factor)*
factor: NUMBER| LPAR expr RPAR | (PLUS|MINUS) factor | variable
variable: ID
"""
def __init__(self, lexer):
self.lexer = lexer
self.current_token = self.lexer.get_next_token()
def error(self, msg = ''):
raise Exception(f'Parse Error! {msg}')
def peek(self,):
if self.current_token is None:
return None
return copy.copy(self.lexer).get_next_token()
def eat(self, token_type):
if type(token_type) == list and self.current_token.type not in token_type:
self.error(f'current token not in list, expect {token_type}, got {self.current_token}.')
elif type(token_type) == str and self.current_token.type != token_type:
self.error(f'current token not match, expect {token_type}, got {self.current_token}.')
else:
self.current_token = self.lexer.get_next_token()
def variable(self,):
f = self.current_token
self.eat(ID)
return Leaf(ID, f.value)
def factor(self,):
f = self.current_token
if f.type == NUMBER:
self.eat(NUMBER)
return Leaf(NUMBER, f.value)
elif f.type == LPAR:
self.eat(LPAR)
expr = self.expr()
self.eat(RPAR)
return expr
elif f.type in [PLUS, MINUS]:
self.eat(f.type)
return UniOp(f.type, self.factor())
else:
return self.variable()
self.error()
def term(self,):
"""
term: factor(MUL|DIV)factor)*
"""
node = self.factor()
while(self.current_token.type in [MUL, DIV]):
op = self.current_token
self.eat([MUL, DIV])
f = self.factor()
_node = BinOp(op.type, node, f)
node = _node
return node
def expr(self,):
node = self.term()
while(self.current_token.type in [PLUS, MINUS]):
op = self.current_token
self.eat([PLUS, MINUS])
t = self.term()
_node = BinOp(op.type, node, t)
node = _node
return node
def assign_statement(self,):
"""
assign_statement: VAR ASSIGN expr
"""
var = self.variable()
op = self.current_token
self.eat(ASSIGN)
expr_node = self.expr()
return BinOp(ASSIGN, var, expr_node)
def empty(self):
return Leaf('EMPTY', None)
def statement(self,):
"""
statement: assign_statement | empty
"""
if self.current_token.type == BEGIN:
return self.compound_statement()
elif self.current_token.type == ID and self.peek().type == ASSIGN:
return self.assign_statement()
else:
return self.empty()
def compound_statement(self):
self.eat(BEGIN)
node = self.statement()
node_list = [node]
while self.current_token.type == SEMI:
self.eat(SEMI)
node_list.append(self.statement())
self.eat(END)
return CompoundStatement('CompoundStatement', node_list)
def program(self):
node = self.compound_statement()
self.eat(DOT)
return node
def ast(self):
return self.program()
class Interpreter:
def __init__(self, parser):
self.parser = parser
self.GLOBAL_SCOPE = {}
def error(self, msg=''):
raise Exception(f'Interpeter Error! {msg}')
def compute(self):
ast = self.parser.ast()
self.visit_node(ast)
return self.GLOBAL_SCOPE
def visit_BinOp(self, node):
if node.type == PLUS:
return self.visit_node(node.left_node) + self.visit_node(node.right_node)
if node.type == MINUS:
return self.visit_node(node.left_node) - self.visit_node(node.right_node)
if node.type == MUL:
return self.visit_node(node.left_node) * self.visit_node(node.right_node)
if node.type == DIV:
return self.visit_node(node.left_node) / self.visit_node(node.right_node)
def visit_UniOp(self, node):
if node.type == PLUS:
return self.visit_node(node.child_node)
if node.type == MINUS:
return - self.visit_node(node.child_node)
def visit_statement(self, node):
if node.type == ASSIGN:
var = node.left_node
expr_result = self.visit_node(node.right_node)
self.GLOBAL_SCOPE[var.value] = expr_result
elif isinstance(node, CompoundStatement):
self.visit_CompoundStatement(node)
def visit_CompoundStatement(self, node):
for statement in node.children:
self.visit_statement(statement)
def visit_Leaf(self, node):
if node.type == NUMBER:
return node.value
elif node.type == ID:
if node.value in self.GLOBAL_SCOPE:
return self.GLOBAL_SCOPE[node.value]
else:
self.error(f"variable '{node.value}' not defined!")
def visit_node(self, node):
if isinstance(node, Leaf):
return self.visit_Leaf(node)
elif isinstance(node, BinOp):
return self.visit_BinOp(node)
elif isinstance(node, UniOp):
return self.visit_UniOp(node)
elif isinstance(node, CompoundStatement):
self.visit_CompoundStatement(node)
测试用例
test_cases = []
test_cases.append("""
BEGIN
BEGIN
number := 2;
a := number;
b := 10 * a + 10 * number / 4;
c := a - - b
END;
x := 11;
END.
""")
test_cases.append("""
BEGIN
BEGIN
number := 2;
a := number;
b := 10 * a + 10 * number / 4;
c := a - - b
END;
BEGIN
number2 := c;
a := number2;
b := 10 * a + 10 * number2 / 4;
c := a - - b
END;
x := number + number2
END.
""")
for text in test_cases:
try:
print('srcCode> ', text.replace('n', 'n.......> '))
if text:
lexer = Lexer(text)
parser = Parser(lexer)
interpreter = Interpreter(parser)
print(interpreter.compute())
print()
except Exception as e:
print(e)
print()
