Похоже, что GCC и LLVM-Clang используют рукописные рекурсивные спускающие парсеры и не, сгенерированные машиной Bison-Flex на основе снизу вверх.
Может кто-нибудь здесь, пожалуйста, подтвердите, что это так? И если да, то почему в основных системах компилятора используются рукописные парсеры?
Обновить: интересный блог на эту тему здесь
Да:
GCC использовал парсер yacc (bison) один раз, но в какой-то момент в серии 3.x он был заменен рукописным рекурсивным парсером спуска: см. http://gcc.gnu.org/wiki/New_C_Parser для ссылок на соответствующие публикации патчей.
Clang также использует рукописный рекурсивный анализатор спуска: см. раздел "Единый унифицированный парсер для C, Objective C, С++ и Objective С++" в конце http://clang.llvm.org/features.html.
Существует фолк-теорема, в которой сказано, что C трудно разобрать, а С++ практически невозможно.
Это неверно.
Верно то, что C и С++ довольно сложно разобрать с помощью парсеров LALR (1) без взлома синтаксического анализа и запутывания в данных таблицы символов. GCC на самом деле используется для их анализа, используя YACC и дополнительные хакеры, подобные этому, и да, это было уродливо. Теперь GCC использует рукописные парсеры, но все же с хакером таблицы символов. Люди Clang никогда не пытались использовать автоматизированные генераторы парсеров; AFAIK анализатор Clang всегда был ручным рекурсивным спуском.
Что верно, так это то, что C и С++ относительно легко разбираются с более сильными автоматически сгенерированными парсерами, например анализаторы GLR, и вы надеваете Не нужны хаки. Elsa Синтаксический анализатор С++ является одним из примеров этого. Наш С++ Front End - это еще один (как и все наши "компиляторы" передних концов, GLR - довольно прекрасная технология синтаксического анализа).
Наш интерфейс С++ не так быстро, как GCC, и, конечно, медленнее, чем Elsa; мы вкладываем немного энергии в тщательную настройку, потому что у нас есть другие более насущные проблемы (не говоря уже о том, что они использовались на миллионах строк кода на С++). Elsa, вероятно, медленнее, чем GCC, просто потому, что она более общая. Учитывая скорость процессора в эти дни, эти различия могут не иметь большого значения на практике.
Но "реальные компиляторы", которые сегодня широко распространены, имеют свои корни в компиляторах 10 или 20 лет назад или более. Неэффективность тогда имела значение гораздо больше, и никто не слышал о парсерах GLR, поэтому люди делали то, что знали, как это делать. Кланг, конечно, более поздний, но тогда народные теоремы сохраняют свою "убедительность" в течение длительного времени.
Вам больше не нужно так поступать. Вы можете очень разумно использовать GLR и другие такие синтаксические анализаторы, как передние, с улучшением ремонтопригодности компилятора.
Что верно, так это то, что получение грамматики, которая соответствует вашему дружественному поведению компилятора, сложна. Хотя практически все компиляторы С++ реализуют (большинство) исходного стандарта, они также имеют множество темных угловых расширений, например, спецификаций DLL в компиляторах MS и т.д. Если у вас сильный механизм синтаксического анализа, вы можете потратьте время, пытаясь получить окончательную грамматику, чтобы соответствовать реальности, вместо того, чтобы пытаться сгибать вашу грамматику в соответствии с ограничениями генератора парсера.
EDIT November 2012: с момента написания этого ответа мы улучшили наш интерфейс С++ для обработки полного С++ 11, включая диалоги ANSI, GNU и MS. Хотя было много лишних вещей, нам не нужно менять наш синтаксический анализатор; мы просто пересмотрели правила грамматики. Нам пришлось изменить семантический анализ; С++ 11 семантически очень сложный, и эта работа усиливает усилия, чтобы запустить парсер.
EDIT Февраль 2015:... теперь обрабатывает полный С++ 14. (См. получить человекоподобный АСТ от кода С++ для анализов GLR простого бита кода и С++ позорного "самого неприятного разбора" ).
EDIT Апрель 2017: Теперь обрабатывает (черновик) С++ 17.
Парсон-партер - рукописный рекурсивный спуск парсер, а также несколько других открытых и коммерческих C и С++ фронтов.
Clang использует парсер рекурсивного спуска по нескольким причинам:
В целом, для компилятора С++ это просто не имеет большого значения: часть синтаксического анализа С++ является нетривиальной, но она по-прежнему остается одной из самых легких частей, поэтому она платит, чтобы она была простой. Семантический анализ - особенно поиск имени, инициализация, разрешение перегрузки и создание шаблона - на порядок сложнее, чем синтаксический анализ. Если вы хотите получить доказательство, пойдите, проверьте распределение кода и запишите в компоненте Clang "Sema" (для семантического анализа) по сравнению с его компонентом "Parse" (для разбора).
gcc parser написан вручную.. Я подозреваю то же самое для clang. Это, вероятно, по нескольким причинам:
Это, вероятно, не случай синдрома "не придумал здесь", но более похоже на то, что "ничего не было оптимизировано специально для того, что нам было нужно, поэтому мы написали свои собственные".
Там странные ответы!
C/С++-грамматики не являются контекстными. Они чувствительны к контексту из-за панели Foo *; неоднозначность. Мы должны создать список typedefs, чтобы узнать, является ли Foo типом или нет.
Ира Бакстер: Я не вижу смысла с твоей GLR. Зачем строить дерево разбора, которое содержит неоднозначность. Разбор означает решение двусмысленностей, построение дерева синтаксиса. Вы разрешаете эти двусмысленности во втором проходе, поэтому это не менее уродливо. Для меня это гораздо более уродливо...
Yacc является генератором парсеров LR (1) (или LALR (1)), но его можно легко модифицировать, чтобы быть чувствительным к контексту. И в этом нет ничего уродливого. Yacc/Bison был создан, чтобы помочь в синтаксическом анализе языка C, поэтому, вероятно, это не самый уродливый инструмент для создания анализатора C...
До GCC 3.x парсер C генерируется yacc/bison, с таблицей typedefs, созданной во время разбора. При построении таблиц "in parse" typedefs C грамматика становится локально контекстной и, кроме того, "локально LR (1)".
Теперь, в Gcc 4.x, это рекурсивный парсер спуска. Это точно такой же парсер, что и в Gcc 3.x, он все еще LR (1) и имеет те же правила грамматики. Разница в том, что парсер yacc был переписан вручную, сдвиг/сокращение теперь скрыты в стеке вызовов, и нет "state454: if (nextsym == '(') goto state398", как в gcc 3.x yacc синтаксический анализатор, поэтому его легче обрабатывать, обрабатывать ошибки и печатать более приятные сообщения, а также выполнять некоторые из следующих шагов компиляции при разборе. По цене гораздо менее "легко читаемого" кода для gcc noob.
Почему они переключились с yacc на рекурсивный спуск? Потому что совершенно необходимо избегать yacc для синтаксического анализа С++ и потому, что GCC мечтает быть многоязычным компилятором, то есть делиться максимальным кодом между различными языками, которые он может скомпилировать. Вот почему С++ и C-парсер записываются таким же образом.
С++ сложнее анализировать, чем C, потому что он не является локально LR (1) как C, это даже не LR (k).
Посмотрите func<4 > 2>, которая является функцией шаблона, созданной с помощью 4 > 2, т.е. func<4 > 2>
следует читать как func<1>. Это определенно не LR (1). Теперь рассмотрим func<4 > 2 > 1 > 3 > 3 > 8 > 9 > 8 > 7 > 8>. Здесь рекурсивный спуск может легко решить двусмысленность по цене еще нескольких вызовов функций (parse_template_parameter - это функция двусмысленного анализатора.Если parse_template_parameter (17tokens) провалился, попробуйте снова parse_template_parameter (15tokens), parse_template_parameter (13tokens)
... пока это не сработает).
Я не знаю, почему было бы невозможно добавить в рекурсивные под грамматики yacc/bison, может быть, это будет следующим шагом в разработке парсера gcc/GNU?