Recursive descent parser for simple arithmetic expressions grammar

Question

What I'd like to see in your review, in order of relevance:

1. Is there any bugs? (I see none, but...)
2. Is the code efficient? (by whatever metric you'd like to use)
3. Is the code easy to understand?

However any feedback is welcomed.

tags.lua

return {
    tokens = {
        num = 1,
        add = 2,
        sub = 3,
        mul = 4,
        div = 5,
        rpa = 6,
        lpa = 7,
        eof = -1
    },
    nodes = {
        num = 1,
        neg = 2,
        add = 3,
        sub = 4,
        mul = 5,
        div = 6
    }
}

tokenizer.lua

local tags = require 'tags'

local function tokenize (s)
    local i = 1
    local tokens = {}
    local sub = string.sub

    local function current ()
        return sub(s, i, i)
    end

    local function is_digit ()
        local c = current() or ' '
        return c >= '0' and c <= '9'
    end

    while i <= #s do
        if current() == '+' then
            tokens[#tokens + 1] = { tag = tags.tokens.add, pos = i }
        elseif current() == '-' then
            tokens[#tokens + 1] = { tag = tags.tokens.sub, pos = i }
        elseif current() == '*' then
            tokens[#tokens + 1] = { tag = tags.tokens.mul, pos = i }
        elseif current() == '/' then
            tokens[#tokens + 1] = { tag = tags.tokens.div, pos = i }
        elseif current() == '(' then
            tokens[#tokens + 1] = { tag = tags.tokens.lpa, pos = i }
        elseif current() == ')' then
            tokens[#tokens + 1] = { tag = tags.tokens.rpa, pos = i }
        elseif is_digit(current()) then
            local j = i

            while is_digit() do
                i = i + 1
            end

            if current() == '.' then
                i = i + 1

                if not is_digit() then
                    error({ message = 'Expected digit after dot', pos = i })
                end

                while is_digit() do
                    i = i + 1
                end
            end

            i = i - 1

            tokens[#tokens + 1] = {
                tag = tags.tokens.num,
                lexeme = string.sub(s, j, i),
                pos = j
            }
        elseif current() ~= ' ' then
            error({ message = 'Symbol not recognized', pos = i })
        end

        i = i + 1
    end

    tokens[#tokens + 1] = { tag = tags.tokens.eof, pos = 1 }

    return tokens
end

return { tokenize = tokenize }

parser.lua

local tags = require 'tags'
local tokenizer = require 'tokenizer'

local tremove = table.remove
local parse_expression_1

local context

local function advance()
    context.i = context.i + 1
end

local function is_at(tag_name)
    return context.tokens[context.i].tag == tags.tokens[tag_name]
end

local function add(node)
    context.ast[#context.ast + 1] = node
end

local function pop()
    return tremove(context.ast, #context.ast)
end

local function current()
    return context.tokens[context.i]
end

local function report_syntax_error(message)
    error({ message = message, pos = current().pos })
end

local function parse_expression_3 ()
    if is_at('num') then
        add({ tag = tags.nodes.num, lexeme = current().lexeme })
        advance()
    elseif is_at('sub') then
        advance()
        parse_expression_3()
        add({ tag = tags.nodes.neg, expr = pop() })
    elseif is_at('lpa') then
        advance()
        parse_expression_1()

        if is_at('rpa') then
            advance()
        else
            report_syntax_error('Expected right parenthese')
        end
    else
        report_syntax_error('Expected number, left parenthese or minus sign')
    end
end

local function parse_expression_2 ()
    parse_expression_3()

    while true do
        local next_tag

        if is_at('mul') then
            next_tag = tags.nodes.mul
        elseif is_at('div') then
            next_tag = tags.nodes.div
        else
            return
        end

        advance()

        parse_expression_3()

        local right = pop()
        local left = pop()

        add({ tag = next_tag, left = left, right = right })
    end
end

function parse_expression_1 ()
    parse_expression_2()

    while true do
        local next_tag

        if is_at('add') then
            next_tag = tags.nodes.add
        elseif is_at('sub') then
            next_tag = tags.nodes.sub
        else
            return
        end

        advance()

        parse_expression_2()

        local right = pop()
        local left = pop()

        add({ tag = next_tag, left = left, right = right })
    end
end

local function parse (raw_code)
    context = { tokens = tokenizer.tokenize(raw_code), i = 1, ast = {} }

    parse_expression_1()

    if not is_at('eof') then
        report_syntax_error('Expected end of input')
    end

    return context.ast[1]
end

return { parse = parse }

---

The following codes are not part of the parser, but you may find them handy in order to test the parser -- and you can review them too if you like.

interpreter.lua

local tags = require 'tags'

local function evaluate (ast)
    if ast.tag == tags.nodes.num then
        return tonumber(ast.lexeme)
    end

    if ast.tag == tags.nodes.neg then
        return -evaluate(ast.expr)
    end

    if ast.tag == tags.nodes.add then
        return evaluate(ast.left) + evaluate(ast.right)
    end

    if ast.tag == tags.nodes.sub then
        return evaluate(ast.left) - evaluate(ast.right)
    end

    if ast.tag == tags.nodes.mul then
        return evaluate(ast.left) * evaluate(ast.right)
    end

    if ast.tag == tags.nodes.div then
        local left = evaluate(ast.left)
        local right = evaluate(ast.right)

        if right == 0 then
            error({ message = 'Cannot divide by 0' })
        end

        return left / right
    end

    error('Internal error: Unexpected ast_tag')
end

return { evaluate = evaluate }

repl.lua

local parser = require 'parser'
local interpreter = require 'interpreter'

local function repl ()
    print('type "exit" to exit')

    while true do
        io.write('> ')

        local s = io.read()

        if s == 'exit' then
            break
        end

        local success, v = pcall(function ()
            return interpreter.evaluate(parser.parse(s))
        end)

        if success then
            print(v)
        else
            print('Error: ' .. v.message)

            if v.pos then
                print(s)
                print(string.rep(' ', v.pos - 1) .. '^')
            end
        end
    end

    print()
    print('Bye ;)')
end

repl()

Answer 1

Style

Your placement of the parameters in a function definition isn't consistent. The typical convention, across languages, is no space between the name and the (. There is no "standard" style for Lua, though, so if you want to put a space before, go ahead! Just do it on all of your functions, and not just most of them.

A useful style is to use "trailing commas" whenever you have lists or tables split across multiple lines. This reduces the churn in line-based diffs (like what git and hg use) and overall can make the code look more regular.

tokens[#tokens + 1] = {
    tag = tags.tokens.num,
    lexeme = string.sub(s, j, i),
    pos = j, -- you can add trailing comma here
}

"left parenthese" isn't correct spelling. Although it may look awkward, the correct word is "left parenthesis". One way to get around this (and also produce a more precise and concise diagnostic) is to just the symbol itself:

report_syntax_error('Expected number, `(` or `-`')

tags

Instead of using numbers for your tags, you can just use strings. == on strings in Lua is exactly as fast (and does essentially the same thing; comparing an integer rather than a float [if you're using Lua 5.1/5.2]) as == on numbers. This will mean your tables are much more interpretable when debugging and it simplifies the overall structure.

The advantage of some kind of "enum" approach is that you can more easily avoid typos (e.g. 'sbu' instead of 'sub') because you have a central place to validate all of the strings you're using, and IDEs will be more able to help you. However, because this is so simple, and bugs here would almost surely be caught in simple tests, I would err on the side of simplicity and deletings tags.lua altogether, just using the string constants as you need them.

One benefit that falls out of this is being able to use punctuation as tags, for example, the self explanatory '(' instead of 'lpu'.

If you want to get value of tags.lua, you might want to, for example, add a metatable to tokens that throws an error if an unknown token is mentioned.

tokenizer

Making an alias local sub = string.sub does help slightly with performance, but it's most likely not worth it. Following the same logic track, you should eliminate current and simply repeat sub(s, i, i) over and over. But actually, computing . and entering functions is not where your code is spending most if its time, so it's not really worth optimizing.

This is especially true when there are other options that will save more time and clean up your code: For example, you don't need to call current() so many times. Instead of having that function, you could instead make a local variable:

local current = s:sub(i, i)
if current == '+' then

By the way, since current() always returned a string, current() or ' ' is redundant; the ' ' branch will never be used.

Instead of using while loops for lexing numbers, you could use Lua's built in pattern matching. This will likely run faster, and is a lot less code.

local _, integer_stop = s:find("[0-9]+", i)
local number_stop = integer_stop
if s:sub(integer_stop + 1, integer_stop + 1) == "." then
    local _, fraction_stop = s:find("[0-9]+", integer_stop + 2)
    if not fraction_stop then
        error({ message = 'Expected digit after dot', pos = integer_stop + 2 })
    end
    number_stop = fraction_stop
end

tokens[#tokens + 1] = {
    pos = i,
    lexeme = s:sub(i, number_stop),
}
i = number_stop - 1

parser

The same comment for localizing string.sub goes for table.remove; you shouldn't write code in a different way just to save a few cycles until everything else is perfect.

Your pop function is unnecessary; table.remove removes the last element from a list if you don't specify an argument. However, I find it inconsistent that you use t[#t + 1] = to insert, but use table.remove to remove. I would be consistent with my idioms, and use t[#t] = nil to pop values off of a stack.

By the way, the typical name for what you call add is push. "add" is an extra unfortunate name, since it's also the name of one of your tokens.

Using a global variable context is an unnecessary source of complexity and ugliness, especially because the things that operate on it are so simple.

I would either

• eliminate add, pop, is_at, and current, inlining them into all of their uses
• or make context an argument to each of add, pop, is_at, and current.

You're not actually using your context.ast stack though! Notice that you pop everything off at the end of every function. Instead of going through the stack, you should make your parse_ functions return the AST that they have just parsed. For example, here's what parse_expression_2 might look like (simplifying to only include '*' and not '/'):

local function parse_expression_2 ()
    local ast = parse_expression_3()

    while true do
        if is_at('*') then
            advance()
        else
            return ast
        end
        local right = parse_expression_3()
        ast = {tag = '*', left = ast, right = right}
    end
end

You could do a similar thing for the tokens (notice that is_at is always paired with an advance() immediately after!) where they return true if it starts, and automatically advances, and otherwise returns false. I would rename them to something like try_consume in that case, to make it clearer what they do.

Instead of an 'eof' token, you could just use size of the token list; unlike, say, C, we know where the ends of our arrays are.

interpreter

The most obvious change to me is to use elseif to compress the many cases. While you could always use that style when a branch returns, it especially makes sense here since you are handling different cases of the same variable. Also, apply the suggestion to use raw strings rather than tokens, and you get something much cleaner:

local function evaluate (ast)
    if ast.tag == 'num' then
        return tonumber(ast.lexeme)
    elseif ast.tag == 'u-' then
        return -evaluate(ast.expr)
    elseif ast.tag == '+' then
        return evaluate(ast.left) + evaluate(ast.right)
    end

repl

Your use of error pcall makes your code fairly simple, but it's also not a great design for large-scale projects. The best way to use error in Lua is to mark programmer errors; ie, if your code throws an error, you have a mistake in your code.

To mark bad input (like you're currently using error for), it should return an error message. The Lua standard library typically does this by returning nil and then the message:

return nil, "Cannot divide by 0"

However, doing this does make your code more complicated, since you have to check error values at every call. On the other hand, if you make a mistake in your program, your pcall is going to try to read that and show it to the user like they put in bad input. (It will actually fail in a confusing way with 'Error: ' .. v.message failing because v.message will be nil).

Not throwing errors makes your code easier to embed in other code. If every caller of your library is supposed to surround every function call with a pcall, you've not designed a very good interface!

On the other hand, if you can be certain that your code doesn't have any unexpected errors (or you catch and rethrow them, for example, by inspecting the type(v) when pcall returns unsuccessfully), you could keep the same internal structure, and just add a pcall to return the error out of each exported function (just evaluate, parse).