7
$\begingroup$

Below, we have an example of two extremely simple languages and a relationship between the two languages:

Input
language
(-1, 0) (0, 1) (1, 0) (0, 1) (0, -1) (1, 0) (1, 0)
Output
language
"left" "up" "right" "up" "down" "right" "right"

In college, I was taught how to write code which would convert one simple language into another simple language using nested while-loops, if-else blocks, break statements, continue statements, and a lot of checks on boolean variables whose names were things like is_done or is_nested.

I find that the nested loop style of parser is difficult to read and understand and the parser is difficult to modify or edit in any useful way.

Suppose that someone wanted to learn how to understand how a well-organized parser works. Suppose that they don't want to only use a parser library, but understand its inner workings.

Pick an example of one specific type of well-organized parser. What is the simplest explanation, in plain English and/or diagrams, you can give for one specific type of well-organized parser you have seen before?

$\endgroup$
2
  • $\begingroup$ If you really want to understand these things, you may want to consider reading a good book on the subject. For instance the Dragon Book (en.wikipedia.org/wiki/…) $\endgroup$ Oct 23, 2023 at 6:03
  • $\begingroup$ You need to take into account properties of the language you want to recognise and the mechanism to recognise it. One crucial property is look ahead: how many tokens do you need to know before knowing which grammar production you are about to enter. As suggested above, this requires some formal understanding of languages and automata recognising them - as this will dictate the implementation. $\endgroup$ Oct 23, 2023 at 8:52

1 Answer 1

10
$\begingroup$

The most straightforward kind of parser to hand-build is a recursive-descent parser. The basic premise is that you have a group of cooperating mutually-recursive functions (or methods), each of which handles one "kind" of thing (formally: a production) and delegates sub-components to other functions.

Often the parser is preceded by a "lexer" or tokenising phase, that turns the input source code into labelled "tokens" of different kinds. For your example, these tokens might be "left-paren", "right-paren", "minus", "integer", and "comma". These are often recognised with regular expressions, or just a character-by-character loop that builds up a list of token items. It's also possible to integrate this with the parser, but probably easier not to for the beginner because you can debug the lexer separately.


For this example, we have three basic productions: a pair (<expression>, <expression>), an integer, and a unary prefix negation -<expression>¹. Let's assume we've produced a list of tokens each with a "kind" property corresponding to one of those token types, and possibly with other properties (like a numeric value) suitable to the token, and now we want to parse from it.

Our toy parser might have the following pseudo-Python:

def parse_expression(tokens):
    next = tokens[0]
    if next.kind == 'left-paren':
        return parse_pair(tokens[1:])
    elif next.kind == 'int':
        return parse_int(tokens)
    elif next.kind == 'minus':
        return parse_negate(tokens[1:])
def parse_pair(tokens):
    lhs, rest = parse_expression(tokens)
    expect('comma', rest[0]) # throws error if not found
    rhs, rest = parse_expression(rest[1:])
    expect('right-paren', rest[0])
    return (Pair(lhs, rhs), rest[1:])
def parse_int(tokens):
    return (Integer(tokens[0].value), tokens[1:])
def parse_negate(tokens):
    val, rest = parse_expression(tokens)
    return (Negate(val), rest)

Pair, Integer, and Negate would be constructors for data structures (abstract syntax tree nodes), and I've set it up to illustrate nodes with zero, one, and two child nodes. They just on to a value (Integer), one inner AST node (Negate), or two inner AST nodes (Pair).

Each function here returns one AST node, and a list of the remaining tokens that it didn't consume. You can see parse_pair uses those returned values, expecting a comma right after the left-hand-side expression completes and then asking for the right-hand-side expression.

After tokenising, we would call parse_expression(the_tokens) and it would give us back a pair of the expression at the start of the list, and the remainder of the list that wasn't used. In this case, we'd expect that to be a Pair node, which would have a left- and right-hand-side node inside it. More complex languages could allow multiple statements, nested declarations, etc, and would have further AST nodes to deal with that.


Once you've parsed that, you can do whatever you want with the AST you've produced. You might implement operations on the AST nodes themselves to produce the values they describe, or set up some external tree-walking recursive functions to inspect them from the outside, or any other processing you wanted. The "output language" is unrelated to the parsing, and you could do several different things with the same syntax tree.

¹ This sample parser permits some constructions you may not want, like -(1, 2) and (1, (2, 3)): you could make it prohibit those if you wanted as well by adding further error-detection and -reporting code within one of the production functions.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .