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

Ответ 1

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

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

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

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

Ответ 2

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

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

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

• EDG front-end используется большинством коммерческих поставщиков (Intel, Portland Group и т.д.) в своих компиляторах, Он стоит денег, но он очень тщательный. Люди платят большие деньги за это, потому что они не хотят иметь дело с болью, написав свой собственный парсер С++.

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

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

• Другие упомянули ANTLR, и для него есть грамматика С++, но я скептически настроен. Я не слышал о том, что передняя часть ANTLR используется в любых основных компиляторах, хотя я считаю, что она используется в среде IDE NetBeans. Он может быть подходящим для IDE, но я скептически отношусь к тому, что вы сможете использовать его для производственного кода.

Ответ 3

Похоже, вы довольно новичок в создании синтаксического анализа/компиляции. Если это так, я настоятельно рекомендую не начинать с С++. Это монстр языка.

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

Ответ 4

Долгое время, а lex и yacc не помогут

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

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

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

Ответ 5

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

Ответ 6

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

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

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

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

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

• ANTLR Грамматики (содержат несколько грамматик для С++)
• YACC-совместимая С++ 2.1 Грамматика и возникающие неоднозначности
• Анализ и обработка кода на С++ (Wikipedia)

Ответ 7

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

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

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

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

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

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

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

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

EDIT: май 2015. Оригинальный ответ был написан в 2010 году; теперь у нас есть 11 лет, и мы продвигаемся через С++ 14. Дело в том, что это бесконечное и большое усилие для создания одного из них.

Ответ 8

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

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

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

Ответ 9

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

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

Если вы делаете google для "С++ grammars", вас ждет пара.

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

Ответ 10

Компилятор С++ очень сложный. Чтобы реализовать достаточное количество С++ для совместимости с большинством кода на С++, несколько разработчиков на пару лет будут на полную ставку. clang - это проект компилятора, финансируемый Apple для разработки нового компилятора для C, С++ и Objective-C, с несколькими полнофункциональными приложениями, и поддержка С++ все еще очень далека от завершения через пару лет разработки.

Ответ 11

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

Люди постоянно преследуют свои хвосты - начиная с Stroustrup, которому всегда казалось, что он является "дизайнером" языка, а не фактическим составителем компилятора (помните, что его С++ был просто кодеген на века и был бы еще там, если бы он был "нет", t для gcc и других людей).

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

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

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

Ответ 12

Рекурсивный порядочный - хороший выбор для синтаксического анализа С++. GCC и clang используют его.

Анализатор Elsa (и мой компилятор ellcc) использует генератор компилятора Elkhound GLR.

В любом случае писать компилятор С++ - это БОЛЬШОЕ задание.

Ответ 13

Ну, что вы понимаете, написав компилятор?

Я сомневаюсь, что любой парень создал настоящий компилятор С++, который полностью переместил его на ассемблерный код, но я использовал lex и yacc для создания компилятора C, и я сделал это без него.

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

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

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