#grammar #context-free-grammar #repeat
#грамматика #контекстно-свободная грамматика #повторять
Вопрос:
Я изучаю контекстно-свободную грамматику, и я хотел бы знать, как (если вообще) можно разработать язык, который избегает повторений.
Давайте возьмем оператор select из SQL в качестве примера:
possible:
SELECT * FROM table
SELECT * FROM table WHERE x > 5
SELECT * FROM table WHERE x > 5 ORDER desc
SELECT * FROM table WHERE x > 5 ORDER desc LIMIT 5
impossible (multiple conflicting statements):
SELECT * FROM table WHERE X > 5 WHERE X > 5
Грамматика может выглядеть примерно так:
S -> SW | SO | SL | "SELECT statement"
W -> "WHERE statement"
O -> "ORDER statement"
L -> "Limit statement"
Эта грамматика допускала бы невозможное утверждение, подобное упомянутому выше. Как я мог бы разработать контекстно-свободную грамматику, которая позволяет избежать невозможного утверждения, оставаясь при этом гибкой?
Гибкий:
Порядок W, O, L не имеет значения. Также не имеет значения, сколько из этих подзаявлений присутствует. Я хотел бы избежать грамматики, которая просто перечисляет все возможные комбинации, так как это было бы довольно запутанно, если бы было много возможностей.
Комментарии:
1. Ваш пример немного странный: в синтаксисе SQL порядок «ГДЕ», «ПОРЯДОК» и «ПРЕДЕЛ» имеет значение.
Ответ №1:
В контекстно-свободной грамматике набор предложений, генерируемых нетерминалом, одинаков для каждого использования нетерминала. Вот что значит контекстно-свободный. Конкретный нетерминальный, S , иногда не может разрешить совпадение, а в других случаях запрещает его. Таким образом, каждый набор возможных совпадений должен иметь свой собственный нетерминал, и в случае ограничения списка k падежей предложениями без повторяющихся падежей потребуется минимум 2k разных нетерминалов, по одному для каждого подмножества k падежей.
Хуже того, если повторение, которое вы пытаетесь ограничить, имеет неограниченное количество возможностей (например, вы хотите разрешить более одного W предложения, но не разрешать два идентичных W ), то это вообще невозможно сделать с контекстно-свободной грамматикой. То же самое верно, если вы хотите настаивать на таком повторении, что в основном и нужно было бы сделать, чтобы контекстно-свободная грамматика настаивала на объявлении переменных перед использованием.
Однако легко выполнить проверку в семантическом действии, например, сохранив битовый вектор встреченных вами предложений (или хэш-набор, если нелегко перечислить возможные предложения). Тогда семантическое действие для добавления предложения в инструкцию должно только проверять, было ли уже добавлено это конкретное предложение, и помечать ошибку, если она была добавлена. Это также позволит получать более качественные сообщения об ошибках, поскольку вы можете легко описать проблему при ее обнаружении, в отличие от простого сообщения о «синтаксической» ошибке, оставляя пользователю самому догадываться, в чем проблема.
Комментарии:
1. Большое вам спасибо за ваш ответ. Итак, если бы я хотел описать вышеупомянутую проблему, используя контекстно-свободную грамматику, единственным вариантом, который у меня есть, было бы использовать что-то вроде
S -> W | WO | WOL | WL | WLO | "SELECT statement", верно? Таким образом, мне пришлось бы перечислить все комбинации утверждений. Конечно, лучшим вариантом является просто выдача синтаксической ошибки! Большое вам спасибо за этот намек.2. Да, единственное решение с чистым cfg — перечислить все допустимые возможности.
3. В общем, это не так, верно? Я могу записать CFG, которые либо не допускают, либо требуют повторения в строках. В определенных случаях это может быть невозможно, но, боже мой, регулярные выражения могут в определенной степени обеспечивать или запрещать повторение.
4. @patrick87: Да, вы правы. «До некоторой степени» это возможно. Поэтому я переписал ответ, пытаясь быть более точным. Я думаю, когда я писал оригинал, я предполагал, что OP пытается избежать точного дублирования. Но проблема перестановки также не может быть решена без учета контекста, за исключением использования экспоненциального числа нетерминалов, что непрактично, если только вариантов очень мало.
Ответ №2:
Я не уверен, что понимаю вашу проблему на основе грамматики. Возможно, вы имеете в виду, что statement и S являются одним и тем же символом. Если это так, я бы сказал, что ваша грамматика просто не подходит для языка, который вы собираетесь описать. Если мы игнорируем ORDER и LIMIT , то ваша грамматика
S -> SW | "SELECT S" | foo
W -> "WHERE S"
Тогда да, вы можете вывести такую ерунду, как
S -> SW -> SWW -> SWWW -> "SELECT foo WHERE foo WHERE foo WHERE foo"
Но это всего лишь ваша первая попытка грамматики, это не доказывает, что не существует грамматики, которая работает. Рассмотрим это:
<S> -> <A><B>
<A> -> SELECT <C>
<B> -> epsilon | WHERE <D>
<C> -> (rules for select lists)
<D> -> (rules for WHERE condition)
Правила для <C> и <D> могут ссылаться на S и A и B , правильно, возможно, используя круглые скобки, как требуется для создания строк, которые работают для вас. Вы больше не можете получать неверные строки.
На самом деле это не та проблема, которую CFG не могут решить сами по себе. Для выполнения таких действий, как обеспечение того, чтобы можно было использовать только объявленные переменные, да, необходимы контекстно-зависимые или более совершенные механизмы, но мы просто говорим о повторяющихся ключевых словах и фразах. Это вполне укладывается в рамки того, что могут делать CFG. Теперь, если вы хотите поддерживать псевдонимы и применять правильные ссылки на псевдонимы в запросе, это невозможно в контекстно-свободных языках. Но это не то, что мы здесь обсуждаем. Причина, по которой это невозможно, заключается в том, что язык L = {ww | w in E*} не является контекстно-свободным языком, и это, по сути, то, что участвует в применении имен переменных или псевдонимов таблиц.