Что такое "запоминать" в PEG-парсерах (например, Pegasus) и когда его следует использовать?

Question

Вот пример из Пегаса:

additive <double> -memoize
= left:additive "+" right:multiplicative { left + right }
/ left:additive "-" right:multiplicative { left - right }
/ multiplicative

Что такое memoize в этом контексте и когда я должен использовать это?

Я понимаю общую концепцию (вывод в кэш для заданных входов) - но что такое "ввод", когда мы говорим о PEG-парсере?

Answer 1

Я автор Пегаса.

Pegasus будет использовать текущее местоположение курсора вместе с текущей версией внутреннего состояния в качестве ключа для кэширования результата определенного правила, если это правило настроено на памятку.

Это следует сделать, если правило будет вызываться в одном и том же состоянии более одного раза.

Например, если у вас есть этот стиль парсера:

a = b "foo"
  / b "bar"
  / b "baz"

b = /* something expensive */

Было бы целесообразно запомнить b правило, так как он используется в качестве префикса для нескольких выражений.

Конечно, это необязательно, потому что во многих случаях это можно оптимизировать лучше:

a = b ("foo" / "bar" / "baz")

Если вы пометите каждое правило -memoize, это в основном то же самое, что синтаксический анализ Packrat. Pegasus позволяет вам контролировать это выборочно, так как есть значительные накладные расходы.