Действительно ли обработчики GCC и Clang действительно написаны?

Похоже, что GCC и LLVM-Clang используют рукописные рекурсивные анализаторы спуска , а не машинные, основанные на Bison-Flex, синтаксический анализ снизу вверх.

Может кто-нибудь здесь, пожалуйста, подтвердите, что это так? И если да, то почему основные frameworks компилятора используют рукописные парсеры?

Обновление : интересный блог на эту тему

Да:

  • GCC использовал парсер yacc (bison) один раз, но в некоторый момент в серии 3.x он был заменен ручным рекурсивным парсером спуска: см. http://gcc.gnu.org/wiki/New_C_Parser для ссылки на соответствующие публикации патчей.

  • Кланг также использует рукописный рекурсивный анализатор спуска: см. Раздел «Единый унифицированный парсер для C, Objective C, C ++ и Objective C ++» в конце http://clang.llvm.org/features.html .

Существует фольклорная теорема о том, что C трудно анализировать, а C ++ практически невозможно.

Это неправда.

Верно то, что C и C ++ довольно сложно разобрать с помощью анализаторов LALR (1) без взлома механизма синтаксического анализа и запутывания в данных таблицы символов. GCC на самом деле используется для их анализа, используя YACC и дополнительные хакеры, подобные этому, и да, это было уродливо. Теперь GCC использует рукописные парсеры, но все же с хакером таблицы символов. Люди Clang никогда не пытались использовать автоматизированные генераторы парсеров; AFAIK анализатор Clang всегда был ручным рекурсивным спусками.

То, что верно, заключается в том, что C и C ++ сравнительно легко разбираются с более сильными автоматически генерируемыми синтаксическими анализаторами, например, анализаторами GLR , и вам не нужны никакие хаки. Одним из примеров этого является парсер Elsa C ++. Наш C ++ Front End – это еще один (как и все наши «компиляторы» передних концов, GLR – прекрасная технология синтаксического анализа).

Наш фронт C ++ не так быстро, как GCC, и, конечно, медленнее, чем Elsa; мы вкладываем немного энергии в тщательную настройку, потому что у нас есть другие более насущные проблемы (не говоря уже о том, что они использовались на миллионах строк кода на C ++). Elsa, вероятно, медленнее, чем GCC, просто потому, что она более общая. Учитывая скорость процессора в эти дни, эти различия могут не иметь большого значения на практике.

Но «реальные компиляторы», которые сегодня широко распространены, уходят корнями в составителей 10 или 20 лет назад или более. Неэффективность тогда имела значение гораздо больше, и никто не слышал о парсерах GLR, поэтому люди делали то, что знали, как это делать. Кланг, конечно, более поздний, но тогда народные теоремы сохраняют свою «убедительность» в течение длительного времени.

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

То, что верно, заключается в том, что получение грамматики, которая соответствует поведению вашего дружественного сообщества, сложна. Хотя практически все компиляторы C ++ реализуют (большинство) исходного стандарта, они также имеют множество темных угловых расширений, например, спецификаций DLL в компиляторах MS и т. Д. Если у вас сильный синтаксический анализатор, вы можете потратить свое время, пытаясь получить окончательная грамматика, чтобы соответствовать реальности, вместо того, чтобы пытаться сгибать вашу грамматику в соответствии с ограничениями вашего генератора парсера.

EDIT November 2012: с момента написания этого ответа мы улучшили наш интерфейс C ++ для обработки полного C ++ 11, включая диалоги ANSI, GNU и MS. Хотя было много лишних вещей, нам не нужно менять наш синтаксический анализатор; мы просто пересмотрели правила грамматики. Нам пришлось изменить семантический анализ; C ++ 11 семантически очень сложный, и эта работа усиливает усилия, чтобы запустить парсер.

EDIT Февраль 2015: … теперь обрабатывает полный C ++ 14. (Посмотрите, чтобы получить читаемый АСТ из кода c ++ для анализов GLR простого бита кода и печально известный «самый неприятный синтаксис» C ++).

EDIT Апрель 2017: Теперь обрабатывает (черновик) C ++ 17.

Анализатор Клана – рукописный рекурсивный спуск парсер, а также несколько других открытых и коммерческих C и C ++ фронтов.

Кланг использует парсер рекурсивного спуска по нескольким причинам:

  • Производительность : рукописный парсер позволяет нам писать быстрый парсер, оптимизируя горячие пути по мере необходимости, и мы всегда контролируем эту производительность. Наличие быстрого парсера позволило использовать Clang в других инструментах разработки, где «реальные» парсеры обычно не используются, например, подсветка синтаксиса и завершение кода в среде IDE.
  • Диагностика и восстановление ошибок : поскольку вы полностью контролируете рукописный рекурсивный спуск парсер, легко добавить специальные случаи, которые обнаруживают общие проблемы и обеспечивают отличную диагностику и восстановление ошибок (например, см. Http: //clang.llvm .org / features.html # expressivediags ) С автоматически создаваемыми парсерами вы ограничены возможностями генератора.
  • Простота : паркуры с рекурсивным спусками легко писать, понимать и отлаживать. Вам не обязательно быть экспертом по parsingу или выучить новый инструмент для расширения / улучшения парсера (что особенно важно для проекта с открытым исходным кодом), но вы все равно можете получить отличные результаты.

В целом, для компилятора C ++ это просто не имеет большого значения: часть синтаксического анализа C ++ нетривиальна, но она по-прежнему остается одной из самых легких частей, поэтому она платит, чтобы она была простой. Семантический анализ – особенно поиск имени, инициализация, разрешение перегрузки и создание шаблона – на порядок сложнее, чем синтаксический анализ. Если вы хотите получить доказательство, перейдите к дистрибутиву кода и запишите в компоненте Clang «Sema» (для семантического анализа) по сравнению с его компонентом «Parse» (для синтаксического анализа).

Парсер gcc написан вручную. , Я подозреваю то же самое для clang. Это, вероятно, по нескольким причинам:

  • Производительность : то, что вы вручную оптимизировали для своей конкретной задачи, почти всегда будет работать лучше, чем общее решение. Абстракция обычно имеет производительность
  • Сроки : по крайней мере, в случае GCC, GCC предшествует множеству бесплатных инструментов разработчика (вышел в 1987 году). В то время не было бесплатной версии yacc и т. Д., Что, я думаю, было бы приоритетом для людей в FSF.

Вероятно, это не случай синдрома «не придумал здесь», но больше по строкам «ничего не было оптимизировано специально для того, что нам было нужно, поэтому мы написали свои собственные».

Там странные ответы!

Графики C / C ++ не являются контекстными. Они чувствительны к контексту из-за панели Foo *; неоднозначность. Мы должны создать список typedefs, чтобы узнать, является ли Foo типом или нет.

Ира Бакстер: Я не вижу смысла с твоей GLR. Зачем строить дерево parsingа, которое содержит неоднозначность. Разбор означает решение двусмысленностей, построение дерева синтаксиса. Вы разрешаете эти двусмысленности во втором проходе, поэтому это не менее уродливо. Для меня это намного уродливее …

Yacc – генератор парсеров LR (1) (или LALR (1)), но его можно легко модифицировать, чтобы быть чувствительным к контексту. И в этом нет ничего уродливого. Yacc / Bison был создан, чтобы помочь в синтаксическом анализе языка C, поэтому, возможно, это не самый уродливый инструмент для создания анализатора C …

До GCC 3.x парсер C генерируется yacc / bison, с таблицей typedefs, созданной во время parsingа. При построении таблиц «in parse» typedefs C грамматика становится локально контекстной и, кроме того, «локально LR (1)».

Теперь, в Gcc 4.x, это рекурсивный парсер спуска. Это точно такой же парсер, что и в Gcc 3.x, он все еще LR (1) и имеет те же правила грамматики. Разница в том, что парсер yacc был переписан вручную, сдвиг / уменьшение теперь скрыты в стеке вызовов, и нет «state454: if (nextsym == ‘(‘) goto state398″, как в gcc 3.x yacc’s синтаксический анализатор, поэтому его легче обрабатывать, обрабатывать ошибки и печатать более приятные сообщения, а также выполнять некоторые из следующих шагов компиляции при parsingе. По цене гораздо менее «легко читаемого» кода для gcc noob.

Почему они переключились с yacc на рекурсивный спуск? Потому что совершенно необходимо избегать yacc для синтаксического анализа C ++ и потому, что GCC мечтает быть многоязычным компилятором, то есть делиться максимальным кодом между различными языками, которые он может скомпилировать. Вот почему C ++ и C-парсер записываются одинаково.

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?

Давайте будем гением компьютера.