Mercurial > lcfOS

comparison python/pyburg.py @ 321:8c569fbe60e4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Load yacc and burg dynamic
author Windel Bouwman
date Sun, 19 Jan 2014 18:48:45 +0100
parents 84d67cce67b7
children 44f336460c2a
comparison
equal deleted inserted replaced
320:84d67cce67b7 321:8c569fbe60e4
1 #!/usr/bin/python 1 #!/usr/bin/python
2 2
3 """ 3 """
4 Bottom up rewrite generator. 4 Bottom up rewrite generator.
5 5
6 This script takes as input a description of patterns and outputs a 6 This script takes as input a description of patterns and outputs a
7 matcher class that can match trees given the patterns. 7 matcher class that can match trees given the patterns.
8 8
9 Patterns are specified as follows: 9 Patterns are specified as follows:
10 reg -> ADDI32(reg, reg) 2 (. add $1 $2 .) 10 reg -> ADDI32(reg, reg) 2 (. add NT0 NT1 .)
11 reg -> MULI32(reg, reg) 3 (. .) 11 reg -> MULI32(reg, reg) 3 (. .)
12 or a multiply add: 12 or a multiply add:
13 reg -> ADDI32(MULI32(reg, reg), reg) 4 (. muladd $1, $2, $3 .) 13 reg -> ADDI32(MULI32(reg, reg), reg) 4 (. muladd $1, $2, $3 .)
14 The general specification pattern is: 14 The general specification pattern is:
15 [result] -> [tree] [cost] [template code] 15 [result] -> [tree] [cost] [template code]
16 16
17 A tree is described using parenthesis notation. For example a node X with 17 Trees
18 three 18 -----
19 child nodes is described as: 19
20 A tree is described using parenthesis notation. For example a node X with
21 three child nodes is described as:
20 X(a, b, b) 22 X(a, b, b)
21 Trees can be nested: 23 Trees can be nested:
22 X(Y(a, a), a) 24 X(Y(a, a), a)
23 The 'a' in the example above indicates an open connection to a next tree 25 The 'a' in the example above indicates an open connection to a next tree
24 pattern. 26 pattern.
25 27
26 In the example above 'reg' is a non-terminal. ADDI32 is a terminal. non-terminals 28
27 cannot have child nodes. A special case occurs in this case: 29 In the example above 'reg' is a non-terminal. ADDI32 is a terminal. non-terminals
28 reg -> rc 30 cannot have child nodes. A special case occurs in this case:
29 where 'rc' is a non-terminal. This is an example of a chain rule. Chain rules 31 reg -> rc
30 can be used to allow several variants of non-terminals. 32 where 'rc' is a non-terminal. This is an example of a chain rule. Chain rules
31 33 can be used to allow several variants of non-terminals.
32 The generated matcher uses dynamic programming to find the best match of the 34
33 tree. This strategy consists of two steps: 35 The generated matcher uses dynamic programming to find the best match of the
34 - label: During this phase the given tree is traversed in a bottom up way. 36 tree. This strategy consists of two steps:
35 each node is labelled with a possible matching rule and the corresponding cost. 37 - label: During this phase the given tree is traversed in a bottom up way.
36 - select: In this step, the tree is traversed again, selecting at each point 38 each node is labelled with a possible matching rule and the corresponding cost.
37 the cheapest way to get to the goal. 39 - select: In this step, the tree is traversed again, selecting at each point
40 the cheapest way to get to the goal.
38 41
39 """ 42 """
40 43
41 import sys 44 import sys
45 import os
42 import argparse 46 import argparse
43 from ppci import Token 47 from ppci import Token
44 import burg_parser # Automatically generated
45 from pyyacc import ParserException, EOF 48 from pyyacc import ParserException, EOF
49 import yacc
46 import baselex 50 import baselex
47 from tree import Tree 51 from tree import Tree
52
53 # Generate parser on the fly:
54 spec_file = os.path.join(os.path.dirname(os.path.abspath(__file__)), 'burg.x')
55 burg_parser = yacc.load_as_module(spec_file)
48 56
49 57
50 class BurgLexer: 58 class BurgLexer:
51 def feed(self, txt): 59 def feed(self, txt):
52 tok_spec = [ 60 tok_spec = [
127 template = template[2:-2].strip() 135 template = template[2:-2].strip()
128 if not template: 136 if not template:
129 template = 'pass' 137 template = 'pass'
130 rule = Rule(non_term, tree, cost, template) 138 rule = Rule(non_term, tree, cost, template)
131 if len(tree.children) == 0 and tree.name not in self.terminals: 139 if len(tree.children) == 0 and tree.name not in self.terminals:
132 print('chain:', rule)
133 self.non_term(tree.name).chain_rules.append(rule) 140 self.non_term(tree.name).chain_rules.append(rule)
134 self.non_term(rule.non_term) 141 self.non_term(rule.non_term)
135 self.rules.append(rule) 142 self.rules.append(rule)
136 rule.nr = len(self.rules) 143 rule.nr = len(self.rules)
137 144
260 child_tests = ' and ' + child_tests if child_tests else '' 267 child_tests = ' and ' + child_tests if child_tests else ''
261 tst = '{}.name == "{}"'.format(prefix, tree.name) 268 tst = '{}.name == "{}"'.format(prefix, tree.name)
262 return tst + child_tests 269 return tst + child_tests
263 270
264 271
265 def main(): 272 def make_argument_parser():
266 # Parse arguments: 273 """ Constructs an argument parser """
267 parser = argparse.ArgumentParser(description='pyburg bottom up rewrite system generator compiler compiler') 274 parser = argparse.ArgumentParser(description='pyburg bottom up rewrite system generator compiler compiler')
268 parser.add_argument('source', type=argparse.FileType('r'), \ 275 parser.add_argument('source', type=argparse.FileType('r'), \
269 help='the parser specification') 276 help='the parser specification')
270 parser.add_argument('-o', '--output', type=argparse.FileType('w'), \ 277 parser.add_argument('-o', '--output', type=argparse.FileType('w'), \
271 default=sys.stdout) 278 default=sys.stdout)
272 args = parser.parse_args() 279 return parser
280
281
282 def main(args):
273 src = args.source.read() 283 src = args.source.read()
274 args.source.close() 284 args.source.close()
275 285
276 # Parse specification into burgsystem: 286 # Parse specification into burgsystem:
277 l = BurgLexer() 287 l = BurgLexer()
281 291
282 # Generate matcher: 292 # Generate matcher:
283 generator = BurgGenerator() 293 generator = BurgGenerator()
284 generator.generate(burg_system, args.output) 294 generator.generate(burg_system, args.output)
285 295
296
286 if __name__ == '__main__': 297 if __name__ == '__main__':
287 main() 298 # Parse arguments:
299 args = make_argument_parser().parse_args()
300 main(args)