Определение набора действительных следующих терминалов при генерации из CFG

Question

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

Ниже приведен пример грамматики в BNF и частичной генерации.

<expr> ::= <term> "+" <expr> | <term>
<term> ::= <term> "*" <factor> | <factor>
<factor> ::= "(" <expr> ")" | <const>
<const> ::= "0" | "1" | "2" | "3" | "4"

Предполагаемая сгенерированная последовательность пока: ( 1 +, В этом случае мы легко видим, что следующий генерируемый токен должен исходить из набора {"(", "0", "1", "2", "3", "4"},

Существует ли алгоритм для определения этого набора с учетом общей грамматики и частичной генерации или для генерации предложения таким образом, чтобы этот набор был доступен на каждом этапе?

Answer 1

Обычный подход к генерации предложений состоит в том, чтобы начать с начального символа, а затем многократно заменить первый (или последний) нетерминал одним из его производств, используя критерий выборки, не совсем соответствующий данному ответу.

Если грамматика анализируется слева направо, вы можете просто проанализировать префикс и затем выбрать один из терминалов, для которых существует действие без ошибок. Это требует таблиц разбора для любого алгоритма слева направо. Если алгоритм LALR(k), вам нужно следить за действиями сокращения, которые приводят к возможным ошибкам. Чтобы избежать этого сценария, если вы решите выбрать действие сокращения, не фиксируйте соответствующий символ предварительного просмотра. Только совершайте, когда вы делаете смену. (Но вы также не можете игнорировать указатели, соответствующие действию сокращения; вам нужно сохранить весь набор, чтобы гарантировать, что символ указателя будет выбран последовательно.)