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

61 views
Skip to first unread message

Simeon Chaos

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

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

得到的这个方法有以下的特点：
1. 能处理左递归，包括间接左递归。
2. 简单直观，解析程序可读性好。
3. 时间效率高。对现有的LL(k), LR方法能处理达到线性时间复杂度的语法，此方法也可以同样达到。
4. 空间效率高。因为不需要自底向上类型方法（LR系列）所需要的转移表，也不需要象传统递归下降方法（比如peg/packrat)为了实现线性时间而设置的整体性memo。
5. 易学易用，学习曲线平坦。
6. 可以实现无扫描解析。不需要独立的词法器。
7. 灵活，适应性强。可以根据需要在解析程序中简单方便地添加前看（lookahead)或者回溯(backtracking), 因此可以任意地适应不同类型的语法。
8. 动态性好。因为不需要从独立的语法产生解析器阶段，因此可以实现动态修改语法规则。

Simeon Chaos

unread,
Aug 6, 2013, 7:08:58 AM8/6/13
to cno...@googlegroups.com
关于peg文法的维基以及stackoverflow
peg.js: javascript 下的peg文法的解析器产生器：http://pegjs.majda.cz/
pyPEG javascript 下的peg文法的解析器产生器 http://fdik.org/pyPEG/
jison：bison的java移植，coffeescript用之作语法解析器产生器 http://zaach.github.io/jison/
python 下的lex/yacc: http://www.dabeaz.com/ply/

peg的packrat解析器：以下论文论述了如何利用memo机制实现左递归
方法比较复杂，需要经过解析器产生阶段，产生的语法可读性较差。全局性memo机制，不灵活。

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

已经编了一些实验性代码，测试很成功。过几天之后将有一个完整的语法解析器出来。
我将用此种新技术为dao语言手写一个完整的解析器，估计一两周之内能够得到比较好的结果。请关注这个github项目：https://github.com/chaosim/daonode

Simeon Chaos

unread,
Aug 6, 2013, 12:52:28 PM8/6/13
to cno...@googlegroups.com
贴上我今天编的实验性代码，这段代码验证了我的思路的可行性
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()

这段代码体现了递归下降分析方法的特点。在上面的代码中，一个函数对应一个文法的非终结符，程序简单直观。以前的问题是，不知道如何在函数调用中避免左递归的无限扩展，本程序的机制很好的实现了扩展和memo的配合。
非常纳闷，为什么如此简单的方法，这么多年来竟然没有被发现？而我自己也是在五年时间内一直保持摸索，尝试过许多别的方法，失败过三四十次，有的方法非常复杂，包括基于python的yield语句（关心的朋友可以搜索一下yieldProlog）的方法，基于后续的方法（continuation-based, cps)，但是都不如这种简单方案彻底，有一次看起来已经解决了，但是代码十分复杂和丑陋，另外还有时间和空间的效率问题，我最终还是放弃了。
请问谁能有个合理的解释？
或者是我的想法中有什么漏洞或者错误？
另外，这种新方法，配合python的yield语句，将是一个非常简单、直观、灵活和强大的手写解析器的方案。具体技术可以参看YieldProlog。

Dolfly

unread,
Jan 24, 2014, 10:15:35 AM1/24/14
to cno...@googlegroups.com
Hi:
test mail
> --
> 您收到此邮件是因为您订阅了 Google 网上论坛的“cnodejs”论坛。
> 要退订此论坛并停止接收此论坛的电子邮件，请发送电子邮件到 cnodejs+u...@googlegroups.com。
> 要查看更多选项，请访问 https://groups.google.com/groups/opt_out。
>
>
Reply all
Reply to author
Forward
0 new messages