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

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

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

В остальном предполагается, что вы будете использовать 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++, прежде чем вы начнете писать свой синтаксический анализатор.

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

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

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

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

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