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

Ответ 1

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

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

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

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

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

Ответ 2

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

В основном это означает, что определение языкового элемента не может измениться в зависимости от того, какие элементы окружают его. По языковым элементам я подразумеваю понятия, такие как выражения и идентификаторы, а не конкретные экземпляры этих понятий внутри программ, например 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 на любом из языков, для которых это действительное утверждение, однако это само по себе не означает, что любой из этих языки не являются свободными от контекста. Вероятно, что вас смущает, так это то, что контекстная свобода отличается от двусмысленности. Это упрощенная версия вашего примера на С++:

a < b > (c)

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

identifier assignment identifier binary-operator identifier semi-colon

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

Ответ 3

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

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

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

В грамматике все равно, что это значит, или если это имеет смысл. Он заботится только о том, что это такое.

Ответ 4

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

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

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 и строка) и переменные. Вы можете делать умножение на целые числа и добавление в строках, но не наоборот.

Первое, что вам нужно, это лексер. Обычно это регулярная грамматика (или равная ей, 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
• Почти все, что не нравится: отсутствует ; или }

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

Итак, вкратце:

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

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

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

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

Чтобы ответить на ваш вопрос! В приведенном выше примере ясно, что грамматика С++ не является контекстно-зависимой. Язык 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 должен в какой-то момент проверить, как что-то было определено в другом месте, просто чтобы сказать, что программа structurally правильная, тогда ее грамматика не является контекстно-зависимой. Если вы изолируете какую-либо часть кода и все еще можете сказать, что она является структурно правильной, то она не имеет контекста.

Ответ 5

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

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

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

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

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

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

Ответ 6

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

string ::= q" Delim1 Chars newline Delim2 "

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

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

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

Ответ 7

Эти ответы заставляют мою голову болеть.

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

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

• он должен обрабатывать макросы и другие материалы препроцессора.
• он должен интерпретировать шаблоны
• он, наконец, интерпретирует ваш код.

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

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

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