Делаю ли я контекстно-свободную грамматику контекстно-зависимой, и имеет ли это значение?

Если у меня есть язык с основными вещами, такими как

a = expression

if expression then ...

while expression do ...

тогда у меня может быть грамматика, которая выглядит так: (псевдокод)

assignment: identifier Equals expression ;
if        : If expression Then ...
while     : While expression Do ...

Теперь тип первого выражения просто должен быть совместим по типу с 'a', но два других выражения должны иметь тип boolean.

В то время как легко проверить тип выражения везде, мне кажется, было бы очень удобно определить в грамматике

boolExpression : expression;

и тогда мои другие правила будут выглядеть так:

assignment: identifier Equals expression ;
if        : If boolExpression Then ...
while     : While boolExpression Do ...

Это позволило бы мне проверить, что boolExpression возвращает тип BOOL, и поэтому мне не пришлось бы добавлять код для проверки каждого выражения.

Но превратил ли я контекстно-свободную грамматику в контекстно-зависимую грамматику, сделав это? И если да, то имеет ли это значение?


antlr4 strong-typing context-free-grammar
person David    schedule 03.02.2018    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Нет, эти изменения не превращают вашу контекстно-свободную грамматику в контекстно-зависимую.

Вы можете увидеть разницу, просто взглянув на левую часть продукции: если каждый LHS является одним символом, это CFG. Если какой-либо LHS имеет несколько символов, то это CSG.

(Это немного упрощение, но достаточно точно, чтобы ответить на ваш вопрос.)

Это грамматика, но когда дело доходит до языков, обратите внимание, что язык, генерируемый вашей грамматикой, отличается от языка программ с допустимым типом. Первый не зависит от контекста, а второй, вероятно, нет.

person Michael Dyck    schedule 04.02.2018
comment
Да, конечно, я прав, потому что не просматривал свои книги по компиляторам в течение 30 лет. Я совершенно забыл значение контекстно-зависимого. Спасибо вам и Ричи за очень полезные комментарии. - person David; 05.02.2018

arrow_upward
2
arrow_downward

Если у вас есть логические переменные, вы не можете синтаксически проверить, является ли выражение логическим или нет. Если вы хотите перехватывать все проверки типов, вам понадобится какая-то семантическая обратная связь, которая действительно сделает язык контекстно-зависимым, а также сделает невозможным синтаксический анализ слева направо, если только вам не потребуются переменные для быть объявлены перед использованием. [См. примечание 1]. Семантическая обратная связь в этой форме обычно считается усложнением, поскольку она создает тесную связь между лексическим анализом и синтаксическим анализом, но многие синтаксические анализаторы делают это либо для удобства, либо по необходимости.

Но, возможно, вы довольствуетесь обнаружением только определенных контекстов. Если это так, ваша грамматика, безусловно, работоспособна и не создает контекстной зависимости. Операторы if и while определенно обеспечивают синтаксически определенный логический контекст. Арифметические операторы обеспечивают определенный числовой контекст (хотя вам может потребоваться проверка типов, если у вас есть несколько арифметических типов). Но есть контексты, которые синтаксически не определяются типом, такие как операторы присваивания, операторы равенства и вызовы функций. Таким образом, вы в конечном итоге будете выполнять проверки типа особого случая в разных местах на прогулке.

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

Заметки

  1. Некоторые языки очень жестко относятся к объявлению перед использованием (например, C), но другие позволяют программисту логически упорядочивать объявления переменных, не беспокоясь о ссылках на них (например, объявления классов C++).

    Лично я предпочитаю не усложнять жизнь программистам, настаивая на объявлении перед использованием. Действительно, как программист я ценю языки, которые могут выводить типы переменных, а не настаивать на избыточных объявлениях. Но вкусы различаются. В любом случае обязательное объявление не обязательно подразумевает объявление перед использованием, и многие языки с обязательным объявлением по-прежнему обеспечивают гибкость в отношении порядка объявления, позволяя (например) взаимно рекурсивные функции без избыточных предварительных объявлений.

person rici    schedule 04.02.2018
comment
Я требую, чтобы переменные были объявлены перед использованием. Это упрощает жизнь программиста, потому что предотвращает использование переменной с ошибкой. Преимущество (или нет) вывода типа выходит за рамки моего вопроса. Определение нетерминала booleanExpression позволяет мне разместить код проверки типов в одном месте, в методе visitBooleanExpression дерева посетителей, вместо того, чтобы добавлять дополнительный код в каждый метод посетителя, использующий выражение. Это казалось весьма полезным, поэтому я задал вопрос о том, действительно ли на практике имеет значение создание контекстно-зависимой грамматики таким образом. - person David; 04.02.2018
comment
@david: И я попытался указать, как это имеет значение на практике. Вы, конечно, можете решить, что эти различия не влияют на ваш вариант использования. (Я не согласен с объявлением перед использованием; C++ также выдает ошибки для переменных с ошибками, не мешая мне собрать все объявления переменных-членов в одном месте. Но это вопрос стиля.) - person rici; 04.02.2018
comment
@david: Однако, прочитав ваш комментарий, я подумал, что, возможно, неправильно понял ваши намерения. Или, по крайней мере, не довел до конца свои мысли. Я попытался переписать ответ в соответствии с этим пересмотром. - person rici; 04.02.2018
comment
Я реализую достаточно простой строго типизированный язык. Поскольку синтаксический анализатор использует ANTLR4 для построения дерева, единственная разница между использованием «expression» и «boolExpression» заключается в том, что я получаю отдельные методы посещения, и поэтому, когда я просматриваю дерево, выполняя семантический анализ и генерацию кода, я могу проверить в одном место, что фактически найденный тип является логическим, вместо того, чтобы вставлять этот код проверки во все места, где я ссылаюсь на выражение, но требую, чтобы тип был логическим. - person David; 04.02.2018
comment
@Дэйвид. Ok. Действуй. - person rici; 04.02.2018
comment
Я только что увидел ваш полный пост - не знаю, почему я не видел его, когда отвечал. Я не проверяю типы на этапе синтаксического анализа (на самом деле мне нравится, что ANTRL4 позволяет вам отложить ВСЕ это до тех пор, пока вы не посетите дерево позже, оставив вам 100% чистую грамматику). Синтаксический анализ по-прежнему не зависит от контекста. Я просто воспользовался преимуществами использования отдельных нетерминалов, чтобы получить отдельные методы посетителей, чтобы я мог консолидировать свою проверку типов, но задавался вопросом, не нарушаю ли я теорию. - person David; 05.02.2018