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

Question

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

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

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

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

Answer 1

На http://lambda-the-ultimate.org/ есть интересная тема, в которой обсуждается грамматика 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));

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

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

Answer 2

Парсеры 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++.)

Answer 3

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

Каков наименьший набор модификаций в грамматике 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++, если вы их знаете!

Answer 4

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

Answer 5

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

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

Answer 6

Проблема "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 считывает вышеуказанную грамматическую нотацию и генерирует анализатор, который обрабатывает проблему "typedef" без двусмысленности в дереве синтаксического анализа или AST. (Раскрытие: я парень, который создал LRSTAR.)