| 199 |
ira |
1 |
#!/usr/bin/env python
|
|
|
2 |
|
| 200 |
ira |
3 |
#
|
| 199 |
ira |
4 |
# Copyright: 2006 Ira W. Snyder
|
|
|
5 |
# Start Date: 2006-02-01
|
|
|
6 |
# License: GNU General Public License v2 (or at your option, any later version)
|
|
|
7 |
#
|
|
|
8 |
|
|
|
9 |
parsing_table = (('', 'BEGIN', 'END', 'IF', 'ELSE', 'WHILE', 'ID', 'READ', 'WRITE', 'NUM', '+', '(', ')', ';', '=', '$'),
|
|
|
10 |
('program', 1, '', '', '', '', '', '', '', '', '', '', '', '', '', ''),
|
|
|
11 |
('stmtseq', '', '', 2, '', 2, 2, 2, 2, '', '', '', '', '', '', ''),
|
|
|
12 |
('stmtseq1', '', 4, '', '', '', '', '', '', '', '', '', '', 3, '', ''),
|
|
|
13 |
('stmt', '', '', 5, '', 6, 7, 8, 9, '', '', '', '', '', '', ''),
|
|
|
14 |
('exp', '', '', '', '', '', 10, '', '', 10, '', 10, '', '', '', ''),
|
|
|
15 |
('exp1', '', 12, '', 12, '', '', '', '', '', 11, '', 12, 12, '', ''),
|
|
|
16 |
('term', '', '', '', '', '', 15, '', '', 14, '', 13, '', '', '', ''))
|
|
|
17 |
|
| 200 |
ira |
18 |
grammar_spec = (('program', 'BEGIN', 'stmtseq', 'END'),
|
|
|
19 |
('stmtseq', 'stmt', 'stmtseq1'),
|
|
|
20 |
('stmtseq1', ';', 'stmt', 'stmtseq1'),
|
|
|
21 |
('stmtseq1', ),
|
|
|
22 |
('stmt', 'IF', '(', 'exp', ')', 'stmt', 'ELSE', 'stmt'),
|
|
|
23 |
('stmt', 'WHILE', '(', 'exp', ')', 'stmt'),
|
|
|
24 |
('stmt', 'ID', '=', 'exp'),
|
|
|
25 |
('stmt', 'READ', 'ID'),
|
|
|
26 |
('stmt', 'WRITE', 'exp'),
|
|
|
27 |
('exp', 'term', 'exp1'),
|
|
|
28 |
('exp1', '+', 'term', 'exp1'),
|
|
|
29 |
('exp1', ),
|
|
|
30 |
('term', '(', 'exp', ')'),
|
|
|
31 |
('term', 'NUM'),
|
|
|
32 |
('term', 'ID'))
|
|
|
33 |
|
|
|
34 |
|
| 199 |
ira |
35 |
def terminals():
|
|
|
36 |
"""Return a list of the terminals in the table"""
|
|
|
37 |
|
|
|
38 |
return [n for n in parsing_table[0] if n != '']
|
|
|
39 |
|
|
|
40 |
def nonterminals():
|
|
|
41 |
"""Return a list of non-terminals in the table"""
|
|
|
42 |
|
|
|
43 |
return [n[0] for n in parsing_table if n[0] != '']
|
|
|
44 |
|
|
|
45 |
def LL1_Parsing_Algo ():
|
|
|
46 |
"""This implements the table-based LL(1) parsing algorithm from Figure 4.2
|
|
|
47 |
(Page 155) in Compiler Construction Principles and Practices"""
|
|
|
48 |
|
|
|
49 |
END_SYMBOL = '$'
|
|
|
50 |
s = Stack()
|
|
|
51 |
s.push(START_SYMBOL)
|
|
|
52 |
|
|
|
53 |
#while s.peek() != END_SYMBOL and input.getNextToken() != END_SYMBOL:
|
|
|
54 |
# pass
|
| 200 |
ira |
55 |
|
| 199 |
ira |
56 |
class InputParser:
|
|
|
57 |
"""Implements a simple tokenizer for the TOY language"""
|
|
|
58 |
|
|
|
59 |
def __init__(self, inputstr):
|
| 200 |
ira |
60 |
self.__inputstr = inputstr.split()
|
| 199 |
ira |
61 |
|
|
|
62 |
def getNextToken(self):
|
|
|
63 |
"""Gets the first token off of the front of the input string, but
|
|
|
64 |
DOES NOT remove any input."""
|
| 200 |
ira |
65 |
|
|
|
66 |
try:
|
|
|
67 |
if self.__inputstr[0] in terminals():
|
|
|
68 |
return self.__inputstr[0]
|
|
|
69 |
else:
|
|
|
70 |
return 'BAD INPUT'
|
|
|
71 |
except IndexError:
|
|
|
72 |
print 'CAUGHT IndexError in getNextToken()'
|
|
|
73 |
return ''
|
| 199 |
ira |
74 |
|
|
|
75 |
def match(self):
|
|
|
76 |
"""A match has happened, so remove the front of the input string."""
|
| 200 |
ira |
77 |
|
|
|
78 |
try:
|
|
|
79 |
del self.__inputstr[0]
|
|
|
80 |
except IndexError:
|
|
|
81 |
print 'CAUGHT IndexError in match()'
|
| 199 |
ira |
82 |
|
|
|
83 |
class Stack:
|
|
|
84 |
"""Implements a simple stack using a list"""
|
|
|
85 |
|
|
|
86 |
def __init__(self):
|
|
|
87 |
self.__data = []
|
|
|
88 |
|
|
|
89 |
def push(self, val):
|
|
|
90 |
"""Push a value onto the top of the stack"""
|
|
|
91 |
self.__data.append(val)
|
|
|
92 |
|
|
|
93 |
def pop(self):
|
|
|
94 |
"""Pop a value off the top of the stack.
|
|
|
95 |
WARNING: throws IndexError if there is nothing left in the stack"""
|
|
|
96 |
return self.__data.pop()
|
|
|
97 |
|
|
|
98 |
def peek(self):
|
|
|
99 |
"""Peek at the top of the stack. Basically a pop() without removing the
|
|
|
100 |
object from the top.
|
|
|
101 |
WARNING: will throw an IndexError if there is nothing left in the stack."""
|
|
|
102 |
|
|
|
103 |
temp = self.pop()
|
|
|
104 |
self.push(temp)
|
|
|
105 |
return temp
|
|
|
106 |
|
|
|
107 |
################################################################################
|
|
|
108 |
################################################################################
|
|
|
109 |
################################################################################
|
|
|
110 |
################################################################################
|
|
|
111 |
################################################################################
|
|
|
112 |
|
|
|
113 |
def main():
|
|
|
114 |
"""The main function for this program"""
|
|
|
115 |
|
| 200 |
ira |
116 |
i = InputParser('BEGIN READ ID ; WHILE ( ID ) ID = ID + NUM ; WRITE ID END')
|
|
|
117 |
|
|
|
118 |
while i.getNextToken() != '':
|
|
|
119 |
print i.getNextToken()
|
|
|
120 |
i.match()
|
|
|
121 |
|
|
|
122 |
|
|
|
123 |
|
| 199 |
ira |
124 |
if __name__ == '__main__':
|
|
|
125 |
main()
|
|
|
126 |
|