Почему C++ не анализируется парсером LR (1)?

Question

Я читал о анализаторами и синтаксического анализа генераторов и нашел это заявление в LR синтаксического анализа -page Википедии:

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

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

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

Answer 1

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

Она включает в себя ссылку на PhD thesis, который включает в себя обсуждение 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)); 

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

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

Answer 2

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

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

Answer 3

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

C и C++ и позволяют следующее заявление:

x * y ; 

Он имеет два различных разборов:

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

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

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

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

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

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

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

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

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

Мы используем эту технику в C и C++ фронт заканчивается для нашего DMS Программное обеспечение реинжиниринга Tookit (по состоянию на июнь 2017 года это обрабатывать полный C++ 17 в MS и GNU диалектов). Они были использованы для обработки миллионов строк больших систем C и C++ с полными точными разборами, в которых получают АСТ с полной информацией об исходном коде. (См the AST for C++'s most vexing parse.)

Answer 4

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

Answer 5

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

что наименьший набор изменений в грамматике C++, которые были бы необходимы, чтобы эта новая грамматика может быть полностью разобран символом «не- контекстно-свободный "yatch-парсер? (Что делает использование только одного «взломать»: на снятии омонимии имяТипа/идентификатор, анализатор информирует лексер каждого ЬурейеЙ/класс/структуры)

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

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

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

   • types: BUILTIN-типа или из-за ЬурейеЕ/класса/структуры
   • шаблона-функции
   • идентификаторы: функции/методы и переменные/объекты

   Рассмотрение шаблонных функций как разных токенов решает проблему неопределенности 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 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*);

   быть resyntaxed как:

   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++

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

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