我终于找到了一种处理左递归文法的简单优雅的解析方法

[Simeon Chaos]

一直以来，在递归下降解析方法下，左递归文法都是不好处理的硬骨头，因为简单处理会导致函数的无限递归调用。因为这个原因，现在主流的解析器以采用LR系列方法为多，利用lex/yacc, bison之类的工具产生解析器。而有的语言虽然采用了递归下降解析方法，不得不限制语法构造，或者使得语法规则体系不必要地复杂化。

昨天晚上，终于找到了在递归下降方法中对左递归的简单优雅的处理办法了。历经将近5年，经过三四十次不断的尝试与失败，终于有了一个漂亮的结果。感觉非常爽。再一次体验到坚持不懈直到成功之后的愉快。

得到的这个方法有以下的特点：

1. 能处理左递归，包括间接左递归。

2. 简单直观，解析程序可读性好。

3. 时间效率高。对现有的LL(k), LR方法能处理达到线性时间复杂度的语法，此方法也可以同样达到。

4. 空间效率高。因为不需要自底向上类型方法（LR系列）所需要的转移表，也不需要象传统递归下降方法（比如peg/packrat)为了实现线性时间而设置的整体性memo。

5. 易学易用，学习曲线平坦。

6. 可以实现无扫描解析。不需要独立的词法器。

7. 灵活，适应性强。可以根据需要在解析程序中简单方便地添加前看（lookahead)或者回溯(backtracking), 因此可以任意地适应不同类型的语法。

8. 动态性好。因为不需要从独立的语法产生解析器阶段，因此可以实现动态修改语法规则。

[Simeon Chaos]

关于peg文法的维基以及stackoverflow

http://stackoverflow.com/questions/1857022/limitations-of-peg-grammar-parser-generators

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

peg.js: javascript 下的peg文法的解析器产生器：http://pegjs.majda.cz/

pyPEG javascript 下的peg文法的解析器产生器 http://fdik.org/pyPEG/

jison：bison的java移植，coffeescript用之作语法解析器产生器 http://zaach.github.io/jison/

bison http://en.wikipedia.org/wiki/Bison  http://en.wikipedia.org/wiki/GNU_bison  

http://www.gnu.org/software/bison/manual/

python 下的lex/yacc: http://www.dabeaz.com/ply/

论及peg中的左递归：http://link.springer.com/chapter/10.1007%2F978-3-642-33182-4_4#page-1

peg的packrat解析器：以下论文论述了如何利用memo机制实现左递归

http://www.vpri.org/pdf/tr2007002_packrat.pdf

方法比较复杂，需要经过解析器产生阶段，产生的语法可读性较差。全局性memo机制，不灵活。

提到两个能处理左递归的工具：

http://stackoverflow.com/questions/4397039/any-peg-parser-capable-to-handle-left-recursion

Ometa2 http://www.meta-alternative.net/mbase1.0.generic.zip

已经编了一些实验性代码，测试很成功。过几天之后将有一个完整的语法解析器出来。

我将用此种新技术为dao语言手写一个完整的解析器，估计一两周之内能够得到比较好的结果。请关注这个github项目：https://github.com/chaosim/daonode

[Zoom.Quiet]

不明觉厉...

> --
> --
> 邮件来自: `CPyUG`华蟒用户组(中文Python技术邮件列表)
> 规则: http://code.google.com/p/cpyug/wiki/PythonCn
> 发言: pyth...@googlegroups.com
> 详情: http://code.google.com/p/cpyug/wiki/CpyUg
> G+: https://plus.google.com/u/0/communities/108786798869709602787
> 严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
> ---
> 您收到此邮件是因为您订阅了 Google 网上论坛的“python-cn(华蟒用户组,CPyUG 邮件列表)”论坛。
> 要退订此论坛并停止接收此论坛的电子邮件，请发送电子邮件到 python-cn+...@googlegroups.com。
> 要查看更多选项，请访问 https://groups.google.com/groups/opt_out。
>
>



--
人生苦短, Pythonic! 冗余不做,日子甭过!备份不做,十恶不赦!
KM keep growing environment culture which promoting organization be learnning!
俺: http://about.me/zoom.quiet
许: http://creativecommons.org/licenses/by-sa/2.5/cn/

[Simeon Chaos]

贴上我今天编的实验性代码，这段代码验证了我的思路的可行性

coffeescript语言：

exports.parse = (element, text) ->

  global.text = text

  global.cursor = 0

  global.tokens = []

  global.memo = {}

  rules[element](0)

match = (c) ->

  if text[cursor] is c

    cursor++;

    true

rules = {

Binary: (start) ->

  "Binary: 1 | Binary+1"

  hash = 'Binary'+start

  m = memo[hash]

  if m is undefined

    memo[hash] = rules.Unary(start)

    rules.Binary(start)

  else

    if not match('+') then delete memo[hash]; return m

    a = rules.Unary(cursor)

    if not a then delete memo[hash]; m

    else memo[hash] = m+a; rules.Binary(start)

Unary: (start) ->

  c = text[cursor]

  switch c

    when '+'

      cursor++;

      if text[cursor]=='+' then cursor++; rules.Unary(cursor)+1;

      else rules.Unary(cursor)

    when '-'

      cursor++;

      if text[cursor]=='-' then cursor++; rules.Unary(cursor)-1

      else -rules.Unary(cursor)

    else

      x = rules.Atom(start)

      if text[cursor]=='+' and text[cursor+1]=='+' then cursor+=2; x+1

      else if text[cursor]=='-' and text[cursor+1]=='-' then cursor+=2; x-1

      else x

Atom: (start) ->

  switch text[cursor]

    when '1' then cursor++; 1

    when '(' then cursor++; exp = rules.Binary(cursor); match(')'); exp

}

以下是所通过的测试:

 "test parse left recursive": (test) ->

    test.equal parse('Binary', '1'), 1

    test.equal parse('Binary', '++1'), 2

    test.equal parse('Binary', '1++'), 2

    test.equal parse('Binary', '1--'), 0

    test.equal parse('Binary', '(1--)--'), -1

    test.equal parse('Binary', '+1'), 1

    test.equal parse('Binary', '-1'), -1

    test.equal parse('Binary', '--1'), 0

    test.equal parse('Binary', '1+1+1'), 3

    test.equal parse('Binary', '1+(1+1)'), 3

    test.equal parse('Binary', '(1+1)+(1+1)'), 4

    test.equal parse('Binary', '1+(1+1+1)+1'), 5

    test.done()

[Simeon Chaos]

这段代码体现了递归下降分析方法的特点。在上面的代码中，一个函数对应一个文法的非终结符，程序简单直观。以前的问题是，不知道如何在函数调用中避免左递归的无限扩展，本程序的机制很好的实现了扩展和memo的配合。

非常纳闷，为什么如此简单的方法，这么多年来竟然没有被发现？而我自己也是在五年时间内一直保持摸索，尝试过许多别的方法，失败过三四十次，有的方法非常复杂，包括基于python的yield语句（关心的朋友可以搜索一下yieldProlog）的方法，基于后续的方法（continuation-based, cps)，但是都不如这种简单方案彻底，有一次看起来已经解决了，但是代码十分复杂和丑陋，另外还有时间和空间的效率问题，我最终还是放弃了。

请问谁能有个合理的解释？

另外，这种新方法，配合python的yield语句，将是一个非常简单、直观、灵活和强大的手写解析器的方案。具体技术可以参看YieldProlog。

[Shiyao Ma]

你有没有看过parsley AllenShort写的。

2013/8/6 Simeon Chaos <simeon...@gmail.com>

--

--
邮件来自: `CPyUG`华蟒用户组(中文Python技术邮件列表)
规则: http://code.google.com/p/cpyug/wiki/PythonCn
发言: pyth...@googlegroups.com
详情: http://code.google.com/p/cpyug/wiki/CpyUg
G+: https://plus.google.com/u/0/communities/108786798869709602787
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
---
您收到此邮件是因为您订阅了 Google 网上论坛的“python-cn(华蟒用户组,CPyUG 邮件列表)”论坛。
要退订此论坛并停止接收此论坛的电子邮件，请发送电子邮件到 python-cn+...@googlegroups.com。
要查看更多选项，请访问 https://groups.google.com/groups/opt_out。
 
 

--

http://about.me/introom

[Simeon Chaos]

猛一看我还以为是earley, 自然语言处理中的那个通用的earley算法:)

以前没有听说过parsley AllenShort. 

在 2013年8月6日星期二UTC+8下午8时50分10秒，shiyao ma写道：

你有没有看过parsley AllenShort写的。

[Simeon Chaos]

刚刚fork：https://github.com/chaosim/parsley。

parsley是Ometa的移植，而Ometa实现了左递归。

http://www.vpri.org/pdf/tr2008003_experimenting.pdf 

Left Recursion Support for Packrat Parsers .

前面的帖子我提到了此phD 论文中单独发表的支持左递归的部分 http://www.vpri.org/pdf/tr2007002_packrat.pdf，方法比较复杂。

可以看到，我的示例代码和论文中的memo机制与论文中的方法有相似之处。

一直还没有发现，不论是就自然语言处理领域，还是就计算机语言编译技术的解析方法而言，就解析能力而言，一直没有发现哪种别的解析方法能达到我在dao和daonode中所实现的。欢迎拍砖。

在 2013年8月6日星期二UTC+8下午10时37分07秒，Simeon Chaos写道：

[Gelin Yan]

听起来可以发期刊了

--

[Simeon Chaos]

发期刊？什么意思？我out了，不太懂哦;)

在 2013年8月6日星期二UTC+8下午11时16分05秒，dynamicgl写道：

听起来可以发期刊了 

[b d]

就是发表论文在学术期刊上的意思~

[Simeon Chaos]

嗯哼，不好意思，刚才我有点瞬间脑子短路了:) 娃哈哈。

在 2013年8月7日星期三UTC+8上午12时06分23秒，bd写道：

就是发表论文在学术期刊上的意思~

[风间星魂]

左递归消除？
这个要mark一下，等看懂代码后在来回。。

--

[Hunter Chen]

5年时间你是在。。。读研究生加博士？

2013/8/7 风间星魂 <fengjia...@gmail.com>

[Simeon Chaos]

我已经毕业很多年......

[Hunter Chen]

哇？那就是教授级的咯？

2013/8/7 Simeon Chaos <simeon...@gmail.com>

我已经毕业很多年......

[Simeon Chaos]

教授？我只是业余的一个草根罢了。

在 2013年8月7日星期三UTC+8下午2时36分25秒，hunter chen写道：