Mercurial > lcfOS
changeset 220:3f6c30a5d234
Major change in expression parsing to enable pointers and structs
| author | Windel Bouwman |
|---|---|
| date | Sat, 06 Jul 2013 21:32:20 +0200 |
| parents | 1fa3e0050b49 |
| children | 848c4b15fd0b |
| files | python/c3/analyse.py python/c3/astnodes.py python/c3/codegenerator.py python/c3/examples/comments.c3 python/c3/parser.py python/c3/typecheck.py python/c3/visitor.py python/stm32f4/blink.c3 python/testc3.py |
| diffstat | 9 files changed, 346 insertions(+), 193 deletions(-) [+] |
line wrap: on
line diff
--- a/python/c3/analyse.py Sat Jul 06 12:38:09 2013 +0200 +++ b/python/c3/analyse.py Sat Jul 06 21:32:20 2013 +0200 @@ -15,9 +15,9 @@ self.ok = True visitor = Visitor() # Prepare top level scope: - self.curScope = topScope + self.scopeStack = [topScope] visitor.visit(pkg, self.enterScope, self.quitScope) - del self.curScope + del self.scopeStack visitor.visit(pkg, self.findRefs) visitor.visit(pkg, self.sanity) return self.ok @@ -26,16 +26,20 @@ self.ok = False self.diag.error(msg, loc) + @property + def currentScope(self): + return self.scopeStack[-1] + # Scope creation: def addSymbol(self, sym): - if self.curScope.hasSymbol(sym.name): + if self.currentScope.hasSymbol(sym.name): self.error('Redefinition of {0}'.format(sym.name), sym.loc) else: - self.curScope.addSymbol(sym) + self.currentScope.addSymbol(sym) def enterScope(self, sym): # Distribute the scope: - sym.scope = self.curScope + sym.scope = self.currentScope # Add symbols to current scope: if isinstance(sym, Symbol): @@ -43,17 +47,18 @@ # Create subscope: if type(sym) in [Package, Function]: - self.curScope = Scope(self.curScope) - sym.innerScope = self.curScope + newScope = Scope(self.currentScope) + self.scopeStack.append(newScope) + sym.innerScope = self.currentScope def quitScope(self, sym): # Pop out of scope: if type(sym) in [Package, Function]: - self.curScope = self.curScope.parent + self.scopeStack.pop(-1) # Reference fixups: def resolveDesignator(self, d, scope): - assert type(d) is Designator + assert type(d) is Designator, type(d) assert type(scope) is Scope if scope.hasSymbol(d.tname): s = scope.getSymbol(d.tname) @@ -66,18 +71,29 @@ msg = 'Cannot resolve name {0}'.format(d.tname) self.diag.error(msg, d.loc) + def resolveType(self, t, scope): + # TODO: what about structs? + if type(t) is PointerType: + t.ptype = self.resolveType(t.ptype, scope) + return t + elif type(t) is Designator: + return self.resolveDesignator(t, scope) + else: + print('ERR resolve type!') + def findRefs(self, sym): if type(sym) in [Variable, Constant]: - sym.typ = self.resolveDesignator(sym.typ, sym.scope) + sym.typ = self.resolveType(sym.typ, sym.scope) elif type(sym) is VariableUse: - sym.target = self.resolveDesignator(sym.target, sym.scope) + sym.target = self.resolveDesignator(sym.target, sym.scope) elif type(sym) is FunctionCall: - sym.proc = self.resolveDesignator(sym.proc, sym.scope) + varuse = sym.proc + sym.proc = self.resolveDesignator(varuse.target, sym.scope) elif type(sym) is Function: # Checkup function type: ft = sym.typ - ft.returntype = self.resolveDesignator(ft.returntype, sym.scope) - ft.parametertypes = [self.resolveDesignator(pt, sym.scope) for pt in ft.parametertypes] + ft.returntype = self.resolveType(ft.returntype, sym.scope) + ft.parametertypes = [self.resolveType(pt, sym.scope) for pt in ft.parametertypes] def sanity(self, sym): if type(sym) is FunctionType:
--- a/python/c3/astnodes.py Sat Jul 06 12:38:09 2013 +0200 +++ b/python/c3/astnodes.py Sat Jul 06 21:32:20 2013 +0200 @@ -5,6 +5,8 @@ Finally code is generated from it. """ +from ppci import SourceLocation + class Node: pass @@ -58,6 +60,8 @@ class PointerType(Type): def __init__(self, ptype): self.ptype = ptype + def __repr__(self): + return '({}*)'.format(self.ptype) class StructureType(Type): def __init__(self, mems): @@ -112,23 +116,33 @@ return 'Func {}'.format(self.name) # Operations / Expressions: -class Unop(Node): - def __init__(self, a, op): - self.a = a - self.op = op - def __repr__(self): +class Expression(Node): + pass + +class Unop(Expression): + def __init__(self, op, a, loc): + assert isinstance(a, Expression) + assert isinstance(op, str) + self.a = a + self.op = op + self.loc = loc + def __repr__(self): return 'UNOP {}'.format(self.op) -class Binop(Node): - def __init__(self, a, op, b, loc): - self.a = a - self.b = b - self.op = op # Operation: '+', '-', '*', '/', 'mod' - self.loc = loc - def __repr__(self): - return 'BINOP {}'.format(self.op) +class Binop(Expression): + def __init__(self, a, op, b, loc): + assert isinstance(a, Expression), type(a) + assert isinstance(b, Expression) + assert isinstance(op, str) + self.a = a + self.b = b + self.op = op # Operation: '+', '-', '*', '/', 'mod' + self.loc = loc -class VariableUse(Node): + def __repr__(self): + return 'BINOP {}'.format(self.op) + +class VariableUse(Expression): def __init__(self, target, loc): self.target = target self.loc = loc @@ -136,40 +150,14 @@ nm = self.target.name if hasattr(self.target, 'name') else '' return 'VAR USE {}'.format(nm) -class Literal(Node): +class Literal(Expression): def __init__(self, val, loc): self.val = val self.loc = loc def __repr__(self): return 'LITERAL {}'.format(self.val) - -# Statements -class CompoundStatement(Node): - def __init__(self, statements): - self.statements = statements - def __repr__(self): - return 'COMPOUND STATEMENT' - -class EmptyStatement(Node): - def __repr__(self): - return 'NOP' - -class ReturnStatement(Node): - def __init__(self, expr): - self.expr = expr - def __repr__(self): - return 'RETURN STATEMENT' - -class Assignment(Node): - def __init__(self, lval, rval, loc): - self.lval = lval - self.rval = rval - self.loc = loc - def __repr__(self): - return 'ASSIGNMENT' - -class FunctionCall(Node): +class FunctionCall(Expression): def __init__(self, proc, args, loc): self.proc = proc self.args = args @@ -177,7 +165,41 @@ def __repr__(self): return 'CALL {0} '.format(self.proc) -class IfStatement(Node): +# Statements +class Statement(Node): + pass + +class CompoundStatement(Statement): + def __init__(self, statements): + self.statements = statements + + def __repr__(self): + return 'COMPOUND STATEMENT' + +class EmptyStatement(Statement): + def __repr__(self): + return 'NOP' + +class ReturnStatement(Statement): + def __init__(self, expr, loc): + self.expr = expr + self.loc = loc + def __repr__(self): + return 'RETURN STATEMENT' + +class Assignment(Node): + def __init__(self, lval, rval, loc): + assert isinstance(lval, Node) + assert isinstance(rval, Node) + assert isinstance(loc, SourceLocation) + self.lval = lval + self.rval = rval + self.loc = loc + + def __repr__(self): + return 'ASSIGNMENT' + +class IfStatement(Statement): def __init__(self, condition, truestatement, falsestatement, loc): self.condition = condition self.truestatement = truestatement @@ -186,7 +208,7 @@ def __repr__(self): return 'IF-statement' -class WhileStatement(Node): +class WhileStatement(Statement): def __init__(self, condition, statement, loc): self.condition = condition self.statement = statement
--- a/python/c3/codegenerator.py Sat Jul 06 12:38:09 2013 +0200 +++ b/python/c3/codegenerator.py Sat Jul 06 21:32:20 2013 +0200 @@ -1,6 +1,7 @@ import ir from . import astnodes from .scope import boolType +from ppci import CompilerError class CodeGenerator: """ Generates intermediate code from a package """ @@ -54,6 +55,7 @@ self.genCode(s) elif type(code) is astnodes.Assignment: re = self.genExprCode(code.rval) + # TODO: Handle pointers loc = self.varMap[code.lval.target] self.builder.addIns(ir.Store(loc, re)) elif type(code) is astnodes.IfStatement: @@ -137,6 +139,15 @@ tmp = self.builder.newTmp() # TODO return tmp + elif type(expr) is astnodes.Unop: + if expr.op == '&': + # Address of operator + ra = self.genExprCode(expr.a) + tmp = self.builder.newTmp('addr') + return tmp + #self.builder.addIns(ins) + else: + print('Unknown {0}'.format(expr)) elif type(expr) is astnodes.Constant: tmp = self.builder.newTmp() # TODO @@ -163,5 +174,5 @@ self.builder.addIns(ins) return tmp else: - print('Unknown expr:', code) + raise CompilerError('Unknown expr {}'.format(expr))
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/c3/examples/comments.c3 Sat Jul 06 21:32:20 2013 +0200 @@ -0,0 +1,14 @@ + +/* + block + comment +*/ + +// fjd jjd- +package comments; // hjfkds + +function int tst() +{ + return 0; +} +
--- a/python/c3/parser.py Sat Jul 06 12:38:09 2013 +0200 +++ b/python/c3/parser.py Sat Jul 06 21:32:20 2013 +0200 @@ -1,11 +1,6 @@ from . import astnodes, lexer from ppci import CompilerError -# binop precedence for expressions: -binopPrecs = {'or': 5, 'and': 10, \ - '<': 20, '>': 20, '==': 20, '<=': 20, '>=': 20, '!=': 20, \ - '+': 30, '-': 30, '*': 40, '/': 40 } - class Parser: """ Parses sourcecode into an abstract syntax tree (AST) """ def __init__(self, diag): @@ -18,27 +13,26 @@ return self.mod except CompilerError as e: self.diag.addDiag(e) + def Error(self, msg): - raise CompilerError(msg, self.token.loc) + raise CompilerError(msg, self.token.loc) + # Lexer helpers: def Consume(self, typ): - if self.Peak == typ: - return self.NextToken() - else: - self.Error('Excected: "{0}", got "{1}"'.format(typ, self.Peak)) + if self.Peak == typ: + return self.NextToken() + else: + self.Error('Excected: "{0}", got "{1}"'.format(typ, self.Peak)) + @property def Peak(self): - return self.token.typ - @property - def PeakPrec(self): - if self.Peak in binopPrecs: - return binopPrecs[self.Peak] - return -1 + return self.token.typ + def hasConsumed(self, typ): - if self.Peak == typ: - self.Consume(typ) - return True - return False + if self.Peak == typ: + self.Consume(typ) + return True + return False def NextToken(self): t = self.token @@ -49,23 +43,24 @@ def initLex(self, source): self.tokens = lexer.tokenize(source) # Lexical stage self.token = self.tokens.__next__() + def addDeclaration(self, decl): self.currentPart.declarations.append(decl) def parseUses(self): + # TODO: parse uses pass def parsePackage(self): - self.Consume('package') - name = self.Consume('ID') - self.Consume(';') - self.mod = astnodes.Package(name.val, name.loc) - self.currentPart = self.mod - self.parseUses() - # TODO: parse uses - while self.Peak != 'END': - self.parseTopLevel() - self.Consume('END') + self.Consume('package') + name = self.Consume('ID') + self.Consume(';') + self.mod = astnodes.Package(name.val, name.loc) + self.currentPart = self.mod + self.parseUses() + while self.Peak != 'END': + self.parseTopLevel() + self.Consume('END') def parseTopLevel(self): if self.Peak == 'function': @@ -127,7 +122,7 @@ v = astnodes.Variable(name.val, t) v.loc = name.loc if self.hasConsumed('='): - v.ival = self.parseExpression() + v.ival = self.Expression() self.addDeclaration(v) parseVar() while self.hasConsumed(','): @@ -140,7 +135,7 @@ def parseConst(): name = self.Consume('ID') self.Consume('=') - val = self.parseExpression() + val = self.Expression() c = astnodes.Constant(name.val, t, val) c.loc = name.loc parseConst() @@ -177,27 +172,11 @@ self.currentPart = savePart # Statements: - def parseAssignment(self, lval): - lval = astnodes.VariableUse(lval, lval.loc) - loc = self.Consume('=').loc - rval = self.parseExpression() - self.Consume(';') - return astnodes.Assignment(lval, rval, loc) - - def parseCall(self, func): - self.Consume('(') - args = [] - if not self.hasConsumed(')'): - args.append(self.parseExpression()) - while self.hasConsumed(','): - args.append(self.parseExpression()) - self.Consume(')') - return astnodes.FunctionCall(func, args, func.loc) def parseIfStatement(self): loc = self.Consume('if').loc self.Consume('(') - condition = self.parseExpression() + condition = self.Expression() self.Consume(')') yes = self.parseCompoundStatement() if self.hasConsumed('else'): @@ -207,88 +186,170 @@ return astnodes.IfStatement(condition, yes, no, loc) def parseWhileStatement(self): - loc = self.Consume('while').loc - self.Consume('(') - condition = self.parseExpression() - self.Consume(')') - statements = self.parseCompoundStatement() - return astnodes.WhileStatement(condition, statements, loc) + loc = self.Consume('while').loc + self.Consume('(') + condition = self.Expression() + self.Consume(')') + statements = self.parseCompoundStatement() + return astnodes.WhileStatement(condition, statements, loc) def parseReturnStatement(self): - self.Consume('return') - expr = self.parseExpression() - self.Consume(';') - return astnodes.ReturnStatement(expr) + loc = self.Consume('return').loc + expr = self.Expression() + self.Consume(';') + return astnodes.ReturnStatement(expr, loc) def parseCompoundStatement(self): - self.Consume('{') - statements = [] - while not self.hasConsumed('}'): - s = self.parseStatement() - if not type(s) is astnodes.EmptyStatement: + self.Consume('{') + statements = [] + while not self.hasConsumed('}'): + s = self.Statement() + if type(s) is astnodes.EmptyStatement: + continue statements.append(s) - return astnodes.CompoundStatement(statements) + return astnodes.CompoundStatement(statements) + + def Statement(self): + # Determine statement type based on the pending token: + if self.Peak == 'if': + return self.parseIfStatement() + elif self.Peak == 'while': + return self.parseWhileStatement() + elif self.Peak == '{': + return self.parseCompoundStatement() + elif self.hasConsumed(';'): + return astnodes.EmptyStatement() + elif self.Peak == 'var': + self.parseVarDef() + return astnodes.EmptyStatement() + elif self.Peak == 'return': + return self.parseReturnStatement() + else: + return self.AssignmentOrCall() + + def AssignmentOrCall(self): + x = self.UnaryExpression() + if self.Peak == '=': + # We enter assignment mode here. + loc = self.Consume('=').loc + rhs = self.Expression() + return astnodes.Assignment(x, rhs, loc) + else: + return x - def parseStatement(self): - # Determine statement type based on the pending token: - if self.Peak == 'if': - return self.parseIfStatement() - elif self.Peak == 'while': - return self.parseWhileStatement() - elif self.Peak == '{': - return self.parseCompoundStatement() - elif self.hasConsumed(';'): - return astnodes.EmptyStatement() - elif self.Peak == 'var': - self.parseVarDef() - return astnodes.EmptyStatement() - elif self.Peak == 'return': - return self.parseReturnStatement() - else: - designator = self.parseDesignator() - if self.Peak == '(': - return self.parseCall(designator) - elif self.Peak == '=': - return self.parseAssignment(designator) - else: - self.Error('Unable to determine statement') + # Expression section: + # We not implement these C constructs: + # a(2), f = 2 + # and this: + # a = 2 < x : 4 ? 1; + + def Expression(self): + exp = self.LogicalAndExpression() + while self.Peak == 'or': + loc = self.Consume('or').loc + e2 = self.LogicalAndExpression() + exp = astnodes.Binop(exp, 'or', e2, loc) + return exp - # Parsing expressions: - def parseExpression(self): - return self.parseBinopRhs(self.parsePrimary(), 0) + def LogicalAndExpression(self): + o = self.EqualityExpression() + while self.Peak == 'and': + loc = self.Consume('and').loc + o2 = self.EqualityExpression() + o = astnodes.Binop(o, 'and', o2, loc) + return o + + def EqualityExpression(self): + ee = self.SimpleExpression() + while self.Peak in ['<', '==', '>']: + op = self.Consume(self.Peak) + ee2 = self.SimpleExpression() + ee = astnodes.Binop(ee, op.typ, ee2, op.loc) + return ee + + def SimpleExpression(self): + e = self.Term() + while self.Peak in ['+', '-']: + op = self.Consume(self.Peak) + e2 = self.Term() + e = astnodes.Binop(e, op.typ, e2, op.loc) + return e - def parsePrimary(self): - if self.hasConsumed('('): - e = self.parseExpression() - self.Consume(')') - return e - elif self.Peak == 'NUMBER': - val = self.Consume('NUMBER') - return astnodes.Literal(val.val, val.loc) - elif self.Peak == 'REAL': - val = self.Consume('REAL') - return astnodes.Literal(val.val, val.loc) - elif self.Peak == 'true': - val = self.Consume('true') - return astnodes.Literal(True, val.loc) - elif self.Peak == 'false': - val = self.Consume('false') - return astnodes.Literal(False, val.loc) - elif self.Peak == 'ID': - d = self.parseDesignator() - if self.Peak == '(': - return self.parseCall(d) - else: + def Term(self): + t = self.Factor() + while self.Peak in ['*', '/']: + op = self.Consume(self.Peak) + t2 = self.Factor() + t = astnodes.Binop(t, op.typ, t2, op.loc) + return t + + def Factor(self): + # TODO: eliminate this step? + return self.CastExpression() + + # Domain of unary expressions: + + def CastExpression(self): + # TODO: cast conflicts with '(' expr ')' + if self.Peak == '(ii': + self.Consume('(') + print('TODO: implement type cast') + #rrrrr + self.parseTypeSpec() + + # Type + self.Consume(')') + ce = self.CastExpression() + return ce + else: + return self.UnaryExpression() + + def UnaryExpression(self): + if self.Peak in ['&', '*']: + op = self.Consume(self.Peak) + ce = self.CastExpression() + return astnodes.Unop(op.typ, ce, op.loc) + else: + return self.PostFixExpression() + + def PostFixExpression(self): + pfe = self.PrimaryExpression() + while self.Peak in ['[', '(', '.', '->']: + if self.hasConsumed('['): + pass + elif self.hasConsumed('('): + # Function call + args = [] + if not self.hasConsumed(')'): + args.append(self.Expression()) + while self.hasConsumed(','): + args.append(self.Expression()) + self.Consume(')') + pfe = astnodes.FunctionCall(pfe, args, pfe.loc) + else: + rrrr + return pfe + + def PrimaryExpression(self): + if self.hasConsumed('('): + e = self.Expression() + self.Consume(')') + return e + elif self.Peak == 'NUMBER': + val = self.Consume('NUMBER') + return astnodes.Literal(val.val, val.loc) + elif self.Peak == 'REAL': + val = self.Consume('REAL') + return astnodes.Literal(val.val, val.loc) + elif self.Peak == 'true': + val = self.Consume('true') + return astnodes.Literal(True, val.loc) + elif self.Peak == 'false': + val = self.Consume('false') + return astnodes.Literal(False, val.loc) + elif self.Peak == 'ID': + d = self.parseDesignator() return astnodes.VariableUse(d, d.loc) - self.Error('Expected NUM, ID or (expr), got {0}'.format(self.Peak)) + self.Error('Expected NUM, ID or (expr), got {0}'.format(self.Peak)) - def parseBinopRhs(self, lhs, min_prec): - while self.PeakPrec >= min_prec: - op_prec = self.PeakPrec - op = self.Consume(self.Peak) - rhs = self.parsePrimary() - while self.PeakPrec > op_prec: - rhs = self.parseBinopRhs(rhs, self.PeakPrec) - lhs = astnodes.Binop(lhs, op.typ, rhs, op.loc) - return lhs
--- a/python/c3/typecheck.py Sat Jul 06 12:38:09 2013 +0200 +++ b/python/c3/typecheck.py Sat Jul 06 21:32:20 2013 +0200 @@ -7,28 +7,34 @@ if type(a) is type(b): if type(a) is BaseType: return a.name == b.name + elif type(a) is PointerType: + return equalTypes(a.ptype, b.ptype) return False class TypeChecker: - def __init__(self, diag): - self.diag = diag - def error(self, msg, loc): + def __init__(self, diag): + self.diag = diag + + def error(self, msg, loc): """ Wrapper that registers the message and marks the result invalid """ self.diag.error(msg, loc) self.ok = False - def checkPackage(self, pkg): + + def checkPackage(self, pkg): self.ok = True visitor = Visitor() visitor.visit(pkg, f_post=self.check2) return self.ok - def check2(self, sym): - if type(sym) is Function: - pass - elif type(sym) in [IfStatement, WhileStatement]: + + def check2(self, sym): + if type(sym) in [IfStatement, WhileStatement]: if not equalTypes(sym.condition.typ, boolType): self.error('Condition must be of type {0}'.format(boolType), sym.condition.loc) elif type(sym) is Assignment: - if not equalTypes(sym.lval.typ, sym.rval.typ): + if type(sym.lval.typ) is PointerType and sym.rval.typ == intType: + print('special case, int to pointer is ok for now') + # TODO: add cast instruction? + elif not equalTypes(sym.lval.typ, sym.rval.typ): self.error('Cannot assign {0} to {1}'.format(sym.rval.typ, sym.lval.typ), sym.loc) elif type(sym) is ReturnStatement: pass @@ -62,6 +68,17 @@ sym.typ = boolType else: self.error('Unknown literal type', sym.loc) + elif type(sym) is Unop: + if sym.op == '&': + sym.typ = PointerType(sym.a.typ) + elif sym.op == '*': + # pointer deref + if type(sym.a.typ) is PointerType: + sym.typ = sym.a.typ.ptype + else: + self.error('Cannot dereference non-pointer type {}'.format(sym.a.typ), sym.loc) + else: + print('unknown unop', sym.op) elif type(sym) is Binop: if sym.op in ['+', '-', '*', '/']: if equalTypes(sym.a.typ, sym.b.typ): @@ -94,7 +111,6 @@ elif type(sym) is Constant: if not equalTypes(sym.typ, sym.value.typ): self.error('Cannot assign {0} to {1}'.format(sym.value.typ, sym.typ), sym.loc) - elif type(sym) in [EmptyStatement, CompoundStatement, Package, Function, FunctionType]: pass else:
--- a/python/c3/visitor.py Sat Jul 06 12:38:09 2013 +0200 +++ b/python/c3/visitor.py Sat Jul 06 21:32:20 2013 +0200 @@ -41,6 +41,8 @@ elif type(node) is Binop: self.do(node.a) self.do(node.b) + elif type(node) is Unop: + self.do(node.a) elif type(node) is Constant: self.do(node.value) elif type(node) in [EmptyStatement, VariableUse, Variable, Literal, FunctionType]:
--- a/python/stm32f4/blink.c3 Sat Jul 06 12:38:09 2013 +0200 +++ b/python/stm32f4/blink.c3 Sat Jul 06 21:32:20 2013 +0200 @@ -31,6 +31,7 @@ var int* RCC_AHB1ENR; RCC_AHB1ENR = 0x40003022; + *RCC_AHB1ENR = *RCC_AHB1ENR | 8943; /* RCC->AHB1ENR |= RCC_AHB1ENR_GPIODEN; RCC->APB1ENR |= RCC_APB1ENR_TIM2EN;
--- a/python/testc3.py Sat Jul 06 12:38:09 2013 +0200 +++ b/python/testc3.py Sat Jul 06 21:32:20 2013 +0200 @@ -1,6 +1,7 @@ import c3 import time, ppci, x86, ir import unittest +import glob testsrc = """package test; @@ -205,13 +206,14 @@ """ self.expectOK(snippet) - @unittest.skip def testPointerType(self): snippet = """ package testpointer; var int* pa; function void t(int a, double b) { + pa = 2; + pa = &a; *pa = 22; } """ @@ -248,6 +250,14 @@ """ self.expectOK(snippet) + def testExamples(self): + """ Test all examples in the c3/examples directory """ + example_filenames = glob.glob('./c3/examples/*.c3') + for filename in example_filenames: + with open(filename, 'r') as f: + src = f.read() + self.expectOK(src) + def test2(self): # testsrc2 is valid code: snippet = """