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

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

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

давайте попробуем построить конкретный пример. Рассмотрим это простое утверждение Кобола:

   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
• почти все, что не нравится: отсутствует ; или }

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

таким образом:

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

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

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

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

чтобы добраться до вашего вопроса! С примером вы упомянуто, ясно, что грамматика c++ не является контекстно-свободной. Язык D, Я абсолютно не знаю, но вы должны быть в состоянии рассуждать об этом сейчас. Подумайте об этом так: в контекстной свободной грамматике нетерминал может расширяться, не принимая во внимание ничего, кроме структуры языка. Подобно тому, что вы сказали, он расширяется, не "глядя" куда-либо еще.

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

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

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

I go there because I want to

или

I jump you that I is air

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

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

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

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

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

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

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

string ::= q" Delim1 Chars newline Delim2 "

где Delim1 и 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");
}

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

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

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

---

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

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

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

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

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

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

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