文档章节

通过 LPeg 介绍解析表达式语法(Parsing Expression Grammars)

FreeBlues
 FreeBlues
发布于 2018/02/09 18:18
字数 3754
阅读 260
收藏 0

通过 LPeg 介绍解析表达式语法(Parsing Expression Grammars)

说明: 本文是对 An introduction to Parsing Expression Grammars with LPeg 的翻译, 此文非常好, 从最简单的模式(Pattern)讲起, 逐步扩展, 最终完成一个计算器表达式的解析器, 非常适合初学者循序渐进地理解学习 LPeg

目录

什么是 PEG

PEG 或者说 解析表达式语法, 是用字符串匹配来描述语言(或模式)的方式. 跟正则表达式不同, PEG 可以解析一门完整的语言, 包括递归结构. 从分类而言, PEG 跟上下文无关文法--通过像YaccBison这样的工具来实现--很相似.

注意: 语法是语言的规格. 在实际中, 我们用语法把某些语言的输入字符串转换成内存中我们可以操作的对象.

跟上下文无关语法(CFG)相比, PEG 的实现方式非常不同. 不同于CFG中被归约为状态机, PEG 采用顺序解析. 这意味着你编写的解析规则的顺序很重要. 随后将会提供一个例子. 它们可能会比 CFG 更慢一些, 但是实际中它们相当快. 从概念上来说 PEG 跟一种通常被称为递归下降的手写模式很相似.

PEG 更容易写, 通常你不需要写一个单独的扫描器(译者注:此处指词法扫描): 你的语法直接作用于输入的文本, 而不需要标识化的步骤(译者注:此处指把输入文本通过词法扫描器分解成 token 序列)。

注意: 如果你对上面这些都没什么感觉也别担心, 通过这个指南你会明白它们是如何工作的.

什么是 LPeg

关于 PEG 我首先介绍的是 LPeg, PEG 算法的一个 Lua 实现. LPeg 语法直接在Lua代码中指定. 这和大多数其他采用编译器-编译器模式(compiler compiler pattern)的工具都不同.

在编译器-编译器模式中, 你用一种定制的领域特定语言来书写语法, 然后把它编译为你的目标语言. 有了 LPeg 你只需编写 Lua 代码即可. 每个解析单元(Parsing Unit)或模式对象都是语言中的一类对象(first class). 它可以被 Lua 的内置操作符和控制语句组合起来. 这使得它成为一种表达语法的非常强大的方式.

MoonScript’s grammar 是一个规模更大用来解析一种完整的编程语言moonscriptLPeg 语法的例子.

安装 LPeg

你可以通过 luarocks.org 来安装 LPeg:

luarocks install lpeg

一旦安装完成, 你可以通过 require 来加载模块:

local lpeg = require("lpeg")

一些简单的语法

LPeg 提供一系列的单和双字母命名的函数, 把 Lua 字面量转换成模式对象. 模式对象能被组合起来制造出更复杂的模式, 或对一个字符串调用检查匹配, 模式对象的操作符被重载用来提供不同的组合方式.

为了简洁起见, 我们假定 lpeg 被导入到所有的例子中:

local lpeg = require("lpeg")

我会尝试解释用在这个指南中的例子里每一样东西, 但是为了对所有内置函数都能有一个全面的了解,我建议阅读 LPeg 官方使用手册

字符串等价

我们能做出的最简单的例子就是检查一个字符串跟另一个字符串相等:

lpeg.P("hello"):match("world") --> 不匹配, 返回 nil
lpeg.P("hello"):match("hello") --> 一个匹配, 返回 6
lpeg.P("hello"):match("helloworld") --> 一个匹配, 返回 6

默认情况下,成功匹配时,LPeg 将返回字符消耗数(译者注: 也就是成功匹配子串之后的下一个字符的位置). 如果你只是想看看是否匹配这就足够好了,但如果你试图解析出字符串的结构来,你必须用一些 LPeg 的捕获(capturing)函数.

注意: 值得注意的是, 即使没有得到字符串的末尾, 匹配仍然会成功. 你可以用 -1 来避免这种情况. 我会在下面描述.

模式组合

乘法和加法运算符是用于组合模式的最常用的两个被重载的运算符.

  • 乘法可以被想成跟 and 一样的,左边的操作数必须匹配,同时右边的操作数必须匹配.

  • 加法可以被想成跟 or 一样的,要么是左操作数匹配,要么右操作数必须匹配。

这两个运算符都被要求保持顺序. 左边操作数一直要在右边操作数之前被检查. 这里有一些例子:

local hello = lpeg.P("hello")
local world = lpeg.P("world")

-- 译者注:如果是在 Lua 的命令行交互模式下执行, 记得去掉 local, 否则会报错
local patt1 = hello * world
local patt2 = hello + world


-- hello followed by world
patt1:match("helloworld") --> matches
patt1:match("worldhello") --> doesn't match

-- either hello or world
patt2:match("hello") --> matches
patt2:match("world") --> matches

注意: 正常的Lua 运算符的处理规则应用到这些操作符上, 因此当需要的时候你将不得不使用括号.

解析数字

有了这个基础, 我们现在可以写一个语法来做些什么. 让我们写一个从任意字符串中提取所有整数的的语法。

该算法将工作如下:

  • 对于每个字符...
    • 如果它是十进制数字字符, 开始捕获...
      • 消耗掉每个字符, 如果它是一个十进制数字字符(译者注:这里的消耗意指比较指针后移一位)
    • 否则忽略, 跳到下一个字符

LPeg 中写一个解析器我喜欢的途径是首先写出最具体的模式。然后使用这些模式作为积木来组装出最终结果。幸运的是,每一个模式都是一个 Lua 中使用 LPeg 的一类对象,所以很容易单独测试每个部件.

首先, 我们写一个解析一个整数的模式:

local integer = lpeg.R("09")^1

这个模式将会匹配 09 之间的任一个数字字符 1 次或者多次. LPeg 中的所有模式都是贪婪的.

我们希望作为返回值的数字值不是匹配结束的字符偏移值. 我们能够立即用一个 / 运算符来应用一个捕获变换函数:

local integer = lpeg.R("09")^1 / tonumber

print(integer:match("2923")) --> The number 2923

译者注: 这里为清楚显示 / 的作用, 补充下面的对比, 如果不加 / tonumber, 那么返回的就是匹配子串位置后移一位的位置:

> integer = lpeg.R("09")^1 / tonumber
> print(integer:match("2923"))
2923
> integer = lpeg.R("09")^1
> print(integer:match("2923"))
5
> 

它的工作机制是, 通过把模式匹配的结果“2923”做为一个字符串来捕获,并将其传递给Lua函数 tonumbermatch 的返回值是一个从字符串解析得到的标准数字值。

注意: 如果在调用 match 时一个捕获被使用, 那么缺省的返回值会被替换成捕获到的值.

现在我们写一个解析器, 用来匹配一个整数或者一些其他字符:

local integer_or_char = integer + lpeg.P(1)

注意: 当使用 LPeg 的操作符重载时, 它会通过把所有的 Lua 字面量传递给 P 而自动地把它们转换为模式. 在上述的例子中我们可以只写 1 来取代 lpeg.P(1)

(译者注: 也就是形如: local integer_or_char = integer + 1)

在这里顺序是很重要的:

完成我们的语法只需要重复我们已有的部件, 并且用 Ct 把捕获到的结果存储到一个表中:

local extract_ints = lpeg.Ct(integer_or_char^0)

这里是完整的语法个一些运行例子:

local integer = lpeg.R("09")^1 / tonumber
local integer_or_char = integer + lpeg.P(1)
local extract_ints = lpeg.Ct(integer_or_char^0)

-- Testing it out:

extract_ints:match("hello!") --> {}
extract_ints:match("hello 123") --> {123}
extract_ints:match("5 5 5 yeah 7 7 7 ") --> {5,5,5,7,7,7}

一个计算器语法解析器

接下来我们准备构建一个计算器表达式解析器. 我重点强调解析器是因为我们不会去求值表达式而是去构建一个被解析表达式的语法树.

如果你曾打算建立一种编程语言,你几乎总是要解析出一个语法树. 针对这个计算器的语法树例子是一个很好的练习.

在写下任意代码之前我们应该定义能被解析的语言. 它应该能够解析整数, 加法, 减法, 乘法和除法. 它应该清楚运算符优先级。它应该允许操作符和数字之间的任意空格.

这里是一些输入例子(由换行符分割):

1*2
1 + 2
5 + 5/2
1*2 + 3
1 * 2 - 3 + 3 + 2

接着我们设计语法树的格式: 我们如何把这些解析表达式映射为 Lua 友好的表示?

对于普通的整数, 我们可以直接把它们映射为 Lua 中的整数. 对于任意二元表达式(加法,除法等), 我们将会使用 Lisp 风格的 S-表达式(S-Expression) 数组, 数组中的第一个项目是被当做字符串的运算符, 数组中的第 2, 第 3 个项目是运算符左边的操作数和右边的操作数.

光用嘴说很麻烦, 用例子很容易领悟:

parse("5") --> 5
parse("1*2") --> {"*", 1, 2}
parse("9+8") --> {"+", 9, 8}
parse("3*2+8") --> {"+", {"*", 3, 2}, 8}

上面的 parse 函数将会成为我们创建的语法.

以规范的方式进行,我们就可以开始编写解析器。像以前一样,我们开始尽可能具体:

local lpeg = require("lpeg")

-- 译者注:处理空格,包括制表符, 回车符, 换行符
local white = lpeg.S(" \t\r\n") ^ 0

local integer = white * lpeg.R("09") ^ 1 / tonumber
local muldiv = white * lpeg.C(lpeg.S("/*"))
local addsub = white * lpeg.C(lpeg.S("+-"))

为了允许任意空格, 我制造了一个空格模式对象 white, 并把它加到所有其他模式对象的前面. 通过这种方式, 我们可以自由地使用模式对象, 而不必去考虑空格是否已经被处理.

我们重复利用了上面的整数模式 integer, 匹配运算符的模式是直线前进. 基于它们的优先级我已经把运算符分成两组不同的模式.

在尝试编写整个语法之前,让我们专注于让单个组件工作起来。我选择编写整数或乘法/除法的解析程序.

注意: 编程语言的创造者一贯把乘法优先级称为因子(factor), 把加法优先级称为项(term)。我们将在这里使用这一术语.

local factor = integer * muldiv * integer + integer

factor:parse("5") --> 5
factor:parse("2*1") --> 2 "*" 1

我们上面工作的乘法运算,但有一个问题。 该模式的捕获(在本例中的返回值)是错误的。它按: 运算符 的顺序返回多个值。我们需要的是一个第一个项目为运算符的表。

为了修复这个问题, 我们将会创建一个变换函数, 节点构造器(node constructor)如下:

local function node(p)
  return p / function(left, op, right)
    return { op, left, right }
  end
end

local factor = node(integer * muldiv * integer) + integer

factor:match("5") --> 5
factor:match("2*1") --> {"*", 2, 1}

看起来很好, 现在我们可以利用节点构造器来构建剩下的语法了.

因为我们正在构建一个递归语法, 我们将会使用 lpeg.P 的语法形式. 让我们以这种语法形式重写上述代码:

local calculator = lpeg.P({
  "exp",
  exp = lpeg.V("factor") + integer,
  factor = node(integer * muldiv * integer)
})

这里有一些新东西. 第一个是语法表里的 "exp", 它是我们语法的根模式. 这意味着被命名为 exp 的模式将会第一个被执行.

lpeg.V 在我们的语法中被用来引用非终结符(non-terminal). 这就是我们如何做的递归,通过对未被声明过的模式的引用. 这种特殊的语法不是递归的,但它仍然演示了 v 如何被使用。

PEG 中我们不能使用任何一种会导致解析器进入无限循环的递归. 为了达到我们想要的优先级,我们需要聪明地构造我们的模式。

由于factor、乘法和除法的优先级最高,所以它应该是模式层次结构中最深的。

让我们重新设计我们的 factor 解析器来处理有重复乘法/除法的情况:

local calculator = lpeg.P({
  "exp",
  exp = lpeg.V("factor") + integer,
  factor = node(integer * muldiv * (lpeg.V("factor") + integer))
})

译者注: 这里可以根据这段代码写出对应的 BNF :

<calculatar> ::= <exp>
<exp> ::= <factor> | <integer>
<factor> ::= <integer>  <muldiv>  { <factor> | <integer>}
<integer> ::= Number
<muldiv> ::= '*' | '/'

使用右递归允许任意数量的乘法链。我们可以把同一优先级的运算符链起来而没有任何问题。它可以被解析为:

calculator:match("5*3*2") --> {"*", {"*"}}

我们工作的方式是降低优先级直到我们到达语法的顶层. 接着是解析 term

local calculator = lpeg.P({
  "exp",
  exp = lpeg.V("term") + lpeg.V("factor") + integer,
  term = node((lpeg.V("factor") + integer) * addsub * lpeg.V("exp")),
  factor = node(integer * muldiv * (lpeg.V("factor") + integer))
})

term 模式只是对可能发生的情况进行考虑。左侧可以是一个高优先级的 factor,或一个整数 integer. 右侧可以是相同优先级的 term, 或高优先级的 factor, 或整数 integer(请注意,这些都根据优先级顺序列出)

我们能够复用 exp 模式作为 term 模式的左边, 因为它刚好符合我们想要的所有东西。

最后是使用了节点构造器的语法:

local lpeg = require("lpeg")
local white = lpeg.S(" \t\r\n") ^ 0

local integer = white * lpeg.R("09") ^ 1 / tonumber
local muldiv = white * lpeg.C(lpeg.S("/*"))
local addsub = white * lpeg.C(lpeg.S("+-"))

local function node(p)
  return p / function(left, op, right)
    return { op, left, right }
  end
end

local calculator = lpeg.P({
  "input",
  input = lpeg.V("exp") * -1,
  exp = lpeg.V("term") + lpeg.V("factor") + integer,
  term = node((lpeg.V("factor") + integer) * addsub * lpeg.V("exp")),
  factor = node(integer * muldiv * (lpeg.V("factor") + integer))
})

注意: 我增加了一个(line)模式, 检查确保解析器到达了输入的末尾.

结束

这就是这篇指南. 希望它对于你在自己的项目中开始使用 LPeg 已经足够了. 用 LPeg 写的语法 是对 Lua模式或正则表达式的一种很好的替代, 因为它们更容易阅读,调试和测试. 此外,他们足够强大到到能够实现这样的解析器, 它可以用于完整的编程语言!

在未来我希望写更多的包括了我在实施 moonscript 中用到的更先进的技术的指导文档。

© 著作权归作者所有

共有 人打赏支持
FreeBlues
粉丝 98
博文 280
码字总数 493678
作品 0
其它
程序员
私信 提问
mysql-proxy发布了0.7版本

Mysql proxy是MySQL官方开发一个mysql数据库前端代理,使用C语言编写,并且支持lua来编写proxy规则,可以用来实现mysql的读写分离,负载均衡等等功能。经过了一年多的等待,mysql proxy终于从...

红薯
2009/02/02
272
0
ZeroBrane Studio v1.40 发布,Lua 集成开发环境

ZeroBrane Studio v1.40 发布了。本次的更新有:Mac 可以输入中文了(虽然不是那么完美),下面是值得关注的更新: Added ability to load/save files with invalid UTF-8 encoded characters...

leolovenet
2016/09/20
1K
4
Lua 的解析表达式语法

使用一个模式 这个例子显示了一个建立和使用模式的程序,它非常简单但很完整: 模式是简单的一个或多个小写字符并在尾端以(-1)结束的序列。该程序调用match来当作一个方法和函数。在以上成功...

沙枣
2013/04/15
4.4K
1
Linux 安装 luarocks(lua的模块管理工具)

1、简介 该软件包可以安装和更新lua的第三方模块。 2、下载地址 请在 http://luarocks.org/releases/ 页面选择需要的软件包。 wget http://luarocks.org/releases/luarocks-2.1.0.tar.gz 3、...

千山万水
2015/09/25
0
0
Lua: 好的, 坏的, 和坑爹的

好的 小巧: 20000行C代码 可以编译进182K的可执行文件 (Linux下). 可移植: 只要是有ANSI C 编译器的平台都可以编译. 你可以看到它可以在几乎所有的平台上运行:从 microcontrollers Lego Mins...

jeffjade
2014/09/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

MySQL中update修改数据与原数据相同会再次执行吗

背景 本文主要测试MySQL执行update语句时,针对与原数据(即未修改)相同的update语句会在MySQL内部重新执行吗? 测试环境 MySQL5.7.25 Centos 7.4 binlog_format为ROW 参数 root@localhost...

阿里云官方博客
8分钟前
0
0
ZStack部署实战之VDI异构部署

作者:ZStack社区 蒋克勤 前言 大家都知道ZStack是一个自主开发、功能齐全、轻量级的私有云和混合云平台,同时,ZStack作为一个开放的云平台,也能够支持各种云桌面终端的接入!大家可以结合...

ZStack社区版
10分钟前
0
0
我的漂泊一生......

突然想起来,给自己的这辈子旅程画个线路图。 懵懂期 青春期 转变期 转变期(二) 现在 感谢 感谢生命里出现的 好的差的,那都是一段旅程 特别感谢几个人对我的帮助: 英泰老叶、工贸老陈、天...

o0无忧亦无怖
11分钟前
5
2
难越高并发这座火焰山?试一试Iron Cloud这朵筋斗云

强如银行巨头,也有难翻的火焰山? 伴随互联网+ 趋势的推进,越来越多金融公司业务渠道从线下转移到线上,业务场景发生质的转变与提升。 支付场景多样化和人们消费水平升级,随之而来的是各大...

heishaovvv
22分钟前
0
0
在线官网Spring Initializr 或 IntelliJ IDEA 快速搭建springboot项目

Spring Boot是由Pivotal团队提供的全新框架,设计目的是用来简化新Spring应用的初始搭建以及开发过程。它主要推崇的是'消灭配置’,实现零配置。 那么,如何快速新建一个一个springboot项目脚...

Mr_ET
23分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部