Using LPEG (Lua Parser Expression Grammars) like boost::spirit

1.1k views Asked by At

So I am playing with lpeg to replace a boost spirit grammar, I must say boost::spirit is far more elegant and natural than lpeg. However it is a bitch to work with due to the constraints of current C++ compiler technology and the issues of TMP in C++. The type mechanism is in this case your enemy rather than your friend. Lpeg on the other hand while ugly and basic results in more productivity.

Anyway, I am digressing, part of my lpeg grammar looks like as follows:

function get_namespace_parser()
  local P, R, S, C, V =
    lpeg.P, lpeg.R, lpeg.S, lpeg.C, lpeg.V

namespace_parser = 
lpeg.P{
    "NAMESPACE";
    NAMESPACE   = V("WS") * P("namespace") * V("SPACE_WS") * V("NAMESPACE_IDENTIFIER") 
                  * V("WS") * V("NAMESPACE_BODY") * V("WS"),

    NAMESPACE_IDENTIFIER = V("IDENTIFIER") / print_string ,
    NAMESPACE_BODY =  "{" * V("WS") *   
                      V("ENTRIES")^0 * V("WS") * "}",


    WS = S(" \t\n")^0,
    SPACE_WS = P(" ") * V("WS") 
}
  return namespace_parser
end 

This grammar (although incomplete) matches the following namespace foo {}. I'd like to achieve the following semantics (which are common use-cases when using boost spirit).

  1. Create a local variable for the namespace rule.
  2. Add a namespace data structure to this local variable when namespace IDENTIFIER { has been matched.
  3. Pass the newly created namespace data structure to the NAMESPACE_BODY for further construction of the AST... so on and so forth.

I am sure this use-case is achievable. No examples show it. I don't know the language or the library enough to figure out how to do it. Can someone show the syntax for it.

edit : After a few days of trying to dance with lpeg, and getting my feet troden on, I have decided to go back to spirit :D it is clear that lpeg is meant to be weaved with lua functions and that such weaving is very free-form (whereas spirit has clear very well documented semantics). I simply do not have the right mental model of lua yet.

1

There are 1 answers

0
Alexander Mashin On

Though "Create a local variable for the namespace rule" sounds disturbingly like "context-sensitive grammar", which is not really for LPEG, I will assume that you want to build an abstract syntax tree.

In Lua, an AST can be represented as a nested table (with named and indexed fields) or a closure, doing whatever task that tree is meant to do.

Both can be produced by a combination of nested LPEG captures.

I will limit this answer to AST as a Lua table.

Most useful, in this case, LPEG captures will be:

  • lpeg.C( pattern ) -- simple capture,
  • lpeg.Ct( pattern ) -- table capture,
  • lpeg.Cg( pattern, name ) -- named group capture.

The following example based on your code will produce a simple syntax tree as a Lua table:

local lpeg = require'lpeg'
local P, V = lpeg.P, lpeg.V
local C, Ct, Cg = lpeg.C, lpeg.Ct, lpeg.Cg
local locale = lpeg.locale()
local blank = locale.space ^ 0
local space = P' ' * blank
local id = P'_' ^ 0 * locale.alpha * (locale.alnum + '_') ^ 0

local NS = P{ 'ns',
                  -- The upper level table with two fields: 'id' and 'entries':
    ns          = Ct( blank * 'namespace' * space * Cg( V'ns_id', 'id' )
                    * blank * Cg( V'ns_body', 'entries' ) * blank ),
    ns_id       = id,
    ns_body     = P'{' * blank
                         -- The field 'entries' is, in turn, an indexed table:
                       * Ct( (C( V'ns_entry' )
                       * (blank * P',' * blank * C( V'ns_entry') ) ^ 0) ^ -1 )
                       * blank * P'}',
    ns_entry    = id
}
  • lpeg.match( NS, 'namespace foo {}' ) will give:
    table#1 {
        ["entries"] = table#2 {
        },
       ["id"] = "foo",
    }
    
  • lpeg.match( NS, 'namespace foo {AA}' ) will give:
    table#1 {
        ["entries"] = table#2 {
            "AA"
        },
       ["id"] = "foo",
    }
    
  • lpeg.match( NS, 'namespace foo {AA, _BB}' ) will give:
    table#1 {
        ["entries"] = table#2 {
            "AA",
            "_BB"
        },
       ["id"] = "foo",
    }
    
  • lpeg.match( NS, 'namespace foo {AA, _BB, CC1}' ) will give:
    table#1 {
        ["entries"] = table#2 {
            "AA",
            "_BB",
            "CC1"
        },
       ["id"] = "foo",
    }