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

если вы хотите простой способ кодирования парсеров, или вы ограничены в пространстве, вы должны вручную кодировать рекурсивный парсер спуска; это по существу LL(1) - парсеров. Это особенно эффективно для языков, которые так же "просты", как и основные. (Я сделал несколько из них еще в 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 битных слов было то, что вы могли бы получить.

---

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

август 2014:

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

июль 2015:

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

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

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

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

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