parser combinators？讨论第2页: - Scala圈子

群组首页 → 编程语言 → Scala圈子 → 论坛

发表回复

parser combinators？

alanwu 2009-10-01

night_stalker 写道

alanwu 写道

谢谢~
太多术语不了解了
EBNF是什么？

Extended Bacus-Naur Form 是一种描述语法的语法。
关于 EBNF 和“左递归”，你最好找本编译原理看看 ……

还要看编译原理。。。

alanwu 2009-10-01

night_stalker 写道

alanwu 写道

这个和则正表达式有点类似？

可以这么说，不过我们平时用的正则是非递归的（除了 Perl）

正则表达式引擎是有递归的，不然他怎么知道自己是不是全匹配？

night_stalker 2009-10-01

alanwu 写道

night_stalker 写道

alanwu 写道

谢谢~
太多术语不了解了
EBNF是什么？

Extended Bacus-Naur Form 是一种描述语法的语法。
关于 EBNF 和“左递归”，你最好找本编译原理看看 ……

还要看编译原理。。。

或者看 wiki …… 速成。
不看也没关系，当魔法用就可以了 ……

alanwu 2009-10-01

night_stalker 写道

或者看 wiki …… 速成。

有没有中文速成的？

alanwu 2009-10-01

Parsing的wiki也很难看懂

http://en.wikipedia.org/wiki/Parsing

night_stalker 2009-10-01

alanwu 写道

night_stalker 写道

alanwu 写道

这个和则正表达式有点类似？

可以这么说，不过我们平时用的正则是非递归的（除了 Perl）

正则表达式引擎是有递归的，不然他怎么知道自己是不是全匹配？

确切的说，是递归语法。

例如 EBNF 描述的这个东西：
expr := '(' expr ')' | 'a'

它匹配 "a"，"(a)"，"((a))"，"(((a)))"，…… 一般正则就不行。

另外跑题一下：combinator 的一个神奇之处是可以把非递归的东西变成递归的东西。。。

alanwu 2009-10-01

night_stalker 写道

alanwu 写道

night_stalker 写道

alanwu 写道

这个和则正表达式有点类似？

可以这么说，不过我们平时用的正则是非递归的（除了 Perl）

正则表达式引擎是有递归的，不然他怎么知道自己是不是全匹配？

确切的说，是递归语法。

例如 EBNF 描述的这个东西：
expr := '(' expr ')' | 'a'

它匹配 "a"，"(a)"，"((a))"，"(((a)))"，…… 一般正则就不行。

combinator 的一个神奇之处是可以把非递归的东西变成递归的东西。。。

很强大

fineqtbull 2009-10-02

alanwu 写道

night_stalker 写道

alanwu 写道

谢谢~
太多术语不了解了
EBNF是什么？

Extended Bacus-Naur Form 是一种描述语法的语法。
关于 EBNF 和“左递归”，你最好找本编译原理看看 ……

还要看编译原理。。。

关于EBNF，推荐一部书《The Definitive ANTLR Reference》，Terence Parr写的。虽然该书是说如何使用ANTLR这个语法分析器生成工具的，但是该书的前几章对于类似于EBNF的语法分析相关概念说的比较透彻易懂。

alanwu 2009-10-03

下到了，谢谢推荐

RednaxelaFX 2009-10-08

呃呵呵……
记得我有一次跟老师讨论问题的时候提到正则语法是非递归的而上下文无关语法支持递归，然后被老师纠正了。其实正则语法中的规则一样是递归的，问题是在规则的右侧能出现的符号受到了限制。
如果一个正则语法的BNF记法的规则如下：

A -> A a
   | a

并且假设其中'a'是一个终结符号（意味着它属于语言的字母表，同时意味着它不会出现在正则语法的规则的左侧）。这条规则表示的语言也可以记为A -> a+，这就是常见的正则表达式了。
如果一个语法是正则语法，那么它肯定可以转换为只使用下述形式的语法来表达：
1、语法中所有规则的左侧都只能有一个符号，该符号为一个非终结符号（non-terminal）
2、规则的右侧只能含有：a)一个终结符号；b)一个非终结符号与一个终结符号；c)空串。
所以说不是不能有递归，而是递归受到了很大的限制。

那假如我要描述一种语言，该语言的字母表是a、b、c、d，唯一合法的句子是abcd，那如何能转化到上述形式呢？很简单，用多条规则就行：

S -> a T
T -> b U
U -> c V
v -> d

下面的语法规则就不是正则语法：

S -> ( S )
   | ε

假设其中的左括号与右括号都是没有特殊意义的普通的终结符号，ε表示空串。则这个语法所描述的语言是n个左括号后接着n个右括号，n属于[0, +∞)。这条规则无法转化到正则语法的形式；它是一个上下文无关语法的规则。所有正则语法都是上下文无关语法，反之则不然。

发表回复

>>返回群组首页

parser combinators？

相关讨论

相关资源推荐