Я часто слышу заявления о том, что C ++ является контекстно-зависимым языком. Возьмите следующий пример:
a b(c);
Это определение переменной или объявление функции? Это зависит от значения символа c
. Если c
это переменная , то a b(c);
определяет переменную с именем b
типа a
. Это напрямую инициализируется с c
. Но если c
это тип , то a b(c);
объявляет функцию с именем, b
которая принимает c
и возвращает a
.
Если вы посмотрите определение контекстно-свободных языков, оно в основном скажет вам, что все грамматические правила должны иметь левые части, которые состоят ровно из одного нетерминального символа. Контекстно-зависимые грамматики, с другой стороны, допускают произвольные строки терминальных и нетерминальных символов в левой части.
Просматривая Приложение A «Языка программирования C ++», я не смог найти ни одного грамматического правила, в котором было бы что-то еще, кроме одного нетерминального символа в левой части. Это подразумевает, что C ++ не зависит от контекста. (Конечно, каждый контекстно-свободный язык также является контекстно-зависимым в том смысле, что контекстно-свободные языки образуют подмножество контекстно-зависимых языков, но это не главное.)
Итак, является ли C ++ контекстно-зависимым или контекстно-зависимым?
источник
Ответы:
Ниже моя (текущая) любимая демонстрация того, почему синтаксический анализ C ++ (вероятно) является завершением по Тьюрингу , поскольку он показывает программу, синтаксически правильную тогда и только тогда, когда данное целое число является простым.
Поэтому я утверждаю, что C ++ не является ни контекстно-зависимым, ни контекстно-зависимым .
Если вы разрешаете произвольные последовательности символов на обеих сторонах любого производства, вы создаете грамматику типа 0 («неограниченную») в иерархии Хомского , которая является более мощной, чем контекстно-зависимая грамматика; неограниченные грамматики полны по Тьюрингу. Контекстно-зависимая (Тип-1) грамматика допускает несколько символов контекста в левой части продукции, но тот же контекст должен появляться в правой части продукции (отсюда и название «контекстно-зависимая»). [1] Контекстно-зависимые грамматики эквивалентны линейно ограниченным машинам Тьюринга .
В примере программы простое вычисление может быть выполнено с помощью машины Тьюринга с линейными ограничениями, поэтому она не вполне доказывает эквивалентность Тьюринга, но важная часть заключается в том, что синтаксическому анализатору необходимо выполнить вычисления для выполнения синтаксического анализа. Это могли быть любые вычисления, выражаемые как создание экземпляра шаблона, и есть все основания полагать, что создание экземпляра шаблона C ++ является Turing-complete. См., Например, статью Тодда Л. Вельдхуйзена за 2003 год .
В любом случае, C ++ может быть проанализирован компьютером, поэтому он может быть проанализирован машиной Тьюринга. Следовательно, неограниченная грамматика может распознать это. На самом деле написание такой грамматики было бы непрактичным, поэтому стандарт не пытается это сделать. (См. ниже.)
Проблема с «неоднозначностью» некоторых выражений - это в основном красная сельдь. Начнем с того, что двусмысленность - это особенность определенной грамматики, а не языка. Даже если можно доказать, что в языке нет однозначных грамматик, если его можно распознать по контекстно-свободной грамматике, он не зависит от контекста. Точно так же, если он не может быть распознан контекстно-свободной грамматикой, но он может быть распознан контекстно-зависимой грамматикой, он является контекстно-зависимым. Неоднозначность не актуальна.
Но в любом случае, как строка 21 (т.е.
auto b = foo<IsPrime<234799>>::typen<1>();
) в программе ниже, выражения вовсе не являются двусмысленными; они просто анализируются по-разному в зависимости от контекста. В самом простом выражении проблемы синтаксическая категория определенных идентификаторов зависит от того, как они были объявлены (например, типы и функции), что означает, что формальному языку придется признать тот факт, что две строки произвольной длины в одна и та же программа идентична (декларация и использование). Это может быть смоделировано грамматикой «копирования», которая является грамматикой, которая распознает две последовательные точные копии одного и того же слова. Это легко доказать с помощью леммы прокачкичто этот язык не является контекстно-свободным. Для этого языка возможна контекстно-зависимая грамматика, а в ответе на этот вопрос приведена грамматика типа 0: /math/163830/context-sensitive-grammar-for-the- язык копирования .Если бы кто-то попытался написать контекстно-зависимую (или неограниченную) грамматику для синтаксического анализа C ++, вполне возможно, что он заполнит вселенную строчками. Написание машины Тьюринга для разбора C ++ было бы столь же невозможным делом. Даже написание программы на C ++ затруднительно, и, насколько я знаю, ни одна из них не оказалась правильной. Вот почему стандарт не пытается предоставить полную формальную грамматику и почему он предпочитает писать некоторые правила синтаксического анализа на техническом английском языке.
То, что выглядит как формальная грамматика в стандарте C ++, не является полным формальным определением синтаксиса языка C ++. Это даже не полное формальное определение языка после предварительной обработки, которое может быть легче формализовать. (Однако это не был бы язык: язык C ++, как определено стандартом, включает в себя препроцессор, и операция препроцессора описывается алгоритмически, поскольку это было бы чрезвычайно трудно описать в любом грамматическом формализме. Это в этом разделе стандарта, где описывается лексическое разложение, включая правила, в которых оно должно применяться более одного раза.)
Различные грамматики (две накладывающиеся грамматики для лексического анализа, одна из которых имеет место перед предварительной обработкой, а другая, если необходимо, впоследствии, плюс «синтаксическая» грамматика), собраны в Приложении A с этим важным примечанием (выделение добавлено):
Наконец, вот обещанная программа. Строка 21 синтаксически правильна тогда и только тогда, когда N in
IsPrime<N>
простое. Иначе,typen
является целым числом, а не шаблоном, поэтомуtypen<1>()
анализируется как(typen<1)>()
синтаксически неверный, поскольку()
не является синтаксически допустимым выражением.[1] Чтобы выразить это более технически, каждое производство в контекстно-зависимой грамматике должно иметь форму:
αAβ → αγβ
где
A
- нетерминальный иα
,β
возможно , являются пустыми последовательностями грамматических символов иγ
является непустой последовательностью. (Символы грамматики могут быть терминалами или нетерминалами).Это можно прочитать
A → γ
только в контексте[α, β]
. В контекстно-свободной (тип 2) грамматикеα
иβ
должен быть пустым.Оказывается, вы также можете ограничить грамматику с помощью «монотонного» ограничения, где каждое произведение должно иметь форму:
α → β
где|α| ≥ |β| > 0
(|α|
означает "длинаα
")Можно доказать, что набор языков, распознаваемых монотонными грамматиками, точно такой же, как набор языков, распознаваемых контекстно-зависимыми грамматиками, и часто бывает проще основывать доказательства на монотонных грамматиках. Следовательно, довольно часто можно увидеть, что «контекстно-зависимый» используется, как если бы он означал «монотонный».
источник
0
внутрь()
, для простого), но я думаю, что это более интересно, потому что это демонстрирует, что вам нужно создание экземпляра шаблона даже для распознавания, если строка является синтаксически правильной программой C ++. Если обе ветви компилируются, то мне пришлось бы работать усерднее, чтобы оспорить аргумент, что разница "семантическая". Любопытно, что хотя мне часто приходится давать определение «синтаксическому», никто никогда не предлагал определения «семантического», кроме «материала, который я не считаю синтаксическим» :)Во-первых, вы правильно заметили, что в грамматике в конце стандарта C ++ нет контекстно-зависимых правил, поэтому грамматика не зависит от контекста.
Однако эта грамматика точно не описывает язык C ++, потому что она производит программы не на C ++, такие как
или
Язык C ++, определенный как «набор правильно сформированных программ на C ++», не является контекстно-свободным (можно показать, что просто требовательные переменные, которые должны быть объявлены, делают это так). Учитывая, что вы можете теоретически писать программы, полные по Тьюрингу, в шаблонах и делать программу плохо сформированной на основе их результатов, она даже не зависит от контекста.
Теперь (невежественные) люди (обычно не теоретики языка, а разработчики синтаксических анализаторов) обычно используют слова «не контекстно-зависимые» в некоторых из следующих значений
Грамматика в конце стандарта не удовлетворяет этим категориям (т. Е. Она неоднозначна, а не LL (k) ...), поэтому грамматика C ++ для них «не контекстно-свободна». И в некотором смысле, они правы, чертовски сложно создать работающий синтаксический анализатор C ++.
Обратите внимание, что используемые здесь свойства слабо связаны с контекстно-свободными языками - неоднозначность не имеет ничего общего с контекстно-зависимым (на самом деле контекстно-зависимые правила обычно помогают устранить неоднозначность в продуктах), остальные два являются просто подмножествами контекста языки. И разбор контекстно-свободных языков не является линейным процессом (хотя разбор детерминированных есть).
источник
ambiguity doesn't have anything to do with context-sensitivity
Это тоже была моя интуиция, поэтому я рад видеть кого-то (а) согласного и (б) объяснить, где я не мог. Я полагаю, что это дисквалифицирует все аргументы, которые основаныa b(c);
, и частично удовлетворяет первоначальному вопросу, предпосылкой которого были «часто слышимые» утверждения о чувствительности к контексту из-за неоднозначности ... особенно, когда для грамматики фактически нет двусмысленности даже в MVP.Да. Следующее выражение имеет различный порядок операций в зависимости от типа разрешенного контекста :
Редактировать: Когда фактический порядок операций меняется, это делает невероятно трудным использование «обычного» компилятора, который анализирует недекорированный AST перед его украшением (распространение информации о типе). Другие упомянутые контекстно-зависимые вещи являются «довольно простыми» по сравнению с этим (не то, чтобы оценка шаблона вообще была легкой).
С последующим:
источник
Чтобы ответить на ваш вопрос, вам нужно выделить два разных вопроса.
Простой синтаксис почти каждого языка программирования не зависит от контекста. Как правило, это дается в виде расширенной формы Бэкуса-Наура или грамматики без контекста.
Однако, даже если программа соответствует грамматике без контекста, определенной языком программирования, она не обязательно является допустимой программой. Есть много неконтекстных попертисов, которым должна соответствовать программа, чтобы быть действительной программой. Например, самым простым таким свойством является область видимости переменных.
Чтобы сделать вывод, является ли C ++ контекстно-зависимым, зависит от того, какой вопрос вы задаете.
источник
VARDECL : TYPENAME IDENTIFIER
, но у вас его не будет, потому что вы не можете отличить имена типов от других идентификаторов на уровне CF. Другой пример: на уровне CF вы не можете решить, анализировать ли этоa*b
как объявление переменной (b
с указателем типа наa
) или как умножение.Возможно, вы захотите взглянуть на дизайн и эволюцию C ++ , Бьярн Страуструп. В нем он описывает свои проблемы, пытаясь использовать yacc (или аналогичный) для анализа ранней версии C ++, и желая, чтобы он использовал вместо этого рекурсивный спуск.
источник
Да, C ++ является контекстно-зависимым, очень контекстно-зависимым. Вы не можете построить синтаксическое дерево, просто проанализировав файл с помощью синтаксического анализатора без контекста, потому что в некоторых случаях вам нужно знать символ из предыдущих знаний, чтобы принять решение (т.е. построить таблицу символов при синтаксическом анализе).
Первый пример:
Это выражение умножения?
ИЛИ
Это объявление
B
переменной, чтобы быть указателем типаA
?Если A - переменная, то это выражение, если A - тип, это объявление указателя.
Второй пример:
Это прототип функции, принимающий аргумент
bar
типа?ИЛИ
Является ли это объявить переменную
B
типаA
и вызывает конструктор А сbar
константой в качестве инициализатора?Вы должны снова знать,
bar
является ли переменная или тип из таблицы символов.Третий пример:
Это тот случай, когда построение таблицы символов во время синтаксического анализа не помогает, потому что объявление x и y идет после определения функции. Поэтому вам нужно сначала просмотреть определение класса и просмотреть определения методов во втором проходе, чтобы сказать, что x * y - это выражение, а не объявление указателя или что-то еще.
источник
A B();
является объявлением функции даже в определении функции. Ищите самый неприятный анализ ...C ++ анализируется с помощью анализатора GLR. Это означает, что во время синтаксического анализа исходного кода анализатор может столкнуться с неоднозначностью, но он должен продолжить и решить, какое грамматическое правило использовать позже .
смотри также,
Почему C ++ не может быть проанализирован с помощью анализатора LR (1)?
Помните, что контекстно-свободная грамматика не может описывать ВСЕ правила синтаксиса языка программирования. Например, грамматика атрибута используется для проверки правильности типа выражения.
Вы не можете описать следующее правило с помощью контекстно-свободной грамматики: правая сторона задания должна быть того же типа, что и левая сторона.
источник
У меня есть ощущение, что есть некоторая путаница между формальным определением «контекстно-зависимым» и неформальным использованием «контекстно-зависимым». Первый имеет четко определенный смысл. Последний используется для выражения «вам нужен контекст для анализа входных данных».
Это также спрашивается здесь: Контекст-чувствительность против неоднозначности .
Вот контекстно-свободная грамматика:
Это неоднозначно, поэтому для анализа входных данных «х» вам нужен некоторый контекст (или жить с неоднозначностью, или выдать «Предупреждение: E8271 - Ввод строки неоднозначен в строке 115»). Но это определенно не контекстно-зависимая грамматика.
источник
Ни один подобный Алголу язык не является контекстно-свободным, потому что у них есть правила, которые ограничивают выражения и операторы, в которых идентификаторы могут появляться в зависимости от их типа, и потому что нет никаких ограничений на количество операторов, которые могут произойти между объявлением и использованием.
Обычное решение состоит в том, чтобы написать не зависящий от контекста синтаксический анализатор, который фактически принимает расширенный набор допустимых программ и помещает чувствительные к контексту части в специальный «семантический» код, присоединенный к правилам.
C ++ выходит далеко за рамки этого благодаря своей полной шаблонной системе Turing. См. Вопрос переполнения стека 794015 .
источник
Правда :)
Дж. Стэнли Уорфорд. Компьютерные системы . Страницы 341-346.
источник
Иногда это хуже: что люди имеют в виду, когда говорят, что C ++ имеет «неразрешимую грамматику»?
источник
Он является контекстно-зависимым, так как
a b(c);
имеет два допустимых синтаксических анализа - объявление и переменную. Когда вы говорите «Еслиc
это тип», это контекст, прямо здесь, и вы точно описали, как C ++ чувствителен к нему. Если у вас не было этого контекста "Что естьc
?" Вы не могли бы разобрать это однозначно.Здесь контекст выражается в выборе токенов - синтаксический анализатор считывает идентификатор как токен имени типа, если он называет тип. Это простейшее решение, и оно позволяет избежать значительной сложности, связанной с контекстом (в данном случае).
Изменить: Есть, конечно, больше вопросов чувствительности к контексту, я просто сосредоточился на том, что вы показали. Шаблоны особенно противны для этого.
источник
a<b<c>>d
, верно? (Ваш пример на самом деле является классическим из C , где он является единственным препятствием для отсутствия контекста.)Продукция в стандарте C ++ написана без контекста, но, как мы все знаем, на самом деле не определяет язык точно. Некоторые из того, что большинство людей воспринимают как двусмысленность в текущем языке, могут (я считаю) быть решены однозначно с помощью контекстно-зависимой грамматики.
Для наиболее наглядного примера, давайте рассмотрим раздосадовать Разбор:
int f(X);
. ЕслиX
это значение, то оно определяетсяf
как переменная, которая будет инициализированаX
. ЕслиX
это тип, он определяетсяf
как функция, принимающая единственный параметр типаX
.Глядя на это с грамматической точки зрения, мы можем рассмотреть это так:
Конечно, чтобы быть полностью правильными, нам нужно было бы добавить некоторые дополнительные «вещи», чтобы учесть возможность вмешательства объявлений других типов (т. Е. A и B должны действительно быть «объявлениями, включающими объявление X как ...»). или что-то в этом порядке).
Это все еще довольно сильно отличается от типичной CSG (или, по крайней мере, то, что я о них помню). Это зависит от создаваемой таблицы символов - той части, которая определенно распознает
X
как тип или значение, а не просто некоторый тип оператора, предшествующего этому, но правильный тип оператора для правильного символа / идентификатора.Как таковой, я должен был бы сделать некоторые взгляды, чтобы быть уверенным, но мое непосредственное предположение - то, что это действительно не квалифицируется как CSG, по крайней мере, поскольку термин обычно используется.
источник
Самый простой случай неконтекстной грамматики включает в себя синтаксический анализ выражений с использованием шаблонов.
Это можно разобрать как
Или
Для устранения двух неоднозначных значений AST можно использовать только объявление «a» - первое AST, если «a» является шаблоном, или второе, если нет.
источник
<
если это может быть скобка (например, она следует за идентификатором, который называет шаблон). В C ++ 11 добавлено требование, чтобы>
и первый символ>>
интерпретировался как закрывающие скобки, если такое использование правдоподобно. Это влияет на синтаксический анализ,a<b>c>
гдеa
находится шаблон, но не влияет наa<b<c>
.a();
(что либоexpr.call
илиexpr.type.conv
)?Было показано, что шаблоны C ++ являются мощными по Тьюрингу. Хотя это и не официальная ссылка, здесь есть место, чтобы взглянуть на это:
http://cpptruths.blogspot.com/2005/11/c-templates-are-turing-complete.html
Я рискну предположить (столь же старый, как фольклорное и краткое доказательство CACM, показывающее, что ALGOL в 60-х годах не может быть представлен CFG) и скажу, что C ++ не может быть правильно проанализирован только CFG. CFGs в сочетании с различными механизмами TP на проходе дерева или во время редукционных событий - это другая история. В общем смысле, из-за проблемы остановки, существует некоторая программа на C ++, которая не может быть показана правильной / неправильной, но тем не менее правильной / неправильной.
{PS - Как автор Meta-S (упомянутый несколькими людьми выше) - я могу с уверенностью сказать, что Thothic не является более не существующей, и программное обеспечение не доступно бесплатно. Возможно, я сформулировал эту версию своего ответа так, чтобы меня не удаляли и не голосовали до -3.}
источник
C ++ не является контекстно-свободным. Я узнал это некоторое время назад в лекции компиляторов. Быстрый поиск дал эту ссылку, где раздел «Синтаксис или семантика» объясняет, почему C и C ++ не являются контекстно-свободными:
Обсуждение Википедии: Грамматика без контекста
С уважением,
Ованес
источник
Очевидно, что если принять дословный вопрос, почти все языки с идентификаторами являются контекстно-зависимыми.
Нужно знать, является ли идентификатор именем типа (именем класса, именем, введенным typedef, параметром шаблона typename), именем шаблона или каким-либо другим именем, чтобы можно было правильно использовать идентификатор. Например:
является приведением, если
name
это имя типа и вызов функции, еслиname
это имя функции. Другой случай - это так называемый «самый неприятный анализ», когда невозможно различить определение переменной и объявление функции (есть правило, гласящее, что это объявление функции).Эта трудность привела к необходимости
typename
иtemplate
с зависимыми именами. Насколько я знаю, остальная часть C ++ не является контекстно-зависимой (то есть для нее можно написать контекстно-свободную грамматику).источник
Правильная ссылка на разбор enigines
Meta-S был собственностью несуществующей компании под названием Thothic. Я могу отправить бесплатную копию Meta-S всем, кто интересуется ею, и я использовал ее в исследованиях анализа РНА. Обратите внимание, что «грамматика псевдоузла», включенная в папки с примерами, была написана программистом, не занимающимся биоинформатикой, и в основном не работает. Мои грамматики используют другой подход и работают довольно хорошо.
источник
Большая проблема здесь заключается в том, что термины «контекстно-свободный» и «контекстно-зависимый» немного не интуитивны в компьютерной науке. Для C ++ чувствительность к контексту очень похожа на неоднозначность, но это не обязательно так в общем случае.
В C / ++ оператор if разрешен только внутри тела функции. Казалось бы, это делает его контекстно-зависимым, верно? Ну нет. Для контекстно-свободных грамматик фактически не требуется свойство, в котором вы можете извлечь некоторую строку кода и определить, является ли она действительной. Это не совсем то, что означает контекстно-свободный. Это действительно просто лейбл, который в некоторой степени подразумевает что-то вроде того, на что это похоже.
Теперь, если оператор в теле функции анализируется по-разному в зависимости от того, что определено вне непосредственных грамматических предков (например, описывает ли идентификатор тип или переменную), как в
a * b;
случае, то он, на самом деле, является контекстно-зависимым. Здесь нет никакой реальной двусмысленности; он будет проанализирован как объявление указателя, еслиa
тип и умножение в противном случае.Быть чувствительным к контексту не обязательно означает «трудно разобрать». C на самом деле не так уж и сложен, потому что печально известная
a * b;
«неоднозначность» может быть решена с помощью таблицы символов, содержащейtypedef
s, с которой встречались ранее. Для решения этого случая не требуется каких-либо произвольных реализаций шаблонов (которые, как было доказано, выполнено с помощью Turing Complete), как это иногда делает C ++. На самом деле невозможно написать программу на C, которая не будет компилироваться за конечное время, даже если она имеет ту же чувствительность к контексту, что и C ++.Python (и другие языки, чувствительные к пробелам) также зависит от контекста, так как он требует состояния в лексере для генерирования маркеров отступа и отступа, но это не усложняет анализ, чем обычная грамматика LL-1. На самом деле он использует генератор синтаксических анализаторов, что является частью того, почему в Python есть такие неинформативные сообщения об ошибках синтаксиса. Здесь также важно отметить, что
a * b;
в Python нет «неоднозначности», подобной проблеме, дающей хороший конкретный пример контекстно-зависимого языка без «неоднозначной» грамматики (как упоминалось в первом абзаце).источник
В этом ответе говорится, что C ++ не является контекстно-свободным ... есть смысл (не отвечающий), что он не может быть проанализирован, и в ответе предлагается пример сложного кода, который создает недопустимую программу на C ++, если определенная константа не является простое число.
Как заметили другие, вопрос о том, является ли язык контекстно-зависимым / свободным, отличается от того же вопроса о конкретной грамматике.
Чтобы поставить вопрос о синтаксическом разборе на отдых, я предлагаю эмпирическое доказательство того, что существуют неконтекстные грамматики для C ++, которые можно использовать для создания AST для неконтекстного анализа исходного текста, фактически анализируя его с помощью существующего GLR. -parser-инструмент, основанный на явной грамматике.
Да, это удается, «принимая слишком много»; не все, что она принимает, является допустимой программой на C ++, поэтому за ней следуют дополнительные проверки (проверки типов). И да, проверка типов может столкнуться с проблемами вычислимости. На практике инструменты не имеют этой проблемы; если бы люди писали такие программы, ни одна из них не скомпилировалась бы. (Я думаю, что стандарт на самом деле накладывает ограничение на количество вычислений, которые вы можете выполнить, разворачивая шаблон, поэтому на самом деле вычисления на самом деле конечны, но, вероятно, довольно большие).
Если вы имеете в виду, определите , является ли исходная программа членом набора допустимых исходных программ на C ++ , тогда я соглашусь, что проблема намного сложнее. Но проблема не в разборе .
Инструмент решает эту проблему, изолируя анализ от проверки типа анализируемой программы. (Если существует несколько интерпретаций в отсутствие контекста, он записывает узел неоднозначности в дереве разбора с несколькими возможными анализами; проверка типа решает, какая из них правильная, и удаляет недопустимые поддеревья). Вы можете увидеть (частичное) дерево разбора в примере ниже; все дерево слишком велико, чтобы уместиться в SO-ответе. Обратите внимание, что вы получаете дерево разбора независимо от того, используется ли значение 234797 или 234799.
Запуск средства определения имени / типа инструмента по AST с исходным значением 234799 завершается успешно. При значении 234797 преобразователь имен завершается неудачно (как и ожидалось) с сообщением об ошибке «typen не является типом». и, следовательно, эта версия не является допустимой программой C ++.
источник