Недавно возникла проблема, необходимо было разработать небольшой интерпретатор. Причем необходимо было использовать его в проекте на .NET Framework и интерпретатор должен полностью состоять из управляемого кода, т.к. необходимо использовать CAS. Первое что приходит в голову в таких случаях это старый добрый bison. Давно проверенное и привычное средство автоматизированного построения парсеров, интерпретаторов и т.д. Первым делом я попытался найти аналог bison для C#. Действительно существует такое средство, называется Gardens Point Parser Generator (gppg). Инструмент не совсем поддерживает формат грамматики для bison и содержит отличия связанные с использованием .NET Framework и что самое главное, gppg ограничивает правую часть правила всего восемью членами. Конечно можно постараться преобразовать грамматику к такому виду, но это создает определенные неудобства, необходимо создавать дополнительные нетерминальные символы и т.д.
Просмотрев ряд других средств для построения интерпретаторов, я остановился на инструменте под названием ANother Tool for Language Recognition (ANTLR).
Как и bison ANTLR принимает на вход грамматику и генерирует на выходе синтаксический анализатор реализованный на целевом языке. ANTLR способен строить анализаторы для LL(*) грамматик – расширения LL(k) грамматик. Это дает большую свободу при описании языков в сравнении с LALR(1) грамматиками bison. Не вдаваясь в теоретические подробности рассмотрим следующую грамматику:
S::={ A | B }*
A::=a | a b c
B::=b dи следующую цепочку, являющуюся одним из порождений этой грамматики:
abd После прочтения терминала a и обнаружения терминала b в look-ahead буфере единичной длинны невозможно решить, является ли ab началом последовательности
abc, которую можно свернуть по правилу
A::=abc или же эту последовательность нужно сворачивать по правилам
A::=a и
B::=b d. Для этого решения необходима информация о терминале, следующем за b в рассматриваемой последовательности, т.е. буфер просмотра вперед должен содержать два терминала, а не один. Размер этого буфера у анализатора, сгенерированного bison как раз равен единице – он предназначен для разбора LALR(1)-грамматик. В этом случае Вам придется преобразовывать свою грамматику. При использовании ANTLR никаких преобразований не требуется.
Согласно описанию ANTLR, LL(*) грамматика – это LL(k) грамматика в которой k может неограниченно возрастать. Рассмотрим еще один пример:
// "int f(int x,int y);"
// "int f() {...}"
method ::= type ID '(' args ')' ';'
| type ID '(' args ')' '{' body '}'
type ::= 'void' | 'int'
// "int x, int y, int z, ..." args ::= arg (',' arg)*
arg ::= 'int' ID
body ::= ...
Такая грамматика не является LL(k) грамматикой, т.к. неизвестно какой длинны должен быть look-ahead буфер, т.е. нельзя заранее определить значение k. Это происходит потому, что цепочка начинающаяся с
type ID '(' далее может содержать неограниченное число конструкций arg, а для выбора альтернативы, в первом правеле, необходимо проанализировать последние 3 символа цепочки. Такая грамматика классифицируется как LL(*) и ANTLR начиная с версии 3 успешено справляется с такими грамматиками.
Целевым языком для bison является С++, для gppg – С#, для ANTLR это могут быть Java, С++ или С#. Для того чтобы не просто определить принадлежит ли некоторая цепочка заданной грамматике а еще и выполнять какие-то действия в процессе разбора этой цепочки в ANTLR как и в bison в каждом правиле задаются эти самые действия выраженные на целевом языке. Действия задаются для каждой альтернативы правила. И здесь снова прослеживается ряд приятных отличий от bison:
- существует блок init выполняемый перед кодом из любой альтернативы;
- правила могут иметь параметры;
- обращение к символам правой части правила осуществляется не по номерам а с помощью идентификаторов.
Создатели ANTLR утверждают, что многие приимущества при определении действий для правил являются следствием того, что ANTLR осуществляет LL рразбор, т.е. использует разбор сверху вниз, в отличии от bison и gppg, которые используют разбор снизу вверх.
Кроме того ANTLR выгодно отличается от других наличием визуальной среды разработки ANTLRWorks, позволяющей создавать и отлаживать грамматики.
Здесь приведены далеко не все возможности ANTLR, есть также возможность построения деревьев разбора, использовани синтаксических и сематических предикатов, которые позволяют разработчику вмешаться в процесс разбора, и многое другое.