Уже есть много хороших ответов, но поскольку вы не осведомлены о грамматиках, парсерах, компиляторах и т. Д., Позвольте мне продемонстрировать это на примере.
Во-первых, концепция грамматики довольно интуитивна.Представьте себе набор правил:
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 в объявлении соответствует вычисляемому.
В любом случае, я просто хотел дать вам идею.Итак, все эти вещи являются контекстно-зависимыми:
- Проверка типа
- Количество аргументов для функции
- значение по умолчанию для функции
- if
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
или
I jump you that I is air
Как видите, второе имеет правильную структуру, но не имеет смысла.Что касается грамматики без контекста, значение не имеет значения.Он просто расширяет verb до любого глагола, не «глядя» на остальную часть предложения.
Итак, если вы думаете, что D должен в какой-то момент проверить, как что-то определено в другом месте, просто сказать, что программа структурно правильно, тогда его грамматика не является контекстно-свободной.Если вы изолируете какую-либо часть кода и он все еще может сказать, что он структурно корректен, то он не зависит от контекста.