Subversion Repositories programming

#!/usr/bin/env python

#
# Copyright: 2006 Ira W. Snyder
# Start Date: 2006-02-01
# License: GNU General Public License v2 (or at your option, any later version)
#

parsing_table = (('', 'BEGIN', 'END', 'IF', 'ELSE', 'WHILE', 'ID', 'READ', 'WRITE', 'NUM', '+', '(', ')', ';', '=', '$'),
                 ('program', 1, '', '', '', '', '', '', '', '', '', '', '', '', '', ''),
                 ('stmtseq', '', '', 2, '', 2, 2, 2, 2, '', '', '', '', '', '', ''),
                 ('stmtseq1', '', 4, '', '', '', '', '', '', '', '', '', '', 3, '', ''),
                 ('stmt', '', '', 5, '', 6, 7, 8, 9, '', '', '', '', '', '', ''),
                 ('exp', '', '', '', '', '', 10, '', '', 10, '', 10, '', '', '', ''),
                 ('exp1', '', 12, '', 12, '', '', '', '', '', 11, '', 12, 12, '', ''),
                 ('term', '', '', '', '', '', 15, '', '', 14, '', 13, '', '', '', ''))

grammar_spec = (('program', 'BEGIN', 'stmtseq', 'END'),
                ('stmtseq', 'stmt', 'stmtseq1'),
                ('stmtseq1', ';', 'stmt', 'stmtseq1'),
                ('stmtseq1', ),
                ('stmt', 'IF', '(', 'exp', ')', 'stmt', 'ELSE', 'stmt'),
                ('stmt', 'WHILE', '(', 'exp', ')', 'stmt'),
                ('stmt', 'ID', '=', 'exp'),
                ('stmt', 'READ', 'ID'),
                ('stmt', 'WRITE', 'exp'),
                ('exp', 'term', 'exp1'),
                ('exp1', '+', 'term', 'exp1'),
                ('exp1', ),
                ('term', '(', 'exp', ')'),
                ('term', 'NUM'),
                ('term', 'ID'))


def terminals():
    """Return a list of the terminals in the table"""

    return [n for n in parsing_table[0] if n != '']

def nonterminals():
    """Return a list of non-terminals in the table"""

    return [n[0] for n in parsing_table if n[0] != '']

def LL1_Parsing_Algo ():
    """This implements the table-based LL(1) parsing algorithm from Figure 4.2
    (Page 155) in Compiler Construction Principles and Practices"""

    END_SYMBOL = '$'
    s = Stack()
    s.push(START_SYMBOL)

    #while s.peek() != END_SYMBOL and input.getNextToken() != END_SYMBOL:
    #    pass

class InputParser:
    """Implements a simple tokenizer for the TOY language"""

    def __init__(self, inputstr):
        self.__inputstr = inputstr.split()

    def getNextToken(self):
        """Gets the first token off of the front of the input string, but
        DOES NOT remove any input."""
        
        try:
            if self.__inputstr[0] in terminals():
                return self.__inputstr[0]
            else:
                return 'BAD INPUT'
        except IndexError:
            print 'CAUGHT IndexError in getNextToken()'
            return ''

    def match(self):
        """A match has happened, so remove the front of the input string."""
        
        try:
            del self.__inputstr[0]
        except IndexError:
            print 'CAUGHT IndexError in match()'

class Stack:
    """Implements a simple stack using a list"""

    def __init__(self):
        self.__data = []

    def push(self, val):
        """Push a value onto the top of the stack"""
        self.__data.append(val)

    def pop(self):
        """Pop a value off the top of the stack.
        WARNING: throws IndexError if there is nothing left in the stack"""
        return self.__data.pop()

    def peek(self):
        """Peek at the top of the stack. Basically a pop() without removing the
        object from the top.
        WARNING: will throw an IndexError if there is nothing left in the stack."""

        temp = self.pop()
        self.push(temp)
        return temp

################################################################################
################################################################################
################################################################################
################################################################################
################################################################################

def main():
    """The main function for this program"""

    i = InputParser('BEGIN  READ ID ; WHILE ( ID ) ID  = ID + NUM ;  WRITE ID END')
    
    while i.getNextToken() != '':
        print i.getNextToken()
        i.match()



if __name__ == '__main__':
    main()