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

Question

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

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

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

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

Answer 1

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

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

x * y ;

Имеет два различных анализа:

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

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

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

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

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

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

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

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

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

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

Answer 2

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

Включает ссылку на кандидатскую диссертацию , которая включает обсуждение синтаксического анализа 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 3

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

Каков наименьший набор модификаций в грамматике C ++, который был бы необходим для того, чтобы эта новая грамматика могла быть идеально проанализирована "неконтекстно-свободным" синтаксическим анализатором yacc? (используя только один хак: имя типа / неоднозначность идентификатора, синтаксический анализатор, информирующий лексер о каждом 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 (& infin;) означает бесконечный просмотр вперед. То есть парсер должен был знать все, что приходило, чтобы выяснить, где он сейчас находится.

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.)