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)

#

class TOYParser:

    """A parser for the TOY language"""

    def __init__(self):

        self.__s = Stack()

        self.__i = InputParser()

        self.END_SYMBOL = '$'

        self.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, '', '', '', ''))

        self.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'))

        self.START_SYMBOL = 'program'

    def terminals(self):

        """Return a list of the terminals in the table"""

        return [n for n in self.PARSING_TABLE[0] if n != '']

    def nonterminals(self):

        """Return a list of non-terminals in the table"""

        return [n[0] for n in self.PARSING_TABLE if n[0] != '']

    def getInput(self):

        self.__i.setInput('BEGIN  READ ID ; WHILE ( ID ) ID  = ID + NUM ;  WRITE ID END')

        self.LL1_Parsing_Algo()

    def getParsingTableEntry(self, nonterm, term):

        """Get the correct production rule out of the parsing table"""

        nt_num = 0

        t_num = 0

        for t in self.PARSING_TABLE:

            if t[0] == nonterm:

                break

            nt_num += 1

        for t in self.PARSING_TABLE[0]:

            if t == term:

                break

            t_num += 1

        return self.PARSING_TABLE[nt_num][t_num]

    def print_production_rule(self, num):

        prod_list = self.GRAMMAR_SPEC[num]

        nt = prod_list[0]

        term_str = ' '.join(prod_list[1:])

        s = 'PRODUCTION: %s -> %s' % (nt, term_str)

        print s

    def LL1_Parsing_Algo (self):

        """This implements the table-based LL(1) parsing algorithm from Figure 4.2

        (Page 155) in Compiler Construction Principles and Practices.

        NOTE: There is a correction in the while() statement, from 'and' to 'or'."""

        self.__s.push(self.END_SYMBOL)

        self.__s.push(self.START_SYMBOL)

        while self.__s.peek() != self.END_SYMBOL or self.__i.getNextToken() != self.END_SYMBOL:

            if self.__s.peek() == self.__i.getNextToken():

                print 'MATCH: %s' % (self.__i.getNextToken(), )

                self.__s.pop()

                self.__i.match()

            elif self.__s.peek() in self.nonterminals() and self.getParsingTableEntry(self.__s.peek(), self.__i.getNextToken()) != '':

                    nt = self.__s.pop()

                    t = self.__i.getNextToken()

                    pte = self.getParsingTableEntry(nt, t)

                    self.print_production_rule(pte-1)

                    # Basically pop the stack, and push back the correct stuff

                    # in reverse order

                    stack_additions = list(self.GRAMMAR_SPEC[pte-1][1:])

                    stack_additions.reverse()

                    for a in stack_additions:

                        self.__s.push(a)

            else:

                print 'An error happened'

            # endif

        # wend

        if self.__s.peek() == self.END_SYMBOL and self.__i.getNextToken() == self.END_SYMBOL:

            print 'ACCEPT'

        else:

            print 'ERROR'

class InputParser:

    """Implements a simple tokenizer for the TOY language"""

    def __init__(self):

        self.__inputstr = []

    def setInput(self, inputstr):

        self.__inputstr = inputstr.split()

        self.__inputstr.append('$') # Append '$' to the input

    def getInput(self):

        """Return a list representation of whatever is remaining of the input"""

        return self.__inputstr[:]

    def getNextToken(self):

        """Gets the first token off of the front of the input string, but

        DOES NOT remove any input."""

        try:

            return self.__inputstr[0]

        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 clear(self):

        """Empty the stack"""

        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 getStack(self):

        """Get whatever is in the stack, from bottom to top, as a list"""

        return self.__data[:]

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

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

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

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

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

def main():

    """The main function for this program"""

    t = TOYParser()

    print t.getInput()

if __name__ == '__main__':

    main()