ANTLR (или альтернативный вариант): разбор парсинга от оценки

У меня есть относительно простой DSL, который я бы хотел обработать более надежно, чем пучок закодированных вручную java.util.regex.Pattern операторов + логика синтаксического анализа.

Наиболее цитируемый инструмент, похоже, ANTLR. Я не знаком с этим и готов попробовать. Однако, когда я смотрю на примеры (например, ANTLR пример оценщика выражений, или, например, Martin Fowler HelloAntlr, или qaru.site/info/6362/...). Причиной этого является то, что файлы грамматики кажутся похожими на то, что они являются мешаниной определений грамматики, чередующихся с фрагментами языка реализации (например, Java), которые являются императивными по своей природе.

То, что я бы предпочел, состоит в том, чтобы отделить часть императива/оценки парсера. Есть ли способ использовать ANTLR (или какой-либо другой инструмент) для определения грамматики и создания набора исходных файлов Java, чтобы он компилировался в классы, которые я могу использовать для синтаксического анализа ввода в структуру без влияния на эту структуру?

например, если бы я хотел использовать оценку выражения только с операторами + и * и (), и у меня был вход

3 * (4 + 7 * 6) * (3 + 7 * (4 + 2))

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

Product
  Term(3)
  Sum
     Term(4)
     Product
        Term(7)
        Term(6)
  Sum
     Term(3)
     Product
        Term(7)
        Sum
            Term(4)
            Term(2)

где я могу использовать такие классы, как

interface Expression<T> {
    public T evaluate();
}

class Term implements Expression<Double> {
    final private double value;
    @Override public Double evaluate() { return value; }
}

class Product implements Expression<Double> {
    final private List<Expression<Double>> terms;
    @Override public Double evaluate() {
        double result = 1;
        for (Expression<Double> ex : terms)
            result *= ex.evaluate();
        return result;
    }
}

class Sum implements Expression<Double> {
    final private List<Expression<Double>> terms;
    @Override public Double evaluate() {
        double result = 0;
        for (Expression<Double> ex : terms)
            result += ex.evaluate();
        return result;
    }
}

и использовать ANTLR для построения структуры. Есть ли способ сделать это? Я бы предпочел продолжить этот подход, поскольку он позволяет мне (и другим разработчикам программного обеспечения) редактировать и визуализировать полные классы Java, не имея при этом, чтобы эти классы были фрагментированы в странные фрагменты в файлах грамматики ANTLR.

Есть ли способ сделать это?

пояснение:. Я хочу как можно больше использовать мои усилия двумя способами: определение самой грамматики и независимой от ANTLR Java (например, моих классов Product/Sum/Term). Я хочу свести к минимуму время/опыт, которые я должен потратить на изучение синтаксиса ANTLR, quirks и API. Я не знаю, как создавать и управлять АСТ из грамматики ANTLR. Поскольку это всего лишь небольшая часть большого Java-проекта, это не только я, это кто-то из моей команды, который должен проверить или поддерживать мой код.

(Я не хочу звучать неловко: я готов вложить время и энергию в использование инструмента, но только если инструмент станет полезным инструментом и не станет становиться камнем преткновения).

Ответы

Ответ 1

Jason S писал (а):

Есть ли способ сделать это?

Да.

Сначала определите свою грамматику (я взял ваш пример парсера выражений только с операторами + и * и ()):

grammar Exp;

// parser rules
parse
  :  additionExp
  ;

additionExp
  :  multiplyExp (Add multiplyExp)*
  ;

multiplyExp
  :  atomExp (Mult atomExp)* 
  ;

atomExp
  :  Number
  |  LParen additionExp RParen
  ;

// lexer rules
Add    : '+' ;
Mult   : '*' ;
LParen : '(' ;
RParen : ')' ;   
Number : ('0'..'9')+ ('.' ('0'..'9')+)? ;
Spaces : (' ' | '\t' | '\r'| '\n') {$channel=HIDDEN;} ;

Если вы хотите, чтобы ANTLR генерировал правильный АСТ из вышеприведенной грамматики, вы должны поставить следующее в верхней части своей грамматики (в соответствии с декларацией грамматики):

options { 
  output=AST; 
}

и вы должны указать, какой должен быть корень каждого из ваших правил анализа. Это можно сделать двумя способами:

  • с помощью переписать правила;
  • или путем размещения одного из "inline tree-операторов" ^ и ! после токенов:
    • ^ означает: сделать этот токен корнем;
    • ! означает: исключить этот токен из AST.

Теперь ваша грамматика будет выглядеть так:

grammar Exp;

options { 
  output=AST; 
}

// parser rules
parse
  :  additionExp
  ;

additionExp
  :  multiplyExp (Add^ multiplyExp)*
  ;

multiplyExp
  :  atomExp (Mult^ atomExp)* 
  ;

atomExp
  :  Number
  |  LParen! additionExp RParen!
  ;

// lexer rules
Add    : '+' ;
Mult   : '*' ;
LParen : '(' ;
RParen : ')' ;   
Number : ('0'..'9')+ ('.' ('0'..'9')+)? ;
Spaces : (' ' | '\t' | '\r'| '\n') {$channel=HIDDEN;} ;

Как вы можете видеть, я создал корни Add и Mult и исключил скобки.

Теперь создайте лексер и парсер из грамматики:

java -cp antlr-3.2.jar org.antlr.Tool Exp.g

создайте небольшой тестовый жгут:

import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;
import java.util.*;

public class Main {

    private static void preOrder(CommonTree tree, int depth) {
        for(int i = 0; i < depth; i++) {
            System.out.print("- ");
        }
        System.out.println("> "+tree + " :: " + ExpParser.tokenNames[tree.getType()]);
        List children = tree.getChildren();
        if(children == null) return;
        for(Object o : children) {
            preOrder((CommonTree)o, depth+1);
        }
    }

    public static void main(String[] args) throws Exception {
        ANTLRStringStream in = new ANTLRStringStream("3 * (4 + 7 * 6) * (3 + 7 * (4 + 2))");
        ExpLexer lexer = new ExpLexer(in);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        ExpParser parser = new ExpParser(tokens);
        CommonTree tree = (CommonTree)parser.parse().getTree();
        preOrder(tree, 0);
    }
}

скомпилировать все:

javac -cp antlr-3.2.jar *.java

и запустите класс Main:

// *nix/Mac OS
java -cp .:antlr-3.2.jar Main

// Windows
java -cp .;antlr-3.2.jar Main

который производит следующее:

> * :: Mult
- > * :: Mult
- - > 3 :: Number
- - > + :: Add
- - - > 4 :: Number
- - - > * :: Mult
- - - - > 7 :: Number
- - - - > 6 :: Number
- > + :: Add
- - > 3 :: Number
- - > * :: Mult
- - - > 7 :: Number
- - - > + :: Add
- - - - > 4 :: Number
- - - - > 2 :: Number

Как вы можете видеть, правило (метод) parse возвращает объект CommonTree, который вы можете использовать для создания собственного ходока/посетителя, оставляя грамматику как есть.

НТН

Ответ 2

Как насчет использования ANTLR AST (абстрактное дерево синтаксиса) и построения зеркального дерева с вашими классами, посетив каждое дерево node.

@Джузеппе Кардоне добавил несколько отличных ссылок, которые я размещаю здесь:

http://www.antlr.org/article/1100569809276/use.tree.grammars.tml

http://www.antlr.org/article/1170602723163/treewalkers.html

Пример можно найти по адресу:

http://sagarsunkle.spaces.live.com/blog/cns!E07F3B561597E4EE!664.entry?sa=97619042

Ответ 3

Примеры, которые вы упоминаете, вставляете действия парсера прямо в грамматику ради краткости. Это отлично подходит для небольших проектов. Для более крупных вы предпочтете сначала создать АСТ, а затем делать все, что хотите. Вы можете сделать это, хе-хе, путем внедрения действий, которые создают дерево, но antlr обеспечивает более удобный, декларативный способ:

http://www.antlr.org/wiki/display/ANTLR3/Tree+construction

Затем вы можете использовать Tree Grammar для генерации кода, например. с StringTemplate. Я использовал эту инструментальную цепочку для своей диссертации, и она работала как прелесть. Но я уверен, что я бы сильно пострадал, не имея справочника Anlr3 (http://pragprog.com/titles/tpantlr/the-definitive-antlr-reference)

Я также нашел, что лекционные заметки, связанные на странице antlr, действительно полезны: http://www.antlr.org/wiki/display/CS652/CS652+Home

Кроме того, используйте AntlrWorks для проверки вашей грамматики. Там также доступен набор для тестирования грамматики. Кроме того, список рассылки antlr действительно активен, и Теренс Парр активно реагирует на большинство сообщений. Кроме того, это очень весело.