Парсеры GCC и Clang действительно написаны от руки?

Question

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

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

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

Answer 1

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

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

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

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

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

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

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

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

РЕДАКТИРОВАТЬ Ноябрь 2012: Со времени написания этого ответа мы улучшили наш внешний интерфейс C ++ для обработки полного C ++ 11, включая варианты диалектов ANSI, GNU и MS. Хотя было много лишних вещей, нам не нужно менять наш механизм синтаксического анализа; мы только что пересмотрели правила грамматики. Нам пришлось изменить семантический анализ; C ++ 11 семантически очень сложен, и эта работа затягивает усилия по запуску синтаксического анализатора.

РЕДАКТИРОВАТЬ Февраль 2015: ... теперь обрабатывает полный C ++ 14. (См. , чтобы получить читабельный AST из кода C ++ для GLR-разборов простого бита кода и печально известного "самого неприятного синтаксического анализа" в C ++).

РЕДАКТИРОВАТЬ Апрель 2017: Теперь обрабатывает (черновик) C ++ 17.

Answer 2

Да

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

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

Answer 3

Clang's parser - это рукописный синтаксический анализатор с рекурсивным спуском, как и несколько других открытых и коммерческих интерфейсов C и C ++.

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

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

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

Answer 4

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

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

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

Answer 5

Странные ответы там!

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

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

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

До GCC 3.x синтаксический анализатор C генерировался с помощью yacc / bison с таблицей typedefs, созданной во время синтаксического анализа. При построении таблицы indese в typedefs грамматика C становится локально не зависящей от контекста и, кроме того, «localally LR (1)».

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

Почему они перешли с 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?

Answer 6

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

В частности, бизон, я не думаю, что справится с грамматикой, не разбирая некоторые вещи двусмысленно и сделав второй проход позже.

Я знаю, что Haskell's Happy допускает монадные (то есть зависящие от состояния) синтаксические анализаторы, которые могут решить конкретную проблему с синтаксисом C, но я не знаю генераторов синтаксического анализатора C, которые допускают предоставленную пользователем монаду состояний.

Теоретически, исправление ошибок было бы преимуществом рукописного синтаксического анализатора, но мой опыт работы с GCC / Clang заключался в том, что сообщения об ошибках не особенно хороши.

Что касается производительности - некоторые претензии представляются необоснованными. Генерация большого конечного автомата с использованием генератора синтаксического анализатора должна привести к чему-то, что O(n), и я сомневаюсь, что синтаксический анализ является узким местом во многих инструментах.