从PEG语法生成正确的短语

Question

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

• 序列p1 p2 ... pn：为每个子解析器生成一个短语并返回串联。
• 替代p1 | p2 | ... | pn：随机选择一个子解析器并用它生成一个短语。
• 重复p{n, m}：选择一个x[n, m]的数字(或[n, n+2]m === Infinity(，并从p返回x生成的短语的串联。
终端
• ：只需返回终端文字。

当我采用以下语法时：

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 productions 那样的东西，其中句子形式派生出较短的字符串，则此方法以非递减的长度顺序生成语法描述的所有字符串。也就是说，一旦您看到长度为 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()以查看堆活动。一些示例输出：

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