Does this code use good Python practices for a context-free grammar implementation?

Question

I'm completing exercises in Compilers: Principles, Techniques, and Tools (2nd Edition) in Python. The following code converts:

{ int x; char y; { bool y; x; y; } x; y; }

to:

{ { x:int; y:bool; } x:int; y:char; }

I had the following concerns about my code:

1. Is it acceptable to do list(tokenize(...)) instead of using it like a proper iterator? I think it would be more efficient, but I wanted the flexibility of an array so that I could traverse backward and forward through the tokens.

2. Does it make sense to handle the control flow of the application by using Exceptions? I decided to use exceptions and rewinding instead of sentinels and peeking forward. I'm not sure if this is the best way though.

I'm not really concerned about the tokenize function as much, since I'm already aware of the problems there.

I would be open to any other suggestions or ways I could make this more Pythonistic.

class exercise(object):
    """
    program -> block
    block   -> { decls stmts }
    decls   -> decls decl
             | ∅
    decl    -> type id ;
    stmts   -> stmts stmt 
             | ∅
    stmt    -> block 
             | factor ;
    factor  -> id
    """

    def __init__(self, target):
        self.at = 0
        self.tokens = list(tokenize(target))
        self.writer = []
        self.symbols = symboltable()

    def match(self, value=None, type='symbol'):
        token = self.tokens[self.at]
        t_type, t_value = token
        if t_type != type or (value and t_value != value):
            raise InvalidSyntax('Expected {0} "{1}" but received {2} "{3}"'. \
                format(type, value, t_type, t_value))
        self.at += 1
        return token

    def parse(self):
        self.writer = []
        self.Program()
        return ' '.join(self.writer)

    def snapshot(self):
        return (self.at, len(self.writer))

    def rewind(self, snapshot):
        old_at, old_writer_len = snapshot
        self.at = old_at
        self.writer = self.writer[:old_writer_len]

    def Program(self):
        self.Block()

    def Block(self):
        self.match('{')
        self.writer.append('{')
        self.symbols = symboltable(self.symbols)
        try:
            self.Decls()
        except ParsingComplete:
            pass
        try:
            self.Stmts()
        except ParsingComplete:
            pass
        self.match('}')
        self.writer.append('}')
        self.symbols = self.symbols.parent

    def Decls(self):
        self.Decls_b()
        #self.Decl()

    def Decls_b(self):
        self.Decl()
        self.Decls()

    def Decl(self):
        snapshot = self.snapshot()
        try:
            _, type = self.match(type='word')
            _, id = self.match(type='word')
            self.symbols.put(id, type)
            self.match(';')
            return
        except:
            self.rewind(snapshot)
        raise ParsingComplete()

    def Stmts(self):
        self.Stmts_b()
        #self.Stmt()

    def Stmts_b(self):
        self.Stmt()
        self.Stmts()

    def Stmt(self):
        snapshot = self.snapshot()
        try:
            self.Block()
            return
        except:
            self.rewind(snapshot)
        try:
            self.Factor()
            self.match(';')
            return
        except:
            self.rewind(snapshot)
        raise ParsingComplete()

    def Factor(self):
        _, id = self.match(type='word')
        type = self.symbols.get(id)
        if not type:
            type = 'undeclared'
        self.writer.append('{0}:{1};'.format(id, type))

class InvalidSyntax(Exception):
    pass

class ParsingComplete(Exception):
    pass

class symboltable(object):
    """ Store lexeme name and value information for a given scope """

    def __init__(self, parent=None):
        self.parent = parent
        self.table = dict()

    def get(self, key):
        if key in self.table:
            return self.table[key]
        if not self.parent:
            return None
        return self.parent.get(key)

    def put(self, key, value):
        self.table.update({key: value})

def tokenize(target):
    i = 0
    while i < len(target):
        c = target[i]
        if c == ' ':
            pass
        elif c.isdigit():
            n = 0
            while True:
                n = n * 10 + int(c)
                c = target[i + 1]
                if not c.isdigit():
                    break
                i += 1
            yield ('number', n)
        elif c.isalpha():
            letters = []
            while True:
                letters.append(c)
                c = target[i + 1]
                if not c.isalpha() and not c.isdigit():
                    break
                i += 1
            word = ''.join(letters)
            yield ('word', word)
        else:
            yield('symbol', c)
        i += 1

input = '{ int x; char y; { bool y; x; y; } x; y; }'
expected = '{ { x:int; y:bool; } x:int; y:char; }'
actual = exercise(input).parse()
assert actual == expected

Answer 1

class exercise(object):

The python style guide recommends CamelCase for class names

    """
    program -> block
    block   -> { decls stmts }
    decls   -> decls decl
             | ∅
    decl    -> type id ;
    stmts   -> stmts stmt 
             | ∅
    stmt    -> block 
             | factor ;
    factor  -> id
    """

    def __init__(self, target):
        self.at = 0
        self.tokens = list(tokenize(target))

This is perfectly fine. It's probably faster this way, but will take more memory.

        self.writer = []
        self.symbols = symboltable()

    def match(self, value=None, type='symbol'):
        token = self.tokens[self.at]
        t_type, t_value = token
        if t_type != type or (value and t_value != value):

For checking if value is None, I recommend value is None rather then just checking for false. Another false value could be passed

            raise InvalidSyntax('Expected {0} "{1}" but received {2} "{3}"'. \
                format(type, value, t_type, t_value))
        self.at += 1
        return token

I would actually separate match, snapshot and, rewind off onto their own class. Those form a unit of logic of operating over the token stream, and are best kept separate from the actual parsing logic.

    def parse(self):
        self.writer = []

This attribute bothers me. I wonder if the code would be cleaner to use return values for this. The name is also a little bit off because its hold data, it doesn't really write anything itself.

        self.Program()
        return ' '.join(self.writer)

    def snapshot(self):
        return (self.at, len(self.writer))

    def rewind(self, snapshot):
        old_at, old_writer_len = snapshot
        self.at = old_at
        self.writer = self.writer[:old_writer_len]

It may be better to del the extra stuff in writer, rather then slice it

    def Program(self):

Python convention is to have lowercase_with_underscores for method names. This method is also internal to the parser and should perhaps begin with an underscore.

        self.Block()

    def Block(self):
        self.match('{')
        self.writer.append('{')
        self.symbols = symboltable(self.symbols)
        try:
            self.Decls()
        except ParsingComplete:
            pass

Using an exception to say something is finished will be severely looked down upon

        try:
            self.Stmts()
        except ParsingComplete:
            pass
        self.match('}')
        self.writer.append('}')
        self.symbols = self.symbols.parent

    def Decls(self):
        self.Decls_b()
        #self.Decl()

There isn't a whole lot of point to a function that just calls another function

    def Decls_b(self):
        self.Decl()
        self.Decls()

I would suggest that you use a loop rather then recursion here, and that you handle the exception here. This is the point where a Decl is either Decl Decls or nothing. So here is the best place to have the logic diverge. Something lile

def Decls(self):
   while True:
       try:
           snapshot = self.snapshot()
           self.Decl() # try parsing another Decl
       except InvalidSyntaxError:
           self.rewind(snapshot)
           break # if we failed to parse the Decl, stop

I think using the looping constructs of the language make this much clearer. However, this points to a problem with your approach. Pretty much every single syntax error will be diagnosed as a missing }, not a very helpful error message. This is because most failure exceptions gets interpreted having attempted to parse the wrong thing.

    def Decl(self):
        snapshot = self.snapshot()
        try:
            _, type = self.match(type='word')
            _, id = self.match(type='word')
            self.symbols.put(id, type)
            self.match(';')
            return
        except:

Don't do this. You should catch only the specific type of exception you are interested in. Otherwise you'll catch other exceptions and make bugs hard to find.

            self.rewind(snapshot)
        raise ParsingComplete()

This is only executed in the case of an exception, so why isn't it in the exception block?

[Snip Stmt section, similar issues apply]

class InvalidSyntax(Exception):
    pass

class ParsingComplete(Exception):
    pass

class symboltable(object):
    """ Store lexeme name and value information for a given scope """

    def __init__(self, parent=None):
        self.parent = parent
        self.table = dict()

    def get(self, key):
        if key in self.table:
            return self.table[key]

This is considered a bad idea in python because you have to lookup the key twice

        if not self.parent:
            return None

Do you really want to return None? Shouldn't you throw an exception?

        return self.parent.get(key)

I'd write this as

try:
   return self.table[key]
except KeyError:
   if self.parent is None:
       raise UnknownVariableError(key)
   else:
       return self.parent.get(key)

I think it is clearer

    def put(self, key, value):
        self.table.update({key: value})

Why not self.table[key] = value?

[skipped tokenize]