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

Я читал о парсерах и генераторах парсеров и нашел это утверждение на странице анализа LR в Википедии:

Многие языки программирования могут быть проанализированы с использованием некоторого варианта синтаксического анализатора LR. Одним заметным исключением является C ++.

Почему это так? Какое специфическое свойство C ++ делает невозможным анализ парсеров LR?

Используя Google, я только обнаружил, что C может быть отлично проанализирован с помощью LR (1), но C ++ требует LR (∞).

На Lambda the Ultimate есть интересная тема, в которой обсуждается грамматика LALR для C ++ .

Он включает в себя ссылку на диссертацию PhD, которая включает обсуждение синтаксического анализа C ++, в котором говорится, что:

«Грамматика C ++ неоднозначна, зависит от контекста и потенциально требует бесконечного взгляда для устранения некоторых неясностей».

Далее приводится ряд примеров (см. Стр. 147 в pdf).

Пример:

int(x), y, *const z;

смысл

int x;
int y;
int *const z;

Сравнить с:

int(x), y, new int;

смысл

(int(x)), (y), (new int));

(разделенное запятыми выражение).

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

Парсеры LR не могут обрабатывать неоднозначные грамматические правила по своему замыслу. (Облегчил теорию еще в 1970-х годах, когда разрабатывались идеи).

C и C ++ допускают следующее утверждение:

x * y ;

У этого есть два различных анализа:

1. Это может быть объявление у, как указатель на тип х
2. Это может быть умножение на x и y, отбрасывая ответ.

Теперь вы можете подумать, что последнее глупо и должно игнорироваться. Большинство согласится с вами; однако, есть случаи, когда это может иметь побочный эффект (например, если умножение перегружено). но это не главное. Дело в том, что есть два разных анализа, и поэтому программа может означать разные вещи в зависимости от того, как это должно быть проанализировано.

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

Таким образом, чистый анализ LR не может справиться с этим. Также многие другие широко доступные генераторы синтаксических анализаторов, такие как Antlr, JavaCC, YACC или традиционный Bison, или даже парсеры PEG-стиля, не могут использоваться «чистым» способом.

Есть много более сложных случаев (синтаксический анализ синтаксиса шаблона требует произвольного просмотра, в то время как LALR (k) может смотреть вперед на большинство k токенов), но только один контрпример требует, чтобы отбросить чистый анализ LR (или другие).

Большинство реальных синтаксических анализаторов C / C ++ обрабатывают этот пример, используя какой-то детерминированный синтаксический анализатор с дополнительным хаком: они переплетаются с синтаксическим анализом с коллекцией таблиц символов ... так что к тому времени, когда "x" встречается, анализатор знает, является ли x типом или нет, и, таким образом, может выбирать между двумя потенциальными анализами. Но парсер, который делает это, не является контекстно-свободным, а парсеры LR (чистые и т. Д.) (В лучшем случае) не зависят от контекста.

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

И если вы обманываете достаточно, вы можете заставить парсеры LR работать на C и C ++. Ребята из GCC сделали это на некоторое время, но отказались от ручного анализа, я думаю, потому что они хотели улучшить диагностику ошибок.

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

Мы используем эту технику в интерфейсах C и C ++ для нашего Tookit по реинжинирингу программного обеспечения DMS (по состоянию на июнь 2017 года они обрабатывают полный C ++ 17 на диалектах MS и GNU). Они использовались для обработки миллионов строк больших систем C и C ++ с полными, точными разборками, производящими AST с полными деталями исходного кода. (См. AST для самого неприятного анализа C ++. )

Проблема никогда не определяется так, хотя это должно быть интересно:

Каков наименьший набор модификаций в грамматике C ++, который был бы необходим для того, чтобы эта новая грамматика могла быть безошибочно проанализирована синтаксическим анализатором yacc «без контекста»? (использование только одного «хака»: неоднозначность typename / identifier, синтаксический анализатор, информирующий лексер о каждом typedef / class / struct)

Я вижу несколько:

1. Type Type;запрещено. Идентификатор, объявленный как имя типа, не может стать идентификатором типа без имени (обратите внимание, чтоstruct Type Type это не является двусмысленным и все еще может быть разрешено).

   Есть 3 типа names tokens:

   • types : встроенный тип или из-за typedef / class / struct
   • Шаблон-функции
   • идентификаторы: функции / методы и переменные / объекты

   Рассмотрение шаблонных функций как различных токенов решает func<неоднозначность. Если funcэто имя функции-шаблона, то оно <должно быть началом списка параметров шаблона, в противном случае funcэто указатель на функцию и <оператор сравнения.

2. Type a(2);это экземпляр объекта. Type a();и Type a(int)являются функциональными прототипами.

3. int (k); полностью запрещено, должно быть написано int k;

4. typedef int func_type(); и typedef int (func_type)();запрещены.

   Функция typedef должна быть указателем функции typedef: typedef int (*func_ptr_type)();

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

6. int a,b,c[9],*d,(*f)(), (*g)()[9], h(char); может быть запрещено, заменено int a,b,c[9],*d; int (*f)();

   int (*g)()[9];

   int h(char);

   одна строка на прототип функции или объявление указателя на функцию.

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

   int (MyClass::*MethodPtr)(char*);

   повторный синтаксис как:

   int (MyClass::*)(char*) MethodPtr;

   это связано с оператором броска (int (MyClass::*)(char*))

7. typedef int type, *type_ptr; может быть запрещено тоже: одна строка для typedef. Таким образом, это станет

   typedef int type;

   typedef int *type_ptr;

8. sizeof int, sizeof char, sizeof long longИ Ко. может быть объявлено в каждом исходном файле. Таким образом, каждый исходный файл, использующий тип, intдолжен начинаться с

   #type int : signed_integer(4)

   и unsigned_integer(4)было бы запрещено вне этой #type директивы, это было бы большим шагом в глупой sizeof intдвусмысленности, присутствующей во многих заголовках C ++

Компилятор, реализующий повторно синтаксисированный C ++, при обнаружении источника C ++, использующего неоднозначный синтаксис, переместит source.cppслишком ambiguous_syntaxпапку и автоматически создаст однозначный перевод source.cppперед его компиляцией.

Пожалуйста, добавьте свои неоднозначные синтаксисы C ++, если вы их знаете!

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

Я думаю, что вы довольно близки к ответу.

LR (1) означает, что для разбора слева направо требуется только один токен для просмотра контекста, в то время как LR (∞) означает бесконечный просмотр вперед. То есть парсер должен знать все, что приходит, чтобы выяснить, где он сейчас.

Проблема «typedef» в C ++ может быть проанализирована с помощью синтаксического анализатора LALR (1), который создает таблицу символов во время синтаксического анализа (а не чисто синтаксический анализатор LALR). Проблема «шаблона», вероятно, не может быть решена с помощью этого метода. Преимущество этого вида синтаксического анализатора LALR (1) состоит в том, что грамматика (показанная ниже) является грамматикой LALR (1) (без двусмысленности).

/* C Typedef Solution. */

/* Terminal Declarations. */

   <identifier> => lookup();  /* Symbol table lookup. */

/* Rules. */

   Goal        -> [Declaration]... <eof>               +> goal_

   Declaration -> Type... VarList ';'                  +> decl_
               -> typedef Type... TypeVarList ';'      +> typedecl_

   VarList     -> Var /','...     
   TypeVarList -> TypeVar /','...

   Var         -> [Ptr]... Identifier 
   TypeVar     -> [Ptr]... TypeIdentifier                               

   Identifier     -> <identifier>       +> identifier_(1)      
   TypeIdentifier -> <identifier>      =+> typedefidentifier_(1,{typedef})

// The above line will assign {typedef} to the <identifier>,  
// because {typedef} is the second argument of the action typeidentifier_(). 
// This handles the context-sensitive feature of the C++ language.

   Ptr          -> '*'                  +> ptr_

   Type         -> char                 +> type_(1)
                -> int                  +> type_(1)
                -> short                +> type_(1)
                -> unsigned             +> type_(1)
                -> {typedef}            +> type_(1)

/* End Of Grammar. */

Следующий вход может быть проанализирован без проблем:

 typedef int x;
 x * y;

 typedef unsigned int uint, *uintptr;
 uint    a, b, c;
 uintptr p, q, r;

Генератор LRSTAR анализатора считывает выше грамматику обозначения и генерирует синтаксический анализатор , который обрабатывает «ЬурейаЯ» проблема без неоднозначности синтаксического дерева или АСТ. (Раскрытие: я парень, который создал LRSTAR.)