Если вы хотите простой способ кодирования синтаксических анализаторов, или у вас мало места, вы должны вручную написать парсер рекурсивного спуска; по сути это 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-ответ https://stackoverflow.com/a/25106688/120163
Июль 2015:
Есть много людей, которые хотят написать простой оценщик выражений. Вы можете сделать это, выполнив те же действия, что и приведенная выше ссылка на «AST builder»; просто делайте арифметику вместо построения узлов дерева.
Вот вычислитель выражений, сделанный таким образом .