Mercurial > lcfOS

comparison test/testpyy.py @ 284:05184b95fa16

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Moved tests to seperate folder
author Windel Bouwman
date Fri, 15 Nov 2013 13:43:22 +0100
parents python/testpyy.py@37ac6c016e0f
children e84047f29c78
comparison
equal deleted inserted replaced
283:c9781c73e7e2 284:05184b95fa16
1 import unittest, pprint
2 from pyyacc import Grammar, Item, ParserGenerationException, ParserException, EPS, EOF
3 from ppci import Token
4
5 def genTokens(lst):
6 for t in lst:
7 yield Token(t, t)
8
9 class testLR(unittest.TestCase):
10 """ Test basic LR(1) parser generator constructs """
11 def testSimpleGrammar(self):
12 # 1. define a simple grammar:
13 g = Grammar(['identifier', '(', ')', '+', '*'])
14 g.add_production('input', ['expression'])
15 g.add_production('expression', ['term'])
16 g.add_production('expression', ['expression', '+', 'term'])
17 g.add_production('term', ['factor'])
18 g.add_production('term', ['term', '*', 'factor'])
19 g.add_production('factor', ['(', 'expression', ')'])
20 g.add_production('factor', ['identifier'])
21 g.start_symbol = 'input'
22 # 2. define input:
23 tokens = genTokens(['identifier', '+', 'identifier', '+', 'identifier'])
24 # 3. build parser:
25 p = g.genParser()
26 # 4. feed input:
27 p.parse(tokens)
28 def testReduceReduceConflict(self):
29 """ Check if a reduce-reduce conflict is detected """
30 # Define a grammar with an obvious reduce-reduce conflict:
31 g = Grammar(['id'])
32 g.add_production('goal', ['a'])
33 g.add_production('a', ['b'])
34 g.add_production('a', ['c'])
35 g.add_production('b', ['id'])
36 g.add_production('c', ['id'])
37 g.start_symbol = 'goal'
38 with self.assertRaises(ParserGenerationException):
39 p = g.genParser()
40 def testShiftReduceConflict(self):
41 """ Must be handled automatically by doing shift """
42 g = Grammar([EOF, 'if', 'then', 'else', 'ass'])
43 # Ambiguous grammar:
44 g.add_production('if_stmt', ['if', 'then', 'stmt'])
45 g.add_production('if_stmt', ['if', 'then', 'stmt', 'else', 'stmt'])
46 g.add_production('stmt', ['if_stmt'])
47 g.add_production('stmt', ['ass'])
48 g.start_symbol = 'stmt'
49 p = g.genParser()
50 # Ambiguous program:
51 tokens = genTokens(['if', 'then','if', 'then', 'ass', 'else', 'ass'])
52 p.parse(tokens)
53
54 def testUndefinedTerminal(self):
55 """ Test correct behavior when a terminal is undefined """
56 g = Grammar(['b'])
57 g.add_production('goal', ['a'])
58 g.add_production('a', ['b'])
59 g.add_production('a', ['c'])
60 g.start_symbol = 'goal'
61 with self.assertRaises(ParserGenerationException):
62 g.genParser()
63 def testRedefineTerminal(self):
64 """ Test correct behavior when a terminal is redefined """
65 g = Grammar([EOF, 'b', 'c'])
66 g.add_production('goal', ['a'])
67 with self.assertRaises(ParserGenerationException):
68 g.add_production('b', ['c']) # Not allowed
69 g.add_production('a', ['c'])
70 g.start_symbol = 'goal'
71 g.genParser()
72 def testEmpty(self):
73 """ Test empty token stream """
74 g = Grammar([','])
75 g.add_production('input', [','])
76 g.start_symbol = 'input'
77 p = g.genParser()
78 tokens = genTokens([])
79 with self.assertRaises(ParserException):
80 p.parse(tokens)
81
82 def testEps(self):
83 """ Test epsilon terminal """
84 g = Grammar(['a', 'b'])
85 g.add_production('input', ['optional_a', 'b'])
86 g.add_production('optional_a', ['a'])
87 g.add_production('optional_a', [])
88 g.start_symbol = 'input'
89 p = g.genParser()
90 tokens = genTokens(['b'])
91 p.parse(tokens)
92
93 def testEps2(self):
94 g = Grammar(['id', ':'])
95 g.add_production('input', ['opt_lab', 'ins', 'op1'])
96 g.add_production('input', ['ins', 'op1'])
97 g.add_production('opt_lab', ['id', ':'])
98 g.add_production('ins', ['id'])
99 g.add_production('op1', ['id'])
100 g.start_symbol = 'input'
101 p = g.genParser()
102 tokens = genTokens(['id', ':', 'id', 'id']) # i.e. "lab_0: inc rax"
103 p.parse(tokens)
104 tokens = genTokens(['id', 'id']) # i.e. "inc rax"
105 p.parse(tokens)
106
107 def test_cb(self):
108 """ Test callback of one rule and order or parameters """
109 self.cb_called = False
110 def cb(a, c, b):
111 self.cb_called = True
112 self.assertEqual(a, 'a')
113 self.assertEqual(b, 'b')
114 self.assertEqual(c, 'c')
115 g = Grammar(['a', 'b', 'c'])
116 g.add_production('goal', ['a', 'c', 'b'], cb)
117 g.start_symbol = 'goal'
118 p = g.genParser()
119 tokens = genTokens(['a', 'c', 'b'])
120 p.parse(tokens)
121 self.assertTrue(self.cb_called)
122
123
124 class testExpressionGrammar(unittest.TestCase):
125 def setUp(self):
126 g = Grammar(['EOF', 'identifier', '(', ')', '+', '*', 'num'])
127 g.add_production('input', ['expression'])
128 g.add_production('expression', ['term'])
129 g.add_production('expression', ['expression', '+', 'term'])
130 g.add_production('term', ['factor'])
131 g.add_production('term', ['term', '*', 'factor'])
132 g.add_production('factor', ['(', 'expression', ')'])
133 g.add_production('factor', ['identifier'])
134 g.add_production('factor', ['num'])
135 g.start_symbol = 'input'
136 self.g = g
137
138 def testFirstSimpleGrammar(self):
139 # 1. define a simple grammar:
140 first = self.g.calcFirstSets()
141 self.assertEqual(first['input'], {'identifier', '(', 'num'})
142 self.assertEqual(first['term'], {'identifier', '(', 'num'})
143
144 def testCanonical(self):
145 s0 = self.g.initialItemSet()
146 s, gt = self.g.genCanonicalSet(s0)
147 # Must result in 12 sets:
148 self.assertEqual(len(s), 24)
149
150 class testPG(unittest.TestCase):
151 """ Tests several parts of the parser generator """
152 def setUp(self):
153 g = Grammar(['(', ')'])
154 g.add_production('goal', ['list'])
155 g.add_production('list', ['list', 'pair'])
156 g.add_production('list', ['pair'])
157 g.add_production('pair', ['(', 'pair', ')'])
158 g.add_production('pair', ['(', ')'])
159 g.start_symbol = 'goal'
160 self.g = g
161
162 def testFirstSet(self):
163 for a in ['(', ')', EOF, 'EPS']:
164 self.assertEqual(self.g.first[a], {a})
165 for nt in ['list', 'pair', 'goal']:
166 self.assertEqual(self.g.first[nt], {'('})
167
168 def testInitItemSet(self):
169 p0, p1, p2, p3, p4 = self.g.productions
170 s0 = self.g.initialItemSet()
171 self.assertEqual(len(s0), 9) # 9 with the goal rule included!
172 self.assertIn(Item(p0, 0, EOF), s0)
173 self.assertIn(Item(p1, 0, EOF), s0)
174 self.assertIn(Item(p1, 0, '('), s0)
175 self.assertIn(Item(p2, 0, EOF), s0)
176 self.assertIn(Item(p2, 0, '('), s0)
177 self.assertIn(Item(p3, 0, EOF), s0)
178 self.assertIn(Item(p3, 0, '('), s0)
179 self.assertIn(Item(p4, 0, EOF), s0)
180 self.assertIn(Item(p4, 0, '('), s0)
181
182 def testCanonical(self):
183 s0 = self.g.initialItemSet()
184 s, gt = self.g.genCanonicalSet(s0)
185 # Must result in 12 sets:
186 self.assertEqual(len(s), 12)
187
188 def testClosure(self):
189 p0, p1, p2, p3, p4 = self.g.productions
190 s0 = set()
191 s0.add(Item(p0, 0, EOF))
192 self.assertEqual(len(s0), 1) # 1 rule
193 self.assertIn(Item(p0, 0, EOF), s0)
194
195 # Invoke closure on set:
196 s0 = self.g.closure(s0)
197 self.assertIn(Item(p0, 0, EOF), s0)
198 self.assertIn(Item(p1, 0, EOF), s0)
199 self.assertIn(Item(p1, 0, '('), s0)
200 self.assertIn(Item(p2, 0, EOF), s0)
201 self.assertIn(Item(p2, 0, '('), s0)
202 self.assertIn(Item(p3, 0, EOF), s0)
203 self.assertIn(Item(p3, 0, '('), s0)
204 self.assertIn(Item(p4, 0, EOF), s0)
205 self.assertIn(Item(p4, 0, '('), s0)
206
207 def testParser(self):
208 tokens = ['(', '(', ')', ')', '(', ')']
209 # 3. build parser:
210 p = self.g.genParser()
211 self.assertEqual(len(p.goto_table), 5)
212 self.assertEqual(len(p.action_table), 19)
213
214 # 4. feed input:
215 p.parse(genTokens(tokens))
216
217 if __name__ == '__main__':
218 unittest.main()
219
220