Я пишу небольшой интерпретатор для простого языка, подобного BASIC, в качестве упражнения на микроконтроллере AVR на C с использованием инструментальной цепочки avr-gcc. Однако мне интересно, есть ли какие-нибудь инструменты с открытым исходным кодом, которые могли бы помочь мне написать лексер и парсер.
Если бы я написал это для работы на моем Linux-компьютере, я бы мог использовать flex / bison. Теперь, когда я ограничился 8-битной платформой, мне нужно делать все вручную, или нет?
Я реализовал парсер для простого командного языка, предназначенного для ATmega328p. Этот чип имеет 32 КБ ПЗУ и только 2 КБ ОЗУ. ОЗУ, безусловно, является более важным ограничением - если вы еще не привязаны к конкретному чипу, выберите тот, у которого как можно больше ОЗУ. Это сделает вашу жизнь намного проще.
Сначала я подумал об использовании flex / bison. Я отказался от этого варианта по двум основным причинам:
Отказавшись от Flex & Bison, я пошел искать другие инструменты-генераторы. Вот некоторые из них:
Вы также можете взглянуть на сравнение Википедии.
В конце концов, я написал и лексер, и парсер вручную.
Для парсинга я использовал парсер с рекурсивным спуском. Я думаю, Ира Бакстер уже проделала адекватную работу по освещению этой темы, и в Интернете есть множество руководств.
Для своего лексера я написал регулярные выражения для всех своих терминалов, построил схему эквивалентного конечного автомата и реализовал его как одну гигантскую функцию, используя goto для перехода между состояниями. Это было утомительно, но результат оказался отличным. Кроме того, goto - отличный инструмент для реализации конечных автоматов - все ваши состояния могут иметь четкие метки рядом с соответствующим кодом, нет никаких дополнительных затрат на вызов функций или переменных состояния, и это примерно настолько быстро, насколько это возможно. У C действительно нет лучшей конструкции для создания статических конечных автоматов.
Есть над чем подумать: на самом деле лексеры - это просто специализация парсеров. Самая большая разница в том, что обычных грамматик обычно достаточно для лексического анализа, тогда как в большинстве языков программирования есть (в основном) контекстно-свободные грамматики. Так что на самом деле ничто не мешает вам реализовать лексер в качестве парсера рекурсивного спуска или использовать генератор парсера для написания лексера. Это обычно не так удобно, как использование более специализированного инструмента.
Если вам нужен простой способ кодирования синтаксических анализаторов или у вас мало места, вам следует вручную написать синтаксический анализатор с рекурсивным спуском; по сути, это LL (1) парсеры. Это особенно эффективно для таких «простых» языков, как Basic. (Я сделал несколько таких еще в 70-х!). Хорошая новость в том, что они не содержат библиотечного кода; просто то, что пишешь.
Их довольно легко закодировать, если у вас уже есть грамматика. Во-первых, вам нужно избавиться от леворекурсивных правил (например, X = X Y). Обычно это довольно легко сделать, поэтому я оставлю это как упражнение. (Для правил формирования списков этого делать не обязательно; см. Обсуждение ниже).
Тогда, если у вас есть правило 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" выше; просто выполняйте арифметические операции вместо построения узлов дерева. Вот вычислитель выражений, выполненный таким образом.
T = '(' T ')' | epsilon как я могу сообщить об ошибке синтаксиса для потоков токенов, таких как (())()? Грамматика останавливается и возвращает истину, когда потребляет 2-й ) и никогда не видит ().
- person Dante; 06.11.2017
Вы можете использовать flex / bison в Linux с его собственным gcc для генерации кода, который затем вы будете кросс-компилировать с вашим AVR gcc для встроенной цели.
GCC может выполнять кросс-компиляцию для различных платформ, но вы запускаете flex и bison на платформе, на которой работает компилятор. Они просто выплевывают код C, который затем строит компилятор. Протестируйте его, чтобы увидеть, насколько велик полученный исполняемый файл на самом деле. Обратите внимание, что у них есть библиотеки времени выполнения (libfl.a и т. Д.), Которые вам также придется скомпилировать для вашей цели.
Попробуйте Boost :: Spirit. Это библиотека только для заголовков, которую вы можете добавить и создать очень быстрый и чистый синтаксический анализатор полностью на C ++. В C ++ вместо специального файла грамматики используются перегруженные операторы.
Вместо того чтобы изобретать колесо заново, взгляните на LUA: www.lua.org. Это интерпретируемый язык, предназначенный для встраивания в другое программное обеспечение и использования в небольших системах, таких как встроенные системы. Встроенное дерево синтаксического анализа процедур, логика управления, математическая поддержка и поддержка переменных - нет необходимости заново изобретать то, что тысячи других уже отлаживали и использовали. И он расширяемый, то есть вы можете добавлять в грамматику свои собственные функции C.
