Lua模式可以表示任何正则语言吗？

2016-6-5 2:25:33
收藏：0
阅读：73
评论：2

这个问题并不是在询问 Lua 模式是否是 PCRE。这个问题已经被问了多次，答案绝对是否定的。

相反，我想问的是 Lua 模式是否有类似于正式语言定义的正则语言的类比。我的直觉是不能，因为我无法为以下正则语言创建模式：

L = {'foo'}* = {'', 'foo', 'foofoo', 'foofoofoo', ...}

我所有的尝试都失败了，因为 Lua 似乎缺乏在捕获上使用 Kleene 星号的能力：

> print(('foofoo'):find('(foo)*'))
nil

你能证明 Lua 中没有模式可以表示 L，并更广义地说，Lua 模式是否能为任何正则语言创建？

点赞
用户734069
用户734069

Lua模式不是正则语言。几乎每个Lua模式都可以表达为正则语言，但是有很多正则表达式不能表达为Lua模式（至少有一个Lua模式不是正则的）。而且你正在尝试的特定正则结构，匹配特定字符序列的重复出现，在Lua模式中是不可能实现的，至少在一般情况下是不行的。

基本上，Lua模式无法执行任何需要基于输入流中的多个字符做出决策点的操作。而正则语言可以做到。

2016-06-05 02:39:45
用户1847592
用户1847592

Kleene 星号可以很容易地实现：

function belongs_to_L(str)
   return str:gsub("foo", "") == ""
end

print(belongs_to_L("foofoo"))  --> true
print(belongs_to_L("bar"))     --> false
2016-06-05 07:44:27

作者:

用户1721424

用户1721424
推荐文章