# A general recursive descent parser

import re

class SyntaxException(Exception): pass

class Parser:

    def __init__(self, string):

        self._str = string

        self._pos = 0

    def parse(self):

        tree = self._main()

        if not self._pos == len(self._str): self._syntax_err('End of string')

        return tree

    def _match_re(self, pattern, required=False):

        matcher = re.compile(pattern).match(self._str, self._pos)

        if matcher:

            self._pos = matcher.end(0)

            return matcher.group(0)

        elif required: self._syntax_err(pattern)

    def _match_str(self, string, required=False):

        end_pos = self._pos + len(string)

        if self._str[self._pos:end_pos] == string:

            self._pos = end_pos

            return True

        elif required: self._syntax_err(string)

        else: return False

    def _syntax_err(self, token):

        raise SyntaxException(token+' expected in '+self._str[self._pos:])