Программное обеспечение лексического и синтаксического анализатора

Question

Программное обеспечение лексического и синтаксического анализатора

Я разрабатываю собственный язык на основе CSS-кода (CSS + нестандартное расширение), который в основном будет работать так:

[object.member.value = 5]{
object.member.anothervalue:8
object.member.yetanothervalue:'hello'
object.member.yetyetanothervalue.anothervalue:blue
}

В основном язык позволяет проверять некоторые условия (если они могут быть вложенными), а затем применять некоторые значения к объекту. Там нет петель.
Это будет храниться в виде текстовых файлов и загружаться в приложение (C ++) во время запуска.

Идея состоит в том, чтобы перевести этот CSS-файл в дерево C ++ или что-то подобное, что можно оценить во время выполнения..

Я рассматриваю возможность использования некоторых лексических анализаторов и токенизаторов (Yacc, Flex, Bison и т. Д.).

Что бы вы предложили использовать инструменты / библиотеки?

1

analyzer c++flex-lexer lexical yacc

Решение

Другие решения

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

1

Вы можете взглянуть на Повысить дух, который позволяет легко писать лексические анализаторы (Boost.Lex) и парсеры (Boost.Qi). У него интересный подход, заключающийся в определении синтаксиса / грамматики непосредственно в коде C ++ вместо использования отдельного файла грамматики. Это портативный, стандартный, автономный и очень элегантный.

Вы могли бы рассмотреть Флекс и Бизон если ваш язык будет развиваться в нечто более сложное. Они используют тот же тип входных файлов, что и Lex & Yacc, которые являются их старшими эквивалентами Unix. Преимущество этих инструментов в том, что в них много литературы. Неудобно, что они генерируют код, смешивая свой скелетный код с частями, которые вы даете в файлах грамматики. Следовательно, его сложнее освоить и поддерживать.

Но в вашем особом случае у вас очень простой язык с парой токенов и, очевидно, простая «LL (1) грамматика». (например, синтаксический анализатор должен прочитать один токен вперед, чтобы без двусмысленности определить, что он собирается анализировать). Было бы легко создать свой собственный код, используя eventuell <regex> упростить сканирование токенов и создание объектов, соответствующих вашим языковым структурам.

1

Источник

Accepted Answer

Если вы собираетесь делать такие вещи более одного раза, узнайте, как использовать генераторы парсеров. Это избавит вас от боли в долгосрочной перспективе.

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

Остальное предполагает, что вы будете использовать flex а также bison (которые lex а также yacc двойники.) Вам не нужно; Есть много альтернатив. Если вы решили попробовать одну из других альтернатив, игнорируйте остальную часть этого ответа.

Но flex а также bison это надежные, хорошо обслуживаемые, хорошо отлаженные пакеты с большим количеством документации, и они широко использовались в течение длительного периода времени. Сначала прочтите документацию.

flex будет читать из стандартного ввода или предоставленного дескриптора файла автоматически. Пусть это сделает это.
flex будет отслеживать номера строк для вас. Пусть это сделает это.
bison автоматически сгенерирует для вас номера токенов. Пусть это сделает это.
bison а также flex оптимизированы для односимвольных токенов. Вам не только не нужно указывать номера токенов, вам даже не нужно указывать имена токенов. В вашем гибком файле просто поместите это в конце или ближе к концу:
```
. { return yytext[0]; }
```
и не надо писать правила для обработки односимвольных токенов. Не беспокойтесь о том, что вы будете токенизировать нелегальных персонажей; bison выдаст сообщение об ошибке для вас.
Однако не позволяйте flex вставить правило по умолчанию. (%option nodefault достаточно, чтобы подавить это.)

Пара других советов:

Даже если yytext является глобальным, притворяться, что это не так. Вы должны скопировать любую строку, которая необходима для дальнейшей обработки. strdup твой друг; использовать его, а не возиться с malloc а также strcpy, использование asprintf также; char* out; asprintf(&out, "%s%s%s", s1, s2, s3); это самый простой способ объединить три строки. Легко доступны неограниченные реализации для платформ, которые не имеют этих вещей, так что не беспокойтесь об аргументах «но они не Posix / Standard C / yadda yadda yadda». И даже не думайте о буферах фиксированной длины. Вы не нуждаетесь в них. Честный.
С другой стороны, если токен может быть обработан в сканере, сделайте это там. Числа, например; это гораздо проще сделать strtol один раз в сканере, и тогда вам даже не нужно думать о распределении памяти.
Не забудь free() Строки, когда они вам больше не нужны, но если вам трудно, начните с утечки памяти, а затем исправьте ситуацию после того, как ваш парсер заработает. (Я знаю, что некоторые люди сочтут это кощунственным, но если вы помните, что делаете это до начала производства, это нормально; вы почувствуете себя гораздо более мотивированным, как только начнете работать с основами.)

И наконец:

Используйте достаточно актуальную версию bison, Если вы столкнулись с таинственным сдвигом / уменьшением конфликтов, используйте glr парсер: да, это немного медленнее, но если это спасет тебя от боли, оно того стоит. Вы всегда можете вернуться и исправить вещи позже. (Парсеры GLR не спасут вас от всех грамматических проблем. Вам все равно нужно убедиться, что ваша грамматика не является двусмысленной. Но они могут помочь.)
Моя личная рекомендация: используйте C интерфейсы. Это нормально для компиляции с C ++, и вы можете использовать стандартные контейнеры C ++ и другие полезные функции; просто не используйте их в своих семантических ценностях, потому что это не очень хорошо bisonУправление внутренним стеком. (Тем не менее, указатели на контейнеры C ++ хороши.) И помните, что flex а также bison просто контролировать поток; большая часть вашей программы будет написана на C / C ++, так что вы не входите в новый мир, используя инструменты компилятора. Вы также не получаете бесплатный пропуск: вам нужно знать, как использовать C / C ++, прежде чем вы начнете писать свой парсер.

Надеюсь, это поможет. Удачи.

1