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

153

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

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

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

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

бодрый
источник
7
Также как: вам нужно понимать рекурсию, чтобы выучить рекурсию ;-).
Toon Krijthe
5
«Вы поймете парсеры, когда разберете эту фразу».
Илья Н.

Ответы:

92

На 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));

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

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

Роб Уокер
источник
29
Было бы здорово иметь некоторое резюме о странице 147 на этой странице. Я собираюсь прочитать эту страницу, хотя. (+1)
Веселый
11
Пример: int (x), y, * const z; // значение: int x; int y; int * const z; (последовательность объявлений) int (x), y, new int; // значение: (int (x)), (y), (new int)); (выражение, разделенное запятыми) Две последовательности токенов имеют одинаковую начальную подпоследовательность, но разные деревья разбора, которые зависят от последнего элемента. Перед однозначным может быть произвольно много токенов.
Blaisorblade
6
Что ж, в этом контексте ∞ означает «произвольно много», потому что прогноз всегда будет ограничен длиной ввода.
MauganRa
1
Я весьма озадачен цитатой, взятой из докторской диссертации. Если есть неоднозначность, то, по определению, НИКАКОЙ взгляд не может когда-либо «разрешить» неоднозначность (то есть решить, какой разбор является правильным значением, так как по крайней мере 2 разбора считаются правильными по грамматике). Более того, в цитате упоминается неоднозначность C, но в объяснении не указывается неоднозначность, а лишь недвусмысленный пример, в котором решение синтаксического анализа может быть принято только после произвольного долгого прогнозирования.
dodecaplex
231

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

Ира Бакстер
источник
11
Хотя пример 'x * y' интересен, то же самое может произойти в C ('y' может быть typedef или переменной). Но C может быть проанализирован парсером LR (1), так в чем же разница с C ++?
Мартин Кот
12
Мой ответчик уже заметил, что у С была та же проблема, я думаю, что вы пропустили это. Нет, он не может быть проанализирован LR (1) по той же причине. Э-э, что вы имеете в виду, что «у» может быть typedef? Возможно, вы имели в виду «х»? Это ничего не меняет.
Ира Бакстер
6
Разбор 2 не обязательно глуп в C ++, так как * может быть переопределен, чтобы иметь побочные эффекты.
Dour High Arch
8
Я посмотрел x * yи усмехнулся - удивительно, как мало кто думает о таких изящных маленьких двусмысленностях, как эта.
new123456
51
@altie Конечно, никто не будет перегружать оператор сдвига битов, чтобы заставить его записывать большинство переменных типов в поток, верно?
Трой Дэниелс
16

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

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

reuns
источник
3
C ++ слишком хорошо укоренился. Никто не будет делать это на практике. Те люди (как мы), которые строят внешние интерфейсы, просто кусают пули и делают разработку, чтобы парсеры работали. И, пока шаблоны существуют в языке, вы не получите чистый контекстно-свободный анализатор.
Ира Бакстер
9

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

Сэм Харвелл
источник
3
Технология синтаксического анализа, которая обрабатывает неоднозначность, просто производит оба варианта AST по мере их анализа и просто устраняет неправильный вариант в зависимости от информации о типе.
Ира Бакстер
@ Ира: Да, это правильно. Особое преимущество в том, что оно позволяет вам поддерживать разделение на первом этапе анализа. Хотя это наиболее широко известно в анализаторе GLR, я не вижу особой причины, по которой я вижу, что вы не можете поразить C ++ "GLL?" парсер тоже.
Сэм Харвелл,
"GLL"? Ну, конечно, но вам придется разобраться с теорией и написать статью для остального использования. Скорее всего, вы можете использовать синтаксический анализатор сверху вниз, или анализатор LALR () с возвратом (но оставьте «отклоненный»), или запустить анализатор Earley. GLR имеет то преимущество, что является чертовски хорошим решением, хорошо документировано и на данный момент хорошо себя зарекомендовало. Технология GLL должна иметь довольно существенные преимущества для отображения GLR.
Ира Бакстер
Проект Rascal (Нидерланды) утверждает, что они создают анализатор GLL без сканера. Работа в процессе, может быть трудно найти любую информацию в Интернете. en.wikipedia.org/wiki/RascalMPL
Ира Бакстер
@IraBaxter Там , кажется, новые разработки по GLL: посмотреть 2010 документ о GLL dotat.at/tmp/gll.pdf
Sjoerd
6

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

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

casademora
источник
4
Из моего класса компиляторов я вспоминаю, что LR (n) при n> 0 математически сводится к LR (1). Разве это не верно для n = бесконечность?
rmeador
14
Нет, непроходимая гора разницы между русским и бесконечным.
Эфимент
4
Разве не ответ: да, учитывая бесконечное количество времени? :)
Стив Фэллоуз
7
На самом деле, по моим смутным воспоминаниям о том, как происходит LR (n) -> LR (1), это включает в себя создание новых промежуточных состояний, поэтому время выполнения является некоторой непостоянной функцией n. Перевод LR (inf) -> LR (1) занял бы бесконечное время.
Аарон
5
"Разве не ответ: да, учитывая бесконечное количество времени?" - Нет: фраза «дано бесконечное количество времени» - это просто бессмысленный, краткий способ сказать «не может быть сделано, если какое-то конечное количество времени». Когда вы видите «бесконечное», думайте: «не любое конечное».
ChrisW
4

Проблема «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.)


источник
Это стандартный хак, используемый GCC с его бывшим парсером LR для обработки неоднозначности таких вещей, как "x * y;" Увы, все еще существует произвольно большое требование для анализа других конструкций, поэтому LR (k) не может быть решением при любом фиксированном k. (GCC переключился на рекурсивный спуск с большим количеством рекламы).
Ира Бакстер