Есть ли альтернатива flex/bison, которую можно использовать в 8-битных встроенных системах?
Я пишу небольшой интерпретатор для простого языка, похожего на BASIC, в качестве упражнения на микроконтроллере AVR в C с использованием цепочки инструментов avr-gcc. Однако мне интересно, есть ли какие-нибудь инструменты с открытым исходным кодом, которые могли бы помочь мне написать лексер и парсер.
Если бы я написал это для запуска на моем Linux-компьютере, я мог бы использовать flex/bison. Теперь, когда я ограничился 8-битной платформой, я должен делать все вручную или нет?
6 ответов
Я реализовал парсер для простого командного языка, предназначенного для ATmega328p. Этот чип имеет 32 КБ ПЗУ и только 2 КБ ОЗУ. RAM, безусловно, является более важным ограничением - если вы еще не привязаны к конкретному чипу, выберите тот, у которого как можно больше памяти. Это сделает вашу жизнь намного проще.
Сначала я подумал об использовании flex/bison. Я отказался от этого варианта по двум основным причинам:
- По умолчанию Flex & Bison зависят от некоторых стандартных библиотечных функций (особенно для ввода-вывода), которые недоступны или не работают одинаково в avr-libc. Я почти уверен, что есть поддерживаемые обходные пути, но это дополнительные усилия, которые вам необходимо принять во внимание.
- У AVR есть Гарвардская Архитектура. C не предназначен для учета этого, поэтому даже постоянные переменные загружаются в RAM по умолчанию. Вы должны использовать специальные макросы / функции для хранения и доступа к данным во флэш-памяти и EEPROM. Flex & Bison создает несколько сравнительно больших справочных таблиц, и они довольно быстро израсходуют вашу оперативную память. Если я не ошибаюсь (что вполне возможно), вам придется отредактировать источник вывода, чтобы воспользоваться преимуществами специальных интерфейсов Flash и EEPROM.
Отказавшись от Flex & Bison, я отправился на поиски других инструментов генератора. Вот некоторые из них, которые я рассмотрел:
Вы также можете взглянуть на сравнение Википедии.
В конечном итоге я закончил ручным кодированием как лексера, так и парсера.
Для разбора я использовал парсер рекурсивного спуска. Я думаю, что Ира Бакстер уже проделала адекватную работу по освещению этой темы, и в Интернете есть множество учебных пособий.
Для моего лексера я написал регулярные выражения для всех своих терминалов, нарисовал эквивалентный конечный автомат и реализовал его как одну гигантскую функцию, используя gotoдля прыжков между штатами. Это было утомительно, но результаты работали отлично. Как в сторону, goto Это отличный инструмент для реализации конечных автоматов - все ваши состояния могут иметь четкие метки рядом с соответствующим кодом, нет вызова функции или служебной переменной состояния, и это происходит так быстро, как вы можете получить. C действительно не имеет лучшей конструкции для создания статических автоматов.
О чем стоит подумать: лексеры - это просто специализация парсеров. Самым большим отличием является то, что регулярных грамматик обычно достаточно для лексического анализа, тогда как большинство языков программирования имеют (в основном) контекстно-свободные грамматики. Так что на самом деле ничто не мешает вам реализовать лексер как парсер рекурсивного спуска или использовать генератор парсера для написания лексера. Обычно это не так удобно, как использование более специализированного инструмента.
Если вы хотите простой способ кодирования синтаксических анализаторов, или у вас мало места, вы должны вручную написать парсер рекурсивного спуска; это по сути LL(1) парсеры. Это особенно эффективно для языков, которые так же "просты", как и Basic. (Я сделал несколько из них еще в 70-х!). Хорошей новостью является то, что они не содержат библиотечного кода; только то, что ты пишешь.
Их довольно легко кодировать, если у вас уже есть грамматика. Во-первых, вы должны избавиться от левых рекурсивных правил (например, X = X Y). Это обычно довольно легко сделать, поэтому я оставляю это как упражнение. (Вы не должны делать это для правил формирования списка; см. Обсуждение ниже).
Тогда, если у вас есть правило БНФ в форме:
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-ответ /questions/46102129/postroenie-abstraktnogo-sintaksicheskogo-dereva-so-spiskom-tokenov/46102146#46102146
Июль 2015:
Есть много людей, которые хотят написать простой оценщик выражений. Вы можете сделать это, выполнив те же действия, что и в приведенной выше ссылке "AST builder"; просто делайте арифметику вместо построения узлов дерева. Вот вычислитель выражений, сделанный таким образом.
Вы можете использовать flex/bison в Linux с его собственным gcc для генерации кода, который вы затем будете кросс-компилировать с вашим AVR gcc для встроенной цели.
GCC может выполнять кросс-компиляцию для различных платформ, но вы запускаете flex и bison на той платформе, на которой работает компилятор. Они просто выкладывают C-код, который затем создает компилятор. Протестируйте его, чтобы увидеть, насколько велик конечный исполняемый файл. Обратите внимание, что у них есть библиотеки времени выполнения (libfl.a и т. д.) что вам также нужно будет выполнить кросс-компиляцию для вашей цели.
Попробуйте Boost::Spirit. Это библиотека только для заголовков, в которую вы можете заскочить и создать очень быстрый, чистый парсер полностью на C++. Перегруженные операторы в C++ используются вместо специального файла грамматики.
Вместо того, чтобы заново изобретать колесо, взгляните на http://www.lua.org/. Это интерпретирующий язык, предназначенный для встраивания в другое программное обеспечение и используемый в небольших системах, таких как встроенные системы. Встроенное процедурное дерево синтаксического синтаксического анализа, логика управления, математика и поддержка переменных - нет необходимости заново изобретать то, что тысячи других уже отладили и использовали. И это расширяемый, то есть вы можете добавить к грамматике, добавив свои собственные функции Си.