|
184
|
1 import unittest, pprint
|
|
192
|
2 from pyyacc import Grammar, Item, EOF, ParserGenerationException
|
|
191
|
3 from ppci import Token
|
|
184
|
4
|
|
191
|
5 def genTokens(lst):
|
|
|
6 for t in lst:
|
|
|
7 yield Token(t, t, 0)
|
|
184
|
8
|
|
|
9 class testLR(unittest.TestCase):
|
|
|
10 def setUp(self):
|
|
|
11 pass
|
|
|
12
|
|
|
13 def testSimpleGrammar(self):
|
|
|
14 # 1. define a simple grammar:
|
|
|
15 g = Grammar(['EOF', 'identifier', '(', ')', '+', '*'])
|
|
|
16 g.add_production('input', ['expression'])
|
|
|
17 g.add_production('expression', ['term'])
|
|
|
18 g.add_production('expression', ['expression', '+', 'term'])
|
|
|
19 g.add_production('term', ['factor'])
|
|
|
20 g.add_production('term', ['term', '*', 'factor'])
|
|
|
21 g.add_production('factor', ['(', 'expression', ')'])
|
|
|
22 g.add_production('factor', ['identifier'])
|
|
|
23 g.start_symbol = 'input'
|
|
|
24 # 2. define input:
|
|
191
|
25 tokens = genTokens(['identifier', '+', 'identifier', '+', 'identifier'])
|
|
184
|
26 # 3. build parser:
|
|
|
27 p = g.genParser()
|
|
|
28 # 4. feed input:
|
|
|
29 p.parse(tokens)
|
|
192
|
30 def testReduceReduceConflict(self):
|
|
|
31 """ Check if a reduce-reduce conflict is detected """
|
|
|
32 # Define a grammar with an obvious reduce-reduce conflict:
|
|
|
33 g = Grammar([EOF, 'id'])
|
|
|
34 g.add_production('goal', ['a'])
|
|
|
35 g.add_production('a', ['b'])
|
|
|
36 g.add_production('a', ['c'])
|
|
|
37 g.add_production('b', ['id'])
|
|
|
38 g.add_production('c', ['id'])
|
|
|
39 g.start_symbol = 'goal'
|
|
|
40 with self.assertRaises(ParserGenerationException):
|
|
|
41 p = g.genParser()
|
|
|
42 def testShiftReduceConflict(self):
|
|
|
43 g = Grammar([EOF, 'if', 'then', 'else'])
|
|
|
44 g.add_production('if_stmt', ['if', 'then'])
|
|
|
45 g.add_production('if_stmt', ['if', 'then', 'else'])
|
|
|
46 g.add_production('stmt', ['if_stmt', 'else'])
|
|
|
47 g.start_symbol = 'stmt'
|
|
|
48 with self.assertRaises(ParserGenerationException):
|
|
|
49 g.genParser()
|
|
|
50 def testUndefinedTerminal(self):
|
|
|
51 """ Test correct behavior when a terminal is undefined """
|
|
|
52 g = Grammar([EOF, 'b'])
|
|
|
53 g.add_production('goal', ['a'])
|
|
|
54 g.add_production('a', ['b'])
|
|
|
55 g.add_production('a', ['c'])
|
|
|
56 g.start_symbol = 'goal'
|
|
|
57 with self.assertRaises(ParserGenerationException):
|
|
|
58 g.genParser()
|
|
|
59 def testRedefineTerminal(self):
|
|
|
60 """ Test correct behavior when a terminal is redefined """
|
|
|
61 g = Grammar([EOF, 'b', 'c'])
|
|
|
62 g.add_production('goal', ['a'])
|
|
|
63 with self.assertRaises(ParserGenerationException):
|
|
|
64 g.add_production('b', ['c']) # Not allowed
|
|
|
65 g.add_production('a', ['c'])
|
|
|
66 g.start_symbol = 'goal'
|
|
|
67 g.genParser()
|
|
184
|
68
|
|
185
|
69 class testExpressionGrammar(unittest.TestCase):
|
|
|
70 def setUp(self):
|
|
|
71 g = Grammar(['EOF', 'identifier', '(', ')', '+', '*', 'num'])
|
|
|
72 g.add_production('input', ['expression'])
|
|
|
73 g.add_production('expression', ['term'])
|
|
|
74 g.add_production('expression', ['expression', '+', 'term'])
|
|
|
75 g.add_production('term', ['factor'])
|
|
|
76 g.add_production('term', ['term', '*', 'factor'])
|
|
|
77 g.add_production('factor', ['(', 'expression', ')'])
|
|
|
78 g.add_production('factor', ['identifier'])
|
|
|
79 g.add_production('factor', ['num'])
|
|
|
80 g.start_symbol = 'input'
|
|
|
81 self.g = g
|
|
|
82
|
|
|
83 def testFirstSimpleGrammar(self):
|
|
|
84 # 1. define a simple grammar:
|
|
|
85 first = self.g.calcFirstSets()
|
|
|
86 self.assertEqual(first['input'], {'identifier', '(', 'num'})
|
|
|
87 self.assertEqual(first['term'], {'identifier', '(', 'num'})
|
|
|
88
|
|
|
89 def testCanonical(self):
|
|
|
90 s0 = self.g.initialItemSet()
|
|
|
91 s, gt = self.g.genCanonicalSet(s0)
|
|
|
92 # Must result in 12 sets:
|
|
|
93 self.assertEqual(len(s), 24)
|
|
|
94
|
|
184
|
95 class testPG(unittest.TestCase):
|
|
|
96 """ Tests several parts of the parser generator """
|
|
|
97 def setUp(self):
|
|
|
98 g = Grammar(['(', ')'])
|
|
|
99 g.add_production('goal', ['list'])
|
|
|
100 g.add_production('list', ['list', 'pair'])
|
|
|
101 g.add_production('list', ['pair'])
|
|
|
102 g.add_production('pair', ['(', 'pair', ')'])
|
|
|
103 g.add_production('pair', ['(', ')'])
|
|
|
104 g.start_symbol = 'goal'
|
|
|
105 self.g = g
|
|
|
106
|
|
|
107 def testFirstSet(self):
|
|
|
108 for a in ['(', ')', EOF, 'EPS']:
|
|
|
109 self.assertEqual(self.g.first[a], {a})
|
|
|
110 for nt in ['list', 'pair', 'goal']:
|
|
|
111 self.assertEqual(self.g.first[nt], {'('})
|
|
|
112
|
|
|
113 def testInitItemSet(self):
|
|
|
114 p0, p1, p2, p3, p4 = self.g.productions
|
|
|
115 s0 = self.g.initialItemSet()
|
|
|
116 self.assertEqual(len(s0), 9) # 9 with the goal rule included!
|
|
|
117 self.assertIn(Item(p0, 0, EOF), s0)
|
|
|
118 self.assertIn(Item(p1, 0, EOF), s0)
|
|
|
119 self.assertIn(Item(p1, 0, '('), s0)
|
|
|
120 self.assertIn(Item(p2, 0, EOF), s0)
|
|
|
121 self.assertIn(Item(p2, 0, '('), s0)
|
|
|
122 self.assertIn(Item(p3, 0, EOF), s0)
|
|
|
123 self.assertIn(Item(p3, 0, '('), s0)
|
|
|
124 self.assertIn(Item(p4, 0, EOF), s0)
|
|
|
125 self.assertIn(Item(p4, 0, '('), s0)
|
|
|
126
|
|
|
127 def testCanonical(self):
|
|
|
128 s0 = self.g.initialItemSet()
|
|
|
129 s, gt = self.g.genCanonicalSet(s0)
|
|
|
130 # Must result in 12 sets:
|
|
|
131 self.assertEqual(len(s), 12)
|
|
|
132
|
|
|
133 def testClosure(self):
|
|
|
134 p0, p1, p2, p3, p4 = self.g.productions
|
|
|
135 s0 = set()
|
|
185
|
136 s0.add(Item(p0, 0, EOF))
|
|
184
|
137 self.assertEqual(len(s0), 1) # 1 rule
|
|
|
138 self.assertIn(Item(p0, 0, EOF), s0)
|
|
|
139
|
|
|
140 # Invoke closure on set:
|
|
|
141 s0 = self.g.closure(s0)
|
|
|
142 self.assertIn(Item(p0, 0, EOF), s0)
|
|
|
143 self.assertIn(Item(p1, 0, EOF), s0)
|
|
|
144 self.assertIn(Item(p1, 0, '('), s0)
|
|
|
145 self.assertIn(Item(p2, 0, EOF), s0)
|
|
|
146 self.assertIn(Item(p2, 0, '('), s0)
|
|
|
147 self.assertIn(Item(p3, 0, EOF), s0)
|
|
|
148 self.assertIn(Item(p3, 0, '('), s0)
|
|
|
149 self.assertIn(Item(p4, 0, EOF), s0)
|
|
|
150 self.assertIn(Item(p4, 0, '('), s0)
|
|
|
151
|
|
|
152 def testParser(self):
|
|
191
|
153 tokens = ['(', '(', ')', ')', '(', ')']
|
|
184
|
154 # 3. build parser:
|
|
|
155 p = self.g.genParser()
|
|
185
|
156 self.assertEqual(len(p.goto_table), 5)
|
|
|
157 self.assertEqual(len(p.action_table), 19)
|
|
|
158
|
|
184
|
159 # 4. feed input:
|
|
191
|
160 p.parse(genTokens(tokens))
|
|
184
|
161
|
|
|
162 if __name__ == '__main__':
|
|
|
163 unittest.main()
|
|
|
164
|
|
|
165
|
