Как разработать контекстную грамматику без повторений? - PullRequest
Новая
       58

Как разработать контекстную грамматику без повторений?

1 голос
/ 06 апреля 2019

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

Давайте возьмем в качестве примера оператор выбора из 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 не имеет значения.Также не имеет значения, сколько из этих вложенных утверждений присутствует.Я хотел бы избежать грамматики, которая просто перечисляет все возможные комбинации, так как это будет довольно грязно, если есть много возможностей.

Ответы [ 2 ]

3 голосов
/ 06 апреля 2019

В грамматике без контекста набор предложений, генерируемых нетерминалом, одинаков для каждого использования нетерминала.Вот что значит контекстно-свободный.Определенный нетерминал, S, иногда не может разрешить совпадение, а иногда запрещает его.Таким образом, каждый набор возможных совпадений должен иметь свой собственный нетерминал, и в случае ограничения списка k случаев предложениями без повторяющихся случаев потребуется минимум 2<sup>k</sup> различных нетерминалов, по одному на каждыйподмножество k случаев.

Хуже того, если повторение, которое вы пытаетесь ограничить, имеет неограниченное количество возможностей (например, вы хотите разрешить более одного предложения W, но не разрешить два идентичных W s), тогдаэто вообще невозможно сделать с помощью контекстно-свободной грамматики.То же самое верно, если вы хотите настаивать на таком повторении, что, в сущности, вам необходимо сделать, чтобы не зависящая от контекста грамматика настаивала на объявлении переменных перед использованием.

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

0 голосов
/ 08 апреля 2019

Я не уверен, что понимаю вашу проблему на основе грамматики. Возможно, вы подразумеваете, что 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*} не является контекстно-свободным языком, и это, по сути, то, что используется для принудительного применения имен переменных или псевдонимов таблиц.

...