Recursive Descent Parser Implementation for a Recursive Language

Question

I'm writing toy parsers for toy languages to understand how parsers work.

Assuming a language as follows (in sketchy EBNF patois)

expression :=  lparen [datum] [expression [datum]] rparen
datum      :=  any string of characters other than ( or )
rparen     :=  (
lparen     :=  )

These are some valid expressions

(hello(one(two(three)a)b)c)
(()abc)
((()))

whereas the following strings are illegal

)(
abc
((abc)
((abc)(
((abc)(abc))

So, these are strings consisting of balanced parentheses, with alphanumeric strings possible between both open and closed parentheses. The data can be arbitrarily nested, but not repeating (so each pair of parentheses contains at most one pair of parentheses at its toplevel -- see the last example in the block above).

I wrote a Python implementation of a parser for this language as follows:

import inspect


class Parser:
    def __init__(self, expression, verbose=True):
        self.expression = expression
        self.position = 0
        self.tokens = []
        self.paren_state = 0
        self.verbose = verbose


    def peek(self):
        if self.position + 1 == len(self.expression):
            return "EOF"
        else:
            return self.expression[self.position + 1]


    def advance(self):
        self.pretty_print_stack()
        if (self.position + 1) >= len(self.expression):
            return self.tokens
        else:
            self.position += 1


    def current(self):
        return self.expression[self.position]


    def parse_paren(self):
        self.pretty_print_stack()
        if self.current() == "(":
            self.parse_lparen()
        elif self.current() == ")":
            self.parse_rparen()
        else:
            raise Exception(f"Expected parentheses at {self.position}")


    def parse_lparen(self):
        self.pretty_print_stack()        
        if self.current() == "(":
            self.paren_state += 1
            self.advance()
        else:
            raise Exception(f"Expected left parentheses at position {self.position}")


    def parse_rparen(self):
        self.pretty_print_stack()
        if self.current() == ")":
            self.paren_state -= 1
            if self.paren_state < 0:
                raise Exception(f"Imbalanced parentheses")
            else:
                self.advance()
        else:
            raise Exception(f"Expected right parentheses at position {self.position}")


    def is_paren(self):
        return self.current() in ["(", ")"]


    def parse_datum(self):
        self.pretty_print_stack()
        buffer = ""
        while not self.is_paren():
            self.pretty_print_stack()
            buffer += self.current()
            self.advance()
        if buffer:
            self.tokens.append(buffer)


    def parse_expression(self):
        self.pretty_print_stack()
        if self.peek() != "EOF":
            self.parse_paren()
            self.parse_datum()
            self.parse_expression()
        else:
            if self.paren_state > 1 or self.current() != ")":
                raise Exception("Imbalanced parentheses")
        return self.tokens 


    def pretty_print_stack(self):
        if self.verbose:
            pretty_printed = ""
            for idx, char in enumerate(self.expression):
                if idx == self.position:
                    pretty_printed += f">{char}<"
                else:
                    pretty_printed += char

            current_frame = inspect.currentframe()
            caller_frame = inspect.getouterframes(current_frame, 2)
            print(f"{pretty_printed:<20} Position {self.position}, in {caller_frame[1][3]}, paren_state: {self.paren_state} peek: {self.peek()}")

This has the expected behavior, which is to bomb on imbalanced parentheses, and build up a list of "tokens" (actually "datums", which are the substrings between the parentheses).

I feel it has some issues

1. The way I detect imbalanced parentheses (adding 1 to paren_state everytime an lparen is encountered and subtracting 1 if an rparen is encountered, then making sure the value of paren_state is always non-negative) feels like a hack. Is there a better way to do this?

2. The code in Parser.parse_expression doesn't "read" like the grammar as recursive descent parsers are supposed to, and overall the implementation feels clumsy

3. Related to the grammar, I have a vague sense that it would help if I could refactor the grammatical definition of expression so that it isn't recursive, but I'm not sure how to do this (or if it is even possible) since the language has a recursive structure

Happy and grateful for any thoughts and feedback on this.

Answer 1

A potential solution to points #1 and #2 is to rework some of the recursive logic of the code. The basic premise is to rework the expression so it is more like:

expression := [datum] [lparen expression rparen]

This allows it to handle brackets by recursively calling itself until they are gone without using a bracket counter. I won't code the solution for you, I will leave that to you but I will run you through the basic logic. It firstly has to check if the next character is a lparen or not. If it is not an lparen then it runs parse_datum. If it is an lparen then it runs advance and then runs parse_expression. Once that parse_expression finishes running, it can check if there is an rparen, if there is then it can continue, otherwise it will raise an error, as they are unmatched parentheses.

The only other thing is that your language needs the outer item to be in parentheses but that can be implemented simply by a check for an lparen before passing it to the parse_expression method.

Answer 2

Here's a suggestion:

For question #1 and #2, parse_expression is written in a way that matches the grammar, which also ensures the parens are balanced. If a '(' is matched, then the optional internal parts of an expression are parsed and then the ')'.

There is a separate top level function call, parse(), that takes the expression to parse and makes sure it starts with a '(' before calling parse_expression. This helps with questions #1 and #3.

I left out pretty_print_stack() for brevity.

class ParseError(Exception):
    def __init__(self, message=''):
        self.message = f"ParseError: {message}"



class Parser:
    def __init__(self, verbose=1):
        self.verbose = verbose


    def advance(self):
        if self.position < len(self.expression):
            self.position += 1

        if self.position < len(self.expression):
            self.current = self.expression[self.position]
        else:
            self.current = "EOF"


    def parse(self, expression):
        """
        Takes expression to parse and returns a parse tree in the form of a
        nested list. E.g., (a((b)c)) -> ['a', ['', ['b', None, ''], 'c'], ''].

        At this level, an expression is required, so make sure the '(' is there.
        Then call self.expression(); otherwise, it's a syntax error.
        """

        self.expression = expression
        self.position = 0
        self.current = self.expression[:1]

        if self.current != '(':
            raise ParseError(f"Missing '(' at position {self.position}.")

        return self.parse_expression()


    def parse_datum(self):
        """
        datum :=  any string of characters other than ( or ) or EOF.

        returns string of chars or empty string
        """

        start = self.position

        while self.current not in ('(',')','EOF'):
            self.advance()

        return self.expression[start:self.position]


    def parse_expression(self):
        """expression :=  '(' [datum] [expression [datum]] ')'

        returns list of elements, or None if it doesn't parse
        """

        if self.current == '(':
            self.advance()

            datum1 = self.parse_datum()

            expression = self.parse_expression()

            datum2 = self.parse_datum() if expression else ''

            if self.current != ')':
                raise ParseError(f"Missing ')' at position {self.position}.")

            self.advance()
            return [ datum1, expression, datum2 ]

        else:
            return None

And the test cases:

tests = {
    'good':[line.strip() for line in """
            (hello(one(two(three)a)b)c)
            (()abc)
            ((()))
            """.strip().splitlines()],
    'bad':[line.strip() for line in """
            )(
            abc
            ((abc)
            ((abc)(
            ((abc)(abc))
            """.strip().splitlines()]
}

p = Parser(verbose=True)

for kind, testset in tests.items():
    print(f"{kind} tests")

    for n,test in enumerate(testset):
        print(f"\n    Test {n}: {test}\n")
        try:
            tree = p.parse(test)
            print(f"        {tree}\n")

        except ParseError as e:
            print(f"        {e.message}")

Output:

good tests

    Test 0: (hello(one(two(three)a)b)c)

        ['hello', ['one', ['two', ['three', None, ''], 'a'], 'b'], 'c']


    Test 1: (()abc)

        ['', ['', None, ''], 'abc']


    Test 2: ((()))

        ['', ['', ['', None, ''], ''], '']

bad tests

    Test 0: )(

        ParseError: Missing '(' at position 0.

    Test 1: abc

        ParseError: Missing '(' at position 0.

    Test 2: ((abc)

        ParseError: Missing ')' at position 6.

    Test 3: ((abc)(

        ParseError: Missing ')' at position 6.

    Test 4: ((abc)(abc))

        ParseError: Missing ')' at position 6.

Answer 3

_{Assuming you used python-3.x.}

---

Parser.peek

This method can be simplified:

def peek(self):
    if self.position + 1 == len(self.expression):
        return "EOF"
    return self.expression[self.position + 1]

The else is necessary, since the method will finish if the condition is satisfied.

---

Parser.advance

This method can be improved, with the same reasons defined above:

def advance(self):
    self.pretty_print_stack()
    if (self.position + 1) >= len(self.expression):
        return self.tokens
    self.position += 1

---

Parser.parse_rparen

This function can be improved:

def parse_rparen(self):
    self.pretty_print_stack()
    if self.current() == ")":
        self.paren_state -= 1
        if self.paren_state < 0:
            raise Exception(f"Imbalanced parentheses")
        self.advance()
    else:
        raise Exception(f"Expected right parentheses at position {self.position}")

Raising an Exception will stop the program (if you don't catch it), so an else here is unnecessary.

---

Parser.is_paren

This function can be simplified:

def is_paren(self):
    return self.current() in "()"

This is the same as you had before, but more pythonic.

---

Parser.pretty_print_stack

This function can be simplified:

def pretty_print_stack(self):
    if self.verbose:
        pretty_printed = "".join([
            f">{char}<" if idx == self.position else char for idx, char in enumerate(self.expression)
        ])
        current_frame = inspect.currentframe()
        caller_frame = inspect.getouterframes(current_frame, 2)
        print(f"{pretty_printed:<20} Position {self.position}, in {caller_frame[1][3]}, paren_state: {self.paren_state} peek: {self.peek()}")

Utilizing .join() and generator expressions, you can reduce the amount of clutter code in this function.

---

Other Suggestions

• Documentation Strings
• Type Hints
• Method Naming