Есть ли альтернатива для flex / bison, которую можно использовать на 8-битных встроенных системах?

Я пишу небольшой интерпретатор для простого языка, подобного BASIC, в качестве упражнения на микроконтроллере AVR на C с использованием инструментальной цепочки avr-gcc. Однако мне интересно, есть ли какие-нибудь инструменты с открытым исходным кодом, которые могли бы помочь мне написать лексер и парсер.

Если бы я написал это для работы на моем Linux-компьютере, я мог бы использовать flex / bison. Теперь, когда я ограничился 8-битной платформой, мне нужно делать все вручную, или нет?

Я реализовал парсер для простого командного языка, предназначенного для ATmega328p . Этот чип имеет 32 КБ ПЗУ и только 2 КБ ОЗУ. ОЗУ, безусловно, является более важным ограничением - если вы еще не привязаны к конкретному чипу, выберите тот, у которого как можно больше ОЗУ. Это сделает вашу жизнь намного проще.

Сначала я подумал об использовании flex / bison. Я отказался от этого варианта по двум основным причинам:

• По умолчанию Flex & Bison зависит от некоторых стандартных библиотечных функций (особенно для ввода-вывода), которые недоступны или не работают одинаково в avr-libc. Я почти уверен, что есть поддерживаемые обходные пути, но вам нужно будет принять во внимание некоторые дополнительные усилия.
• AVR имеет Гарвардскую архитектуру . C не предназначен для этого, поэтому даже постоянные переменные по умолчанию загружаются в оперативную память . Вы должны использовать специальные макросы / функции для хранения и доступа к данным во флэш-памяти и EEPROM . Flex и Bison создают несколько относительно больших таблиц поиска, которые довольно быстро занимают вашу оперативную память. Если я не ошибаюсь (что вполне возможно), вам придется отредактировать выходной источник, чтобы воспользоваться преимуществами специальных интерфейсов Flash и EEPROM.

Отказавшись от Flex & Bison, я пошел искать другие инструменты-генераторы. Вот некоторые из них:

• ЛИМОН
• Рагель
• re2c

Вы также можете взглянуть на сравнение Википедии .

В конце концов, я написал кодирование и лексера, и парсера вручную.

Для разбора я использовал парсер с рекурсивным спуском. Я думаю, Ира Бакстер уже проделала адекватную работу по освещению этой темы, и в Интернете есть множество руководств.

Для своего лексера я написал регулярные выражения для всех своих терминалов, построил схему эквивалентного конечного автомата и реализовал его как одну гигантскую функцию, используя goto's для перехода между состояниями. Это было утомительно, но результат оказался отличным. Кроме того, gotoэто отличный инструмент для реализации конечных автоматов - все ваши состояния могут иметь четкие метки рядом с соответствующим кодом, нет никаких дополнительных затрат на вызов функций или переменных состояния, и это примерно так быстро, как вы можете получить. У C действительно нет лучшей конструкции для создания статических конечных автоматов.

Есть над чем подумать: на самом деле лексеры - это просто специализация парсеров. Самая большая разница в том, что для лексического анализа обычно достаточно обычных грамматик, тогда как в большинстве языков программирования есть (в основном) контекстно-свободные грамматики. Так что на самом деле ничто не мешает вам реализовать лексер в качестве парсера рекурсивного спуска или использовать генератор парсера для написания лексера. Это обычно не так удобно, как использование более специализированного инструмента.

Если вам нужен простой способ кодирования парсеров или у вас мало места, вам следует вручную написать парсер с рекурсивным спуском; по сути, это парсеры LL (1). Это особенно эффективно для таких «простых» языков, как Basic. (Я сделал несколько таких еще в 70-х!). Хорошая новость в том, что они не содержат библиотечного кода; просто то, что пишешь.

Их довольно легко закодировать, если у вас уже есть грамматика. Во-первых, вы должны избавиться от леворекурсивных правил (например, X = XY). Обычно это довольно легко сделать, поэтому я оставлю это как упражнение. (Для правил формирования списков этого делать не обязательно; см. Обсуждение ниже).

Тогда, если у вас есть правило BNF в форме:

 X = A B C ;

создать подпрограмму для каждого элемента в правиле (X, A, B, C), которая возвращает логическое значение «Я видел соответствующую синтаксическую конструкцию». Для X код:

subroutine X()
     if ~(A()) return false;
     if ~(B()) { error(); return false; }
     if ~(C()) { error(); return false; }
     // insert semantic action here: generate code, do the work, ....
     return true;
end X;

Аналогично для A, B, C.

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

Если ваше правило BNF рекурсивное ... не волнуйтесь. Просто закодируйте рекурсивный вызов. Это обрабатывает такие правила грамматики, как:

T  =  '('  T  ')' ;

Это можно закодировать как:

subroutine T()
     if ~(left_paren()) return false;
     if ~(T()) { error(); return false; }
     if ~(right_paren()) { error(); return false; }
     // insert semantic action here: generate code, do the work, ....
     return true;
end T;

Если у вас есть правило BNF с альтернативой:

 P = Q | R ;

затем введите P с альтернативными вариантами:

subroutine P()
    if ~(Q())
        {if ~(R()) return false;
         return true;
        }
    return true;
end P;

Иногда встречаются правила формирования списков. Они, как правило, рекурсивны слева, и в этом случае легко справиться. Основная идея состоит в том, чтобы использовать итерацию, а не рекурсию, и это позволяет избежать бесконечной рекурсии, которую вы могли бы получить, делая это «очевидным» способом. Пример:

L  =  A |  L A ;

Вы можете закодировать это, используя итерацию, как:

subroutine L()
    if ~(A()) then return false;
    while (A()) do { /* loop */ }
    return true;
end L;

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

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

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

Август 2014:

Я получаю много запросов, «как построить AST с парсером». Подробнее об этом, который по существу уточняет этот ответ, см. В другом моем ответе SO https://stackoverflow.com/a/25106688/120163

Июль 2015:

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

Вы можете использовать flex / bison в Linux с его собственным gcc, чтобы сгенерировать код, который вы затем скомпилируете с помощью своего AVR gcc для встроенной цели.

GCC может выполнять кросс-компиляцию для множества платформ, но вы запускаете flex и bison на платформе, на которой работает компилятор. Они просто выплевывают код C, который затем строит компилятор. Протестируйте его, чтобы увидеть, насколько велик полученный исполняемый файл. Обратите внимание, что у них есть библиотеки времени выполнения ( libfl.aи т. Д.), Которые вам также придется скомпилировать для своей цели.

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

Вместо того, чтобы заново изобретать колесо, взгляните на LUA: www.lua.org . Это интерпретируемый язык, предназначенный для встраивания в другое программное обеспечение и использования в небольших системах, таких как встроенные системы. Встроенное дерево синтаксического анализа процедур, логика управления, математическая поддержка и поддержка переменных - нет необходимости заново изобретать то, что тысячи других уже отлаживали и использовали. И он расширяемый, что означает, что вы можете добавлять в грамматику свои собственные функции C.