{"id":70,"date":"2015-06-12T23:41:45","date_gmt":"2015-06-13T04:41:45","guid":{"rendered":"http:\/\/www.playwithlua.com\/?p=70"},"modified":"2015-06-12T23:41:45","modified_gmt":"2015-06-13T04:41:45","slug":"making-a-toy-programming-language-in-lua-part-3","status":"publish","type":"post","link":"http:\/\/www.playwithlua.com\/?p=70","title":{"rendered":"Making a toy programming language in Lua, part 3"},"content":{"rendered":"

This is part three of my series on writing a toy programming language using LPeg<\/a>. You should start with part one here<\/a>.<\/p>\n

Last time, we added variables and arrays to the language. Assigning to arrays was starting to strain our design some, so this time we’ll refactor it a lot, and add two features that would be impossible without that refactoring: conditional statements and loops.<\/p>\n

<\/p>\n

Abstract syntax trees<\/h2>\n

Right now, our parser evaluates expressions as soon as it can, while it’s still in the process of parsing them. This was fine while we were just parsing mathematical expressions, and it’s even fine when we start to include variables (as long as assignment statements can’t appear inside expressions), but conditionals and loops break that: we need to parse<\/em> the entire “if” statement, but we only want the body to happen<\/em> after we evaluate the condition. With our current parser, we would evaluate the body (and cause the side-effects of any assignment statements it contains) as soon as we parse it, so those statements would run whether the condition was true or false.<\/p>\n

In order to fix this, we first need to do a major overhaul of our language. I’m going to part with The Unix Programming Environment<\/em> a little here: they jumped right to compilation and code generation, whereas I’m going to do that, but not immediately: it’s more common to do what I’m going to do, and build an abstract syntax tree<\/em> first.<\/p>\n

So, the first thing we need to do is decide how to represent an AST. Let’s have each node be a table with index 1 being the type of node, and the rest being the captures. So, the AST for “2+3” would be:<\/p>\n\n

{<\/span> "expr"<\/span>,<\/span>\n  {<\/span> "term"<\/span>,<\/span> 2<\/span> }<\/span>,<\/span>\n  "+"<\/span>,<\/span>\n  {<\/span> "term"<\/span>,<\/span> 3<\/span> }<\/span>\n}<\/span><\/pre><\/div><\/div><\/div>\n\n
We can construct this easily enough. Actually much more easily than if we were using Yacc. We’ll use two more LPeg functions, Cc<\/code> and Ct<\/code>. Ct<\/code> is a table capture,<\/em> which wraps up all the captures for a pattern into a table, and Cc<\/code> is a constant capture,<\/em> which consumes none of the input but captures its argument. By taking a nonterminal like EXPR, which looks like this:<\/p>\n\n
EXPR =<\/span> V(<\/span>"TERM"<\/span>)<\/span> *<\/span> (<\/span> expr_op *<\/span> V(<\/span>"TERM"<\/span>)<\/span> )<\/span>^<\/span>0<\/span> \/<\/span> eval,<\/span><\/pre><\/div><\/div><\/div>\n\n
…Removing the function captures (because we don’t want to evaluate it yet), wrapping it up in Ct<\/code>, and prefacing it with Cc<\/code> to tag it:<\/p>\n\n
EXPR =<\/span> Ct(<\/span> Cc(<\/span>"expr"<\/span>)<\/span> *<\/span> V(<\/span>"TERM"<\/span>)<\/span> *<\/span> (<\/span> expr_op *<\/span> V(<\/span>"TERM"<\/span>)<\/span> )<\/span>^<\/span>0<\/span> )<\/span>,<\/span><\/pre><\/div><\/div><\/div>\n\n
…we can make our parser generate an AST. The way LPeg can build this directly into the grammar is really quite neat, I think.<\/p>\n
When we do this to the entire grammar, here’s what we’re left with:<\/p>\n\n
stmt =<\/span> spc *<\/span> P{<\/span>\n    "STMT"<\/span>;<\/span>\n    STMT =<\/span> \n        Ct(<\/span> Cc(<\/span>"assign"<\/span>)<\/span> *<\/span> V(<\/span>"REF"<\/span>)<\/span> *<\/span> "="<\/span> *<\/span> spc *<\/span> V(<\/span>"VAL"<\/span>)<\/span> )<\/span> +<\/span>\n        V(<\/span>"EXPR"<\/span>)<\/span>,<\/span>\n    EXPR =<\/span> Ct(<\/span> Cc(<\/span>"expr"<\/span>)<\/span> *<\/span> V(<\/span>"TERM"<\/span>)<\/span> *<\/span> (<\/span> expr_op *<\/span> V(<\/span>"TERM"<\/span>)<\/span> )<\/span>^<\/span>0<\/span> )<\/span>,<\/span>\n    TERM =<\/span> Ct(<\/span> Cc(<\/span>"term"<\/span>)<\/span> *<\/span> V(<\/span>"FACT"<\/span>)<\/span> *<\/span> (<\/span> term_op *<\/span> V(<\/span>"FACT"<\/span>)<\/span> )<\/span>^<\/span>0<\/span> )<\/span>,<\/span>\n    REF =<\/span> Ct(<\/span> Cc(<\/span>"ref"<\/span>)<\/span> *<\/span> name *<\/span> (<\/span>lbrack *<\/span> V(<\/span>"EXPR"<\/span>)<\/span> *<\/span> rbrack)<\/span>^<\/span>0<\/span> )<\/span>,<\/span>\n    FACT =<\/span>\n        number +<\/span>\n        lparen *<\/span> V(<\/span>"EXPR"<\/span>)<\/span> *<\/span> rparen +<\/span>\n        V(<\/span>"REF"<\/span>)<\/span>,<\/span>\n    ARRAY =<\/span> Ct(<\/span> Cc(<\/span>"array"<\/span>)<\/span> *<\/span> lbrack *<\/span> Ct(<\/span> V(<\/span>"VAL_LIST"<\/span>)<\/span>^-<\/span>1<\/span> )<\/span> *<\/span> rbrack )<\/span>,<\/span>\n    VAL_LIST =<\/span> V(<\/span>"VAL"<\/span>)<\/span> *<\/span> (<\/span>comma *<\/span> V(<\/span>"VAL"<\/span>)<\/span>)<\/span>^<\/span>0<\/span>,<\/span>\n    VAL =<\/span> V(<\/span>"EXPR"<\/span>)<\/span> +<\/span> V(<\/span>"ARRAY"<\/span>)<\/span>\n}<\/span><\/pre><\/div><\/div><\/div>\n\n
As you can see, we’ve only changed a few of them, because some things are simple enough not to need their own nodes: numbers and REFs don’t really need to be wrapped in FACT nodes, because a FACT will always just evaluate to its only child, for example. Same with STMT, we only really care if it’s an assignment or an EXPR, because a STMT that contains an EXPR just evaluates that EXPR.<\/p>\n
So, now, trying to match “2+3” yields the exact tree that we’d expect:<\/p>\n\n
-- stmt:match("2+3") gives:<\/span>\n \n{<\/span> "expr"<\/span>,<\/span>\n  {<\/span> "term"<\/span>,<\/span> 2<\/span> }<\/span>,<\/span>\n  "+"<\/span>,<\/span>\n  {<\/span> "term"<\/span>,<\/span> 3<\/span> }<\/span>\n}<\/span><\/pre><\/div><\/div><\/div>\n\n
Evaluating an AST<\/h2>\n
Obviously we’ll need to change the eval<\/code> function to handle these. In fact, let’s split it up into several functions. TERMs and EXPRs can share a function that’s a lot like the current eval<\/code>:<\/p>\n\n
function<\/span> eval_expr(<\/span>expr)<\/span>\n    local<\/span> accum =<\/span> eval(<\/span>expr[<\/span>2<\/span>]<\/span>)<\/span> -- because 1 is "expr"<\/span>\n    for<\/span> i =<\/span> 3<\/span>,<\/span> #<\/span>expr,<\/span> 2<\/span> do<\/span>\n        local<\/span> operator =<\/span> expr[<\/span>i]<\/span>\n        local<\/span> num2 =<\/span> eval(<\/span>expr[<\/span>i+<\/span>1<\/span>]<\/span>)<\/span>\n \n        if<\/span> operator ==<\/span> '+'<\/span> then<\/span>\n            accum =<\/span> accum +<\/span> num2\n        elseif<\/span> operator ==<\/span> '-'<\/span> then<\/span>\n            accum =<\/span> accum -<\/span> num2\n        elseif<\/span> operator ==<\/span> '*'<\/span> then<\/span>\n            accum =<\/span> accum *<\/span> num2\n        elseif<\/span> operator ==<\/span> '\/'<\/span> then<\/span>\n            accum =<\/span> accum \/<\/span> num2\n        end<\/span>\n    end<\/span>\n    return<\/span> accum\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
We’re still doing the same basic thing, with the loop and accumulator. The main differences are that we start at index 2 (because index 1 is the name of the node, either “expr” or “term”), and that all the subvalues, num1<\/code> and num2<\/code>, get sent to eval<\/code> before being used. This recursion lets us handle EXPRs that have nested EXPRs or TERMs in them.<\/p>\n
The eval<\/code> function itself becomes fairly simple as well. There aren’t many things we can possibly send it:<\/p>\n\n
function<\/span> eval(<\/span>ast)<\/span>\n    if<\/span> type<\/span>(<\/span>ast)<\/span> ==<\/span> 'number'<\/span> then<\/span>\n        return<\/span> ast\n    elseif<\/span> ast[<\/span>1<\/span>]<\/span> ==<\/span> 'expr'<\/span> or<\/span> ast[<\/span>1<\/span>]<\/span> ==<\/span> 'term'<\/span> then<\/span>\n        return<\/span> eval_expr(<\/span>ast)<\/span>\n    elseif<\/span> ast[<\/span>1<\/span>]<\/span> ==<\/span> 'array'<\/span> then<\/span>\n        local<\/span> new =<\/span> {<\/span>}<\/span>\n        for<\/span> _,<\/span> el in<\/span> ipairs<\/span>(<\/span>ast[<\/span>2<\/span>]<\/span>)<\/span> do<\/span>\n            table.insert<\/span>(<\/span>new,<\/span> eval(<\/span>el)<\/span>)<\/span>\n        end<\/span>\n        return<\/span> new\n    elseif<\/span> ast[<\/span>1<\/span>]<\/span> ==<\/span> 'ref'<\/span> then<\/span>\n        return<\/span> lookup(<\/span>ast)<\/span>\n    elseif<\/span> ast[<\/span>1<\/span>]<\/span> ==<\/span> 'assign'<\/span> then<\/span>\n        return<\/span> assign(<\/span>ast[<\/span>2<\/span>]<\/span>,<\/span> eval(<\/span>ast[<\/span>3<\/span>]<\/span>)<\/span>)<\/span>\n    end<\/span>\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
Numbers are returned untouched, expressions and terms get sent to eval_expr<\/code>, and arrays are recursively evaluated and returned in a table. References and assignments are a little more complicated.<\/p>\n
Variables in an AST<\/h2>\n
To evaluate a REF, we need to follow a chain of indices: the first element in the chain is a variable name, but the variable could be an array, in which case there will be more elements, until finally you reach a number. So, the lookup<\/code> function to do this, which has a lot in common with makeref<\/code> from last time:<\/p>\n\n
function<\/span> lookup(<\/span>ref)<\/span>\n    local<\/span> current =<\/span> VARS\n    for<\/span> i =<\/span> 2<\/span>,<\/span> #<\/span>ref do<\/span>\n        local<\/span> next_index =<\/span> ref[<\/span>i]<\/span>\n        if<\/span> type<\/span>(<\/span>next_index)<\/span> ==<\/span> 'table'<\/span> then<\/span>\n            next_index =<\/span> eval(<\/span>next_index)<\/span>\n        end<\/span>\n \n        current =<\/span> current[<\/span>next_index]<\/span>\n    end<\/span>\n    return<\/span> current\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
At each step, the next index can be a variable name, a number, or an expression that evaluates to a number. So, if it’s a table, it must be an expression, and we eval<\/code> it.<\/p>\n
An assignment is pretty much the same: we take a ref and a value, follow down to one before the end of the chain of indices, and then set the value:<\/p>\n\n
function<\/span> assign(<\/span>ref,<\/span> value)<\/span>\n    local<\/span> current =<\/span> VARS\n    for<\/span> i =<\/span> 2<\/span>,<\/span> #<\/span>ref do<\/span>\n        local<\/span> next_index =<\/span> ref[<\/span>i]<\/span>\n        if<\/span> type<\/span>(<\/span>next_index)<\/span> ==<\/span> 'table'<\/span> then<\/span>\n            next_index =<\/span> eval(<\/span>next_index)<\/span>\n        end<\/span>\n \n        if<\/span> i ==<\/span> #<\/span>ref then<\/span> -- last one, set the value<\/span>\n            current[<\/span>next_index]<\/span> =<\/span> value\n            return<\/span> value\n        else<\/span> -- not the last, keep following the chain<\/span>\n            current =<\/span> current[<\/span>next_index]<\/span>\n        end<\/span>\n    end<\/span>\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
So, with these changes, and one minor tweak in our test<\/code> function (add stmt = stmt \/ eval<\/code> to the top of it), all our tests will pass again. Now we’re ready to start adding functionality to use the AST.<\/p>\n
Conditionals<\/h2>\n
First, let’s modify the parser to handle conditionals. We’ll need to add three new concepts: a statement list (that will go inside the conditional), a boolean expression (that will be the predicate of the conditional), and the conditional itself. Booleans seem easy enough to start with. Match the possible operators:<\/p>\n\n
boolean =<\/span> C(<\/span> S(<\/span>"<>"<\/span>)<\/span> +<\/span> "<="<\/span> +<\/span> ">="<\/span> +<\/span> "!="<\/span> +<\/span> "=="<\/span> )<\/span> *<\/span> spc<\/pre><\/div><\/div><\/div>\n\n
Then add another nonterminal to the parser:<\/p>\n\n
BOOL =<\/span> Ct(<\/span> Cc(<\/span>"bool"<\/span>)<\/span> *<\/span> V(<\/span>"EXPR"<\/span>)<\/span> *<\/span> boolean *<\/span> V(<\/span>"EXPR"<\/span>)<\/span> )<\/span><\/pre><\/div><\/div><\/div>\n\n
Statement lists are easy enough, and they’ll become our new starting nonterminal, replacing STMT:<\/p>\n\n
LIST =<\/span>\n    V(<\/span>"STMT"<\/span>)<\/span> +<\/span>\n    Ct(<\/span> Cc(<\/span>"list"<\/span>)<\/span> *<\/span>\n            lcurly *<\/span>\n            V(<\/span>"STMT"<\/span>)<\/span> *<\/span> (<\/span> ";"<\/span> *<\/span> spc *<\/span> V(<\/span>"STMT"<\/span>)<\/span> )<\/span>^<\/span>0<\/span> *<\/span>\n            rcurly )<\/span>,<\/span><\/pre><\/div><\/div><\/div>\n\n
So a LIST is either a single STMT, or a series of them inside braces and separated by semicolons (lcurly<\/code> and rcurly<\/code> match left and right curly braces). Finally, here’s how we’ll define a conditional:<\/p>\n\n
IF =<\/span> Ct(<\/span> C(<\/span>"if"<\/span>)<\/span> *<\/span> spc *<\/span> lparen *<\/span> V(<\/span>"BOOL"<\/span>)<\/span> *<\/span> rparen *<\/span> V(<\/span>"LIST"<\/span>)<\/span> )<\/span><\/pre><\/div><\/div><\/div>\n\n
All together, here’s our parser now:<\/p>\n\n
stmt =<\/span> spc *<\/span> P{<\/span>\n    "LIST"<\/span>;<\/span>\n    LIST =<\/span>\n        V(<\/span>"STMT"<\/span>)<\/span> +<\/span>\n        Ct(<\/span> Cc(<\/span>"list"<\/span>)<\/span> *<\/span>\n                lcurly *<\/span>\n                V(<\/span>"STMT"<\/span>)<\/span> *<\/span> (<\/span> ";"<\/span> *<\/span> spc *<\/span> V(<\/span>"STMT"<\/span>)<\/span> )<\/span>^<\/span>0<\/span> *<\/span>\n                rcurly )<\/span>,<\/span>\n    STMT =<\/span> \n        Ct(<\/span> Cc(<\/span>"assign"<\/span>)<\/span> *<\/span> V(<\/span>"REF"<\/span>)<\/span> *<\/span> "="<\/span> *<\/span> spc *<\/span> V(<\/span>"VAL"<\/span>)<\/span> )<\/span> +<\/span>\n        V(<\/span>"EXPR"<\/span>)<\/span> +<\/span>\n        V(<\/span>"IF"<\/span>)<\/span>,<\/span>\n    EXPR =<\/span> Ct(<\/span> Cc(<\/span>"expr"<\/span>)<\/span> *<\/span> V(<\/span>"TERM"<\/span>)<\/span> *<\/span> (<\/span> expr_op *<\/span> V(<\/span>"TERM"<\/span>)<\/span> )<\/span>^<\/span>0<\/span> )<\/span>,<\/span>\n    TERM =<\/span> Ct(<\/span> Cc(<\/span>"term"<\/span>)<\/span> *<\/span> V(<\/span>"FACT"<\/span>)<\/span> *<\/span> (<\/span> term_op *<\/span> V(<\/span>"FACT"<\/span>)<\/span> )<\/span>^<\/span>0<\/span> )<\/span>,<\/span>\n    REF =<\/span> Ct(<\/span> Cc(<\/span>"ref"<\/span>)<\/span> *<\/span> name *<\/span> (<\/span>lbrack *<\/span> V(<\/span>"EXPR"<\/span>)<\/span> *<\/span> rbrack)<\/span>^<\/span>0<\/span> )<\/span>,<\/span>\n    FACT =<\/span>\n        number +<\/span>\n        lparen *<\/span> V(<\/span>"EXPR"<\/span>)<\/span> *<\/span> rparen +<\/span>\n        V(<\/span>"REF"<\/span>)<\/span>,<\/span>\n    ARRAY =<\/span> Ct(<\/span> Cc(<\/span>"array"<\/span>)<\/span> *<\/span> lbrack *<\/span> Ct(<\/span> V(<\/span>"VAL_LIST"<\/span>)<\/span>^-<\/span>1<\/span> )<\/span> *<\/span> rbrack )<\/span>,<\/span>\n    VAL_LIST =<\/span> V(<\/span>"VAL"<\/span>)<\/span> *<\/span> (<\/span>comma *<\/span> V(<\/span>"VAL"<\/span>)<\/span>)<\/span>^<\/span>0<\/span>,<\/span>\n    VAL =<\/span> V(<\/span>"EXPR"<\/span>)<\/span> +<\/span> V(<\/span>"ARRAY"<\/span>)<\/span>,<\/span>\n    BOOL =<\/span> Ct(<\/span> Cc(<\/span>"bool"<\/span>)<\/span> *<\/span> V(<\/span>"EXPR"<\/span>)<\/span> *<\/span> boolean *<\/span> V(<\/span>"EXPR"<\/span>)<\/span> )<\/span>,<\/span>\n    IF =<\/span> Ct(<\/span> C(<\/span>"if"<\/span>)<\/span> *<\/span> spc *<\/span> lparen *<\/span> V(<\/span>"BOOL"<\/span>)<\/span> *<\/span> rparen *<\/span> V(<\/span>"LIST"<\/span>)<\/span> )<\/span>\n}<\/span><\/pre><\/div><\/div><\/div>\n\n
There’s one final tweak to make. An “if” statement will actually be parsed as a name, and eval<\/code> will try to look up the variable called “if.” We need to tell the name<\/code> pattern to not recognize “if” as a name; this is the first keyword<\/em> in our language (there will be more):<\/p>\n\n
name =<\/span> C(<\/span> letter *<\/span> (<\/span>digit+<\/span>letter+<\/span>"_"<\/span>)<\/span>^<\/span>0<\/span> )<\/span> *<\/span> spc\nkeywords =<\/span> P(<\/span>"if"<\/span>)<\/span> *<\/span> spc\nname =<\/span> name -<\/span> keywords<\/pre><\/div><\/div><\/div>\n\n
Parsing an example “if” statement like “if(a > 0) { 2+3; a=4*5 }” now gives this parse tree:<\/p>\n\n
{<\/span> "if"<\/span>,<\/span>\n  {<\/span> "bool"<\/span>,<\/span>\n    {<\/span> "expr"<\/span>,<\/span>\n      {<\/span> "term"<\/span>,<\/span> {<\/span> "ref"<\/span>,<\/span> "a"<\/span> }<\/span> }<\/span> }<\/span>,<\/span>\n      ">"<\/span>,<\/span>\n      {<\/span> "expr"<\/span>,<\/span> {<\/span> "term"<\/span>,<\/span> 0<\/span> }<\/span> }<\/span>\n    }<\/span>,<\/span>\n  {<\/span> "list"<\/span>,<\/span>\n    {<\/span> "expr"<\/span>,<\/span>\n      {<\/span> "term"<\/span>,<\/span> 2<\/span> }<\/span>,<\/span> "+"<\/span>,<\/span> {<\/span> "term"<\/span>,<\/span> 3<\/span> }<\/span>\n    }<\/span>,<\/span>\n    {<\/span> "assign"<\/span>,<\/span>\n      {<\/span> "ref"<\/span>,<\/span> "a"<\/span> }<\/span>,<\/span>\n      {<\/span> "expr"<\/span>,<\/span>\n        {<\/span> "term"<\/span>,<\/span> 4<\/span>,<\/span> "*"<\/span>,<\/span> 5<\/span> }<\/span>\n      }<\/span>\n    }<\/span>\n  }<\/span>\n}<\/span><\/pre><\/div><\/div><\/div>\n\n
Evaluating conditionals<\/h2>\n
This is all obviously going to mean some changes to the eval<\/code> function. We’ll have to add a function like eval_expr<\/code> to handle boolean expressions, and two new options in eval<\/code> to handle statement lists and “if” statements. Here’s how we do booleans:<\/p>\n\n
function<\/span> eval_bool(<\/span>expr)<\/span>\n    local<\/span> num1 =<\/span> eval(<\/span>expr[<\/span>2<\/span>]<\/span>)<\/span>\n    local<\/span> operator =<\/span> expr[<\/span>3<\/span>]<\/span>\n    local<\/span> num2 =<\/span> eval(<\/span>expr[<\/span>4<\/span>]<\/span>)<\/span>\n \n    if<\/span> operator ==<\/span> '<'<\/span> then<\/span>\n        return<\/span> num1 <<\/span> num2\n    elseif<\/span> operator ==<\/span> '<='<\/span> then<\/span>\n        return<\/span> num1 <=<\/span> num2\n    elseif<\/span> operator ==<\/span> '>'<\/span> then<\/span>\n        return<\/span> num1 ><\/span> num2\n    elseif<\/span> operator ==<\/span> '>='<\/span> then<\/span>\n        return<\/span> num1 >=<\/span> num2\n    elseif<\/span> operator ==<\/span> '=='<\/span> then<\/span>\n        return<\/span> num1 ==<\/span> num2\n    elseif<\/span> operator ==<\/span> '!='<\/span> then<\/span>\n        return<\/span> num1 ~=<\/span> num2\n    end<\/span>\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
This is a lot simpler than eval_expr<\/code> because we know exactly how many arguments there will be: we can’t chain together booleans like we can EXPRs and TERMs.<\/p>\n
The two new paths through eval<\/code> differ from the rest in one way: they’re not guaranteed to return anything. Statement lists and conditionals can’t be nested inside of other value-returning constructs (like EXPRs) so we won’t ever have to return a value from those to eval<\/code> itself. Here’s the new eval<\/code>:<\/p>\n\n
function<\/span> eval(<\/span>ast)<\/span>\n    if<\/span> type<\/span>(<\/span>ast)<\/span> ==<\/span> 'number'<\/span> then<\/span>\n        return<\/span> ast\n    elseif<\/span> ast[<\/span>1<\/span>]<\/span> ==<\/span> 'expr'<\/span> or<\/span> ast[<\/span>1<\/span>]<\/span> ==<\/span> 'term'<\/span> then<\/span>\n        return<\/span> eval_expr(<\/span>ast)<\/span>\n    elseif<\/span> ast[<\/span>1<\/span>]<\/span> ==<\/span> 'array'<\/span> then<\/span>\n        local<\/span> new =<\/span> {<\/span>}<\/span>\n        for<\/span> _,<\/span> el in<\/span> ipairs<\/span>(<\/span>ast[<\/span>2<\/span>]<\/span>)<\/span> do<\/span>\n            table.insert<\/span>(<\/span>new,<\/span> eval(<\/span>el)<\/span>)<\/span>\n        end<\/span>\n        return<\/span> new\n    elseif<\/span> ast[<\/span>1<\/span>]<\/span> ==<\/span> 'ref'<\/span> then<\/span>\n        return<\/span> lookup(<\/span>ast)<\/span>\n    elseif<\/span> ast[<\/span>1<\/span>]<\/span> ==<\/span> 'assign'<\/span> then<\/span>\n        return<\/span> assign(<\/span>ast[<\/span>2<\/span>]<\/span>,<\/span> eval(<\/span>ast[<\/span>3<\/span>]<\/span>)<\/span>)<\/span>\n    elseif<\/span> ast[<\/span>1<\/span>]<\/span> ==<\/span> 'list'<\/span> then<\/span>\n        for<\/span> i =<\/span> 2<\/span>,<\/span> #<\/span>ast do<\/span>\n            eval(<\/span>ast[<\/span>i]<\/span>)<\/span>\n        end<\/span>\n    elseif<\/span> ast[<\/span>1<\/span>]<\/span> ==<\/span> 'if'<\/span> then<\/span>\n        if<\/span> eval_bool(<\/span>ast[<\/span>2<\/span>]<\/span>)<\/span> then<\/span>\n            return<\/span> eval(<\/span>ast[<\/span>3<\/span>]<\/span>)<\/span>\n        end<\/span>\n    end<\/span>\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
Evaluating a list just means evaluating everything in it, and evaluating an “if” means eval_bool<\/code>-ing the condition, then evaluating the body only if it’s true<\/em>. This means we can now stick this in the bottom of test<\/code> and it will pass:<\/p>\n\n
stmt:<\/span>match(<\/span>"if(1 < 0) b = 5"<\/span>)<\/span>;<\/span> assert<\/span>(<\/span>VARS.<\/span>b ~=<\/span> 5<\/span>)<\/span><\/pre><\/div><\/div><\/div>\n\n
Because 1 is not less than 0, the part of the AST that does the assignment is never run, and nothing gets assigned to “b”.<\/p>\n
Loops<\/h2>\n
We can implement loops almost the same way. First we modify the parser to parse loops, which is already mostly done, since it’s the same general thing as conditionals:<\/p>\n\n
WHILE =<\/span> Ct(<\/span> C(<\/span>"while"<\/span>)<\/span> *<\/span> spc *<\/span> lparen *<\/span> V(<\/span>"BOOL"<\/span>)<\/span> *<\/span> rparen *<\/span> V(<\/span>"LIST"<\/span>)<\/span> )<\/span><\/pre><\/div><\/div><\/div>\n\n
Add “while” to the list of keywords:<\/p>\n\n
keywords =<\/span> (<\/span>P(<\/span>"if"<\/span>)<\/span>+<\/span>P(<\/span>"while"<\/span>)<\/span>)<\/span> *<\/span> spc<\/pre><\/div><\/div><\/div>\n\n
And we should be able to parse loops:<\/p>\n
\r\nwhile(n<10) {\r\n  n = n+1\r\n}\r\n<\/pre>\n
turns into<\/p>\n\n
{<\/span> "while"<\/span>,<\/span>\n  {<\/span> "bool"<\/span>,<\/span>\n    {<\/span> "expr"<\/span>,<\/span> {<\/span> "term"<\/span>,<\/span> {<\/span> "ref"<\/span>,<\/span> "n"<\/span> }<\/span> }<\/span> }<\/span>,<\/span>\n    "<"<\/span>,<\/span>\n    {<\/span> "expr"<\/span>,<\/span> {<\/span> "term"<\/span>,<\/span> 10<\/span> }<\/span> }<\/span>\n  }<\/span>,<\/span>\n  {<\/span> "list"<\/span>,<\/span>\n    {<\/span> "assign"<\/span>,<\/span>\n      {<\/span> "ref"<\/span>,<\/span> "n"<\/span> }<\/span>,<\/span>\n      {<\/span> "expr"<\/span>,<\/span>\n        {<\/span> "term"<\/span>,<\/span> {<\/span> "ref"<\/span>,<\/span> "n"<\/span> }<\/span> }<\/span>,<\/span>\n        "+"<\/span>,<\/span>\n        {<\/span> "term"<\/span>,<\/span> 1<\/span> }<\/span>\n      }<\/span>\n    }<\/span>\n  }<\/span>\n}<\/span><\/pre><\/div><\/div><\/div>\n\n
Now we just need the eval<\/code> function to actually run the loops. We'll do this in much the same way as the conditionals. Add a case to eval<\/code> to handle \"while\" nodes:<\/p>\n\n
function<\/span> eval(<\/span>ast)<\/span>\n    -- stuff elided --<\/span>\n    elseif<\/span> ast[<\/span>1<\/span>]<\/span> ==<\/span> 'while'<\/span> then<\/span>\n        while<\/span> eval_bool(<\/span>ast[<\/span>2<\/span>]<\/span>)<\/span> do<\/span>\n            eval(<\/span>ast[<\/span>3<\/span>]<\/span>)<\/span>\n        end<\/span>\n    end<\/span>\nend<\/span><\/pre><\/div><\/div><\/div>\n\n
And now we can write a unit test for this:<\/p>\n\n
VARS.<\/span>n=<\/span>0<\/span>;<\/span> VARS.<\/span>x=<\/span>1<\/span>\nstmt:<\/span>match(<\/span>"while(n < 8) { x = x * 2; n = n + 1 }"<\/span>)<\/span>\nassert<\/span>(<\/span>VARS.<\/span>x ==<\/span> 256<\/span>)<\/span><\/pre><\/div><\/div><\/div>\n\n
Next steps<\/h2>\n
So, now that we've separated parsing our language from running programs we've parsed, we can easily add new features like control structures. Most new features you might want to add follow this basic pattern: modify the parser to recognize it, then modify the evaluator to run the parse tree. And that's mostly what we're going to do next time too: we'll modify the parser to recognize function definitions, and we'll modify the evaluator to store and call them.<\/p>\n
As always, the completed code for this chapter is available here<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
This is part three of my series on writing a toy programming language using LPeg. You should start with part one here. Last time, we added variables and arrays to the language. Assigning to arrays was starting to strain our design some, so this time we’ll refactor it a lot, and add two features that […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=\/wp\/v2\/posts\/70"}],"collection":[{"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=70"}],"version-history":[{"count":0,"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=\/wp\/v2\/posts\/70\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=70"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=70"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.playwithlua.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=70"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}