Распознавание перестановок конечного набора строк в формальной грамматике

Цель: найти способ формального определения грамматики, которая распознает элементы из множества 0 или 1 раз в любом порядке. Впоследствии я хочу разобрать его и также сгенерировать AST.

Например: скажем, набор допустимых строк на моем языке равен {A, B, C}. Я хочу определить грамматику, которая распознает все допустимые перестановки любого количества этих элементов.

Синтаксически допустимые строки будут включать:

  • (пустая строка)
  • A,
  • B A и
  • C A B

Синтаксически недопустимые строки будут включать:

  • A A и
  • B A C B

Чтобы было ясно, явное определение всех возможных перестановок в CFG неприемлемо для моих целей, поскольку невозможно поддерживать большие наборы.

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

Обновлять

То, что мне нужно, называется «языком перестановок», который Бенедек Надь проделал некоторую теоретическую работу над расширением контекстно-свободных языков.

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

Своего рода решение этой проблемы было написано в ANTLR. Он использует семантические предикаты, чтобы «кодировать» проблему.


parsing grammar context-free-grammar formal-languages
person drfloob    schedule 26.08.2013    source источник
comment
Язык конечен (хотя он может быть довольно большим), поэтому он определенно регулярен (и, следовательно, не зависит от контекста), поскольку все конечные языки регулярны. (Простое доказательство: язык определяется как конъюнкция всех возможных строк w1|w2|w3|w4...|wlast, что, очевидно, является регулярным выражением.) Этот факт не очень полезен для вас, но все же факт.   -  person rici    schedule 27.08.2013
comment
Кроме того, решение ANTLR — это не взлом, ИМХО. Это (или его эквивалент для другого генератора синтаксического анализатора, который допускает предикаты), вероятно, ваш лучший выбор. В вашем случае вам не нужна проверка, так что это еще проще.   -  person rici    schedule 27.08.2013

Ответы (1)


arrow_upward
1
arrow_downward

Предполагая, что набор альтернативных строк фиксирован и известен заранее, скажем, размера n, можно получить (неконтекстно-свободную) грамматику размера O(n!)< /эм>. Это асимптотически не меньше, чем перечисление всех перестановок, поэтому я полагаю, что это нельзя считать хорошим решением. Я считаю, что эту грамматику можно переформулировать как контекстно-зависимую грамматику (хотя в той форме, которую я предлагаю ниже, это не так).

Для примера {a, b, c}, упомянутого в вопросе, одна из таких грамматик следующая. Я использую строчные буквы для терминальных символов и прописные буквы для нетерминалов, как это принято. S — начальный нетерминальный символ.

S ::= XabcY
XabcY ::= aXbcY | bXacY | cXabY
XabY  ::= ab | ba
XacY  ::= ac | ca
XbcY  ::= bc | cb

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

person nickie    schedule 26.08.2013
comment
Я думаю, что это обычный язык с O(SUMi(C(N,i))) состояний в автоматах, что должно быть намного меньше, чем O(N!). Автоматы будут иметь одно состояние для каждого символа в качестве первого слоя, одно состояние для каждой комбинации символов во втором и так далее до конечного состояния со всеми символами. - person Apalala; 27.08.2013
comment
@Apalala: это 2 ** N, так что да, это меньше, чем N !, но все же довольно велико, если N не очень мало. - person rici; 27.08.2013
comment
@rici 2N возможных состояний или O(2N) памяти, но с линейным синтаксическим анализом, O(N) для любой входной последовательности. Требование к памяти можно обойти, если автоматы собираются на ходу. Это похоже на домашнее задание по теории языка. Задача может быть решена за O(N) алгоритмически. - person Apalala; 27.08.2013
comment
О, насколько я знаю, большинство языков, которые могут быть интересны, требуют семантики, подаваемой в синтаксический анализ. IOW, самые интересные языки не CF. - person Apalala; 27.08.2013
comment
@Apalala: у меня нет аргументов ни по одному пункту. Совершенно очевидно, что проблема может быть решена алгоритмически (с помощью логического вектора visible[token]), но мне кажется, что это больше похоже на практический вопрос анализа, чем на теорию формального языка. Тем не менее, я был вне класса (с любой стороны) слишком долго, чтобы быть уверенным. И этот язык оказывается CF, даже если его неудобно анализировать таким образом. Эта конкретная проблема привлекла определенное внимание много лет назад из-за оператора & в объявлениях SGML, но с тех пор я его не видел. - person rici; 27.08.2013