Лучшее решение, чем lex / yacc для разбора DSL в C?

Question

Одна из моих программ принимает команды (например, kill foo) во время выполнения.Думайте об этом как о небольшом предметно-ориентированном языке.Вот несколько примеров:

kill
kill client
exit

Но также разрешены цепочечные команды, и пробел не имеет значения до и после команд, поэтому допустимы также следующие примеры:

kill ; say "that was fun"
  kill  ;  kill      ; kill;

Iв настоящее время реализовали это с помощью lex / yacc (если быть точным, flex / bison), и это вызвало много головной боли.Лексер очень сильно зависит от контекста (например, токены пробелов обычно не возвращаются, если, например, после ключевого слова kill) и имеет много разных состояний.В грамматике возникали конфликты, и мне не очень нравится формат, в котором она должна быть указана (особенно $ 1, $ 2, $ 3,… для использования аргументов для нетерминалов).Кроме того, сообщения об ошибках, которые предоставляет bison (во время анализа), иногда точны, но часто нет (команда kill с необязательными аргументами приводит к сообщениям об ошибках, таких как Unexpected $undefined, expected $end or ; для kill clont вместо kill client).Наконец, C API для yacc является жестоким (внешний определяет везде).

Я не прошу вас решать все вышеупомянутые вопросы (я открою отдельные темы с более конкретными описаниями и кодом, если естьнет пути к lex / yacc).Вместо этого меня интересуют альтернативы lex / yacc.

Мои критерии следующие:

• Входные данные - это строка (const char *), нет выходных данных, но вместо этого некоторыекод должен вызываться для каждого отдельного ключевого слова.
• Я хочу использовать это с C (C99).
• Программное обеспечение должно быть уже включено в основные дистрибутивы Linux или, по крайней мере, легко объединяться /пакет.
• Это должно быть хорошо задокументировано.
• Синтаксис для описания моего языка должен быть простым.
• Он должен выводить значимые сообщения об ошибках при разборе ошибок.
• Производительность не так важна (конечно, она должна быть быстрой, но типичным вариантом использования является интерактивное использование, а не обработка тонн МБ команд).

Answer 1

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

Просто читайте ввод по одному символу за раз, разбивая на пробелы (хотя не в строке в кавычках).Каждая «команда» переводит машину в другое состояние, где она анализирует аргументы команды.";"или "\ n" верните машину в исходное состояние.

Answer 2

Что касается очень простой и маленькой грамматики, я бы подумал написать лексер / парсер вручную - часто это не так много работы.

Практически во всех дистрибутивах Linux имеется вариант lex / yacc. Кроме этого, два других широко используемых генератора синтаксических анализаторов: lemon и antlr .

Answer 3

Вы можете рассмотреть Ragel .Я недавно начал использовать его, и мне было приятно работать, как только вы наберете скорость.В вашем примере вы можете сделать что-то вроде (примечание: не проверено!):

#include <stdio.h>
#include <string.h>

%%{
    machine my_cmd_lang;

    action pk { printf("Killing %.*s\n", fpc-mark, mark); }
    action mk { mark = fpc; }

    k = 'kill'; # creates a machine that doesn't do anything
    x = 'exit' @{ printf("Exiting\n"); };
    arg = alpha+ >mk; # arg to kill is built in machine 'alpha' 1 or more times
    cmd = ((k space arg) @pk space* ';'?) | x;
    main := cmd* ;
}%%

%% write data;

int main(int argc, char* argv[]) {
    int cs;
    char* p = "kill client";
    char* pe = p + strlen(p);
    char* mark;

    %% write init;
    %% write exec;

    return 0;
}

Запустите его через Ragel с ragel <filename.rl>, и оно выплюнет <filename.c>.

Answer 4

Интересной альтернативой Lex & Yacc является Lemon парсер. У этого есть довольно много для этого, но я не использовал это всерьез, поэтому я не совсем уверен, насколько хорошо это действительно работает. Используется SQLite.

Answer 5

Мне очень нравится ANTLR , я несколько раз использовал его в производственных системах.

Что-то странное в том, что в версии 2 он поддерживает генерацию кода C ++, но не C, тогда как в версии 3 он поддерживает генерацию кода C, но не C ++. Мне нравится C ++, и я до сих пор использую ANTLR v2, но вам, вероятно, понравится v3. Тем лучше для тебя.

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

ANTLR не генерирует супер удивительные сообщения об ошибках "из коробки". Похоже, что это является чем-то общим для большинства общих систем синтаксического анализа, и, по сути, это не простая задача для решения. Однако, проделав некоторую работу, я увидел приличный диагностический вывод, поступающий из системы на основе ANTLR (в приложении была некоторая логика, помогающая выяснить, что сказать пользователю - ANTLR здесь не так уж много волшебства). 1009 *

Answer 6

Вам понадобится парсер без лексера (например, реализация PEG ). Поскольку вы используете C и уже знакомы с yacc, возможно, стоит попробовать что-то вроде , .

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