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

StackOverflow https://stackoverflow.com/questions/243383

Вопрос

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

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

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

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

Это было полезно?

Решение

Есть интересная тема Лямбда 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));

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

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

Другие советы

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

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

x * y ;

У этого есть два различных анализа:

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

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

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

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

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

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

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

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

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

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

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

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

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

    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++, если вы его знаете!

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

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

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

    " typedef " Проблема в C ++ может быть проанализирована с помощью синтаксического анализатора LALR (1), который создает таблицу символов во время синтаксического анализа (а не чисто анализатор LALR). & Quot; template & Quot; проблема, вероятно, не может быть решена с помощью этого метода. Преимущество этого вида синтаксического анализатора 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 < !> Quot; проблема без двусмысленности в дереве разбора или AST. (Раскрытие: я парень, который создал LRSTAR.)

    Лицензировано под: CC-BY-SA с атрибуция
    Не связан с StackOverflow
    scroll top