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