2 files changed, 109 insertions(+), 34 deletions(-) viff/sfdl/grammar.py | 72 ++++++++++++++++++++++++++++++++++++++-- viff/test/sfdl/test_grammar.py | 71 +++++++++++++++++++++------------------
# HG changeset patch # User Martin Geisler <[EMAIL PROTECTED]> # Date 1227518476 -3600 # Node ID 26aeb27a29aa51078f6e9487febfb0a0939e5111 # Parent bcc1d60786c59a8270aeb84fead22bec80267640 Parsing and evaluation of constant expressions. diff --git a/viff/sfdl/grammar.py b/viff/sfdl/grammar.py --- a/viff/sfdl/grammar.py +++ b/viff/sfdl/grammar.py @@ -15,16 +15,43 @@ # You should have received a copy of the GNU Lesser General Public # License along with VIFF. If not, see <http://www.gnu.org/licenses/>. +import operator +from math import log, ceil + from pyparsing import Suppress, Word, Keyword, ZeroOrMore, Optional, Group, \ OneOrMore, Forward, delimitedList, \ oneOf, operatorPrecedence, opAssoc, \ - cppStyleComment, alphas, alphanums, nums + cppStyleComment, alphas, alphanums, nums, \ + ParseException + +class attrdict(dict): + + def __getattr__(self, attr): + try: + return self[attr] + except KeyError: + raise AttributeError("attrdict object has no attribute '%s'" % attr) + + def __setattr__(self, attr, value): + if attr not in self and hasattr(self, attr): + raise AttributeError("cannot overwrite attribute '%s'" % attr) + self[attr] = value + + def __delattr__(self, attr): + try: + del self[attr] + except KeyError: + raise AttributeError("attrdict object has no attribute '%s'" % attr) + class SFDLGrammar: def __init__(self): + self.global_scope = {} + SCOLON = Suppress(";") EQUAL = Suppress("=") + DOT = Suppress(".") LCURLY, RCURLY = Suppress("{"), Suppress("}") LPAREN, RPAREN = Suppress("("), Suppress(")") @@ -33,7 +60,7 @@ const_op = oneOf(".bitSize .length") self.const_atom = const_atom \ - = Word(nums) | ident + ZeroOrMore(~const_op + "." + ident) + = Word(nums) | ident + ZeroOrMore(~const_op + DOT + ident) self.const_expr = const_expr \ = operatorPrecedence(const_atom, [(const_op, 1, opAssoc.LEFT), @@ -41,6 +68,10 @@ self.const_dec = const_dec \ = Keyword("const") + ident + EQUAL + const_expr + SCOLON + const_atom.setParseAction(self.parse_const_atom) + const_expr.setParseAction(self.parse_const_expr) + const_dec.setParseAction(self.parse_const_dec) + self.data_type = data_type = Forward() self.struct_field = struct_field = Group(data_type + ident) @@ -92,3 +123,40 @@ self.program = program = Keyword("program") + ident \ + LCURLY + program_body + RCURLY program.ignore(cppStyleComment) + + def parse_const_atom(self, s, loc, toks): + atom = toks[0] + if atom.isdigit(): + return int(atom) + else: + try: + result = self.global_scope[atom] + for atom in toks[1:]: + result = result[atom] + return result + except KeyError: + name = ".".join(toks) + raise ParseException(s, loc, "undefined constant: %s" % name) + + def parse_const_dec(self, s, loc, toks): + self.global_scope[toks[1]] = toks[2] + + def parse_const_expr(self, s, loc, toks): + if isinstance(toks[0], int): + return toks[0] + else: + result = toks[0][0] + op = operator.add + for sym in toks[0][1:]: + if sym == "+": + op = operator.add + elif sym == "-": + op = operator.sub + elif sym == ".bitSize": + # TODO: Fix for negative values and 2^n values. + result = int(ceil(log(result, 2))+1) + elif sym == ".length": + result = result.length + else: + result = op(result, sym) + return result diff --git a/viff/test/sfdl/test_grammar.py b/viff/test/sfdl/test_grammar.py --- a/viff/test/sfdl/test_grammar.py +++ b/viff/test/sfdl/test_grammar.py @@ -19,7 +19,7 @@ try: from pyparsing import ParseException - from viff.sfdl.grammar import SFDLGrammar + from viff.sfdl.grammar import SFDLGrammar, attrdict except ImportError: SFDLGrammar = None @@ -66,47 +66,49 @@ ['program', 'empty']) def test_const_atom(self): - self.assertParse(self.grammar.const_atom, "123", ['123']) - self.assertParse(self.grammar.const_atom, "foo", ['foo']) + self.assertParse(self.grammar.const_atom, "123", [123]) + self.grammar.global_scope["foo"] = 10 + self.assertParse(self.grammar.const_atom, "foo", [10]) self.assertNoParse(self.grammar.const_atom, "x.10") self.assertNoParse(self.grammar.const_atom, "10.x") def test_const_expr(self): - self.assertParse(self.grammar.const_expr, "1 + 2", [['1', '+', '2']]) - self.assertParse(self.grammar.const_expr, "1 + x", [['1', '+', 'x']]) - self.assertParse(self.grammar.const_expr, "10 + (x - 20)", - [['10', '+', ['x', '-', '20']]]) + self.assertParse(self.grammar.const_expr, "1 + 2", [3]) + self.grammar.global_scope['x'] = 17 + self.assertParse(self.grammar.const_expr, "1 + x", [18]) + self.assertParse(self.grammar.const_expr, "10 + (x - 20)", [7]) self.assertNoParse(self.grammar.const_expr, "10 +") self.assertNoParse(self.grammar.const_expr, "x y") def test_const_expr_bitsize(self): + # TODO: Test negative numbers, check corner cases. + # Bit size of an integer: - self.assertParse(self.grammar.const_expr, "32.bitSize", - [['32', '.bitSize']]) - # Bit size of a declared variable: - self.assertParse(self.grammar.const_expr, "x.bitSize", - [['x', '.bitSize']]) + self.assertParse(self.grammar.const_expr, "20.bitSize", [6]) + # Bit size of a declared constant: + self.grammar.global_scope['x'] = 15 + self.assertParse(self.grammar.const_expr, "x.bitSize", [5]) # Bit size of a compound expression: - self.assertParse(self.grammar.const_expr, "(10 + x).bitSize", - [[['10', '+', 'x'], '.bitSize']]) + self.assertParse(self.grammar.const_expr, "(10 + x).bitSize", [6]) self.assertNoParse(self.grammar.const_expr, ".bitSize") def test_const_expr_length(self): + # Length of an array: + self.grammar.global_scope['n'] = attrdict(length=10) + self.assertParse(self.grammar.const_expr, "n.length", [10]) + # Length of an array in a struct: - self.assertParse(self.grammar.const_expr, "n.length", - [['n', '.length']]) - - self.assertParse(self.grammar.const_expr, "x.y.length", - [['x', '.', 'y', '.length']]) + self.grammar.global_scope['x'] = attrdict(y=attrdict(length=2)) + self.assertParse(self.grammar.const_expr, "x.y.length", [2]) def test_const_dec(self): self.assertParse(self.grammar.const_dec, "const x = 10;", - ['const', 'x', '10']) - self.assertParse(self.grammar.const_dec, "const x = 10 + y;", - ['const', 'x', ['10', '+', 'y']]) + ['const', 'x', 10]) + self.assertParse(self.grammar.const_dec, "const y = 10 + x;", + ['const', 'y', 20]) self.assertNoParse(self.grammar.const_dec, "const x;") self.assertNoParse(self.grammar.const_dec, "const x 123;") @@ -117,11 +119,13 @@ def test_int_type(self): self.assertParse(self.grammar.known_type, "Int<8>", - ['Int', '<', '8', '>']) + ['Int', '<', 8, '>']) + + self.grammar.global_scope['MAX'] = 10 self.assertParse(self.grammar.known_type, "Int<MAX>", - ['Int', '<', 'MAX', '>']) + ['Int', '<', 10, '>']) self.assertParse(self.grammar.known_type, "Int<MAX+1>", - ['Int', '<', ['MAX', '+', '1'], '>']) + ['Int', '<', 11, '>']) def test_struct_type(self): self.assertParse(self.grammar.struct_type, "struct { Boolean x }", @@ -143,15 +147,17 @@ def test_data_type(self): self.assertParse(self.grammar.data_type, "Boolean[4]", - ['Boolean', ['[', '4', ']']]) + ['Boolean', ['[', 4, ']']]) + self.grammar.global_scope['MIN'] = 17 + self.grammar.global_scope['MAX'] = 4 self.assertParse(self.grammar.data_type, "Int<MAX>[MIN]", - ['Int', '<', 'MAX', '>', ['[', 'MIN', ']']]) + ['Int', '<', 4, '>', ['[', 17, ']']]) def test_type_dec(self): self.assertParse(self.grammar.type_dec, "type x = Boolean;", ['type', 'x', 'Boolean']) self.assertParse(self.grammar.type_dec, "type x = AnotherType[4];", - ['type', 'x', 'AnotherType', ['[', '4', ']']]) + ['type', 'x', 'AnotherType', ['[', 4, ']']]) def test_qual_ident(self): @@ -278,7 +284,7 @@ def test_for_stm(self): self.assertParse(self.grammar.for_stm, "for (i = 0 to 10) { x[i] = 42; }", - ['for', ['i', '0'], 'to', ['10'], + ['for', ['i', 0], 'to', [10], [['x', '[', 'i', ']', '42']]]) src = """ @@ -287,8 +293,9 @@ y[i] = b[i] && z[i]; } """ + self.grammar.global_scope['MIN'] = 7 self.assertParse(self.grammar.for_stm, src, - ['for', ['i', 'MIN'], 'to', [['MIN', '+', '10']], + ['for', ['i', 7], 'to', [17], [['b', '[', 'i', ']', ['x', '[', 'i', ']', '<', @@ -350,7 +357,7 @@ """ self.assertParse(self.grammar.program, src, ['program', 'p', - ['type', 'Byte', 'Int', '<', '8', '>']]) + ['type', 'Byte', 'Int', '<', 8, '>']]) src = """ program p { @@ -358,7 +365,7 @@ } """ self.assertParse(self.grammar.program, src, - ['program', 'p', ['const', 'x', '10']]) + ['program', 'p', ['const', 'x', 10]]) src = """ program p { _______________________________________________ viff-patches mailing list [email protected] http://lists.viff.dk/listinfo.cgi/viff-patches-viff.dk
