antlr3 - Генерация дерева разбора

Question

antlr3 - Генерация дерева разбора

У меня возникают проблемы с выяснением API antlr3, чтобы я мог генерировать и использовать дерево разбора в некотором коде JavaScript. Когда я открываю файл грамматики с помощью antlrWorks (их IDE), интерпретатор может показать мне дерево разбора, и это даже правильно.

У меня много трудностей с поиском ресурсов о том, как получить это дерево разбора в моем коде, используя среду выполнения antlr3. Я возился с различными функциями в файлах времени выполнения и Parser, но безрезультатно:

var input = "(PR=5000)",
cstream = new org.antlr.runtime.ANTLRStringStream(input),
lexer = new TLexer(cstream),
tstream = new org.antlr.runtime.CommonTokenStream(lexer),
parser = new TParser(tstream);

var tree = parser.query().tree;
var nodeStream = new org.antlr.runtime.tree.CommonTreeNodeStream(tree);
nodeStream.setTokenStream(tstream);

parseTree = new org.antlr.runtime.tree.TreeParser(nodeStream);

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

3

antlr antlr3 antlrworks parse-tree

Источник

user750945 12 май '11 в 16:24

1 ответ

Решение

Другие вопросы по тегам antlr antlr3 antlrworks parse-tree

user50476 12 май '11 в 18:14 2011-05-12 18:14 · Accepted Answer · 2011-05-12 18:14

HugeAntlrs написал (а):
Поскольку antlrWorks может отображать дерево разбора без какой-либо грамматики дерева от себя, и поскольку я прочитал, что antlr автоматически генерирует дерево разбора из файла грамматики, я предполагаю, что могу получить доступ к этому основному дереву разбора с помощью некоторых функций времени выполнения, которые я наверное не в курсе. Я прав в этом мышлении?

Нет, это неверно. ANTLR создает плоский одномерный поток токенов.

ANTLRWorks создает собственное дерево разбора на лету при интерпретации некоторого источника. У вас нет доступа к этому дереву (не с Javascript или даже с Java). Вам нужно будет определить токены, которые, по вашему мнению, должны быть корнями ваших (под) деревьев и / или определить токены, которые необходимо удалить из вашего AST. Ознакомьтесь со следующими вопросами и ответами, в которых объясняется, как создать правильный AST: Как вывести AST, созданный с использованием ANTLR?

РЕДАКТИРОВАТЬ

Поскольку на SO еще нет надлежащей демонстрации JavaScript, вот короткая демонстрация.

Следующая грамматика анализирует логическое выражение со следующими операторами:

или же
а также
является
не

где not имеет наивысший приоритет.

Конечно есть true а также false и выражения могут быть сгруппированы с помощью круглых скобок.

файл: Exp.g

grammar Exp;

options {
  output=AST;
  language=JavaScript;
}

parse
  :  exp EOF -> exp
  ;

exp
  :  orExp
  ;

orExp
  :  andExp (OR^ andExp)*
  ;

andExp
  :  eqExp (AND^ eqExp)*
  ;

eqExp
  :  unaryExp (IS^ unaryExp)*
  ;

unaryExp
  :  NOT atom -> ^(NOT atom)
  |  atom
  ;

atom
  :  TRUE
  |  FALSE
  |  '(' exp ')' -> exp
  ;

OR     : 'or' ;
AND    : 'and' ;
IS     : 'is' ;
NOT    : 'not' ;
TRUE   : 'true' ;
FALSE  : 'false' ;
SPACE  : (' ' | '\t' | '\r' | '\n') {$channel=HIDDEN;} ;

Приведенная выше грамматика дает AST, который можно подавать на дерево, идущее ниже:

файл: ExpWalker.g

tree grammar ExpWalker;

options {
  tokenVocab=Exp;
  ASTLabelType=CommonTree;
  language=JavaScript;
}

// `walk` returns a string
walk returns [expr]
  :  exp {expr = ($exp.expr == 1) ? 'True' : 'False';}
  ;

// `exp` returns either 1 (true) or 0 (false)
exp returns [expr]
  :  ^(OR  a=exp b=exp) {expr = ($a.expr == 1 || $b.expr == 1) ? 1 : 0;}
  |  ^(AND a=exp b=exp) {expr = ($a.expr == 1 && $b.expr == 1) ? 1 : 0;}
  |  ^(IS  a=exp b=exp) {expr = ($a.expr == $b.expr) ? 1 : 0;}
  |  ^(NOT a=exp)       {expr = ($a.expr == 1) ? 0 : 1;}
  |  TRUE               {expr = 1;}
  |  FALSE              {expr = 0;}
  ;

(извиняюсь за грязный код JavaScript внутри { ... } : У меня очень мало опыта работы с JavaScript!)

Теперь загрузите ANTLR 3.3 (не более раннюю версию!) И файлы времени выполнения JavaScript:

переименовывать antlr-3.3-complete.jar в antlr-3.3.jar и расстегнуть молнию antlr-javascript-runtime-3.1.zip и хранить все файлы в той же папке, что и ваш Exp.g а также ExpWalker.g файлы.

Теперь сгенерируйте лексер, парсер и обходчик дерева:

java -cp antlr-3.3.jar org.antlr.Tool Exp.g 
java -cp antlr-3.3.jar org.antlr.Tool ExpWalker.g

И протестируйте все это с помощью следующего HTML-файла:

<html>
  <head>
    <script type="text/javascript" src="antlr3-all-min.js"></script>
    <script type="text/javascript" src="ExpLexer.js"></script>
    <script type="text/javascript" src="ExpParser.js"></script>
    <script type="text/javascript" src="ExpWalker.js"></script>

    <script type="text/javascript">

    function init() {
      var evalButton = document.getElementById("eval");
      evalButton.onclick = evalExpression;
    }

    function evalExpression() {
      document.getElementById("answer").innerHTML = "";
      var expression = document.getElementById("exp").value;
      if(expression) {
        var lexer = new ExpLexer(new org.antlr.runtime.ANTLRStringStream(expression));
        var tokens = new org.antlr.runtime.CommonTokenStream(lexer);
        var parser = new ExpParser(tokens);
        var nodes = new org.antlr.runtime.tree.CommonTreeNodeStream(parser.parse().getTree());
        nodes.setTokenStream(tokens);
        var walker = new ExpWalker(nodes);
        var value = walker.walk();
        document.getElementById("answer").innerHTML = expression + " = " + value;
      }
      else {
        document.getElementById("exp").value = "enter an expression here first"; 
      }
    }

    </script>
  </head>
  <body onload="init()">
    <input id="exp" type="text" size="35" />
    <button id="eval">evaluate</button>
    <div id="answer"></div>
  </body>
</html>

И вот результат:

введите описание изображения здесь