# -*- coding: utf-8 -*- from ast import * from token import Tag from scope import Scope class ParseError(Exception): pass class Parser: def __init__(self, lexer): self.lexer = lexer self.scope = Scope() self.move() def parse(self): return self.program() def move(self): self.token = self.lexer.scan() def error(self, msg): raise ParseError(msg) def _match(self, tag): if self.token == None: self.error("Unexpected end of file.") if self.token.tag != tag: self.error("match: expected %s got %s\n" %(tag, self.token.tag)) val = self.token.value self.move() return val def match(self, tag, *tags): for t in (tag,) + tags: res = self._match(t) return res # boolean = join { "||" join }. def boolean(self): res = self.join() while self.token.tag == Tag.OPERATOR and self.token.value == "||": res = BinaryExpression(res, self.match(Tag.OPERATOR), self.join(), self.lexer.line) return res # join = relation { "&&" relation }. def join(self): res = self.relation() while self.token.tag == Tag.OPERATOR and self.token.value == "&&": res = BinaryExpression(res, self.match(Tag.OPERATOR), self.relation(), self.lexer.line) return res # relation = expression [ ( "==" | "!=" | "<" | "<=" | ">=" | ">" ) expression ]. def relation(self): res = self.expression() while self.token.tag == Tag.OPERATOR and self.token.value in ["==", "!=", "<", "<=", ">=", ">"]: res = BinaryExpression(res, self.match(Tag.OPERATOR), self.expression(), self.lexer.line) return res # expression = term [ ( "+" | "-" ) term ]. def expression(self): res = self.term() while self.token.tag == Tag.OPERATOR and self.token.value in ["+", "-"]: res = BinaryExpression(res, self.match(Tag.OPERATOR), self.term(), self.lexer.line) return res # term = unary [ ( "*" | "/" | "%" ) unary ]. def term(self): res = self.unary() while self.token.tag == Tag.OPERATOR and self.token.value in ["*", "/", "%"]: res = BinaryExpression(res, self.match(Tag.OPERATOR), self.unary(), self.lexer.line) return res # unary = "!" unary | "-" unary | factor. def unary(self): if self.token.tag == Tag.OPERATOR and self.token.value in ["!", "-"]: return UnaryExpression(self.match(Tag.OPERATOR), self.unary(), self.lexer.line) return self.factor() # factor = "(" boolean ")" | integer | "true" | "false" | ident | function_call. def factor(self): if self.token.tag == Tag.LPAREN: self.move() res = self.boolean() self.match(Tag.RPAREN) return res if self.token.tag == Tag.NUMBER: return Constant(self.match(Tag.NUMBER), self.lexer.line) if self.token.tag == Tag.TRUE: self.move() return Constant(1, self.lexer.line) if self.token.tag == Tag.FALSE: self.move() return Constant(0, self.lexer.line) if self.token.tag == Tag.IDENT: line = self.lexer.line name = self.match(Tag.IDENT) if not self.scope.contains(name): raise SyntaxError("%s is not declared in line %d" % (name, line)) return Variable(name, line) return self.function_call() # function_call = "call" ident "[" [ expression_list ] "]". def function_call(self): name = self.match(Tag.CALL, Tag.IDENT) self.match(Tag.LBRAK) args = [] if self.token.tag == Tag.RBRAK else self.expression_list() self.match(Tag.RBRAK) return FunctionCall(name, args, self.lexer.line) # ident_list = ident { "," ident }. def ident_list(self): ident = [self.match(Tag.IDENT)] while self.token.tag == Tag.COMMA: self.move() ident.append(self.match(Tag.IDENT)) return ident # expression_list = boolean { "," boolean }. def expression_list(self): exp = [self.boolean()] while self.token.tag == Tag.COMMA: self.move() exp.append(self.boolean()) return exp # function_list = function { function }. def function_list(self): funcs = [self.function()] while self.token: funcs.append(self.function()) return funcs # statement_list = statement { statement }. def statement_list(self): if self.token.tag in [Tag.END, Tag.ELSE]: return None return Sequence(self.statement(), self.statement_list(), self.lexer.line) # function = "fun" ident "[" [ ident_list ] "]" nl statement_list "end" nl. def function(self): line = self.lexer.line name = self.match(Tag.FUN, Tag.IDENT) self.match(Tag.LBRAK) args = [] if self.token.tag == Tag.RBRAK else self.ident_list() self.match(Tag.RBRAK, Tag.NEWLINE) self.scope.new(name) self.scope.add_params(args) block = self.statement_list() self.match(Tag.END, Tag.NEWLINE) return Function(name, args, block, line) # statement = ( if_statement | while_statement | assign_statement | return_statement | function_call | print_statement ) nl. def statement(self): res = {Tag.IF: self.if_statement, Tag.WHILE: self.while_statement, Tag.IDENT: self.assignment, Tag.RETURN: self.return_statement, Tag.PRINT: self.print_statement, Tag.CALL: self.function_call, }[self.token.tag]() self.match(Tag.NEWLINE) return res # if_statement = "if" boolean nl statement_list [ "else" nl statement_list ] "end". def if_statement(self): line = self.lexer.line self.match(Tag.IF) condition = self.boolean() self.match(Tag.NEWLINE) true_case = self.statement_list() else_case = None if self.token.tag == Tag.ELSE: self.move() self.match(Tag.NEWLINE) else_case = self.statement_list() self.match(Tag.END) return IfStatement(condition, true_case, else_case, line) # while_statement = "while" boolean nl statement_list "end". def while_statement(self): line = self.lexer.line self.match(Tag.WHILE) condition = self.boolean() self.match(Tag.NEWLINE) body = self.statement_list() self.match(Tag.END) return WhileStatement(condition, body, line) # return_statement = "@" boolean. def return_statement(self): line = self.lexer.line self.match(Tag.RETURN) exp = self.boolean() return ReturnStatement(exp, line) # assignment = ident "=" boolean. def assignment(self): line = self.lexer.line name = self.match(Tag.IDENT) self.match(Tag.ASSIGNMENT) exp = self.boolean() self.scope.add_locals(name) return AssignStatement(name, exp, line) def print_statement(self): line = self.lexer.line self.match(Tag.PRINT) exp = self.boolean() return PrintStatement(exp, line) # program = function_list. def program(self): return Program(self.function_list())