algorithm - 从 PEG 语法生成正确的短语

Question

我写了一个 PEG 解析器生成器只是为了好玩(有时间我会在 NPM 上发布它)，并认为在它上面添加一个随机短语生成器会很容易。这个想法是在给定语法的情况下自动获得正确的短语。所以我设置了以下规则来从每种类型的解析器生成字符串:

序列p1 p2 ... pn :为每个子解析器生成一个短语并返回连接。

替代 p1 | p2 | ... | pn :随机选择一个子解析器并用它生成一个短语。

重复p{n, m} : 选择一个号码 x在 [n, m] (或 [n, n+2] 是 m === Infinity )并返回 x 的串联从 p 生成的短语.

终端:只需返回终端文字。

当我采用以下语法时:

S: NP VP
PP: P NP
NP: Det N | Det N PP | 'I'
VP: V NP | VP PP
V: 'shot' | 'killed' | 'wounded'
Det: 'an' | 'my' 
N: 'elephant' | 'pajamas' | 'cat' | 'dog'
P: 'in' | 'outside'

它工作得很好。一些例子 :

my pajamas killed my elephant
an pajamas wounded my pajamas in my pajamas
an dog in I wounded my cat in I outside my elephant in my elephant in an pajamas outside an cat
I wounded my pajamas in my dog

这个文法有一个递归( PP: P NP > NP: Det N PP )。当我采用其他递归语法时，这次用于数学表达式:

expr: term (('+' | '-') term)*
term: fact (('*' | '/') fact)*
fact: '1' | '(' expr ')'

几乎有两次，我得到了 “超出最大调用堆栈大小”错误(在 NodeJS 中)。另一半时间，我得到正确的表达:

( 1 ) * 1 + 1
( ( 1 ) / ( 1 + 1 ) - ( 1 / ( 1 * 1 ) ) / ( 1 / 1 - 1 ) ) * 1
( ( ( 1 ) ) )
1
1 / 1

我猜 fact 的递归产生被调用太频繁，在调用堆栈中太深，这使得整个事情都被炸毁了。

我怎样才能让我的方法不那么幼稚，以避免那些导致调用堆栈爆炸的情况？谢谢你。

Answer 1

当然，如果语法描述任意长的输入，您很容易以非常深的递归结束。避免这个陷阱的一个简单方法是保持一个部分扩展的句子形式的优先级队列，其中关键是长度。删除最短的并以各种可能的方式替换每个非终端，发出那些现在都是终端的并将其余的添加回队列。您可能还想维护一个“已发出”集以避免发出重复项。如果语法没有类似 epsilon 产生式的任何东西，其中句子形式派生出较短的字符串，则此方法以非递减长度顺序产生语法描述的所有字符串。也就是说，一旦您看到长度为 N 的输出，所有长度为 N-1 或更短的字符串都已经出现。

由于 OP 询问了详细信息，因此这里是表达式语法的实现。通过将 PEG 重写为 CFG 来简化它。

import heapq

def run():
  g = {
    '<expr>': [
      ['<term>'],
      ['<term>', '+', '<expr>'],
      ['<term>', '-', '<expr>'],
    ],
    '<term>': [
      ['<fact>'],
      ['<fact>', '*', '<term>'],
      ['<fact>', '/', '<term>'],
    ],
    '<fact>': [
      ['1'],
      ['(', '<expr>', ')']
    ],
  }
  gen(g)

def is_terminal(s):
  for sym in s:
    if sym.startswith('<'):
      return False;
  return True;

def gen(g, lim = 10000):
  q = [(1, ['<expr>'])]
  n = 0;
  while n < lim:
    _, s = heapq.heappop(q)
    # print("pop: " + ''.join(s))
    a = []
    b = s.copy()
    while b:
      sym = b.pop(0)
      if sym.startswith('<'):
        for rhs in g[sym]:
          s_new = a.copy()
          s_new.extend(rhs)
          s_new.extend(b)
          if is_terminal(s_new):
            print(''.join(s_new))
            n += 1
          else:
            # print("push: " + ''.join(s_new))
            heapq.heappush(q, (len(s_new), s_new))
        break # only generate leftmost derivations
      a.append(sym)

run()

取消注释额外的 print() s 查看堆事件。一些示例输出:

1
(1)
1*1
1/1
1+1
1-1
((1))
(1*1)
(1/1)
(1)*1
(1)+1
(1)-1
(1)/1
(1+1)
(1-1)
1*(1)
1*1*1
1*1/1
1+(1)
1+1*1
1+1/1
1+1+1
1+1-1
1-(1)
1-1*1
1-1/1
1-1+1
1-1-1
1/(1)
1/1*1
1/1/1
1*1+1
1*1-1
1/1+1
1/1-1
(((1)))
((1*1))
((1/1))
((1))*1
((1))+1
((1))-1
((1))/1
((1)*1)
((1)+1)
((1)-1)
((1)/1)
((1+1))
((1-1))
(1)*(1)
(1)*1*1
(1)*1/1
(1)+(1)
(1)+1*1