Генерация правильных фраз из грамматик PEG

Question

Я написал генератор анализатора PEG просто для удовольствия (я опубликую sh его на NPM некоторое время) и подумал, что было бы легко добавить генератор случайных фраз поверх него. Идея состоит в том, чтобы автоматически получать правильные фразы, учитывая грамматику. Поэтому я установил следующие правила для генерации строк из каждого типа синтаксических анализаторов:

• Sequence p1 p2 ... pn: сгенерировать фразу для каждого подпарасера ​​и вернуть объединение.
• Alternative p1 | p2 | ... | pn : Случайно выберите подпарсер и сгенерируйте с ним фразу.
• Повтор p{n, m}: Выберите число x в [n, m] (или [n, n+2] равно m === Infinity) и верните конкатенацию x сгенерированные фразы из p.
• Terminal: Просто верните литерал терминала.

Когда я беру следующую грамматику:

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