# HG changeset patch # User Windel Bouwman # Date 1390153725 -3600 # Node ID 8c569fbe60e4efd5a6c2d14eb677f43e2041f5e8 # Parent 84d67cce67b7e578928c3d59fb192a7d8b53aa55 Load yacc and burg dynamic diff -r 84d67cce67b7 -r 8c569fbe60e4 python/arm.pb --- a/python/arm.pb Sun Jan 19 16:09:44 2014 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,20 +0,0 @@ - -%terminal ADDI ADDRLP ASGNI -%terminal CNSTI CVCI IOI INDIRC - -%% - -stmt: ASGNI(disp, reg) 1 (. print('ASGNI') .) -stmt: reg 0 (. .) -reg: ADDI(reg, rc) 1 (. print('ADDI(reg, rc)') .) -reg: CVCI(INDIRC(disp)) 1 (. .) -reg: IOI 0 (. .) -reg: disp 1 (. .) -disp: ADDI(reg, con) 1 (. .) -disp: ADDRLP 0 (. print('ADDRLP') .) -rc: con 0 (. .) -rc: reg 0 (. .) -con: CNSTI 0 (. print('CNSTI') .) -con: IOI 0 (. .) - - diff -r 84d67cce67b7 -r 8c569fbe60e4 python/bootstrap.sh --- a/python/bootstrap.sh Sun Jan 19 16:09:44 2014 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,10 +0,0 @@ -#!/usr/bin/bash - -echo "Generating burg_parser.py" - -./yacc.py burg.x -o burg_parser.py - -echo "Generating arm code generator" - -./pyburg.py arm.pb -o arm_burm.py - diff -r 84d67cce67b7 -r 8c569fbe60e4 python/pyburg.py --- a/python/pyburg.py Sun Jan 19 16:09:44 2014 +0100 +++ b/python/pyburg.py Sun Jan 19 18:48:45 2014 +0100 @@ -1,51 +1,59 @@ #!/usr/bin/python """ - Bottom up rewrite generator. +Bottom up rewrite generator. - This script takes as input a description of patterns and outputs a - matcher class that can match trees given the patterns. +This script takes as input a description of patterns and outputs a +matcher class that can match trees given the patterns. Patterns are specified as follows: - reg -> ADDI32(reg, reg) 2 (. add $1 $2 .) + reg -> ADDI32(reg, reg) 2 (. add NT0 NT1 .) reg -> MULI32(reg, reg) 3 (. .) or a multiply add: reg -> ADDI32(MULI32(reg, reg), reg) 4 (. muladd $1, $2, $3 .) The general specification pattern is: [result] -> [tree] [cost] [template code] - A tree is described using parenthesis notation. For example a node X with - three - child nodes is described as: +Trees +----- + +A tree is described using parenthesis notation. For example a node X with +three child nodes is described as: X(a, b, b) - Trees can be nested: +Trees can be nested: X(Y(a, a), a) - The 'a' in the example above indicates an open connection to a next tree - pattern. +The 'a' in the example above indicates an open connection to a next tree +pattern. + - In the example above 'reg' is a non-terminal. ADDI32 is a terminal. non-terminals - cannot have child nodes. A special case occurs in this case: - reg -> rc - where 'rc' is a non-terminal. This is an example of a chain rule. Chain rules - can be used to allow several variants of non-terminals. +In the example above 'reg' is a non-terminal. ADDI32 is a terminal. non-terminals +cannot have child nodes. A special case occurs in this case: +reg -> rc +where 'rc' is a non-terminal. This is an example of a chain rule. Chain rules +can be used to allow several variants of non-terminals. - The generated matcher uses dynamic programming to find the best match of the - tree. This strategy consists of two steps: - - label: During this phase the given tree is traversed in a bottom up way. - each node is labelled with a possible matching rule and the corresponding cost. - - select: In this step, the tree is traversed again, selecting at each point - the cheapest way to get to the goal. +The generated matcher uses dynamic programming to find the best match of the +tree. This strategy consists of two steps: + - label: During this phase the given tree is traversed in a bottom up way. + each node is labelled with a possible matching rule and the corresponding cost. + - select: In this step, the tree is traversed again, selecting at each point + the cheapest way to get to the goal. """ import sys +import os import argparse from ppci import Token -import burg_parser # Automatically generated from pyyacc import ParserException, EOF +import yacc import baselex from tree import Tree +# Generate parser on the fly: +spec_file = os.path.join(os.path.dirname(os.path.abspath(__file__)), 'burg.x') +burg_parser = yacc.load_as_module(spec_file) + class BurgLexer: def feed(self, txt): @@ -129,7 +137,6 @@ template = 'pass' rule = Rule(non_term, tree, cost, template) if len(tree.children) == 0 and tree.name not in self.terminals: - print('chain:', rule) self.non_term(tree.name).chain_rules.append(rule) self.non_term(rule.non_term) self.rules.append(rule) @@ -262,14 +269,17 @@ return tst + child_tests -def main(): - # Parse arguments: +def make_argument_parser(): + """ Constructs an argument parser """ parser = argparse.ArgumentParser(description='pyburg bottom up rewrite system generator compiler compiler') parser.add_argument('source', type=argparse.FileType('r'), \ help='the parser specification') parser.add_argument('-o', '--output', type=argparse.FileType('w'), \ default=sys.stdout) - args = parser.parse_args() + return parser + + +def main(args): src = args.source.read() args.source.close() @@ -283,5 +293,8 @@ generator = BurgGenerator() generator.generate(burg_system, args.output) + if __name__ == '__main__': - main() + # Parse arguments: + args = make_argument_parser().parse_args() + main(args) diff -r 84d67cce67b7 -r 8c569fbe60e4 python/test_burm.py --- a/python/test_burm.py Sun Jan 19 16:09:44 2014 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,17 +0,0 @@ -from tree import Tree -from arm_burm import Matcher - - -def main(): - t = Tree('ASGNI', - Tree('ADDRLP'), - Tree('ADDI', - Tree('CVCI', Tree('INDIRC', Tree('ADDRLP'))), - Tree('CNSTI') - ) - ) - print(t) - Matcher().gen(t) - -if __name__ == '__main__': - main() diff -r 84d67cce67b7 -r 8c569fbe60e4 python/yacc.py --- a/python/yacc.py Sun Jan 19 16:09:44 2014 +0100 +++ b/python/yacc.py Sun Jan 19 18:48:45 2014 +0100 @@ -22,12 +22,25 @@ p.parse() +Alternatively you can load the parser on the fly: + +.. code:: + + import yacc + parser_mod = yacc.load_as_module('mygrammar.x') + class MyParser(parser_mod.Parser): + pass + p = MyParser() + p.parse() + """ import argparse import re import sys import datetime +import types +import io from pyyacc import Grammar, print_grammar @@ -101,7 +114,6 @@ t = self.token if t[0] != 'eof': self.token = self.tokens.__next__() - #print(t) return t @@ -192,50 +204,54 @@ pass def generate(self, grammar, headers, output_file): - print_grammar(grammar) + self.output_file = output_file self.grammar = grammar self.headers = headers self.action_table, self.goto_table = grammar.doGenerate() - self.generate_python_script(output_file) + self.generate_python_script() - def generate_python_script(self, output_file): + def print(self, *args): + """ Print helper function that prints to output file """ + print(*args, file=self.output_file) + + def generate_python_script(self): """ Generate python script with the parser table """ - print('#!/usr/bin/python', file=output_file) + self.print('#!/usr/bin/python') stamp = datetime.datetime.now().ctime() - print('""" Automatically generated by xacc on {} """'.format(stamp), file=output_file) - print('from pyyacc import LRParser, Reduce, Shift, Accept, Production, Grammar', file=output_file) - print('from ppci import Token', file=output_file) - print(file=output_file) + self.print('""" Automatically generated by xacc on {} """'.format(stamp)) + self.print('from pyyacc import LRParser, Reduce, Shift, Accept, Production, Grammar') + self.print('from ppci import Token') + self.print('') for h in self.headers: print(h, file=output_file) - print(file=output_file) - print('class Parser(LRParser):', file=output_file) - print(' def __init__(self):', file=output_file) + self.print('') + self.print('class Parser(LRParser):') + self.print(' def __init__(self):') # Generate rules: - print(' self.start_symbol = "{}"'.format(self.grammar.start_symbol), file=output_file) - print(' self.grammar = Grammar({})'.format(self.grammar.terminals), file=output_file) + self.print(' self.start_symbol = "{}"'.format(self.grammar.start_symbol)) + self.print(' self.grammar = Grammar({})'.format(self.grammar.terminals)) for rule_number, rule in enumerate(self.grammar.productions): rule.f_name = 'action_{}_{}'.format(rule.name, rule_number) - print(' self.grammar.add_production("{}", {}, self.{})'.format(rule.name, rule.symbols, rule.f_name), file=output_file) + self.print(' self.grammar.add_production("{}", {}, self.{})'.format(rule.name, rule.symbols, rule.f_name)) # Fill action table: - print(' self.action_table = {}', file=output_file) + self.print(' self.action_table = {}') for state in self.action_table: action = self.action_table[state] - print(' self.action_table[{}] = {}'.format(state, action), file=output_file) - print('', file=output_file) + self.print(' self.action_table[{}] = {}'.format(state, action)) + self.print('') # Fill goto table: - print(' self.goto_table = {}', file=output_file) + self.print(' self.goto_table = {}') for gt in self.goto_table: to = self.goto_table[gt] - print(' self.goto_table[{}] = {}'.format(gt, to), file=output_file) - print('', file=output_file) + self.print(' self.goto_table[{}] = {}'.format(gt, to)) + self.print('') # Generate a function for each action: for rule in self.grammar.productions: M = len(rule.symbols) args = ', '.join('arg{}'.format(n + 1) for n in range(M)) - print(' def {}(self, {}):'.format(rule.f_name, args), file=output_file) + self.print(' def {}(self, {}):'.format(rule.f_name, args)) if rule.f == None: semantics = 'pass' else: @@ -244,17 +260,29 @@ semantics = 'pass' for n in range(M): semantics = semantics.replace('${}'.format(n + 1), 'arg{}'.format(n + 1)) - print(' {}'.format(semantics), file=output_file) + self.print(' {}'.format(semantics)) -def main(): +def make_argument_parser(): # Parse arguments: parser = argparse.ArgumentParser(description='xacc compiler compiler') parser.add_argument('source', type=argparse.FileType('r'), \ help='the parser specification') parser.add_argument('-o', '--output', type=argparse.FileType('w'), \ default=sys.stdout) - args = parser.parse_args() + + +def load_as_module(filename): + """ Load a parser spec file, generate LR tables and create module """ + ob = io.StringIO() + args = argparse.Namespace(source=open(filename), output=ob) + main(args) + + parser_mod = types.ModuleType('generated_parser') + exec(ob.getvalue(), parser_mod.__dict__) + return parser_mod + +def main(args): src = args.source.read() args.source.close() @@ -266,9 +294,10 @@ # Sequence source through the generator parts: lexer.feed(src) grammar = parser.parse_grammar() + # TODO: optionize this: print_grammar(grammar) generator.generate(grammar, parser.headers, args.output) - args.output.close() if __name__ == '__main__': - main() + args = make_argument_parser().parse_args() + main(args) diff -r 84d67cce67b7 -r 8c569fbe60e4 test/sample4.brg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/sample4.brg Sun Jan 19 18:48:45 2014 +0100 @@ -0,0 +1,20 @@ + +%terminal ADDI ADDRLP ASGNI +%terminal CNSTI CVCI IOI INDIRC + +%% + +stmt: ASGNI(disp, reg) 1 (. self.tr(1) .) +stmt: reg 0 (. self.tr(2).) +reg: ADDI(reg, rc) 1 (. self.tr(3) .) +reg: CVCI(INDIRC(disp)) 1 (. self.tr(4) .) +reg: IOI 0 (. self.tr(5).) +reg: disp 1 (. self.tr(6).) +disp: ADDI(reg, con) 1 (. self.tr(7).) +disp: ADDRLP 0 (. self.tr(8).) +rc: con 0 (. self.tr(9).) +rc: reg 0 (. self.tr(10).) +con: CNSTI 0 (. self.tr(11).) +con: IOI 0 (. self.tr(12).) + + diff -r 84d67cce67b7 -r 8c569fbe60e4 test/test_burm.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/test_burm.py Sun Jan 19 18:48:45 2014 +0100 @@ -0,0 +1,44 @@ +import unittest +import io +import argparse + +from tree import Tree +import pyburg + + +class testBURG(unittest.TestCase): + def testSample4(self): + """ Test sample4 burg system """ + # Generate matcher from spec: + buf = io.StringIO() + args = argparse.Namespace(source=open('sample4.brg'), output=buf) + pyburg.main(args) + + # Execute generated script into global scope: + exec(buf.getvalue(), globals()) + + # Sample tree: + t = Tree('ASGNI', + Tree('ADDRLP'), + Tree('ADDI', + Tree('CVCI', Tree('INDIRC', Tree('ADDRLP'))), + Tree('CNSTI') + ) + ) + + # Subclass generated matcher: + class MyMatcher(Matcher): + def __init__(self): + super().__init__() + self.trace = [] + + def tr(self, r): + self.trace.append(r) + + # Match tree: + mm = MyMatcher() + mm.gen(t) + self.assertSequenceEqual([8,8,4,11,9,3,1], mm.trace) + +if __name__ == '__main__': + unittest.main() diff -r 84d67cce67b7 -r 8c569fbe60e4 test/testzcc.py --- a/test/testzcc.py Sun Jan 19 16:09:44 2014 +0100 +++ b/test/testzcc.py Sun Jan 19 18:48:45 2014 +0100 @@ -9,10 +9,17 @@ import target +# Store testdir for safe switch back to directory: +testdir = os.path.dirname(os.path.abspath(__file__)) + + class ZccTestCase(unittest.TestCase): """ Tests the compiler driver """ def setUp(self): - os.chdir(os.path.dirname(os.path.abspath(__file__))) + os.chdir(testdir) + + def tearDown(self): + os.chdir(testdir) def do(self, filenames, imps=[]): basedir = os.path.join('..', 'examples', 'c3')