Введение в antlr
ANTLR (http://www.antlr.org/) - генератор парсеров написанный на Java.
ANTLR позволяет создавать лексические и синтаксические анализаторы на различных языках (Java,C,C++,Python, C#,ActionScript,JavaScript,PHP) на основе грамматик.
Для ANTLR существует среда разработки грамматик ANTLRWorks ( http://www.antlr.org/works/ ) со встроенным отладчиком, редактором и т.д.
Процесс создания анализатора можно описать следующим образом:
- создание грамматики для лексического анализатора
- создание грамматики для синтаксического анализатора
- отладка грамматики
- генерация классов лексического и синтаксического анализатора
- компиляция классов лексера(лексического анализатора) и парсера(синтаксического анализатора)
- использование классов для обработки текста
Лексические и синтаксические анализаторы могут применятся для:
- раскраска по синтаксическим правилам
- разбор файлов (например, конфигурации)
- создание интерпретаторов
- создание компиляторов
- создание DSL
Создадим простую грамматику для разбора некоторого файла конфигурации. Пусть файл конфигурации будет иметь формат:
// Single line comment
/*
multiline comment
*/
key=value;
key="value;
multiline value";
key=
value;
Для разбора такого текста нам понадобятся следующие правила:
- правило для однострочного комментария
- правило для многострочного комментария
- правило для пробельных символов
- правило для ключей
- правило для значений
Комментарии и пробельные символы являются незначащими, поэтому они переносятся в поток HIDDEN.
Правила для лексического анализатора будут иметь вид:
COMMENT
: '//' ~('\n'|'\r')* '\r'? '\n' {$channel=HIDDEN;}
| '/*' ( options {greedy=false;} : . )* '*/' {$channel=HIDDEN;}
;
WS : ( ' '
| '\t'
| '\r'
| '\n'
) {$channel=HIDDEN;}
;
Определимся с правилами для ключей. Ключ может состоять из множества символов (букв в разных регистрах) и цифр. Ключ всегда начинается с буквы.
Добавим следующие правила для букв и цифр:
fragment
LETTER
: ('a'..'z'|'A'..'Z');
fragment
DIGIT
: '0'..'9';
ключевое слово fragment указывает, что это не самостоятельные правила, а правила для других.
Добавим правила для идентификатора(ключа):
IDENTIFIER
: (LETTER|'_') (LETTER | DIGIT |'_')*;
Теперь необходимо добавить правила для чисел:
NUMBER
: DIGIT+;
Для разделителей:
DELIMETER
: ';';
Для строк:
STRING
: '"' ( options {greedy=false;} : . )* '"';
строки должны быть обёрнуты в кавычки, между кавычками разрешены любые символы кроме кавычки. options {greedy=false;} : - настраивает способ чтения символов из потока для правила.
Теперь приступим к написанию правил синтаксического анализатора.
Для начала создадим правило, которое описывает весь наш код, который состоит из множества выражений:
code: expression+;
Выражение состоит из утверждения и разделителя (или просто разделителя):
expression
: statement? DELIMETER ;
Утверждение состоит из пары ключ, значение, разделённых символом '='
statement: IDENTIFIER '=' value;
А само значение может быть идентификатором, строкой или числом:
value
: IDENTIFIER | STRING | NUMBER;
Результирующий файл грамматики будет выглядеть так:
grammar config;
options {
language=Java;
output=AST;
}
COMMENT
: '//' ~('\n'|'\r')* '\r'? '\n' {$channel=HIDDEN;}
| '/*' ( options {greedy=false;} : . )* '*/' {$channel=HIDDEN;}
;
WS : ( ' '
| '\t'
| '\r'
| '\n'
) {$channel=HIDDEN;}
;
fragment
LETTER
: ('a'..'z'|'A'..'Z');
fragment
DIGIT
: '0'..'9';
IDENTIFIER
: (LETTER|'_') (LETTER | DIGIT |'_')*;
NUMBER
: DIGIT+;
DELIMETER
: ';';
STRING
: '"' ( options {greedy=false;} : . )* '"';
value
: IDENTIFIER | STRING | NUMBER;
statement: IDENTIFIER '=' value;
expression
: statement? DELIMETER ;
code: expression+;
Откроем файл с грамматикой в ANTLRWorks и введём такой код для проверки:
// Single line comment
/*
multiline comment
*/
key=value;
key="value;
multiline value";
key=
value;
Key_1= value2;
_2=2;
Если выбрать правило code в выпадающем списке и нажать на кнопку play, то в окне вывода мы увидим синтаксическое дерево для нашего кода с конфигом. Окно будет выглядеть так:
Дерево в окне вывода представляет собой синтаксическое дерево построенное автоматически, однако для программного разбора необходимо построить другое дерево, которое больше подходит для разбора(убрать разделители и символы равенства, например). Для этого необходимо воспользоваться описанием преобразования правил (rewrite rule) в грамматике.