383

Вопрос по grammar, context-sensitive-grammar, c++, syntax, context-free-grammar – Является ли C ++ контекстно-зависимым или контекстно-зависимым?

Я часто слышу заявления о том, что C ++ является контекстно-зависимым языком. Возьмите следующий пример:

a b(c);

Это определение переменной или объявление функции? Это зависит от значения символаc, Еслиc этоvariable, затемa b(c); определяет переменную с именемb типаa, Это непосредственно инициализируется сc, Но еслиc этоtype, затемa b(c); объявляет функцию с именемb это занимаетc и возвращаетa.

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

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

Итак, является ли C ++ контекстно-зависимым или контекстно-зависимым?

IIUC это немного зависит от того, где вы проводите черту для чувствительности к контексту. Я думаю, что я видел, как люди утверждают, что почти все статически типизированные языки программирования являются контекстно-зависимыми, не потому, что вы не можете создать для них практический компилятор с помощью инструментов синтаксического анализа CFG, а потому, что такие реализации & quot; cheat & quot; анализируя некоторые некорректные программы и отклоняя их только позже, во время проверки типа. Таким образом, если вы считаете, что плохо напечатанные программы не на языке (в смысле CS, то есть на наборе строк), синтаксический анализатор должен принять, больше языков, чем C ++, являются контекстно-зависимыми.

от user395760

@CarlNorum Пожалуйста, покажите мне одно грамматическое правило C ++, которое не состоит из единственного нетерминального символа в левой части, и я сразу же поверю вам.

от fredoverflow

@DeadMG: нет, вы не правы. Нет "разбора" или "семантика" в теории формального языка вообще, просто «язык» который представляет собой набор строк.

от jpalecek

УвидетьIs D's grammar really context-free?, На самом деле, я думаю,everybody Здесь следует прочитать этот вопрос и его ответы!

от Lightness Races in Orbit

До сих пор ни один из ответов не отвечал вашему определению «контекстно-свободной грамматики». На мой взгляд, правильный ответ на этот вопрос либо ссылается на продукцию в приложении А, которая не соответствует вашему определению, либо демонстрирует, что ваше определение неверно или недостаточно. Стоять на своем!

от Lightness Races in Orbit
19 ответов
2

C ++ не является контекстно-свободным. Я узнал это некоторое время наз

ад в лекции компиляторов. Быстрый поиск дал эту ссылку, где "Синтаксис или семантика" В разделе объясняется, почему C и C ++ не являются контекстно-свободными:

Обсуждение Википедии: Грамматика без контекста

С Уважением,
Ованес

5

Самый простой случай неконтекстной грамматики включает в себя синтакси

ческий анализ выражений с использованием шаблонов.

a<b<c>()

Это можно разобрать как

template
   |
   a < expr > ()
        |
        <
      /   \
     b     c

Или же

 expr
   |
   <
 /   \
a   template
     |
     b < expr > ()
          |
          c

Эти два AST могут быть устранены только путем изучения декларации «a»; - бывший AST if 'a'; шаблон или последний, если нет.

@rici: упс, я не понял, что это асимметрично.

от 

Вы описываетеambiguityили контекстная чувствительность?

от 

@aaron: как это проще, чемa(); (который либоexpr.call или жеexpr.type.conv)?

от 

Я полагаю, что C ++ 11 требует последней интерпретации, и вы должны добавить парены, чтобы подписаться на первую.

от 

@ ДжозефГарвин, нет. С ++ обязывает, что< должен быть скобкой, если это может быть (например, он следует за идентификатором, который называет шаблон). C ++ 11 добавил требование, чтобы> и первый персонаж>> интерпретировать как закрывающие скобки, если такое использование правдоподобно. Это влияет на разборa<b>c> гдеa шаблон, но не влияет наa<b<c>.

от 
10

Да

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

Первый пример:

A*B;

Это выражение умножения?

ИЛИ ЖЕ

Это декларацияB переменная, чтобы быть указателем типаA?

Если A является переменной, то это выражение, если A является типом, это объявление указателя.

Второй пример:

A B(bar);

Это прототип функции, принимающий аргументbar тип?

ИЛИ ЖЕ

Это объявить переменнуюB типаA и вызывает конструктор A с помощьюbar константа как инициализатор?

Вам нужно знать еще раз,bar переменная или тип из таблицы символов.

Третий пример:

class Foo
{
public:
    void fn(){x*y;}
    int x, y;
};

Это тот случай, когда построение таблицы символов во время синтаксического анализа не помогает, потому что объявление x и y идет после определения функции. Поэтому вам нужно сначала просмотреть определение класса и просмотреть определения методов во втором проходе, чтобы сказать, что x * y - это выражение, а не объявление указателя или что-то еще.

& quot; Синтаксическое дерево нельзя построить, просто проанализировав файл & quot; ЛОЖНЫЙ. Смотри мой ответ.

от 

A B(); является объявлением функции даже в определении функции. Ищите самый неприятный анализ ...

от 
5

Ни один подобный Алголу язык не является контекстно-свободным

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

Обычное решение состоит в том, чтобы написать не зависящий от контекста парсер, который фактически принимает расширенный набор допустимых программ и помещает чувствительные к контексту части вad hoc & Quot; семантическая & Quot; код прикреплен к правилам.

C ++ выходит далеко за рамки этого благодаря своей полной шаблонной системе Turing. УвидетьВопрос о переполнении стека 794015.

23

Чтобы ответить на ваш вопрос, вам нужно выделить два разных вопроса.

The mere syntax of almost every programming language is context-free. Typically, it is given as an extended Backus-Naur form or context-free gramar.

However, even if a program conforms with the context-free gramar defined by the programming language, it is not necessarily a valid program. There are many non-context-free poperties that a program has to satisfy in order to be a valid program. E.g., the most simple such property is the scope of variables.

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

Интересно отметить, что вам часто приходится указывать «простой синтаксис»; уровень ниже, чем вы ожидаете, чтобы получить CFG для вашего языка программирования. Взять, к примеру, С. Вы можете подумать, что правило грамматики для простого объявления переменной в C будетVARDECL : TYPENAME IDENTIFIER, но тыcannot есть, потому что вы не можете отличить имена типов от других идентификаторов на уровне CF. Другой пример: на уровне CF вы не можете решить, нужно ли анализироватьa*b как объявление переменной (b указатель типа наa) или как умножение.

от 

@ Дан: то, о чем вы говорите, является приближением языка, заданного некоторой контекстно-свободной грамматикой. Конечно, такое приближение по определению не имеет контекста. В этом смысле "синтаксис" часто используется при обсуждении языков программирования.

от 

@LaC: Да, спасибо за указание на это! Кстати, я уверен, что есть более часто используемый технический термин дляmere syntax, У кого-нибудь правильный термин?

от 
60

Да. Следующее выражение имеет другое

order of operations в зависимости отtype resolved context:

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

#if FIRST_MEANING
   template<bool B>
   class foo
   { };
#else
   static const int foo = 0;
   static const int bar = 15;
#endif

С последующим:

static int foobar( foo < 2 ? 1 < 1 : 0 > & bar );

Почему эта проблема не может быть решена, как в случае с C, если вспомнить, какие определения типов находятся в области видимости?

от 

@Blaisorblade: один из способов сделать компилятор "чистым" состоит в том, чтобы разделить задачи на независимые шаги в цепочке, такие как создание дерева разбора из входных данных, за которым следует шаг, который выполняет анализ типов. C ++ вынуждает вас либо: 1) объединить эти шаги в один или 2) проанализировать документ в соответствии с обоими / всеми возможными интерпретациями и позволить этапам разрешения типов сузить его до правильной интерпретации.

от 

@ 280Z28: согласен, но это касается и C; Я думаю, что хороший ответ на этот вопрос должен показать, почему C ++ хуже, чем C. Тезис PhD, связанный здесь, делает это:stackoverflow.com/a/243447/53974

от 
8

У меня есть ощущение

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

Это также спрашивается здесь: Чувствительность к контексту против неоднозначности.

Вот контекстно-свободная грамматика:

<a> ::= <b> | <c>
<b> ::= "x"
<c> ::= "x"

Это неоднозначно, поэтому для анализа входных данных "х" вам нужен какой-то контекст (или жить с неоднозначностью, или выдать "Предупреждение: E8271 - В строке 115 ввод неоднозначен"). Но это определенно не контекстно-зависимая грамматика.

Я думаю C ++is формально контекстно-зависимый, но проблема, с которой я сталкиваюсь, заключается в том, что я не понимаю, как контекстно-зависимая грамматика будет иметь больший успех при разборе C ++, чем CFG.

от 

Мой ответ в ответ на первое предложение: «Я часто слышу заявления о том, что C ++ является контекстно-зависимым языком». Если в этих утверждениях используется выражение «зависимый от контекста» неофициально, то проблем нет. Я не думаю, что C ++ формально является контекстно-зависимым.

от 

Как наличие нескольких символов на левой стороне производства решает эту проблему? Я не думаю, что этот ответ отвечает на вопрос.

от 
-4

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

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

Чтобы поставить вопрос о разборе отдыха на отдых, я предлагаю эмпирическое доказательство того, что существуют неконтекстные грамматики для C ++, которые можно использовать создать AST для неконтекстного анализа исходного текста фактически анализируя его с помощью существующего инструмента на основе синтаксического анализатора GLR, который управляется явной грамматикой.

Да, это удается, "принимая слишком много"; не все, что она принимает, является допустимой программой на C ++, поэтому за ней следуют дополнительные проверки (проверки типов). И да, проверка типов может столкнуться с проблемами вычислимости. На практике инструменты не имеют этой проблемы; если бы люди писали такие программы, ни одна из них не скомпилировалась бы. (Я думаю, что стандарт на самом деле накладывает ограничение на количество вычислений, которые вы можете выполнить, разворачивая шаблон, поэтому на самом деле вычисления на самом деле конечны, но, вероятно, довольно большие).

Если вы имеете в виду,determine if the source program is a member of the set of valid C++ source programsтогда я соглашусь проблема намного сложнее. Но это не такparsing это проблема.

Инструмент решает эту проблему, изолируя анализ от проверки типов разобранная программа. (Там, где есть несколько интерпретаций в отсутствие контекста он записываетambiguity узел в дереве разбора с несколькими возможными разборами; тип проверка решает, какой из них является правильным и устраняет недействительное поддеревья). Вы можете увидеть (частичное) дерево разбора в примере ниже; все дерево слишком велико, чтобы уместиться в SO-ответе. Обратите внимание, что вы получаете дерево разбора независимо от того, используется ли значение 234797 или 234799.

Запуск средства определения имени / типа инструмента по AST с исходным значением 234799 завершается успешно. При значении 234797 преобразователь имен завершается неудачно (как и ожидалось) с сообщением об ошибке "typen не является типом". и, следовательно, эта версия не является допустимой программой C ++.

967 tree nodes in tree.
15 ambiguity nodes in tree.
([email protected]~GCC5=2#6b11a20^0 Line 1 Column 1 File C:/temp/prime_with_templates.cpp
 ([email protected]~GCC5=1021#6b06640^1#6b11a20:1 {10} Line 1 Column 1 File C:/temp/prime_with_templates.cpp
  ([email protected]~GCC5=1022#6b049a0^1#6b06640:1 Line 1 Column 1 File C:/temp/prime_with_templates.cpp
   ([email protected]~GCC5=1036#6b04980^1#6b049a0:1 Line 1 Column 1 File C:/temp/prime_with_templates.cpp
   |([email protected]~GCC5=2079#6b04960^1#6b04980:1 Line 1 Column 1 File C:/temp/prime_with_templates.cpp
   | ([email protected]~GCC5=2082#6afbde0^1#6b04960:1 Line 1 Column 10 File C:/temp/prime_with_templates.cpp
   |  ([email protected]~GCC5=2085#6afbd80^1#6afbde0:1 Line 1 Column 10 File C:/temp/prime_with_templates.cpp
   |   ([email protected]~GCC5=1611#6afbd40^1#6afbd80:1 Line 1 Column 10 File C:/temp/prime_with_templates.cpp
   |   |([email protected]~GCC5=1070#6afb880^1#6afbd40:1 Line 1 Column 10 File C:/temp/prime_with_templates.cpp
   |   | ([email protected]~GCC5=1073#6afb840^1#6afb880:1 Line 1 Column 10 File C:/temp/prime_with_templates.cpp
   |   |  ([email protected]~GCC5=1118#6afb7e0^1#6afb840:1 Line 1 Column 10 File C:/temp/prime_with_templates.cpp
   |   |   ([email protected]~GCC5=1138#6afb7a0^1#6afb7e0:1 Line 1 Column 10 File C:/temp/prime_with_templates.cpp)simple_type_specifier
   |   |  )trailing_type_specifier#6afb7e0
   |   | )decl_specifier#6afb840
   |   |)basic_decl_specifier_seq#6afb880
   |   |([email protected]~GCC5=1417#6afbc40^1#6afbd40:2 Line 1 Column 15 File C:/temp/prime_with_templates.cpp
   |   | ([email protected]~GCC5=1421#6afbba0^1#6afbc40:1 Line 1 Column 15 File C:/temp/prime_with_templates.cpp
   |   |  ([email protected]~GCC5=1487#6afbb80^1#6afbba0:1 Line 1 Column 15 File C:/temp/prime_with_templates.cpp
   |   |   ([email protected]~GCC5=317#6afbaa0^1#6afbb80:1 Line 1 Column 15 File C:/temp/prime_with_templates.cpp
   |   |   |([email protected]~GCC5=319#6afb9c0^1#6afbaa0:1 Line 1 Column 15 File C:/temp/prime_with_templates.cpp
   |   |   | ([email protected]~GCC5=3368#6afb780^1#6afb9c0:1[`V'] Line 1 Column 15 File C:/temp/prime_with_templates.cpp)IDENTIFIER
   |   |   |)unqualified_id#6afb9c0
   |   |   )id_expression#6afbaa0
   |   |  )declarator_id#6afbb80
   |   | )noptr_declarator#6afbba0
   |   |)ptr_declarator#6afbc40
   |   )parameter_declaration#6afbd40
   |  )template_parameter#6afbd80
   | )template_parameter_list#6afbde0
   | ([email protected]~GCC5=1033#6b04940^1#6b04960:2 Line 1 Column 18 File C:/temp/prime_with_templates.cpp
   |  ([email protected]~GCC5=1050#6b04920^1#6b04940:1 Line 1 Column 18 File C:/temp/prime_with_templates.cpp
   |   ([email protected]~GCC5=1060#6b04900^1#6b04920:1 Line 1 Column 18 File C:/temp/prime_with_templates.cpp
   |   |([email protected]~GCC5=1070#6b048e0^1#6b04900:1 Line 1 Column 18 File C:/temp/prime_with_templates.cpp
   |   | ([email protected]~GCC5=1073#6b048c0^1#6b048e0:1 Line 1 Column 18 File C:/temp/prime_with_templates.cpp
   |   |  ([email protected]~GCC5=1110#6b048a0^1#6b048c0:1 Line 1 Column 18 File C:/temp/prime_with_templates.cpp
   |   |   ([email protected]~GCC5=1761#6b04880^1#6b048a0:1 Line 1 Column 18 File C:/temp/prime_with_templates.cpp
   |   |   |([email protected]~GCC5=1763#6afb980^1#6b04880:1 Line 1 Column 18 File C:/temp/prime_with_templates.cpp
   |   |   | ([email protected]~GCC5=1791#6afbca0^1#6afb980:1 Line 1 Column 18 File C:/temp/prime_with_templates.cpp)class_key
   |   |   | ([email protected]~GCC5=3368#6afbcc0^1#6afb980:2[`answer'] Line 1 Column 25 File C:/temp/prime_with_templates.cpp)IDENTIFIER
   |   |   | ([email protected]~GCC5=1872#6afba60^1#6afb980:3 Line 1 Column 32 File C:/temp/prime_with_templates.cpp)optional_base_clause
   |   |   |)class_head#6afb980
   |   |   |([email protected]~GCC5=1794#6b042e0^1#6b04880:2 {2} Line 1 Column 34 File C:/temp/prime_with_templates.cpp
   |   |   | ([email protected]~GCC5=1806#6b04060^1#6b042e0:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
   |   |   |  (member_declarat[email protected]~GCC5=1822#6b04040^1#6b04060:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
   |   |   |   ([email protected]~GCC5=1632#6b04020^1#6b04040:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
   |   |   |   |([email protected]~GCC5=1673#6afbec0^1#6b04020:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
   |   |   |   | ([email protected]~GCC5=1417#6afbfe0^1#6afbec0:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
   |   |   |   |  ([email protected]~GCC5=1422#6afbf80^1#6afbfe0:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
   |   |   |   |   ([email protected]~GCC5=1421#6afbf60^1#6afbf80:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |([email protected]~GCC5=1487#6afbea0^1#6afbf60:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
   |   |   |   |   | ([email protected]~GCC5=317#6afbb40^1#6afbea0:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |  ([email protected]~GCC5=319#6afbc80^1#6afbb40:1 Line 1 Column 34 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |   ([email protected]~GCC5=3368#6afbc20^1#6afbc80:1[`answer'] Line 1 Column 34 File C:/temp/prime_with_templates.cpp)IDENTIFIER
   |   |   |   |   |  )unqualified_id#6afbc80
   |   |   |   |   | )id_expression#6afbb40
   |   |   |   |   |)declarator_id#6afbea0
   |   |   |   |   )noptr_declarator#6afbf60
   |   |   |   |   ([email protected]~GCC5=1559#6afbd00^1#6afbf80:2 Line 1 Column 41 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |([email protected]~GCC5=1570#6afb940^1#6afbd00:1 Line 1 Column 41 File C:/temp/prime_with_templates.cpp
   |   |   |   |   | ([email protected]~GCC5=1574#6afb800^1#6afb940:1 Line 1 Column 41 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |  ([email protected]~GCC5=1610#6afb9a0^1#6afb800:1 Line 1 Column 41 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |   ([email protected]~GCC5=1070#6afbf40^1#6afb9a0:1 Line 1 Column 41 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |   |([email protected]~GCC5=1073#6afbfa0^1#6afbf40:1 Line 1 Column 41 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |   | ([email protected]~GCC5=1118#6afbfc0^1#6afbfa0:1 Line 1 Column 41 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |   |  ([email protected]~GCC5=1140#6afb860^1#6afbfc0:1 Line 1 Column 41 File C:/temp/prime_with_templates.cpp)simple_type_specifier
   |   |   |   |   |   | )trailing_type_specifier#6afbfc0
   |   |   |   |   |   |)decl_specifier#6afbfa0
   |   |   |   |   |   )basic_decl_specifier_seq#6afbf40
   |   |   |   |   |  )parameter_declaration#6afb9a0
   |   |   |   |   | )pp_parameter_declaration_seq#6afb800
   |   |   |   |   |)pp_parameter_declaration_list#6afb940
   |   |   |   |   )parameter_declaration_clause#6afbd00
   |   |   |   |   ([email protected]~GCC5=1438#6afbce0^1#6afbf80:3 Line 1 Column 46 File C:/temp/prime_with_templates.cpp)function_qualifiers
   |   |   |   |  )noptr_declarator#6afbf80
   |   |   |   | )ptr_declarator#6afbfe0
   |   |   |   |)function_head#6afbec0
   |   |   |   |([email protected]~GCC5=1680#6b04000^1#6b04020:2 Line 1 Column 46 File C:/temp/prime_with_templates.cpp
   |   |   |   | ([email protected]~GCC5=888#6afbee0^1#6b04000:1 Line 1 Column 46 File C:/temp/prime_with_templates.cpp)compound_statement
   |   |   |   |)function_body#6b04000
   |   |   |   )function_definition#6b04020
   |   |   |  )member_declaration#6b04040
   |   |   | )member_declaration_or_access_specifier#6b04060
   |   |   | ([email protected]~GCC5=1806#6b042c0^1#6b042e0:2 Line 1 Column 49 File C:/temp/prime_with_templates.cpp
   |   |   |  ([email protected]~GCC5=1822#6b04820^1#6b042c0:1 Line 1 Column 49 File C:/temp/prime_with_templates.cpp
   |   |   |   ([email protected]~GCC5=1632#6b04280^1#6b04820:1 Line 1 Column 49 File C:/temp/prime_with_templates.cpp
   |   |   |   |([email protected]~GCC5=1674#6b04220^1#6b04280:1 Line 1 Column 49 File C:/temp/prime_with_templates.cpp
   |   |   |   | ([email protected]~GCC5=1070#6b040e0^1#6b04220:1 Line 1 Column 49 File C:/temp/prime_with_templates.cpp
   |   |   |   |  ([email protected]~GCC5=1073#6b040c0^1#6b040e0:1 Line 1 Column 49 File C:/temp/prime_with_templates.cpp
   |   |   |   |   ([email protected]~GCC5=1118#6b040a0^1#6b040c0:1 Line 1 Column 49 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |([email protected]~GCC5=1138#6b04080^1#6b040a0:1 Line 1 Column 49 File C:/temp/prime_with_templates.cpp)simple_type_specifier
   |   |   |   |   )trailing_type_specifier#6b040a0
   |   |   |   |  )decl_specifier#6b040c0
   |   |   |   | )basic_decl_specifier_seq#6b040e0
   |   |   |   | ([email protected]~GCC5=1417#6b04200^1#6b04220:2 Line 1 Column 54 File C:/temp/prime_with_templates.cpp
   |   |   |   |  ([email protected]~GCC5=1422#6b041e0^1#6b04200:1 Line 1 Column 54 File C:/temp/prime_with_templates.cpp
   |   |   |   |   ([email protected]~GCC5=1421#6b041a0^1#6b041e0:1 Line 1 Column 54 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |([email protected]~GCC5=1487#6b04180^1#6b041a0:1 Line 1 Column 54 File C:/temp/prime_with_templates.cpp
   |   |   |   |   | ([email protected]~GCC5=317#6b04160^1#6b04180:1 Line 1 Column 54 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |  ([email protected]~GCC5=320#6b04140^1#6b04160:1 Line 1 Column 54 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |   ([email protected]~GCC5=2027#6b04120^1#6b04140:1 Line 1 Column 54 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |   |([email protected]~GCC5=2070#6b04100^1#6b04120:1 Line 1 Column 62 File C:/temp/prime_with_templates.cpp)operator
   |   |   |   |   |   )operator_function_id#6b04120
   |   |   |   |   |  )unqualified_id#6b04140
   |   |   |   |   | )id_expression#6b04160
   |   |   |   |   |)declarator_id#6b04180
   |   |   |   |   )noptr_declarator#6b041a0
   |   |   |   |   ([email protected]~GCC5=1558#6afba40^1#6b041e0:2 Line 1 Column 65 File C:/temp/prime_with_templates.cpp)parameter_declaration_clause
   |   |   |   |   ([email protected]~GCC5=1438#6b041c0^1#6b041e0:3 Line 1 Column 66 File C:/temp/prime_with_templates.cpp)function_qualifiers
   |   |   |   |  )noptr_declarator#6b041e0
   |   |   |   | )ptr_declarator#6b04200
   |   |   |   |)function_head#6b04220
   |   |   |   |([email protected]~GCC5=1680#6b04300^1#6b04280:2 Line 1 Column 66 File C:/temp/prime_with_templates.cpp
   |   |   |   | ([email protected]~GCC5=889#6b04760^1#6b04300:1 Line 1 Column 66 File C:/temp/prime_with_templates.cpp
   |   |   |   |  ([email protected]~GCC5=894#6b04780^1#6b04760:1 Line 1 Column 67 File C:/temp/prime_with_templates.cpp
   |   |   |   |   ([email protected]~GCC5=857#6b04440^1#6b04780:1 Line 1 Column 67 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |([email protected]~GCC5=1011#6afba80^1#6b04440:1 Line 1 Column 67 File C:/temp/prime_with_templates.cpp
   |   |   |   |   | ([email protected]~GCC5=551#6b04380^1#6afba80:1 Line 1 Column 74 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |  ([email protected]~GCC5=543#6b04360^1#6b04380:1 Line 1 Column 74 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |   ([email protected]~GCC5=465#6b04340^1#6b04360:1 Line 1 Column 74 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |   |([email protected]~GCC5=307#6b04320^1#6b04340:1 Line 1 Column 74 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |   | ([email protected]~GCC5=317#6b042a0^1#6b04320:1 Line 1 Column 74 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |   |  ([email protected]~GCC5=319#6b04260^1#6b042a0:1 Line 1 Column 74 File C:/temp/prime_with_templates.cpp
   |   |   |   |   |   |   ([email protected]~GCC5=3368#6b04240^1#6b04260:1[`V'] Line 1 Column 74 File C:/temp/prime_with_templates.cpp)IDENTIFIER
   |   |   |   |   |   |  )unqualified_id#6b04260
   |   |   |   |   |   | )id_expression#6b042a0
   |   |   |   |   |   |)primary_expression#6b04320
   |   |   |   |   |   )unary_expression#6b04340
   |   |   |   |   |  )cast_expression#6b04360
   |   |   |   |   | )pm_expression#6b04380
   |   |   |   |   |)jump_statement#6afba80
   |   |   |   |   )statement#6b04440
   |   |   |   |  )pp_statement_seq#6b04780
   |   |   |   | )compound_statement#6b04760
   |   |   |   |)function_body#6b04300
   |   |   |   )function_definition#6b04280
   |   |   |  )member_declaration#6b04820
   |   |   | )member_declaration_or_access_specifier#6b042c0
   |   |   |)member_specification#6b042e0
   |   |   )class_specifier#6b04880
   |   |  )type_specifier#6b048a0
   |   | )decl_specifier#6b048c0
   |   |)basic_decl_specifier_seq#6b048e0
   |   )simple_declaration#6b04900
   |  )block_declaration#6b04920
   | )declaration#6b04940
   |)template_declaration#6b04960
   )declaration#6b04980
  )pp_declaration_seq#6b049a0
  ([email protected]~GCC5=1022#6b06620^1#6b06640:2 Line 3 Column 1 File C:/temp/prime_with_templates.cpp
   ([email protected]~GCC5=1036#6b06600^1#6b06620:1 Line 3 Column 1 File C:/temp/prime_with_templates.cpp
   |([email protected]~GCC5=2079#6b065e0^1#6b06600:1 Line 3 Column 1 File C:/temp/prime_with_templates.cpp
   | ([email protected]~GCC5=2083#6b05460^1#6b065e0:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
   |  ([email protected]~GCC5=2083#6b05140^1#6b05460:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
   |   ([email protected]~GCC5=2083#6b04ee0^1#6b05140:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
   |   |([email protected]~GCC5=2082#6b04cc0^1#6b04ee0:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
   |   | ([email protected]~GCC5=2085#6b04ca0^1#6b04cc0:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
   |   |  ([email protected]~GCC5=1611#6b04c80^1#6b04ca0:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
   |   |   ([email protected]~GCC5=1070#6b04a40^1#6b04c80:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
   |   |   |([email protected]~GCC5=1073#6b04a20^1#6b04a40:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
   |   |   | ([email protected]~GCC5=1118#6b04a00^1#6b04a20:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp
   |   |   |  ([email protected]~GCC5=1138#6b049e0^1#6b04a00:1 Line 3 Column 10 File C:/temp/prime_with_templates.cpp)simple_type_specifier
   |   |   | )trailing_type_specifier#6b04a00
   |   |   |)decl_specifier#6b04a20
   |   |   )basic_decl_specifier_seq#6b04a40
   |   |   ([email protected]~GCC5=1417#6b04c40^1#6b04c80:2 Line 3 Column 15 File C:/temp/prime_with_templates.cpp
   |   |   |([email protected]~GCC5=1421#6b04be0^1#6b04c40:1 Line 3 Column 15 File C:/temp/prime_with_templates.cpp
   |   |   | ([email protected]~GCC5=1487#6b04bc0^1#6b04be0:1 Line 3 Column 15 File C:/temp/prime_with_templates.cpp
   |   |   |  ([email protected]~GCC5=317#6b04b60^1#6b04bc0:1 Line 3 Column 15 File C:/temp/prime_with_templates.cpp
   |   |   |   ([email protected]~GCC5=319#6b04ac0^1#6b04b60:1 Line 3 Column 15 File C:/temp/prime_with_templates.cpp
   |   |   |   |([email protected]~GCC5=3368#6b049c0^1#6b04ac0:1[`no'] Line 3 Column 15 File C:/temp/prime_with_templates.cpp)IDENTIFIER
   |   |   |   )unqualified_id#6b04ac0
   |   |   |  )id_expression#6b04b60
   |   |   | )declarator_id#6b04bc0
   |   |   |)noptr_declarator#6b04be0
   |   |   )ptr_declarator#6b04c40
   |   |  )parameter_declaration#6b04c80
   |   | )template_parameter#6b04ca0
   |   |)template_parameter_list#6b04cc0
   |   |([email protected]~GCC5=2085#6b04ec0^1#6b04ee0:2 Line 3 Column 19 File C:/temp/prime_with_templates.cpp
   |   | ([email protected]~GCC5=1611#6b04ea0^1#6b04ec0:1 Line 3 Column 19 File C:/temp/prime_with_templates.cpp
   |   |  ([email protected]~GCC5=1070#6b04b40^1#6b04ea0:1 Line 3 Column 19 File C:/temp/prime_with_templates.cpp
   |   |   ([email protected]~GCC5=1073#6b04ba0^1#6b04b40:1 Line 3 Column 19 File C:/temp/prime_with_templates.cpp
   |   |   |(trailing_typ[email protected]~GCC5=1118#6b04c60^1#6b04ba0:1 Line 3 Column 19 File C:/temp/prime_with_templates.cpp
   |   |   | ([email protected]~GCC5=1138#6b04580^1#6b04c60:1 Line 3 Column 19 File C:/temp/prime_with_templates.cpp)simple_type_specifier
   |   |   |)trailing_type_specifier#6b04c60
   |   |   )decl_specifier#6b04ba0
   |   |  )basic_decl_specifier_seq#6b04b40
   |   |  ([email protected]~GCC5=1417#6b04e60^1#6b04ea0:2 Line 3 Column 24 File C:/temp/prime_with_templates.cpp
   |   |   ([email protected]~GCC5=1421#6b04e40^1#6b04e60:1 Line 3 Column 24 File C:/temp/prime_with_templates.cpp
   |   |   |([email protected]~GCC5=1487#6b04de0^1#6b04e40:1 Line 3 Column 24 File C:/temp/prime_with_templates.cpp
   |   |   | ([email protected]~GCC5=317#6b04d80^1#6b04de0:1 Line 3 Column 24 File C:/temp/prime_with_templates.cpp
   |   |   |  ([email protected]~GCC5=319#6b04ce0^1#6b04d80:1 Line 3 Column 24 File C:/temp/prime_with_templates.cpp
   |   |   |   ([email protected]~GCC5=3368#6b04560^1#6b04ce0:1[`yes'] Line 3 Column 24 File C:/temp/prime_with_templates.cpp)IDENTIFIER
   |   |   |  )unqualified_id#6b04ce0
   |   |   | )id_expression#6b04d80
   |   |   |)declarator_id#6b04de0
   |   |   )noptr_declarator#6b04e40
   |   |  )ptr_declarator#6b04e60
   |   | )parameter_declaration#6b04ea0
   |   |)template_parameter#6b04ec0
   |   )template_parameter_list#6b04ee0
   |   ([email protected]~GCC5=2085#6b05120^1#6b05140:2 Line 3 Column 29 File C:/temp/prime_with_templates.cpp
   |   |([email protected]~GCC5=1611#6b05100^1#6b05120:1 Line 3 Column 29 File C:/temp/prime_with_templates.cpp
   |   | ([email protected]~GCC5=1070#6b04d20^1#6b05100:1 Line 3 Column 29 File C:/temp/prime_with_templates.cpp
   |   |  ([email protected]~GCC5=1073#6b04dc0^1#6b04d20:1 Line 3 Column 29 File C:/temp/prime_with_templates.cpp
   |   |   ([email protected]~GCC5=1118#6b04e80^1#6b04dc0:1 Line 3 Column 29 File C:/temp/prime_with_templates.cpp
   |   |   |([email protected]~GCC5=1140#6b046e0^1#6b04e80:1 Line 3 Column 29 File C:/temp/prime_with_templates.cpp)simple_type_specifier
   |   |   )trailing_type_specifier#6b04e80
   |   |  )decl_specifier#6b04dc0
   |   | )basic_decl_specifier_seq#6b04d20
   |   | ([email protected]~GCC5=1417#6b05080^1#6b05100:2 Line 3 Column 33 File C:/temp/prime_with_templates.cpp
   |   |  ([email protected]~GCC5=1421#6b05020^1#6b05080:1 Line 3 Column 33 File C:/temp/prime_with_templates.cpp
   |   |   ([email protected]~GCC5=1487#6b05000^1#6b05020:1 Line 3 Column 33 File C:/temp/prime_with_templates.cpp
   |   |   |([email protected]~GCC5=317#6b04fa0^1#6b05000:1 Line 3 Column 33 File C:/temp/prime_with_templates.cpp
   |   |   | ([email protected]~GCC5=319#6b04f00^1#6b04fa0:1 Line 3 Column 33 File C:/temp/prime_with_templates.cpp
   |   |   |  ([email protected]~GCC5=3368#6b046c0^1#6b04f00:1[`f'] Line 3 Column 33 File C:/temp/prime_with_templates.cpp)IDENTIFIER
   |   |   | )unqualified_id#6b04f00
   |   |   |)id_expression#6b04fa0
   |   |   )declarator_id#6b05000
   |   |  )noptr_declarator#6b05020
   |   | )ptr_declarator#6b05080
   |   |)parameter_declaration#6b05100
   |   )template_parameter#6b05120
   |  )template_parameter_list#6b05140
   |  ([email protected]~GCC5=2085#6b05440^1#6b05460:2 Line 3 Column 36 File C:/temp/prime_with_templates.cpp
   |   ([email protected]~GCC5=1611#6b05420^1#6b05440:1 Line 3 Column 36 File C:/temp/prime_with_templates.cpp
   |   |([email protected]~GCC5=1070#6b05160^1#6b05420:1 Line 3 Column 36 File C:/temp/prime_with_templates.cpp
   |   | ([email protected]~GCC5=1073#6b04fe0^1#6b05160:1 Line 3 Column 36 File C:/temp/prime_with_templates.cpp
   |   |  ([email protected]~GCC5=1118#6b050e0^1#6b04fe0:1 Line 3 Column 36 File C:/temp/prime_with_templates.cpp
   |   |   ([email protected]~GCC5=1140#6b050c0^1#6b050e0:1 Line 3 Column 36 File C:/temp/prime_with_templates.cpp)simple_type_specifier
   |   |  )trailing_type_specifier#6b050e0
   |   | )decl_specifier#6b04fe0
   |   |)basic_decl_specifier_seq#6b05160
   |   |([email protected]~GCC5=1417#6b053e0^1#6b05420:2 Line 3 Column 40 File C:/temp/prime_with_templates.cpp
   |   | ([email protected]~GCC5=1421#6b053c0^1#6b053e0:1 Line 3 Column 40 File C:/temp/prime_with_templates.cpp
   |   |  ([email protected]~GCC5=1487#6b05360^1#6b053c0:1 Line 3 Column 40 File C:/temp/prime_with_templates.cpp
   |   |   ([email protected]~GCC5=317#6b05280^1#6b05360:1 Line 3 Column 40 File C:/temp/prime_with_templates.cpp
   |   |   |([email protected]~GCC5=319#6b051a0^1#6b05280:1 Line 3 Column 40 File C:/temp/prime_with_templates.cpp
   |   |   | ([email protected]~GCC5=3368#6b046a0^1#6b051a0:1[`p'] Line 3 Column 40 File C:/temp/prime_with_templates.cpp)IDENTIFIER
   |   |   |)unqualified_id#6b051a0
   |   |   )id_expression#6b05280
   |   |  )declarator_id#6b05360
   |   | )noptr_declarator#6b053c0
   |   |)ptr_declarator#6b053e0
   |   )parameter_declaration#6b05420
   |  )template_parameter#6b05440
   | )template_parameter_list#6b05460

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

от 

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

от 

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

от 
4

Произведения в стандарте C ++ написаны без контекста

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

В качестве наиболее очевидного примера рассмотрим наиболее сложный анализ:int f(X);, ЕслиX это значение, то это определяетf как переменная, которая будет инициализирована сX, ЕслиX это тип, он определяетf как функция, принимающая единственный параметр типаX.

Глядя на это с грамматической точки зрения, мы можем рассмотреть это так:

A variable_decl ::= <type> <identifier> '(' initializer ')' ';'

B function_decl ::= <type> <identifier> '(' param_decl ')' ';'

A ::= [declaration of X as value]
B ::= [declaration of X as type]

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

Это все еще довольно сильно отличается от типичной CSG (или, по крайней мере, то, что я о них помню). Это зависит от создаваемой таблицы символов - той части, которая специально распознаетX как тип или значение, не просто некоторый тип оператора, предшествующего этому, но правильный тип оператора для правильного символа / идентификатора.

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

Продукция (без контекста) достаточно хорошо определяет наиболее неприятный синтаксический анализ, чтобы его можно было проанализировать с помощью механизма синтаксического анализа. Это отодвигает проблему принятия решения о том, какая из нескольких интерпретаций действительна до тех пор, пока анализ не будет завершен, но это только упрощает разработку синтаксического анализатора и преобразователя имен, поскольку они являются модульными, а не запутанными, как в обычных синтаксических анализаторах C ++. Смотрите AST для наиболее неприятного анализа:stackoverflow.com/questions/17388771/…

от 
111

Во-первых

вы правильно заметили, что в грамматике в конце стандарта C ++ нет контекстно-зависимых правил, так что грамматикаis контекстно-свободный.

Однако эта грамматика не совсем точно описывает язык C ++, потому что она производит программы не на C ++, такие как

int m() { m++; }

или же

typedef static int int;

Язык C ++, определенный как «набор правильно сформированных программ C ++» не является контекстно-свободным (можно показать, что только требовательные переменные, которые должны быть объявлены, делают это так). Учитывая, что вы можете теоретически писать программы, полные по Тьюрингу, в шаблонах и делать программу плохо сформированной на основе их результатов, она даже не зависит от контекста.

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

ambiguous can't be parsed with Bison not LL(k), LR(k), LALR(k) ,or whatever parser-defined language class they chose

Грамматика в конце стандарта не удовлетворяет этим категориям (то есть она неоднозначна, а не LL (k) ...), поэтому грамматика C ++ «не является контекстно-свободной». для них. И в некотором смысле, они правы, чертовски трудно создать работающий синтаксический анализатор C ++.

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

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

от 

ambiguity doesn't have anything to do with context-sensitivity Это тоже была моя интуиция, поэтому я рад видеть кого-то (а) согласного и (б) объяснить, где я не мог. Я считаю, что это дисквалифицирует все аргументы, которые основаны наa b(c);и частично удовлетворить первоначальный вопрос, предпосылка которого была «часто слышна» утверждения о чувствительности к контексту происходят из-за двусмысленности ... особенно когда дляgrammar на самом деле нет никакой двусмысленности даже в MVP.

от 

@KonradRudolph: я оспариваю, что это "общая ссылка". Тот факт, что я прочитал этоrather complex статьи и не постигать его в достаточной мере, чтобы вырезать этот маленький факт, должно быть достаточно, чтобы продемонстрировать это. Это не так, как если бы вы сказали что-то вроде «компьютеры обычно используют электричество», или «биты могут быть истинными или ложными».

от 

Насколько я могу судить, @Konrad ошибся, когда сказал, что «контекстно-зависимый эквивалентен завершению по Тьюрингу». (по крайней мере, он был, если он обозначал «Рекурсивно перечислимый» термином «Тьюринг завершен»), и с тех пор не смог распознать эту ошибку. Вот ссылка для правильного отношения включения набора, вовлеченного здесь:en.wikipedia.org/wiki/Chomsky_hierarchy

от 

@KonradRudolph: Стандарт гласит: «Существует количество, определяемое реализацией, которое задает ограничение на общую глубину рекурсивных реализаций, которое может включать более одного шаблона. Результат бесконечной рекурсии в экземпляре не определен. & Quot; (14.7.1p15) Я понимаю, что это означает, что реализация не обязана понимать каждую действительную программу на С ++, а не то, что программы с слишком большой глубиной рекурсии недопустимы. Единственные, которые помечены как недействительные, это те, которые имеют бесконечную глубину рекурсии.

от 
3
1

Meta-S&quot

is a context-sensitive parsing engine by Quinn Tyler Jackson. I've not used it, but he tells an impressive story. Check out his comments in comp.compilers, and see rnaparse.com/MetaS%20defined.htm – Ira Baxter Jul 25 at 10:42

Правильная ссылкаразбор загадок

Meta-S был собственностью несуществующей компании под названием Thothic. Я могу отправить бесплатную копию Meta-S всем, кто заинтересован, и я использовал ее в исследованиях анализа РНА. Обратите внимание на «грамматику псевдоузла». включенные в папки с примерами были написаны программистом, не занимающимся биоинформатикой, и в основном не работают. Мои грамматики используют другой подход и работают довольно хорошо.

This is actually an interesting find. – Dervin Thunk Sep 18 '09 at 15:11

от 
10

C ++ анализируется с помощью анализатора GLR. Это означает

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

смотри также,

Почему C ++ не может быть проанализирован парсером LR (1)?

Помните, что контекстно-бесплатная грамматикаcan not описыватьALL правила синтаксиса языка программирования. Например, грамматика атрибута используется для проверки правильности типа выражения.

int x;
x = 9 + 1.0;

Выcan not Опишите следующее правило с помощью контекстно-свободной грамматики: The Right Side of the assignment should be of the same type of the Left Hand side.

Большинство синтаксических анализаторов C ++ не используют технологию синтаксического анализа GLR. GCC не поддерживает Некоторые делают. Увидетьsemanticdesigns.com/Products/FrontEnds/CppFrontEnd.html для того, кто делает.

от 
11

Возможно, вы захотите взглянуть на

Дизайн и дизайн Эволюция С ++Бьярн Страуструп. В нем он описывает свои проблемы, пытаясь использовать yacc (или аналогичный) для анализа ранней версии C ++, и желая, чтобы он использовал вместо этого рекурсивный спуск.

@IraBaxter: ваш x-ref сегодня MIA - и твердые ссылки на программное обеспечение кажутся неуловимыми (поиск Google не дает хороших указаний ни с сайта: site: rnaparse.com meta-s ', ни с' quinn jackson ' meta-s '; есть фрагменты, ноmeta-s.com приводит к неинформативному веб-сайту, например).

от 

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

от 

Отличная книга для понимания, почему C ++. Я рекомендую это и Lippman's In the C ++ Object Model для понимания того, как работает C ++. Хотя оба немного устарели, они все еще хорошо читаются.

от 

@Jonathan: было некоторое время, только что заметил вашу жалобу. Не знаю, почему ссылка плохая, я думал, что это было хорошо, когда я ее написал. Куинн был довольно активен в comp.compilers. Google, кажется, становится ненадежным, это все, что я могу найти:groups.google.com/group/comp.compilers/browse_thread/thread/…  IIRC, он передал права на MetaS некоторым компаниям на Гавайях для перепродажи. Учитывая, как странно это было странно, ИМХО это подписание смертного приговора. Похоже, очень умная схема.

от 

& Quot; Мета-S & Quot; является контекстно-зависимым механизмом синтаксического анализа Куинн Тайлер Джексон. Я им не пользовался, но он рассказывает впечатляющую историю. Проверьте его комментарии в comp.compilers, и посмотритеrnaparse.com/MetaS%20defined.htm

от 
4

Правда :)

Дж. Стэнли Уорфорд.Компьютерные системы, Стр. 341-346.

4

Это зависит от контекста, как

a b(c); имеет два допустимых синтаксических анализа - объявление и переменную. Когда вы говорите "Еслиc это тип ", это контекст, прямо здесь, и вы точно описали, насколько C ++ чувствителен к нему. Если у вас не было этого контекста "Что такоеc? & Quot; Вы не могли бы разобрать это однозначно.

Здесь контекст выражается в выборе токенов - синтаксический анализатор считывает идентификатор как токен имени типа, если он называет тип. Это простейшее решение, и оно позволяет избежать значительной сложности, связанной с контекстом (в данном случае).

Изменить: Есть, конечно, больше вопросов чувствительности к контексту, я просто сосредоточился на том, что вы показали. Шаблоны особенно противны для этого.

@DeadMG Я не думаю, что вы отвечаете на вопрос (я не думаю, что я тоже). Как наличие терминалов на левой стороне производства решает эту проблему?

от 

Опрашивающий не спрашивает, как онmore контекстно-зависимый, чем C, только чтобы показать, что он контекстно-зависимый.

от 

Такжеa<b<c>>d, право? (Ваш пример на самом деле классический изCгде этоonly препятствие к тому, чтобы быть свободным от контекста.)

от 

Я думаю, это скорее проблема лексизма. Но, безусловно, в той же категории, да.

от 

Хм, хорошая мысль.

от 
1

Очевидно

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

Необходимо знать, является ли идентификатор именем типа (именем класса, именем, введенным typedef, параметром шаблона typename), именем шаблона или каким-либо другим именем, чтобы можно было правильно использовать идентификатор. Например:

x = (name)(expression);

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

Эта трудность привела к необходимостиtypename а такжеtemplate с зависимыми именами. Насколько я знаю, остальная часть C ++ не является контекстно-зависимой (то есть для нее можно написать контекстно-свободную грамматику).

3

Было показано

что шаблоны 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.}

Кажется, он имеет в видуthothic.com

от 
323

Ниже моя (текущая) любимая демонстрация того

почему синтаксический анализ C ++ (вероятно)Тьюринг, поскольку он показывает программу, синтаксически правильную тогда и только тогда, когда заданное целое число является простым.

Так что я утверждаю, чтоC++ is neither context-free nor context-sensitive.

Если вы разрешаете произвольные последовательности символов на обеих сторонах любого производства, вы создаете грамматику Типа-0 («неограниченно») вХомская иерархия, который является более мощным, чем контекстно-зависимая грамматика; неограниченные грамматики полны по Тьюрингу. Контекстно-зависимая (Тип-1) грамматика допускает несколько символов контекста в левой части продукции, но тот же контекст должен появляться в правой части продукции (отсюда и название «контекстно-зависимая»). [1] Контекстно-зависимые грамматики эквивалентнылинейные машины Тьюринга.

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

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

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

Но в любом случае, как строка 21 (т.е.auto b = foo<IsPrime<234799>>::typen<1>();в приведенных ниже программах выражения вовсе не являются двусмысленными; они просто анализируются по-разному в зависимости от контекста. В самом простом выражении проблемы синтаксическая категория определенных идентификаторов зависит от того, как они были объявлены (например, типы и функции), что означает, что формальный язык должен будет признать тот факт, что две строки произвольной длины в одна и та же программа идентична (декларация и использование). Это может быть смоделировано с помощью «копии» грамматика, которая является грамматикой, которая распознает две последовательные точные копии одного и того же слова. Это легко доказать с помощьюнасосная лемма что этот язык не является контекстно-свободным. Для этого языка возможна контекстно-зависимая грамматика, а в ответе на этот вопрос приведена грамматика типа 0:https://math.stackexchange.com/questions/163830/context-sensitive-grammar-for-the-copy-language .

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

То, что выглядит как формальная грамматика в стандарте C ++, не является полным формальным определением синтаксиса языка C ++. Это даже не полное формальное определение языка после предварительной обработки, которое может быть легче формализовать. (Однако это не был бы язык: язык C ++, как определено стандартом, включает в себя препроцессор, а операция препроцессора описывается алгоритмически, так как это было бы чрезвычайно трудно описать в любом грамматическом формализме. Это в этом разделе стандарта, где описывается лексическое разложение, включая правила, в которых оно должно применяться более одного раза.)

Различные грамматики (две накладывающиеся грамматики для лексического анализа, одна из которых имеет место перед предварительной обработкой, а другая, если необходимо, впоследствии, плюс «синтаксическая» грамматика), собрана в Приложении А, с этим важным примечанием (выделение добавлено):

This summary of C++ syntax is intended to be an aid to comprehension. It is not an exact statement of the language. In particular, the grammar described here accepts a superset of valid C++ constructs. Disambiguation rules (6.8, 7.1, 10.2) must be applied to distinguish expressions from declarations. Further, access control, ambiguity, and type rules must be used to weed out syntactically valid but meaningless constructs.

Наконец, вот обещанная программа. Строка 21 синтаксически правильна тогда и только тогда, когда N вIsPrime<N> прост. Иначе,typen целое число, а не шаблон, такtypen<1>() анализируется как(typen<1)>() что синтаксически неверно, потому что() не является синтаксически допустимым выражением.

template<bool V> struct answer { answer(int) {} bool operator()(){return V;}};

template<bool no, bool yes, int f, int p> struct IsPrimeHelper
  : IsPrimeHelper<p % f == 0, f * f >= p, f + 2, p> {};
template<bool yes, int f, int p> struct IsPrimeHelper<true, yes, f, p> { using type = answer<false>; };
template<int f, int p> struct IsPrimeHelper<false, true, f, p> { using type = answer<true>; };

template<int I> using IsPrime = typename IsPrimeHelper<!(I&1), false, 3, I>::type;
template<int I>
struct X { static const int i = I; int a[i]; }; 

template<typename A> struct foo;
template<>struct foo<answer<true>>{
  template<int I> using typen = X<I>;
};
template<> struct foo<answer<false>>{
  static const int typen = 0;
};

int main() {
  auto b = foo<IsPrime<234799>>::typen<1>(); // Syntax error if not prime
  return 0;
}

[1] Чтобы выразить это более технически, каждое производство в контекстно-зависимой грамматике должно иметь форму:

αAβ → αγβ

гдеA нетерминальный иα, β возможно пустые последовательности грамматических символов, иγ непустая последовательность (Символы грамматики могут быть терминалами или нетерминалами).

Это можно прочитать какA → γ только в контексте[α, β], В контекстно-свободной (тип 2) грамматикеα а такжеβ должен быть пустым.

Оказывается, что вы также можете ограничить грамматику с помощью "монотонной" ограничение, где каждая продукция должна иметь вид:

α → β где|α| ≥ |β| > 0& # XA0; & # xA0; (|α| означает "длинаα& Quot;)

Можно доказать, что набор языков, распознаваемых монотонными грамматиками, в точности совпадает с набором языков, распознаваемых контекстно-зависимыми грамматиками, и часто бывает так, что доказательства легче основывать на монотонных грамматиках. Следовательно, довольно часто можно видеть «контекстно-зависимый». используется, как если бы это означало «монотонный».

У меня есть одно сомнение: как вы показываете, результат оценки шаблона может иметь значение между правильно сформированной и плохо сформированной программой. Оценка шаблона завершена. Поэтому для правильного определения того, находится ли строка на языке (C ++), требуется полнота по Тьюрингу? Как вы говорите, контекстно-зависимый язык является "просто" «линейный ограниченный автомат», который не является полным по Тьюрингу AFAIK. Или ваш аргумент использует ограничения, которые стандарт C ++ накладывает на некоторые вещи, включая глубину оценки шаблона?

от 

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

от 

@mehrdad, ОП говорит «контекстно-зависимый язык», а не контекстно-зависимая грамматика. Неоднозначность - это особенность грамматики, а не языка. Язык действительно контекстно-зависимый, но не потому, что конкретная грамматика для него неоднозначна.

от 

@AntonGolov: Моя оригинальная версия этого примера сделала именно это (вы можете добиться этого, поставив0 Внутри()(для простого), но я думаю, что это более интересно, потому что он демонстрирует, что вам нужно создать экземпляр шаблона даже для того, чтобы распознать, является ли строка синтаксически корректной программой C ++. Если обе ветви компилируются, тогда мне придется работать усерднее, чтобы оспорить аргумент, что различие является «семантическим». Любопытно, что хотя мне часто приходится определять «синтаксический», никто никогда не предлагал определения «семантического». кроме «материала, который я не считаю синтаксическим»; :)

от 

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

от 

Похожие вопросы