Действительно ли грамматика D контекстно-свободна?

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

Обычно контекстно-свободное определение распространяется с грамматик на язык, утверждая, что язык является контекстно-свободным, если существует по крайней мере одна контекстно-свободная грамматика, описывающая его.

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

Говоря, что C ++ не является контекстно-независимым, люди имеют в виду, что это разделение невозможно удобным способом (с удобным включением в качестве критериев "почти соответствует описанию официального языка" и "мой инструмент генератора синтаксического анализатора поддерживает такое разделение "; разрешение грамматики быть неоднозначным, а неоднозначность разрешена семантической проверкой - это относительно простой способ сделать сокращение для C ++ и полностью следовать стандарту C ++, но это неудобно, когда вы полагаетесь на инструменты, которые не допускают неоднозначной грамматики, когда у вас есть такие инструменты, это удобно).

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

Свойство быть контекстно-свободным - очень формальная концепция; вы можете найти определение здесь. Обратите внимание, что это применимо к грамматикам: язык считается контекстно-свободным, если существует хотя бы одна контекстно-свободная грамматика, которая его распознает. Обратите внимание, что могут быть и другие грамматики, возможно, не связанные с контекстом, которые распознают тот же язык.

В основном это означает, что определение языкового элемента не может меняться в зависимости от того, какие элементы его окружают. Под элементами языка я имею в виду такие понятия, как выражения и идентификаторы, а не конкретные экземпляры этих понятий внутри программ, такие как a + b или count.

Попробуем построить конкретный пример. Рассмотрим этот простой оператор COBOL:

   01 my-field PICTURE 9.9 VALUE 9.9.

Здесь я определяю поле, то есть переменную, размер которой рассчитан на хранение одной целой цифры, десятичной точки и одной десятичной цифры с начальным значением 9.9. Неполная грамматика для этого может быть:

field-declaration ::= level-number identifier 'PICTURE' expression 'VALUE' expression '.'
expression ::= digit+ ( '.' digit+ )

К сожалению, допустимые выражения, которые могут следовать за PICTURE, не являются теми же действительными выражениями, которые могут следовать за VALUE. Я мог бы переписать вторую продукцию в своей грамматике следующим образом:

'PICTURE' expression ::= digit+ ( '.' digit+ ) | 'A'+ | 'X'+
'VALUE' expression ::= digit+ ( '.' digit+ )

Это сделает мою грамматику контекстно-зависимой, потому что expression будет другим, в зависимости от того, был ли он найден после 'PICTURE' или после 'VALUE'. Однако, как было указано, это ничего не говорит о базовом языке. Лучшей альтернативой было бы:

field-declaration ::= level-number identifier 'PICTURE' format 'VALUE' expression '.'
format ::= digit+ ( '.' digit+ ) | 'A'+ | 'X'+
expression ::= digit+ ( '.' digit+ )

который не зависит от контекста.

Как видите, это сильно отличается от вашего понимания. Учитывать:

a = b + c;

Вы очень мало можете сказать об этом утверждении, не просматривая объявления a, b и c, на любом из языков, для которых это утверждение является допустимым, однако это само по себе не означает, что какой-либо из этих языков не является контекст свободный. Возможно, вас сбивает с толку тот факт, что свобода контекста отличается от двусмысленности. Это упрощенная версия вашего примера на C ++:

a < b > (c)

Это неоднозначно, поскольку, глядя только на него, вы не можете сказать, является ли это вызовом шаблона функции или логическим выражением. С другой стороны, предыдущий пример не является двусмысленным; С точки зрения грамматики это можно интерпретировать только как:

identifier assignment identifier binary-operator identifier semi-colon

В некоторых случаях вы можете разрешить двусмысленность, введя контекстную чувствительность на уровне грамматики. Я не думаю, что это относится к приведенному выше неоднозначному примеру: в этом случае вы не можете устранить двусмысленность, не зная, является ли a шаблоном или нет. Обратите внимание: когда такая информация недоступна, например, когда она зависит от конкретной специализации шаблона, язык предоставляет способы устранения неоднозначности: вот почему вам иногда приходится использовать typename для ссылки на определенные типы в шаблонах или использовать template, когда вы вызовите шаблоны функций-членов.

Уже есть много хороших ответов, но, поскольку вы не знакомы с грамматиками, синтаксическими анализаторами, компиляторами и т. Д., Позвольте мне продемонстрировать это на примере.

Во-первых, понятие грамматики довольно интуитивно понятно. Представьте себе набор правил:

S -> a T
T -> b G t
T -> Y d
b G -> a Y b
Y -> c
Y -> lambda (nothing)

И представьте, что вы начинаете с S. Заглавные буквы не являются терминалами, а маленькие буквы - терминалами. Это означает, что если вы получите предложение всех терминалов, вы можете сказать, что грамматика сгенерировала это предложение как «слово» в языке. Представьте себе такие замены с приведенной выше грамматикой (заменяется фраза между * фразами *):

*S* -> a *T* -> a *b G* t -> a a *Y* b t -> a a b t

Итак, я мог создать aabt с этой грамматикой.

Хорошо, вернемся к основной строке.

Предположим, простой язык. У вас есть числа, два типа (int и string) и переменные. Вы можете выполнять умножение целых чисел и сложение строк, но не наоборот.

Первое, что вам понадобится, это лексер. Это обычно обычная грамматика (или равнозначная ей, DFA или, в равной степени, регулярное выражение), которая соответствует программным токенам. Их принято выражать в регулярных выражениях. В нашем примере:

(Я придумываю эти синтаксисы)

number: [1-9][0-9]*    // One digit from 1 to 9, followed by any number
                       // of digits from 0-9
variable: [a-zA-Z_][a-zA-Z_0-9]*  // You get the idea. First a-z or A-Z or _
                                  // then as many a-z or A-Z or _ or 0-9
                                  // this is similar to C
int: 'i' 'n' 't'
string: 's' 't' 'r' 'i' 'n' 'g'
equal: '='
plus: '+'
multiply: '*'

whitespace: (' ' or '\n' or '\t' or '\r')*   // to ignore this type of token

Итак, теперь у вас есть обычная грамматика, токенизирующая ваш ввод, но она ничего не понимает в структуре.

Тогда вам понадобится парсер. Синтаксический анализатор обычно является контекстно-свободной грамматикой. Грамматика без контекста означает, что в грамматике есть только один нетерминал в левой части правил грамматики. В примере в начале этого ответа правило

b G -> a Y b

делает грамматику контекстно чувствительной, потому что слева у вас b G, а не только G. Что это значит?

Что ж, когда вы пишете грамматику, каждый из нетерминалов имеет значение. Напишем для нашего примера неконтекстную грамматику (| означает или. Как если бы в одной строке было написано много правил):

program -> statement program | lambda
statement -> declaration | executable
declaration -> int variable | string variable
executable -> variable equal expression
expression -> integer_type | string_type
integer_type -> variable multiply variable |
                variable multiply number |
                number multiply variable |
                number multiply number
string_type -> variable plus variable

Теперь эта грамматика может принять этот код:

x = 1*y
int x
string y
z = x+y

Грамматически это правильный код. Итак, вернемся к тому, что означает «контекстно-свободный». Как вы можете видеть в приведенном выше примере, когда вы раскрываете executable, вы генерируете один оператор формы variable = operand operator operand без какого-либо учета того, в какой части кода вы находитесь. Будь то самое начало или середина, определены ли переменные или нет, или совпадают ли типы, вы не знаете, и вам все равно.

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

executable -> variable equal expression

у вас должно быть что-то вроде:

declaration some_code executable -> declaration some_code variable equal expression

однако более сложно убедиться, что variable в объявлении совпадает с вычисляемым.

В любом случае, я просто хотел дать вам идею. Итак, все эти вещи контекстно-зависимы:

• Проверка типа
• Количество аргументов функции
• значение по умолчанию для работы
• если member существует в obj в коде: obj.member
• Почти все, что не похоже: отсутствует ; или }

Надеюсь, вы поняли, в чем разница (если нет, я буду более чем счастлив объяснить).

Итак, в итоге:

• Lexer использует обычную грамматику для токенизации ввода
• Parser использует контекстно-свободную грамматику, чтобы убедиться, что программа имеет правильную структуру.
• Семантический анализатор использует контекстно-зависимую грамматику для проверки типов, сопоставления параметров и т. Д.

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

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

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

Чтобы перейти к вашему вопросу! В приведенном вами примере ясно, что грамматика C ++ не является контекстно-зависимой. Я понятия не имею о языке D, но теперь вы можете рассуждать о нем. Подумайте об этом так: в контекстно-свободной грамматике нетерминал может расширяться, не принимая во внимание ничего, НО структуру языка. Подобно тому, что вы сказали, оно расширяется, никуда не «глядя».

Знакомый пример - естественные языки. Например, на английском вы скажете:

sentence -> subject verb object clause
clause -> .... | lambda

Ну, sentence и clause здесь нетерминалы. С помощью этой грамматики вы можете составить следующие предложения:

I go there because I want to

or

I jump you that I is air

Как видите, второй имеет правильную структуру, но не имеет смысла. Если речь идет о грамматике, свободной от контекста, значение не имеет значения. Он просто заменяется verb на любой глагол, не «глядя» на остальную часть предложения.

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

В лексере D есть конструкция:

string ::= q" Delim1 Chars newline Delim2 "

где Delim1 и Delim2 - совпадающие идентификаторы, а Chars не содержит новую строку Delim2.

Эта конструкция зависит от контекста, поэтому грамматика лексера D зависит от контекста.

Прошло несколько лет с тех пор, как я много работал с грамматикой D, поэтому я не могу вспомнить все проблемные места с головы до ног, или даже если какие-либо из них делают грамматику синтаксического анализатора D контекстно-зависимой, но я считаю, что они нет. Вспоминая, я бы сказал, что грамматика D контекстно-свободна, а не LL (k) для любого k, и в ней есть досадная двусмысленность.

Грамматика не может быть контекстно-свободной, если мне нужно, я не могу определить тип выражения, просто взглянув на него.

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

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

Грамматике все равно, что это значит, и имеет ли это смысл. Его волнует только то, что это есть.

Чтобы ответить на вопрос, является ли язык программирования контекстно-свободным, вы должны сначала решить, где провести грань между синтаксисом и семантикой. В качестве крайнего примера, в C недопустимо, чтобы программа использовала значения некоторых видов целых чисел после того, как им было разрешено переполнение. Ясно, что это нельзя проверить во время компиляции, не говоря уже о времени синтаксического анализа:

void Fn() {
  int i = INT_MAX;
  FnThatMightNotReturn();  // halting problem?
  i++;
  if(Test(i)) printf("Weeee!\n");
}

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

В качестве практического определения я бы начал с вопроса: Можете ли вы правильно и однозначно определить дерево синтаксического анализа всех правильных программ, используя контекстно-свободную грамматику, и для всех некорректных программ (которые требует отклонения языка) либо отклонить их как синтаксически недопустимые или создать дерево синтаксического анализа, которое последующие передачи могут определить как недопустимые и отклонить?

Учитывая, что наиболее правильной спецификацией для синтаксиса D является синтаксический анализатор (IIRC - синтаксический анализатор LL), я сильно подозреваю, что он на самом деле контекстно-свободный по определению, которое я предложил.

Примечание: приведенное выше ничего не говорит о том, какую грамматику использует языковая документация или данный парсер, только если существует контекстно-свободная грамматика. Кроме того, единственной полной документацией на языке D является исходный код компилятора DMD.

От этих ответов у меня болит голова.

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

В C ++ (порядок может быть отключен, но это не должно отменять мою точку зрения):

1. он должен обрабатывать макросы и другие вещи препроцессора
2. он должен интерпретировать шаблоны
3. наконец он интерпретирует ваш код.

Поскольку первый шаг может изменить контекст второго шага, а второй шаг может изменить контекст третьего шага, язык, на котором ВЫ пишете (включая все эти шаги), зависит от контекста.

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

Большинство языков в целом контекстно-зависимы, но у большинства языков есть только эти незначительные исключения из контекста.