Я читал о парсерах и генераторах парсеров и нашел это утверждение на странице анализа LR в Википедии:
Многие языки программирования могут быть проанализированы с использованием некоторого варианта синтаксического анализатора LR. Одним заметным исключением является C ++.
Почему это так? Какое специфическое свойство C ++ делает невозможным анализ парсеров LR?
Используя Google, я только обнаружил, что C может быть отлично проанализирован с помощью LR (1), но C ++ требует LR (∞).
c++
parsing
grammar
formal-languages
бодрый
источник
источник
Ответы:
На Lambda the Ultimate есть интересная тема, в которой обсуждается грамматика LALR для C ++ .
Он включает в себя ссылку на диссертацию PhD, которая включает обсуждение синтаксического анализа C ++, в котором говорится, что:
Далее приводится ряд примеров (см. Стр. 147 в pdf).
Пример:
смысл
Сравнить с:
смысл
(разделенное запятыми выражение).
Две последовательности токенов имеют одинаковую начальную подпоследовательность, но разные деревья разбора, которые зависят от последнего элемента. Перед однозначным может быть произвольно много токенов.
источник
Парсеры LR не могут обрабатывать неоднозначные грамматические правила по своему замыслу. (Облегчил теорию еще в 1970-х годах, когда разрабатывались идеи).
C и C ++ допускают следующее утверждение:
У этого есть два различных анализа:
Теперь вы можете подумать, что последнее глупо и должно игнорироваться. Большинство согласится с вами; однако, есть случаи, когда это может иметь побочный эффект (например, если умножение перегружено). но это не главное. Дело в том, что есть два разных анализа, и поэтому программа может означать разные вещи в зависимости от того, как это должно быть проанализировано.
Компилятор должен принять соответствующую информацию при соответствующих обстоятельствах, а при отсутствии какой-либо другой информации (например, знание типа 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 ++. )
источник
x * y
и усмехнулся - удивительно, как мало кто думает о таких изящных маленьких двусмысленностях, как эта.Проблема никогда не определяется так, хотя это должно быть интересно:
Каков наименьший набор модификаций в грамматике C ++, который был бы необходим для того, чтобы эта новая грамматика могла быть безошибочно проанализирована синтаксическим анализатором yacc «без контекста»? (использование только одного «хака»: неоднозначность typename / identifier, синтаксический анализатор, информирующий лексер о каждом typedef / class / struct)
Я вижу несколько:
Type Type;
запрещено. Идентификатор, объявленный как имя типа, не может стать идентификатором типа без имени (обратите внимание, чтоstruct Type Type
это не является двусмысленным и все еще может быть разрешено).Есть 3 типа
names tokens
:types
: встроенный тип или из-за typedef / class / structРассмотрение шаблонных функций как различных токенов решает
func<
неоднозначность. Еслиfunc
это имя функции-шаблона, то оно<
должно быть началом списка параметров шаблона, в противном случаеfunc
это указатель на функцию и<
оператор сравнения.Type a(2);
это экземпляр объекта.Type a();
иType a(int)
являются функциональными прототипами.int (k);
полностью запрещено, должно быть написаноint k;
typedef int func_type();
иtypedef int (func_type)();
запрещены.Функция typedef должна быть указателем функции typedef:
typedef int (*func_ptr_type)();
рекурсия шаблона ограничена 1024, в противном случае увеличенный максимум может быть передан компилятору в качестве опции.
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*))
typedef int type, *type_ptr;
может быть запрещено тоже: одна строка для typedef. Таким образом, это станетtypedef int type;
typedef int *type_ptr;
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) (без двусмысленности).
Следующий вход может быть проанализирован без проблем:
Генератор LRSTAR анализатора считывает выше грамматику обозначения и генерирует синтаксический анализатор , который обрабатывает «ЬурейаЯ» проблема без неоднозначности синтаксического дерева или АСТ. (Раскрытие: я парень, который создал LRSTAR.)
источник