[an error occurred while processing this directive] IT • archiv :: Print

IT • archiv


[an error occurred while processing this directive]

[an error occurred while processing this directive]

Создайте свой собственный язык используя JavaCC

[an error occurred while processing this directive](none) [an error occurred while processing this directive](none)[an error occurred while processing this directive] ::
[an error occurred while processing this directive](none)
[an error occurred while processing this directive]([an error occurred while processing this directive] Оливер Ензелинг [an error occurred while processing this directive])

[an error occurred while processing this directive](none)

JavaCC позволяет легко написать свой собственный компилятор или интерпретатор для языка вашей собственной разработки на Java.

Cool Tools
PDF versionPDF версия
Обзор
В первой редакции новой колонки Cool Tools Оливер Ензелинг обсуждает JavaCC — the Java Compiler Compiler. JavaCC ускоряет создание и реализацию вашего собственного языка программирования на Java. Вы можете создать удобные небольшие языки для решения узких проблем или написать сложные компиляторы для языков вроде Java или C++. Или вы можете написать инструментарий, который будет разбирать исходники на Java и выполнять автоматический анализ и преобразования. Оливер обсудит основы построения компиляторов и покажет как создать удобный небольшой калькулятор, работающий из командной строки. (1670 слов)

Вас когда-нибудь интересовало как работает Java компилятор? Вам приходится писать парсеры для языков разметки, не подпадающие под стандарт HTML или XML? Или вы хотите написать свой собственный небольшой язык программирования просто ради интереса? JavaCC позволяет вам сделать все это на Java. Так что если вы просто хотите узнать больше о том, как работают компиляторы или интерпретаторы, или у вас есть амбиции создать язык, круче чем Java, присоединяйтесь к нашему исследованию JavaCC на примере создания удобного калькулятора командной строки.

Основы создания компиляторов

Языки программирования часто разделяют, несколько искусственно, на интерпретируемые и компилируемые, хотя эти границы зачастую размыты. Так что не стоит об этом так уж беспокоится. Концепции, расмотренные в этой статье, одинаково применимы для компилируемых и интерпретируемых языков. Мы будем использовать слово компилятор далее, но в рамках статьи, этот термин будет включать и интерпретатор.

Компиляторы должны уметь выполнять три основных действия над текстом программы (исходным кодом):

  1. Лексический анализ
  2. Синтаксический анализ
  3. Создание кода или выполнение

Основная работа компилятора сосредоточена на шагах 1 и 2, что включает разбор исходного кода программы и проверку его синтаксической правильности. Мы называем этот процесс парсингом (parsing), и за его выполнение отвечает парсер.

Лексический анализ (лексинг — lexing)

Лексический анализ поверхностно рассматривает исходный код программы и разбивает его на соответствующие токены (tokens). Токен- это значащая часть исходного кода. Примеры токенов включают ключевые слова, пунктуационные знаки, и литералы, такие как числа и строки. Нетокены включат пробелы, которые обычно игнорируются, но используются для разделения токенов, и комментарии.

Синтаксический анализ (парсинг — parsing)

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

Теория компьютерных языков выделяет программы, грамматику и языки. В этом смысле, программа- это набор токенов. Литерал- это базовый элемент, который не может быть разделен на более мелкие куски. Грамматика определяет правила для создания синтаксически корректных программ. Только программы, которые придерживаются правил игры, заданных в грамматике, считаются корректными. Язык программирования это просто набор всех программ, соответсвующих всем правилам грамматики.

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

Грамматика компьютерного языка может быть однозначно и полностью задана с помощью нотации EBNF (Расширенной формы Бакуса-Наура — Extended Backus-Naur-Form) (вы можете узнать больше об EBNF в Ресурсах). EBNF определяет грамматику в терминах порождающих правил (production rules). Порождающее правило определяет, что элементы грамматики — либо литералы, либо сложные элементы — могут быть собраны из других элементов грамматики. Литералы, как элементарные единицы- это ключевые слова или фрагменты статического текста программы, такие как знаки пунктуации. Сложные элементы получаются в результате применения порождающих правил. Порождающие правила соответствуют следующему общему формату:

GRAMMAR_ELEMENT := список элементов грамматики
             | альтернативный список элементов грамматики
 

В качестве примера, давайте рассмотрим правила грамматики для небольшого языка, который описывает простейшие арифметические выражения:

expr := number
       | expr '+' expr
       | expr '-' expr
       | expr '*' expr
       | expr '/' expr
       | '(' expr ')'
       | -expr
 number := digit+ ('.' digit+)?
 digit := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
 

Три порождающих правила определяют элементы грамматики:

  • expr
  • number
  • digit

Язык, заданный такой грамматикой, позволяет нам задавать арифметические выражения. expr является либо числом, либо одним из четырех выражений, примененных к двум expr-ам, expr и скобкам, или отрицательному expr. number- это число с плавающей точкой, с необязательным значением после запятой. digit должен быть одной из обычных десятичных цифр.

Создание и выполнение кода

После того как парсер успешно разбирает программу без ошибок, она существует во внутреннем представлении, которое легко может быть обработано компилятором. Теперь уже сравнительно легко создать машинный код (или Java байткод в нашем случае) из этого представления или выполнить его непосредственно. В первом случае мы компилируем, во втором — интерпретируем.

JavaCC

JavaCC, доступный бесплатно, это генератор парсеров. Он обеспечивает расширение языка Java для задания грамматики нового языка программирования. JavaCC изначально был разработан Sun Microsystems, но в настоящее время поддерживается MetaMata. Как любой порядочный инструментарий программирования, JavaCC использовался для создания грамматики входного формата JavaCC.

Более того, JavaCC позволяет нам задавать грамматики в виде, сходном с EBNF, делая легким перенос грамматик EBNF в формат JavaCC. Кроме того, JavaCC является самым популярным инструментом для создания парсеров на Java, с большим набором готовых JavaCC грамматик, доступных как отправная точка.

Разработка простого калькулятора

Теперь мы вернемся к нашему маленькому арифметическому языку, чтобы построить простой калькулятор на Java, используя JavaCC. В начале мы должны оттранслировать грамматику EBNF в формат JavaCC и сохранить ее как файл Arithmetic.jj:

options
 {
     LOOKAHEAD=2;
 }

 PARSER_BEGIN(Arithmetic)

 public class Arithmetic
 {
 }

 PARSER_END(Arithmetic)

 SKIP :
 {
     " "
 | "\r"
 | "\t"
 }

 TOKEN:
 {
     < NUMBER: (<DIGIT>)+ ( "." (<DIGIT>)+ )? >
 | < DIGIT: ["0"-"9"] >
 }

 double expr():
 {
 }
 {
     term() ( "+" expr() | "-" expr() )*
 }

 double term():
 {
 }
 {
     unary() ( "*" term() | "/" term() )*
 }

 double unary():
 {
 }
 {
     "-" element() | element()
 }

 double element():
 {
 }
 {
     <NUMBER> | "(" expr() ")"
 }
 

Приведенный код должен дать вам представление о том, как задавать грамматику для JavaCC. Секция options вверху задает набор опций для нашей грамматики. Мы задали lookahead равным 2. Дополнительные опции управляют отладочным интерфейсом JavaCC и другими возможностями. Эти же опции могут быть заданы и из командной строки JavaCC.

Инструкция PARSER_BEGIN задает что дальше будет идти определение класса парсера. JavaCC создает класс Java для каждого парсера. Мы называем класс парсера Arithmetic. Для начала нам требуется только пустое определение класса; JavaCC добавит декларации, которые относятся к парсингу, позже. Мы завершаем определение класса инструкцией PARSER_END.

Секция SKIP определяет символы, которые мы хотим пропустить. В нашем случае, это пробелы. Далее, мы определяем токены для нашего языка в секции TOKEN. Мы задали числа и цифры, как токены. Заметьте, что JavaCC различает определения токенов и определения для других порождающих правил, которые отличаются от EBNF. Секции SKIP и TOKEN задают лексический анализ для этой грамматики.

Далее мы определяем порождающие правила для expr, грамматического элемента верхнего уровня. Заметьте, как это определение сильно отличается от определения expr в EBNF. Что же тут происходит? Оказывается, определение в EBNF неоднозначно, так как позволяет создавать множественные представления одной и той же программы. Например, давайте рассмотрим выражение 1+2*3. Мы можем создать expr со значением 1+2 и получить expr*3, как на Рисунке 1.

Дерево разбора EBNF для 1+2*3.
Рисунок 1. Дерево разбора EBNF для 1+2*3.

Однако, мы можем сначала поместить 2*3 в expr и далее получить 1+expr, как показано на Рисунке 2.

Альтернативное дерево разбора EBNF для 1+2*3.
Рисунок 2. Альтернативное дерево разбора EBNF для 1+2*3.

Для JavaCC мы должны задать грамматические правила однозначно. Как следствие, мы разделим наше определение expr на три порождающих правила, задав грамматические элементы expr, term, unary и element. Теперь выражение 1+2*3 будет разобрано так, как показано на Рисунке 3.

Дерево разбора для 1+2*3.
Рисунок 3. Дерево разбора для 1+2*3.

Теперь мы можем запустить JavaCC из командной строки для проверки нашей грамматики:

 javacc Arithmetic.jj
 Java Compiler Compiler Version 1.1 (Parser Generator)
 Copyright (c) 1996-1999 Sun Microsystems, Inc.
 Copyright (c) 1997-1999 Metamata, Inc.
 (type "javacc" with no arguments for help)
 Reading from file Arithmetic.jj . . .
 Warning: Lookahead adequacy checking not being performed since option LOOKAHEAD
 is more than 1. Set option FORCE_LA_CHECK to true to force checking.
 Parser generated with 0 errors and 1 warnings.
 

Запуск проверил наши определения грамматики и создал исходные коды на Java:

 TokenMgrError.java
 ParseException.java
 Token.java
 ASCII_CharStream.java
 Arithmetic.java
 ArithmeticConstants.java
 ArithmeticTokenManager.java
 

Все вместе эти файлы реализуют парсер на Java. Вы можете запустить этот парсер создав копию класса Arithmetic:

public class Arithmetic implements ArithmeticConstants
 {
    public Arithmetic(java.io.InputStream stream) { ... }
     public Arithmetic(java.io.Reader stream) { ... }
    public Arithmetic(ArithmeticTokenManager tm) { ... }

    static final public double expr() throws ParseException { ... }
    static final public double term() throws ParseException { ... }
    static final public double unary() throws ParseException { ... }
    static final public double element() throws ParseException { ... }

    static public void ReInit(java.io.InputStream stream) { ... }
    static public void ReInit(java.io.Reader stream) { ... }
    public void ReInit(ArithmeticTokenManager tm) { ... }

    static final public Token getNextToken() { ... }
    static final public Token getToken(int index) { ... }

    static final public ParseException generateParseException() { ... }

    static final public void enable_tracing() { ... }
    static final public void disable_tracing() { ... }
 }
 

Если вы хотите использовать этот парсер, вы должны создать копию класса используя один его из конструкторов. Конструкторы позволяют передать InputStream, Reader, или ArithmeticTokenManager как исходник программы. Далее, вы можете задать главные грамматические элементы своего языка, например:

 Arithmetic parser = new Arithmetic(System.in);
 parser.expr();
 

Пока еще наш код ничего нее делает, так как в Arithmetic.jj мы задали только правила грамматики. Теперь нам нужно добавить код, который будет производить вычисления. Для этого мы добавим соответсвующие действия к правилам грамматики. Calcualtor.jj содержит полный калькулятор, включая действия: actions:

options
 {
     LOOKAHEAD=2;
 }

 PARSER_BEGIN(Calculator)

 public class Calculator
 {
     public static void main(String args[]) throws ParseException
     {
         Calculator parser = new Calculator(System.in);
         while (true)
         {
             parser.parseOneLine();
         }
     }
 }

 PARSER_END(Calculator)

 SKIP :
 {
     " "
 | "\r"
 | "\t"
 }

 TOKEN:
 {
     < NUMBER: (<DIGIT>)+ ( "." (<DIGIT>)+ )? >
 | < DIGIT: ["0"-"9"] >
 | < EOL: "\n" >
 }

 void parseOneLine():
 {
     double a;
 }
 {
     a=expr() <EOL> { System.out.println(a); }
   | <EOL>
   | <EOF> { System.exit(-1); }
 }

 double expr():
 {
     double a;
     double b;
 }
 {
     a=term()
     (
         "+" b=expr() { a += b; }
     | "-" b=expr() { a -= b; }
     )*
                         { return a; }
 }

 double term():
 {
     double a;
     double b;
 }
 {
     a=unary()
     (
         "*" b=term() { a *= b; }
     | "/" b=term() { a /= b; }
     )*
                         { return a; }
 }

 double unary():
 {
     double a;
 }
 {
     "-" a=element() { return -a; }
 | a=element() { return a; }
 }

 double element():
 {
     Token t;
     double a;
 }
 {
     t=<NUMBER> { return Double.parseDouble(t.toString()); }
 | "(" a=expr() ")" { return a; }
 }
 

Главный метод сначала создает объект парсера, который читает standard input и вызывает метод parseOneLine() в бесконечном цикле. Метод parseOneLine() определен как дополнительное правило грамматики. Это правило просто определяет, что мы ожидаем каждое выражение в отдельной строке, что пустые строки допустимы, и что мы завершаем программу по достижению конца файла.

Мы поменяли возвращаемый тип исходных грамматических элементов на double. Мы выполняем все необходимые вычисления прямо во время парсинга и передаем результаты в вверх дерева вызовов. Мы также переделали определения грамматических элементов, чтобы они хранили свои результаты в локальных переменных. Например, a=element() парсит element и сохраняет результат в переменной a. Это позволяет нам использовать результаты отпарсенных элементов в коде действий справа. Действия- это блоки кода на Java, которые выполняются, когда найдено соответсвующее правило грамматики во входном потоке.

Заметьте, как мало Java кода мы добавили, чтобы сделать наш калькулятор полностью функциональным. Более того, добавлять функциональность, например встроенные функции или даже переменные очень легко.

Выводы

JavaCC, генератор парсеров для Java, делает написание парсеров для языков программирования очень простым. JavaCC обеспечивает высокоуровневую нотацию для определяющей грамматики и сжатую спецификацию для грамматики и соответствующих действий. Ее также легко читать. Для разработчиков Java будут особенно полезными грамматики, которые входят в дистрибутив JavaCC (грамматика для Java 1.2 может быть загружена отдельно). Основываясь на этих грамматиках, вы можете создать свой набор удобных инструментов, таких как собственная версия утилиты javadoc, интерпретатор Java или класс для распечатки Java. Практически нет пределов тому, что вы можете делать.

JavaCC включает два дополнительных инструмента. JJDoc автоматически генерирует документацию для вашей грамматики в HTML подобно javadoc. JJTree автоматически создает действия для построения древовидной структуры при парсинге программы. Он обеспечивает построенный на паттерне Visitor каркас, которые позволяет вам сканировать дерево программы в памяти.

Об авторе

Оливер Ензелинг — опытный архитектор программного обеспечения. Программирование было его любимым делом с 16 лет. Будучи Sun-certified Java developer, Оливер работает над разработкой распределенных систем в Twin Cities в Миннесота.

Ресурсы

Reprinted with permission from the December 2000 edition of JavaWorld magazine. Copyright © ITworld.com, Inc., an IDG Communications company.
View the original article at: http://www.javaworld.com/ jw-12-2000/jw-1229-cooltools.html

[an error occurred while processing this directive]
[an error occurred while processing this directive] Перевод на русский © Сергей Миссан, 2001
< Вернуться на caйт :: Copyright © 1999 — 2010, IT • archiv.