Как представить в Java контекстно-свободную грамматику?

Question

У меня есть простая грамматика:

R --> R and R | R or R | atom

Единственный терминал, который у нас есть, это атом. Это рекурсивная грамматика, потому что каждый R может быть составлен вложенным R. Проблемы, с которыми я сталкиваюсь:

1. Как бороться с рекурсией?
2. Как построить Java-класс R, который может быть решен по одному из 3 правил?

Как бы вы представили эту грамматику с помощью классов Java?

Answer 1

Самый простой способ - нормализовать все правила как отдельные варианты, а затем представить их как массив массивов.

Сначала мы назначаем уникальный код каждому "атому" (токену) в грамматике.

Тогда все правила должны быть нормализованы как

LHS -->  RHS1 RHS2 ... RHSn

Например, правила из: a -> b | c следует нормализовать как два правила: a -> b и a -> c . Если у вас есть другие причудливые нотационные устройства EBNF, такие как kleene start или plus, вы также нормализуете их.

Теперь у вас есть K правил; Вы можете определить массив с K слотами, каждый слот содержит одно правило. Слот правила содержит пару: LHS и массив размера n для этого правила. (Проще: слот для правил содержит массив размером n+1, причем индекс левого элемента 0 содержит LHS, индекс 1 - RHS1 и т. Д.).

Теперь у вас есть грамматика, представленная на Java.

[Рекурсия - это семантическое свойство грамматики, а не ее представление.]

Альтернатива: если вы создаете классический синтаксический анализатор для BNF (в конце концов, (E)BNF также имеет грамматику), вы можете проанализировать свой BNF, используя синтаксический анализатор, и построить дерево для этого. Это, очевидно, также представление. Это не удобно в качестве массива массивов для обработки.