Сколько времени потребуется, чтобы написать компилятор C ++ с использованием flex / yacc?

Question

Сколько времени потребуется для написания компилятора C ++ с использованием lex / yacc?

С чего мне начать?

Answer 1

Существует много правил синтаксического анализа, которые не могут быть проанализированы синтаксическим анализатором bison / yacc (например, в некоторых случаях различаются объявление и вызов функции). Кроме того, иногда интерпретация токенов требует ввода от синтаксического анализатора, особенно в C ++ 0x. Например, обработка последовательности символов >> в решающей степени зависит от контекста синтаксического анализа.

Эти два инструмента являются очень плохим выбором для синтаксического анализа C ++, и вам придется добавить множество особых случаев, которые выходят за рамки базовой структуры, на которую опираются эти инструменты, для правильного синтаксического анализа C ++. Это займет у вас много времени, и даже в этом случае ваш парсер будет иметь странные ошибки.

yacc и bison являются LALR (1) генераторами синтаксического анализатора, которые не достаточно сложны для эффективной обработки C ++. Как отмечали другие люди, большинство компиляторов C ++ теперь используют синтаксический анализатор с рекурсивным спуском , а некоторые другие ответы указывают на хорошие решения для написания вашего собственного.

Шаблоны C ++ не годятся для обработки строк, даже константных (хотя это может быть исправлено в C ++ 0x, я не проводил тщательных исследований), но если бы они были, вы могли бы довольно легко написать анализатор рекурсивного спуска в язык шаблонов C ++. Я нахожу это довольно забавным.

Answer 2

Похоже, вы довольно новичок в разборе / создании компилятора. В таком случае я бы настоятельно рекомендовал , а не , начиная с C ++. Это монстр языка.

Либо придумайте свой собственный тривиальный игрушечный язык, либо сделайте что-нибудь по образцу чего-то гораздо меньшего и более простого. Я видел синтаксический анализатор lua, где определение грамматики было длиной около страницы. Это было бы гораздо разумнее в качестве отправной точки.

Answer 3

Это, вероятно, займет у вас лет , и вы, вероятно, переключитесь на какой-нибудь другой генератор синтаксического анализатора в процессе.

Синтаксический анализ C ++, как известно, подвержен ошибкам. Грамматика не полностью LR-анализируемая, так как многие части являются контекстно-зависимыми. Вы не сможете заставить его работать правильно в flex / yacc, или по крайней мере это будет очень неудобно для реализации. Есть только два интерфейса, о которых я знаю, которые понимают это правильно. Лучше всего использовать один из них и сосредоточиться на написании серверной части. Вот где интересные вещи в любом случае: -).

Существующие внешние интерфейсы C ++:

1. Интерфейс EDG используется большинством коммерческих поставщиков ( Intel , Portland Group и т. Д. .) в своих компиляторах. Это стоит денег , но это очень тщательно. Люди платят большие деньги за это, потому что они не хотят иметь дело с болью написания собственного синтаксического анализатора C ++.

2. Внешний интерфейс GCC для C ++ достаточно тщателен для производственного кода, но вам нужно будет выяснить, как интегрировать это в ваш проект. Я считаю, что это довольно сложно отделить от GCC. Это также будет GPL, но я не уверен, является ли это проблемой для вас. Вы можете использовать интерфейс GCC в своем проекте через gcc_xml , но это даст вам XML только для классов, функций, пространств имен и typedefs. Это не даст вам синтаксическое дерево для кода.

3. Другая возможность - использовать clang , но их поддержка C ++ в настоящее время не совсем корректна. Было бы хорошо видеть, как они исправляют все ошибки, но если вы посмотрите на их страницу состояния C ++ , вы заметите, что есть еще несколько тестовых случаев, которые все еще ломаются. Обратите внимание - Clang - это большой проект. Если эти ребята потратят годы на внедрение внешнего интерфейса C ++, вам понадобится больше времени.

4. Другие упоминали ANTLR , и есть грамматика C ++, но я скептически отношусь. Я не слышал о том, чтобы интерфейс ANTLR использовался в каких-либо крупных компиляторах, хотя я уверен, что он используется в IDE NetBeans. Возможно, он подойдет для IDE, но я скептически отношусь к тому, что вы сможете использовать его в рабочем коде.

Answer 4

долго, а lex и yacc не помогут

Если у вас есть навыки написания компилятора для такого большого языка, вам не понадобится небольшая помощь, которую вам оказывают lex и yacc. На самом деле, несмотря на то, что с lex все в порядке, использование yacc может занять больше времени, поскольку на самом деле он недостаточно мощен для C или C ++, и вы можете потратить гораздо больше времени, чтобы заставить его работать правильно, чем просто написание рекурсивного анализатор спуска.

Я считаю, что lex и yacc лучше всего использовать для простых грамматик, или когда стоит приложить дополнительные усилия, чтобы получить хорошо читаемый файл грамматики, возможно, потому, что грамматика является экспериментальной и может быть изменена.

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

Answer 5

Как уже говорили другие, yacc - плохой выбор для реализации синтаксического анализатора C ++ . Можно это сделать; оригинальный GCC сделал это, прежде чем команда GCC почувствовала отвращение к тому, как трудно было поддерживать и расширять. (Flex может быть в качестве лексера).

Некоторые говорят, что парсеры с рекурсивным спуском являются лучшими, потому что так сказал Бьярн Страустроп. Наш опыт показывает, что синтаксический анализ GLR - правильный ответ на этот вопрос, и наш интерфейс на основе GLR *1006* является хорошим доказательством, как и интерфейс Elsa. Наш интерфейс использовался в гневе на миллионах строк C ++ (включая диалекты Microsoft и GCC) для проведения анализа программ и масштабного преобразования исходного кода.

Но недостаточно подчеркивается, что синтаксический анализ - это лишь малая часть того, что требуется для сборки компилятора, особенно для C ++. Вам также необходимо создать таблицы символов («что означает этот идентификатор в этом контексте?») И для этого вам необходимо закодировать практически все несколько сотен страниц стандарта C ++. Мы считаем, что фундамент, на котором мы создаем инструменты, подобные компилятору, DMS , чрезвычайно хорош для этого, и нам потребовался человеко-год, чтобы сделать эту часть правильной.

Но тогда вам нужно рассмотреть остальную часть компилятора:

• Препроцессор
• АСТ строительство
• Семантический анализ и проверка типов
• Управление, поток данных и анализ указателей
• Генерация базового кода
• Оптимизация
• Регистр распределения
• Окончательная генерация кода
• Поддержка отладки

Я продолжаю говорить следующее: создание синтаксического анализатора (часть BNF) для языка похоже на восхождение в предгорьях Гималаев. Создание полного компилятора похоже на восхождение на Эверест. Почти любой ком может сделать первое (хотя C ++ прямо на краю). Только действительно серьезные делают последнее, и только когда очень хорошо подготовлены.

Ожидайте, что сборка C ++ займет у вас годы.

(Внешний интерфейс SD C ++ обрабатывает лексирование, синтаксический анализ, генерацию AST, таблицы символов, некоторую проверку типов и восстановление скомпилированного исходного текста из AST, включая исходные комментарии, для основных диалектов C ++. сроком около 6 лет).

РЕДАКТИРОВАТЬ: май 2015 года. Первоначальный ответ был написан в 2010 году; теперь мы потратили 11 лет, взяв нас на C ++ 14. Дело в том, что создание одного из них - это бесконечные большие усилия.

Answer 6

Это нетривиальная проблема, и довольно много времени нужно сделать правильно. Во-первых, грамматика для C ++ не полностью разбирается LALR-парсером , таким как yacc. Вы можете делать подмножества языка, но получить правильную полную спецификацию языка сложно.

Вы не первый человек, который думает, что это весело. Вот хорошая статья в стиле блога на эту тему: Разбор C ++

Вот важная цитата из статьи:

"После долгих исследований я решил, что написание анализатор / анализ-инструмент для C ++ достаточно сложно, что это помимо того, что я хочу сделать в качестве хобби. "

Проблема этой статьи в том, что она устарела, и некоторые ссылки не работают. Вот несколько ссылок на некоторые другие ресурсы по написанию синтаксических анализаторов C ++:

• Грамматики ANTLR (содержат несколько грамматик для C ++)
• грамматика C ++ 2.1 с поддержкой YACC и возникающие в результате неоднозначности
• Разбор и обработка кода C ++ (Википедия)

Answer 7

Во-первых, тег «flex» в SO относится к продукту Adobe, а не к генератору лексеров. Во-вторых, Бьярн Страуструп заявил, что ему хотелось бы реализовать Cfront (первый компилятор C ++) с использованием рекурсивного спуска, а не инструмента, управляемого таблицами. И в-третьих, чтобы ответить на ваш вопрос напрямую - много. Если вам кажется, что вам нужно написать один, взгляните на ANTLR - не мой любимый инструмент, но для него уже есть парсеры C ++.

Answer 8

Если вы уже не написали несколько других компиляторов; C ++ не является языком, для которого вы даже хотите начать писать компилятор с нуля, у языка много мест, где значение требует большого контекста, прежде чем ситуация может быть устранена.

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

Если вы делаете Google для "C ++ грамматик", есть пара, чтобы начать.

C++ LEX  Tokens:   http://www.computing.surrey.ac.uk/research/dsrg/fog/CxxLexer.l
C++ YACC Grammer:  http://www.computing.surrey.ac.uk/research/dsrg/fog/CxxGrammar.y
                   http://www.computing.surrey.ac.uk/research/dsrg/fog/CxxTester.y

Answer 9

Лекс, yacc не хватит. Вам нужен компоновщик, ассемблер тоже .., c препроцессором. Это зависит от того, как вы это делаете. Сколько готовых компонентов вы планируете использовать? Вам нужно откуда-нибудь получить описание синтаксиса и его токена.

Например, если вы используете LLVM, вы можете продолжить работу быстрее. Он уже предоставляет множество инструментов, ассемблер, компоновщик, оптимизатор .... Вы можете получить препроцессор c из проекта boost. Вам нужно создать набор тестов для автоматического тестирования вашего компилятора.

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

Answer 10

Несколько лет - если вы можете получить исследовательский грант, чтобы переписать новый lex / yacc: -)

Люди все чаще гоняются за этим - начиная со Страуструпа, который всегда мечтал стать «дизайнером» языка, а не настоящим автором компилятора (помните, что его C ++ был простым коденом целую вечность и все равно был бы там, если бы его не было) т для gcc и других людей).

Основная проблема заключается в том, что реальные исследования генераторов синтаксических анализаторов практически прекратились с тех пор, как процессоры стали достаточно быстрыми для обработки функциональных языков и рекурсивного спуска методом "грубой силы". Рекурсивный спуск - это последнее средство, когда вы не знаете, что делать, - он проводит исчерпывающий поиск, пока не соберет одно «правило», которое срабатывает. Если вы довольны этим, вы теряете интерес к поиску эффективных способов сделать это.

В сущности, вам понадобится разумный средний уровень - например, LALR (2) с фиксированным, ограниченным возвратом (плюс статическая проверка, чтобы выкрикивать, если «desiogner» превращается в недетерминированное дерево), а также ограниченная и секционированная обратная связь в таблице символов (современный парсер должен быть ориентирован на параллелизм).

Звучит как предложение на исследовательский грант, не правда ли :-) Теперь, если бы мы нашли кого-то, кто бы на самом деле его финансировал, это было бы что-то: -))