LPeg Parsing Expression Grammars For Lua, version

Introduction

LPeg is a new pattern-matching library for Lua, based on Parsing Expression Grammars (PEGs). In this text, I assume you are familiar with PEGs. If you are not, you can get a quick start reading the Wikipedia Entry for PEGs or Section 2 of Parsing Expression Grammars: A Recognition-Based Syntactic Foundation (the section has only one page). The nice thing about PEGs is that it has a formal basis (instead of being an ad-hoc set of features), allows an efficient and simple implementation, and does most things we expect from a pattern-matching library (and more, as we can define entire grammars).

作者是Lua语言的Robert， 2100行ANSI c代码， 和boost:spirit差不多强大。我等有福气了，做个小型的文法分析器轻轻松松.  作者200行用lpeg实现了一个regex模块. 一起来吧， lua也有了yacc & lex.

评论

1 楼 mryufeng 2008-07-14  

mysql-proxy的作者jan用lpeg写了个mysql 的select语法， The whole thing was about 6 hours of work without knowing LPEG before, the final indenter is only a few lines of LUA。 开发效率够高！！！

local l = require("lpeg")

module("sql")

---
-- turn a string into a case-insensitive lpeg-pattern
--
function lpeg_ci_str(s)
local p

for i = 1, #s do
local c = s:sub(i, i)

local lp = l.S(c:upper() .. c:lower() )

if p then
p = p * lp
else
p = lp
end
end

return p
end

slash_comment  = l.P("/*") * ( 1 - l.P("*/") )^0 * l.P("*/")
-- FIXME: we need support for -- comments too
comment = slash_comment

WS       = l.S(" \t\n") + comment
SELECT   = lpeg_ci_str("SELECT") * WS^1
STAR     = l.P("*") * WS^0
FROM     = lpeg_ci_str("FROM") * WS^1
alpha    = l.R("az", "AZ") -- [a-zA-Z]
digit    = l.R("09")       -- [0-9]
number   = (l.P("-") + "") * digit^1         -- [0-9]+
literal_char = alpha + l.S("_") -- /[_a-z]/i
literal_unquoted  = literal_char * ( literal_char + digit )^0  -- /[_a-z][_a-z0-9]*/i
literal_quoted  = l.P("`") * ( 1 - l.P("`") )^0 * l.P("`") -- /`.*`/
string_quoted  = l.P("\"") * ( 1 - l.P("\"") )^0 * l.P("\"") -- /".*"/
literal  = literal_unquoted + literal_quoted

fieldname  = literal * ( WS^0 * l.P(".") * WS^0 * literal ) ^0

---
-- expressions
--

funcname   = literal_unquoted
user_var   = "@" * literal_unquoted * WS^0
NULL       = lpeg_ci_str("NULL")
LogicalOp  = (lpeg_ci_str("OR") + lpeg_ci_str("AND")) * WS^1
AssignOp   = l.P(":=") * WS^0
FactorOp   = l.S("*/") * WS^0
TermOp     = l.S("+-") * WS^0
CompOp     = (
l.P("=") +
l.P("!=") +
l.P("<>") +
l.P("<=") +
l.P(">=") +
l.P("<") +
l.P(">") +
lpeg_ci_str("IS") * WS^1 * lpeg_ci_str("NOT") +
lpeg_ci_str("IS") * WS) * WS^0
ParanOpen = l.P("(") * WS^0
ParanClose = l.P(")") * WS^0
Comma = l.P(",") * WS^0

Assign  = l.V("Assign") * WS^0
Exp     = l.V("Exp") * WS^0
Logical = l.V("Logical") * WS^0
Comp    = l.V("Comp") * WS^0
Factor  = l.V("Factor") * WS^0
Term    = l.V("Term") * WS^0

expr       = l.P({
Assign,
Assign   = (( user_var * AssignOp ) + "") * Exp,
Exp      = Logical * ( LogicalOp * Logical)^0,
Logical  = Comp * ( CompOp * Comp)^0,
Comp     = Factor * ( FactorOp * Factor)^0,
Factor   = Term * ( TermOp * Term )^0,
Term     =
lpeg_ci_str("CAST") * ParanOpen * Assign * lpeg_ci_str("AS") * WS^1 * literal_unquoted * ParanClose +
funcname * ParanOpen * (( Assign * ( Comma * Assign )^0) + "") * ParanClose +
ParanOpen * Assign * ParanClose +
number +
string_quoted +
user_var +
fieldname +
NULL
})

alias = lpeg_ci_str("AS") * WS^1 * literal * WS^0
opt_alias = ((alias) + "")
alias_expr = expr * opt_alias

select_opt = (l.P("SQL_CALC_FOUND_ROWS") + l.P("SQL_NO_CACHE")) * WS^1

table = literal * WS^0
alias_table = table * opt_alias
WHERE = lpeg_ci_str("WHERE") * WS^0
USING = lpeg_ci_str("USING") * WS^0
LEFT = lpeg_ci_str("LEFT") * WS^0
RIGHT = lpeg_ci_str("RIGHT") * WS^0
INNER = lpeg_ci_str("INNER") * WS^0
OUTER = lpeg_ci_str("OUTER") * WS^0
JOIN = lpeg_ci_str("JOIN") * WS^0
join_type =
  ((INNER + "") * JOIN) +
  (LEFT * (OUTER + "") * JOIN) +
  (RIGHT * (OUTER + "") * JOIN)

ON           = lpeg_ci_str("ON") * WS^0
DESC         = lpeg_ci_str("DESC") * WS^0
ASC          = lpeg_ci_str("ASC") * WS^0
ORDERBY      = lpeg_ci_str("ORDER") * WS^1 * lpeg_ci_str("BY") * WS^0
orderby_expr = expr * (ASC + DESC + "")
GROUPBY      = lpeg_ci_str("GROUP") * WS^1 * lpeg_ci_str("BY") * WS^0
HAVING       = lpeg_ci_str("HAVING") * WS^0

select_pat = l.P({
"simple_select",

simple_select = l.C(SELECT) *
l.Ct((l.C(select_opt))^0) *
l.Ct(l.C(alias_expr) * (l.C(Comma * alias_expr))^0) *
(-1 +
(l.C(FROM) *  -- FROM tbl [AS alias] [, tbl [AS alias]]
   l.Ct(l.V("subq_table") *
    (((l.C(Comma) * l.V("subq_table")) +
              l.C((join_type)) * l.Ct(l.V("subq_table")) *
                        ((l.C(USING) * l.Ct(l.C(ParanOpen * fieldname * ParanClose))) +
                         (l.C(ON) * l.Ct(l.C(expr))) + "")))^0)) *
   (-1 + -- [WHERE ...]
    ((l.C(WHERE) * l.Ct(l.C(expr))) + "") *
            ((l.C(ORDERBY) * l.Ct(l.C(orderby_expr) * ( l.C(Comma * orderby_expr))^0)) + "") *
            ((l.C(GROUPBY) * l.Ct(l.C(expr) * ( l.C(Comma * expr))^0) * ( l.C(HAVING) * l.Ct(l.C(expr)) + "")) + "")
           ) + "") +
"",

subq_table = l.C(alias_table) +
l.C(ParanOpen) * l.Ct(l.V("simple_select")) * l.C(ParanClose * alias )
})