Автор: Artyom
Год публикации: 2003
ANTLR —
ANother Tool for Language Recognition (
www.antlr.org) набор средств для написания парсеров. Подобные средства оказываются незаменимыми, если необходимо использовать в работе программы данные какого-нибудь сложного формата:
- текстовые конфигурационные файлы;
- файлы скриптов, данные стандартных протоколов, таких как HTTP, SQL и т. д.
Написание модулей, разбирающих эти данные, вручную является очень трудоемкой задачей и не всегда гарантирует хороший результат — результат, как правило, представляет собой многие килобайты кода, который достаточно сложно отлаживать. Использование готовых парсеров для стандартных типов данных (ASN.1, SQL и т. д.) тоже не всегда приемлемо, т.к. при этом навязывается структура хранения разобранных данных.
ANTLR, как и многие другие подобные средства, состоит из библиотеки классов, облегчающих основные операции при разборе (буферизация, поиск и т. д.), и утилиты, генерирующей код парсера на основе файла, описывающего грамматику разбираемого языка. Сам ANTLR написан на Java, но позволяет генерировать код на Java и C++. В качестве источника данных, используется класс потока, что позволяет разбирать данные, находящиеся в файле, в памяти процесса или приходящие по сети. Результатом работы ANTLR являются два класса — лексер и парсер. Лексер разбивает поток символов на поток токенов в соответствии с правилами, а парсер обрабатывает поток токенов в соответствии с другими правилами. Правила пишутся в грамматике на специальном языке, основанном на регулярных выражениях.
Краткая справка элементов языка грамматики приведена ниже.
Symbol Description
(...) подпрвило
(...)* повторение подправила 0 или более раз
(...)+ Повторение подправила 1 или более раз
(...)? подправило, может отсутствовать
{...} семантические действия (на языке, использующемся в качестве выходного, напр. Java)
[...] параметры правила
{...}? Semantic predicate(см. ниже)
(...)=> Syntactic predicate(см ниже)
| оператор альтернативы
.. оператор диапазона
~ отрицание
. любой символ
= присвоение
: метка, начало правила
; конец правила
class класс грамматики
extends определяет базовый класс для грамматики
returns описание возвращаемого значения для правила
options секция опций
tokens секция токенов
header заголовок
Для наглядности рассмотрим простой пример.
На вход парсера поступают данные в виде пар имя-число. Имена и числа могут быть разделены пробелами, символами табуляции и перевода строки. Заканчивается список ключевым словом "END". Итак, попробуем написать грамматику для программы, разбирающей подобные данные.
Начнем с лексера.
class MyLexer extends Lexer;
// опции лексера.
options{
// диапазон возможных символов (0-127 ASCII).
charVocabulary = ''..'177';
}
// правило для имени (состоит из букв и цифр, первый символ - буква).
NAME: (('a'..'z')|('A'..'Z'))
(('a'..'z')|('A'..'Z')|('0'..'9'))*
;
// правило для числа (произвольное количество цифр)
NUM: ('0'..'9')+;
// правило для разделителей (пробелы, символы перевода
// строки, табуляции в любых комбинациях).
SPACES: (
' '|'t'|
//Когда встречаем символ перевода строки
//необходимо вызвать метод newline() для правильной
//нумерации строк.
(('n'|"rn"){newline();})
)+
// Не разбирать этот тип токенов в парсере.
{$setType(Token.SKIP);}
;
Теперь лексер готов. Он преобразует поток символов в поток токенов типа NAME и NUM.
Примечание: имена правил для лексера должны начинаться с заглавной буквы, а для парсера — с прописной.
Итак, напишем парсер, который обработает данный поток токенов.
class MyParser extends Parser;
mainRule:
(element)+
"END"
;
element:
NAME NUM
;
Вот и все. Помещаем это в один файл (напр. Example1.g). Вызываем ANTLR:
java antlr.Tool Example1.g
В результате получаем несколько файлов исходного кода. Теперь напишем программу, использующую данный парсер.
import java.io.*;
public class Proba
{
public static void main (String[] args)
{
// создаем объект лексера. В качестве входа используем стандартный
// ввод.
MyLexer lexer = new MyLexer(new DataInputStream(System.in));
// создаем объект парсера
MyParser parser = new MyParser(lexer);
try{
// вызываем парсинг по правилу mainRule
parser.mainRule();
}catch(Exception e)
{
// обрабатываем ошибки
System.out.println("Error: "+e);
}
}
}
Компилируем программу (например, javac *.java) и запускаем. Можно запустить просто (java Proba) и писать на стандартный ввод данные, а можно переопределить ввод из файла (java Proba <proba.file). В случае несоответствия файла грамматике будут выведены ошибки. В противном случае ничего не случиться. Для того, чтобы программа делала что-то полезное, необходимо в грамматику добавить семантические действия. Например, при разборе можно добавить заполнение таблицы разобранными значениями.
header{
import java.util.*;
}
class MyParser extends Parser;
{
public Hashtable results = new Hashtable();
}
mainRule:
(element)+
"END"
;
element:
name:NAME number:NUM
{
results.put(name.getText(), number.getText());
}
;
class MyLexer extends Lexer;
options{
charVocabulary = ''..'177';
}
NAME: (('a'..'z')|('A'..'Z'))
(('a'..'z')|('A'..'Z')|('0'..'9'))*
;
NUM: ('0'..'9')+;
SPACES: (
' '|'t'|
(('n'|"rn"){newline();})
)+
{$setType(Token.SKIP);}
;
Для вывода результатов немного изменим главный класс:
import java.io.*;
import java.util.*;
public class Proba
{
public static void main (String[] args)
{
MyLexer lexer = new MyLexer(new DataInputStream(System.in));
MyParser parser = new MyParser(lexer);
try{
parser.mainRule();
}catch(Exception e)
{
System.out.println("Error: "+e);
System.exit(0);
}
// Отображаем содержимое таблицы.
Enumeration keys = parser.results.keys();
while(keys.hasMoreElements())
{
String key = (String)keys.nextElement();
System.out.println(">" + key + " " + parser.results.get(key));
}
// Задержка до нажатия ENTER
try{
System.in.read();
}catch(Exception e){}
}
}
Теперь программа делает что-то полезное для общества.
Теперь добавим в грамматику разбор(точнее пропуск) комментариев. Комментарии сделаем по образу и подобию С. Для этого в лексер добавим следующее правило:
COMMENT:
"/*"
(
{ LA(2)!='/' }? '*'
| 'r' 'n' {newline();}
| 'r' {newline();}
| 'n' {newline();}
| ~('*'|'n'|'r')
)*
"*/"
{$setType(Token.SKIP);}
;
В данном случае внутри комментария могут встречаться символы "*", но признаком окончания комментария являются не все. ANTLR принимает решение относительно того, какое правило использовать на основе k символов "впереди" текущей позиции. К называется глубиной предыскания. По умолчанию k=1, но его можно изменить в опциях. Однако, увеличение k ведет к увеличению сложности парсера, так что даже в больших парсерах не рекомендуется использовать k>2. Однако, если увеличение k не целесообразно, или разбор зависит от каких-нибудь внешних факторов (например, необходима проверка по таблице символов), можно использовать semantic predicate (семантическое утверждение?). Оно выглядит так:
Подправило выполняется только когда выражение принимает значение true. Выражение должно быть написано на языке исходного кода (в нашем примере это Java). Подправило обязательно должно иметь альтернативу, пусть даже пустую. Внутри фигурных скобок можно использовать несколько очень полезных функций.
Лексер:
LA(n) — возвращает символ, стоящий на n позиций впереди текущей позиции.
Парсер:
LA(n) — возвращает тип токена, стоящего впереди текущей позиции на n токенов. Тип токена — целое число, присваиваемое токенам в соответствии с тем, какому правилу они удовлетворяют. ANTLR задает константы для типов. Для токена, соответствующему правилу константа типа выглядит как имя правила (напр. NAME).Для токена, соответствующего литералу, константа выглядит как LITERAL_литерал (напр. LITERAL_END).
LT(n) — возвращает токен, стоящий впереди текущей позиции на n токенов. Класс возвращаемого значения Token. Из полезных методов этого класса можно выделить 2: getType() — возвращает тип токена (LT(n).getType() аналогично LA(n)) и getText() — возвращает значение токена.
Конечно, в данной статье описана лишь малая часть всех возможностей ANTLR, но, надеюсь, приведенные здесь примеры могут помочь начинающему понять основные принципы работы ANTLR и подобных ему средств. Более подробную и полную информацию, документацию, примеры грамматик для стандартных типов данных, можно получить на сайте ANTLR.
Удачи!