Eliminating left recursion from function call parsing

199 views Asked by At

First of all, I know there are a lot of answers and resources already available regarding this topic. However, I'm having a really hard time understanding the grammar notation that is often used in these answers. So I was hoping someone could explain it in a more intuitive way.

I'm trying to write a simple recursive descent parser for some kind of C-type language. However, I am running into some issues when implementing a function call.

I am trying to support the following syntax:

a(b)
a(b, c)
a(b, c)()
a(b, c)(d)

Like I said, I have a hard time understanding the grammar notation often used, so I will show my implementation:

const functionCall = new Expression((parser) => {
    parser.expect(expression)
    parser.expect('(')
    if (parser.optional(expression)) {
        while (true) {
            if (parser.optional(',')) {
                parser.expect(expression)
            } else {
                break
            }
        }
    }
    parser.expect(')')    
})

const expression = new Expression((parser) => {
    parser.either([functionCall, literal])
})

const literal = new Expression((parser) => {
    parser.either([{name: 'string_literal'}, {name: 'number_literal'}, {name: 'identifier'}])
})

As I understand my grammar is (indirectly?) left recursive because the first thing that can be matched in a function call, can be a function call. If this assumption is right, I wouldn't know how to eliminate this recursion.

0

There are 0 answers