Subversion Repositories programming

Rev

Rev 200 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 200 Rev 201
Line 4... Line 4...
4 
# Copyright: 2006 Ira W. Snyder
 4 
# Copyright: 2006 Ira W. Snyder
5 
# Start Date: 2006-02-01
 5 
# Start Date: 2006-02-01
6 
# License: GNU General Public License v2 (or at your option, any later version)
 6 
# License: GNU General Public License v2 (or at your option, any later version)
7 
#
 7 
#
8 
 
 8 
 
9 
parsing_table = (('', 'BEGIN', 'END', 'IF', 'ELSE', 'WHILE', 'ID', 'READ', 'WRITE', 'NUM', '+', '(', ')', ';', '=', '$'),
 - 
 
10 
                 ('program', 1, '', '', '', '', '', '', '', '', '', '', '', '', '', ''),
 - 
 
11 
                 ('stmtseq', '', '', 2, '', 2, 2, 2, 2, '', '', '', '', '', '', ''),
 9 
class TOYParser:
12 
                 ('stmtseq1', '', 4, '', '', '', '', '', '', '', '', '', '', 3, '', ''),
 - 
 
13 
                 ('stmt', '', '', 5, '', 6, 7, 8, 9, '', '', '', '', '', '', ''),
 10 
    """A parser for the TOY language"""
14 
                 ('exp', '', '', '', '', '', 10, '', '', 10, '', 10, '', '', '', ''),
 - 
 
15 
                 ('exp1', '', 12, '', 12, '', '', '', '', '', 11, '', 12, 12, '', ''),
 - 
 
16 
                 ('term', '', '', '', '', '', 15, '', '', 14, '', 13, '', '', '', ''))
 - 
 
17 
 
 11 
 
- 
 
 12 
    def __init__(self):
- 
 
 13 
        self.__s = Stack()
- 
 
 14 
        self.__i = InputParser()
- 
 
 15 
        self.END_SYMBOL = '$'
- 
 
 16 
        self.PARSING_TABLE = (('', 'BEGIN', 'END', 'IF', 'ELSE', 'WHILE', 'ID', 'READ', 'WRITE', 'NUM', '+', '(', ')', ';', '=', '$'),
- 
 
 17 
                ('program', 1, '', '', '', '', '', '', '', '', '', '', '', '', '', ''),
- 
 
 18 
                ('stmtseq', '', '', 2, '', 2, 2, 2, 2, '', '', '', '', '', '', ''),
- 
 
 19 
                ('stmtseq1', '', 4, '', '', '', '', '', '', '', '', '', '', 3, '', ''),
- 
 
 20 
                ('stmt', '', '', 5, '', 6, 7, 8, 9, '', '', '', '', '', '', ''),
- 
 
 21 
                ('exp', '', '', '', '', '', 10, '', '', 10, '', 10, '', '', '', ''),
- 
 
 22 
                ('exp1', '', 12, '', 12, '', '', '', '', '', 11, '', 12, 12, '', ''),
- 
 
 23 
                ('term', '', '', '', '', '', 15, '', '', 14, '', 13, '', '', '', ''))
- 
 
 24 
 
18 
grammar_spec = (('program', 'BEGIN', 'stmtseq', 'END'),
 25 
        self.GRAMMAR_SPEC = (('program', 'BEGIN', 'stmtseq', 'END'),
19 
                ('stmtseq', 'stmt', 'stmtseq1'),
 26 
                ('stmtseq', 'stmt', 'stmtseq1'),
20 
                ('stmtseq1', ';', 'stmt', 'stmtseq1'),
 27 
                ('stmtseq1', ';', 'stmt', 'stmtseq1'),
21 
                ('stmtseq1', ),
 28 
                ('stmtseq1', ),
22 
                ('stmt', 'IF', '(', 'exp', ')', 'stmt', 'ELSE', 'stmt'),
 29 
                ('stmt', 'IF', '(', 'exp', ')', 'stmt', 'ELSE', 'stmt'),
23 
                ('stmt', 'WHILE', '(', 'exp', ')', 'stmt'),
 30 
                ('stmt', 'WHILE', '(', 'exp', ')', 'stmt'),
Line 29... Line 36...
29 
                ('exp1', ),
 36 
                ('exp1', ),
30 
                ('term', '(', 'exp', ')'),
 37 
                ('term', '(', 'exp', ')'),
31 
                ('term', 'NUM'),
 38 
                ('term', 'NUM'),
32 
                ('term', 'ID'))
 39 
                ('term', 'ID'))
33 
 
 40 
 
- 
 
 41 
        self.START_SYMBOL = 'program'
- 
 
 42 
 
- 
 
 43 
    def terminals(self):
- 
 
 44 
        """Return a list of the terminals in the table"""
- 
 
 45 
 
- 
 
 46 
        return [n for n in self.PARSING_TABLE[0] if n != '']
- 
 
 47 
 
- 
 
 48 
    def nonterminals(self):
- 
 
 49 
        """Return a list of non-terminals in the table"""
- 
 
 50 
 
- 
 
 51 
        return [n[0] for n in self.PARSING_TABLE if n[0] != '']
- 
 
 52
- 
 
 53 
    def getInput(self):
- 
 
 54 
        self.__i.setInput('BEGIN  READ ID ; WHILE ( ID ) ID  = ID + NUM ;  WRITE ID END')
- 
 
 55 
        self.LL1_Parsing_Algo()
- 
 
 56 
 
- 
 
 57 
    def getParsingTableEntry(self, nonterm, term):
- 
 
 58 
        """Get the correct production rule out of the parsing table"""
- 
 
 59 
 
- 
 
 60 
        nt_num = 0
- 
 
 61 
        t_num = 0
- 
 
 62
- 
 
 63 
        for t in self.PARSING_TABLE:
- 
 
 64 
            if t[0] == nonterm:
- 
 
 65 
                break
- 
 
 66 
 
- 
 
 67 
            nt_num += 1
- 
 
 68 
 
- 
 
 69 
        for t in self.PARSING_TABLE[0]:
- 
 
 70 
            if t == term:
- 
 
 71 
                break
- 
 
 72 
 
- 
 
 73 
            t_num += 1
- 
 
 74 
 
- 
 
 75 
        return self.PARSING_TABLE[nt_num][t_num]
- 
 
 76 
 
- 
 
 77 
    def print_production_rule(self, num):
- 
 
 78 
        prod_list = self.GRAMMAR_SPEC[num]
- 
 
 79
- 
 
 80 
        nt = prod_list[0]
- 
 
 81 
        term_str = ' '.join(prod_list[1:])
- 
 
 82 
 
- 
 
 83 
        s = 'PRODUCTION: %s -> %s' % (nt, term_str)
34 
 
 84 
 
35 
def terminals():
 85 
        print s
- 
 
 86
- 
 
 87 
    def LL1_Parsing_Algo (self):
- 
 
 88 
        """This implements the table-based LL(1) parsing algorithm from Figure 4.2
36 
    """Return a list of the terminals in the table"""
 89 
        (Page 155) in Compiler Construction Principles and Practices.
- 
 
 90 
        NOTE: There is a correction in the while() statement, from 'and' to 'or'."""
- 
 
 91 
 
- 
 
 92 
        self.__s.push(self.END_SYMBOL)
- 
 
 93 
        self.__s.push(self.START_SYMBOL)
37 
 
 94 
 
38 
    return [n for n in parsing_table[0] if n != '']
 95 
        while self.__s.peek() != self.END_SYMBOL or self.__i.getNextToken() != self.END_SYMBOL:
39 
 
 96 
 
- 
 
 97 
            if self.__s.peek() == self.__i.getNextToken():
- 
 
 98 
                print 'MATCH: %s' % (self.__i.getNextToken(), )
40 
def nonterminals():
 99 
                self.__s.pop()
41 
    """Return a list of non-terminals in the table"""
 100 
                self.__i.match()
42 
 
 101 
 
43 
    return [n[0] for n in parsing_table if n[0] != '']
 102 
            elif self.__s.peek() in self.nonterminals() and self.getParsingTableEntry(self.__s.peek(), self.__i.getNextToken()) != '':
44 
 
 103 
 
45 
def LL1_Parsing_Algo ():
 104 
                    nt = self.__s.pop()
46 
    """This implements the table-based LL(1) parsing algorithm from Figure 4.2
 105 
                    t = self.__i.getNextToken()
47 
    (Page 155) in Compiler Construction Principles and Practices"""
 106 
                    pte = self.getParsingTableEntry(nt, t)
48 
 
 107 
 
49 
    END_SYMBOL = '$'
 108 
                    self.print_production_rule(pte-1)
50 
    s = Stack()
 109
- 
 
 110 
                    # Basically pop the stack, and push back the correct stuff
51 
    s.push(START_SYMBOL)
 111 
                    # in reverse order
- 
 
 112 
                    stack_additions = list(self.GRAMMAR_SPEC[pte-1][1:])
- 
 
 113 
                    stack_additions.reverse()
52 
 
 114 
 
- 
 
 115 
                    for a in stack_additions:
- 
 
 116 
                        self.__s.push(a)
- 
 
 117 
 
- 
 
 118 
            else:
- 
 
 119 
                print 'An error happened'
- 
 
 120 
            # endif
- 
 
 121 
        # wend
- 
 
 122 
 
53 
    #while s.peek() != END_SYMBOL and input.getNextToken() != END_SYMBOL:
 123 
        if self.__s.peek() == self.END_SYMBOL and self.__i.getNextToken() == self.END_SYMBOL:
- 
 
 124 
            print 'ACCEPT'
54 
    #    pass
 125 
        else:
- 
 
 126 
            print 'ERROR'
55 
 
 127 
 
56 
class InputParser:
 128 
class InputParser:
57 
    """Implements a simple tokenizer for the TOY language"""
 129 
    """Implements a simple tokenizer for the TOY language"""
58 
 
 130 
 
- 
 
 131 
    def __init__(self):
- 
 
 132 
        self.__inputstr = []
- 
 
 133 
 
59 
    def __init__(self, inputstr):
 134 
    def setInput(self, inputstr):
60 
        self.__inputstr = inputstr.split()
 135 
        self.__inputstr = inputstr.split()
- 
 
 136 
        self.__inputstr.append('$') # Append '$' to the input
61 
 
 137 
 
- 
 
 138 
    def getInput(self):
- 
 
 139 
        """Return a list representation of whatever is remaining of the input"""
- 
 
 140 
 
- 
 
 141 
        return self.__inputstr[:]
- 
 
 142
62 
    def getNextToken(self):
 143 
    def getNextToken(self):
63 
        """Gets the first token off of the front of the input string, but
 144 
        """Gets the first token off of the front of the input string, but
64 
        DOES NOT remove any input."""
 145 
        DOES NOT remove any input."""
65
146
66 
        try:
 147 
        try:
67 
            if self.__inputstr[0] in terminals():
 - 
 
68 
                return self.__inputstr[0]
 148 
            return self.__inputstr[0]
69 
            else:
 - 
 
70 
                return 'BAD INPUT'
 - 
 
71 
        except IndexError:
 149 
        except IndexError:
72 
            print 'CAUGHT IndexError in getNextToken()'
 150 
            print 'CAUGHT IndexError in getNextToken()'
73 
            return ''
 151 
            return ''
74 
 
 152 
 
75 
    def match(self):
 153 
    def match(self):
Line 84... Line 162...
84 
    """Implements a simple stack using a list"""
 162 
    """Implements a simple stack using a list"""
85 
 
 163 
 
86 
    def __init__(self):
 164 
    def __init__(self):
87 
        self.__data = []
 165 
        self.__data = []
88 
 
 166 
 
- 
 
 167 
    def clear(self):
- 
 
 168 
        """Empty the stack"""
- 
 
 169 
        self.__data = []
- 
 
 170
89 
    def push(self, val):
 171 
    def push(self, val):
90 
        """Push a value onto the top of the stack"""
 172 
        """Push a value onto the top of the stack"""
91 
        self.__data.append(val)
 173 
        self.__data.append(val)
92 
 
 174 
 
93 
    def pop(self):
 175 
    def pop(self):
Line 102... Line 184...
102 
 
 184 
 
103 
        temp = self.pop()
 185 
        temp = self.pop()
104 
        self.push(temp)
 186 
        self.push(temp)
105 
        return temp
 187 
        return temp
106 
 
 188 
 
- 
 
 189 
    def getStack(self):
- 
 
 190 
        """Get whatever is in the stack, from bottom to top, as a list"""
- 
 
 191 
 
- 
 
 192 
        return self.__data[:]
- 
 
 193 
 
107 
################################################################################
 194 
################################################################################
108 
################################################################################
 195 
################################################################################
109 
################################################################################
 196 
################################################################################
110 
################################################################################
 197 
################################################################################
111 
################################################################################
 198 
################################################################################
112 
 
 199 
 
113 
def main():
 200 
def main():
114 
    """The main function for this program"""
 201 
    """The main function for this program"""
115 
 
 202 
 
116 
    i = InputParser('BEGIN  READ ID ; WHILE ( ID ) ID  = ID + NUM ;  WRITE ID END')
 - 
 
117
- 
 
118 
    while i.getNextToken() != '':
 203 
    t = TOYParser()
119 
        print i.getNextToken()
 204 
    print t.getInput()
120 
        i.match()
 - 
 
121 
 
 - 
 
122 
 
 - 
 
123 
 
 205 
 
124 
if __name__ == '__main__':
 206 
if __name__ == '__main__':
125 
    main()
 207 
    main()
126 
 
 208