changeset 321:8c569fbe60e4

Load yacc and burg dynamic
author Windel Bouwman
date Sun, 19 Jan 2014 18:48:45 +0100
parents 84d67cce67b7
children 44f336460c2a
files python/arm.pb python/bootstrap.sh python/pyburg.py python/test_burm.py python/yacc.py test/sample4.brg test/test_burm.py test/testzcc.py
diffstat 8 files changed, 168 insertions(+), 102 deletions(-) [+]
line wrap: on
line diff
--- 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 (. .)
-
-
--- 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
-
--- 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)
--- 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()
--- 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)
--- /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).)
+
+
--- /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()
--- 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')