Является ли генератор синтаксического анализатора ANTLR лучшим для приложения C ++ с ограниченной памятью? - PullRequest
Новая
       9

Является ли генератор синтаксического анализатора ANTLR лучшим для приложения C ++ с ограниченной памятью?

7 голосов
/ 21 апреля 2009

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

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

  • Анализатор, который генерирует код C или C ++ с помощью MSVC. ANTLR 3 не поддерживает C ++; он утверждает, что генерирует прямой C, но документы о том, как заставить его работать, немного сбивают с толку.
  • Сильно ограниченное использование памяти. Память имеет огромное преимущество в нашем приложении, и даже крошечные утечки являются фатальными. Мне нужно иметь возможность переопределить распределитель памяти анализатора для использования нашего пользовательского malloc (), или, по крайней мере, мне нужно предоставить ему непрерывный пул, из которого он извлекает всю свою память (и который я могу впоследствии освободить в блоке). Я могу сэкономить около 200 КБ для самого исполняемого файла синтаксического анализатора, но какую бы динамическую кучу он ни выделил при разборе, впоследствии он должен быть освобожден.
  • Хорошая производительность. Это менее критично, но мы должны иметь возможность анализировать 100 КБ текста не более чем за секунду на 3 ГГц процессоре.
  • Должно быть без GPL. Мы не можем использовать код GNU.

Мне нравятся IDE и инструменты отладки ANTLRworks, но похоже, что заставить свою цель C работать с нашим приложением будет огромным трудом. Прежде чем я приступлю к этому опыту, является ли ANTLR подходящим инструментом для этой работы?

Текстовый формат выглядит примерно так: 

attribute "FluxCapacitance"  real constant

asset DeLorean
{
    //comment foo bar baz
    model "delorean.mdl"
    animation "gullwing.anm"
    references "Marty"
    loadonce
}

template TimeMachine
{
    attribute FluxCapacitance 10      
    asset DeLorean
}

Ответы [ 7 ]

4 голосов
/ 21 апреля 2009

ANTLR 3 не поддерживает C ++; это утверждает генерировать прямой C, но документы на заставить его на самом деле работать вроде путаницы.

Он генерирует C, и, кроме того, он работает с Visual Studio и C ++. Я знаю это, потому что я сделал это раньше и представил патч, чтобы заставить его работать с stdcall.

Память в нашем приложении очень важна и даже крошечные утечки смертельны. я нуждаюсь чтобы иметь возможность переопределить парсер Распределитель памяти для использования наших пользовательских malloc () или, по крайней мере, мне нужно дать ему непрерывный бассейн из который он тянет всю свою память (и который я могу освободить в блоке впоследствии). Я могу сэкономить около 200 КБ для самого исполняемого файла парсера, но какую динамическую кучу он выделяет в парсинг должен быть освобожден впоследствии.

Среда выполнения antlr3c, которую я проверял в прошлый раз, не имела утечки памяти и использует описанную вами парадигму пула памяти. Однако у него есть один недостаток в API, который автор отказывается изменить, а именно: если вы запрашиваете строку узла, он будет каждый раз создавать новую копию, пока вы не освободите весь анализатор.

У меня нет комментариев относительно простоты использования пользовательского malloc, но в нем есть макрос для определения, какую функцию malloc использовать во всем проекте.

Что касается размера исполняемого файла, размер моей компиляции составлял около 100 КБ, включая небольшой интерпретатор.

Я предлагаю вам продолжать изучать ANTLR, потому что он все еще соответствует вашим требованиям, и вам, вероятно, придется пожертвовать немного больше времени, прежде чем он начнет работать на вас.

4 голосов
/ 21 апреля 2009

Мы успешно используем Boost Spirit в нашем приложении. Лицензия Boost является очень либеральной, поэтому ее использование в коммерческих приложениях не представляет никаких проблем.

Цитата из документации:

Spirit - это объектно-ориентированная среда генератора синтаксического анализатора с рекурсивным спуском, реализованная с использованием методов метапрограммирования шаблонов. Шаблоны выражений позволяют нам полностью аппроксимировать синтаксис расширенной формы Backus-Normal (EBNF) в C ++. Платформа Spirit позволяет писать целевую грамматику исключительно на C ++. Встроенные спецификации грамматики EBNF могут свободно смешиваться с другим кодом C ++ и, благодаря мощным возможностям шаблонов C ++, могут быть немедленно выполнены. Оглядываясь назад, обычные компиляторы-компиляторы или парсеры-генераторы должны выполнить дополнительный шаг трансляции из исходного кода EBNF в код C или C ++.

2 голосов
/ 01 марта 2012

Пожалуйста, посмотрите на новую цель C ++, которую я опубликовал для ANTLR. Он также имеет возможность ограничить использование памяти анализатором и предоставляет все необходимые процедуры управления памятью в форме признаков.

http://www.antlr.org/wiki/pages/viewpage.action?pageId=29130826

2 голосов
/ 27 июня 2009

Парсер с ручным кодированием рекурсивного спуска на самом деле довольно быстрый и может быть очень компактным. Единственным недостатком является то, что вы должны быть осторожны кодировать по существу LL (1) грамматики. [Если вы используете ANTLR, у вас есть подобные ограничения, так что это не так уж и страшно].

Вы можете написать код для таких синтаксических анализаторов как простой рекурсивный C-код. (Смотрите этот ответ для полной информации: Есть ли альтернатива flex / bison, которую можно использовать в 8-битных встроенных системах? )

Если вы действительно ограничены в пространстве, вы можете определить синтаксический анализ виртуальную машину, и создайте крошечный интерпретатор C для ее запуска. Раньше я создавал интерпретаторы BASIC еще в начале 70-х годов.

Придерживаясь очень простых соглашений, которые делают эти парсеры действительно работают, вы можете гарантировать, что есть нет утечки памяти, вызванной механизмом синтаксического анализа. (Конечно, вы можете прикрепить произвольные действия к парсеру, где он распознает предметы интереса; вопрос утечки этих действий общего программирования, а не парсера).

Идеи пришли из статьи 1964 года о метакомпиляторах, написанной Val. Шорре, который показывает, как собрать полные компиляторы за 10 страниц. Крошечный генератор парсера Шорре производит довольно хороший рекурсивный спуск парсеры. Сайт с описанием этой статьи и показывая, как именно создавать такие парсеры, можно найти на http://www.bayfronttechnologies.com/metaii.html

Я использовал методы Шорре для создания базовых компиляторов в конце 70-х, после того, как я устал от ручного кодирования сложных грамматик.

1 голос
/ 21 апреля 2009

Тогда почему бы вам не использовать flex / yacc? Он генерирует код на C, может быть запущен из MSVC, разработан с учетом эффективности, может иметь переопределение malloc (google для yymalloc), они сами являются GPL, но полученный код (код, который вы используете в своем проекте) AFAIK нет. 1001 *

Или используйте парсер ручной работы.

0 голосов
/ 17 июня 2009

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

Я бы сказал, посмотрите на ANTLR и Spirit, также посмотрите на Flex и Bison. Есть и другие, менее известные парсеры, такие как Coco / R (также содержит генераторы для многих языков, включая C ++).

0 голосов
/ 21 апреля 2009

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

Упс, моя ошибка, поскольку ANTLR, по-видимому, генерирует рекурсивный спуск. Тем не менее, у меня были проблемы с генерацией больших парсеров ANTLR.

...