antlr3 - 生成解析树 [英] antlr3 - Generating a Parse Tree

查看：43
本文介绍了antlr3 - 生成解析树的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我在弄清楚 antlr3 API 时遇到了麻烦，因此我可以在某些 javascript 代码中生成和使用解析树.当我使用 antlrWorks(他们的 IDE)打开语法文件时，解释器能够向我展示解析树，它甚至是正确的.

我在追踪有关如何使用 antlr3 运行时在我的代码中获取此解析树的资源时遇到了很多困难.我一直在处理运行时和解析器文件中的各种函数，但无济于事:

var input = "(PR=5000)",cstream = new org.antlr.runtime.ANTLRStringStream(input),词法分析器 = 新 TLexer(cstream),tstream = new org.antlr.runtime.CommonTokenStream(lexer),解析器 = 新 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 自动从语法文件生成一个解析树，我假设我可以使用一些运行时函数访问这个基本的解析树我可能不知道.我的想法正确吗?

解决方案

HugeAntlrs 写道:

由于 antlrWorks 可以在没有我自己的任何树语法的情况下显示解析树，并且由于我已经阅读了 antlr 自动从语法文件生成一个解析树，我假设我可以使用一些运行时函数访问这个基本的解析树我可能不知道.我的想法正确吗?

不，那是不正确的.ANTLR 创建了一个扁平的一维令牌流.

ANTLRWorks 在解释某些源时会即时创建自己的解析树.您无权访问此树(使用 Javascript 甚至 Java 都无法访问).您必须定义您认为应该是(子)树的根的标记和/或定义需要从 AST 中删除的标记.查看以下说明如何创建正确 AST 的问答:How输出使用 ANTLR 构建的 AST?

编辑

由于 SO 上还没有合适的 JavaScript 演示，这里有一个快速演示.

以下语法使用以下运算符解析布尔表达式:

  • 或
  • 和
  • 是
  • 不是

其中 not 的优先级最高.

当然有true和false，表达式可以用括号分组.

文件:Exp.g

grammar Exp;选项 {输出=AST;语言=JavaScript；}解析: exp EOF ->经验值;经验值: orexp;或Exp: andExp (OR^ andExp)*;和Exp: eqExp (AND^ eqExp)*;等式: unaryExp (IS^ unaryExp)*;一元Exp: 不是原子 ->^(不是原子)|原子;原子:  真的|错误的|'('exp')' ->经验值;或:'或';AND : '和' ;伊斯兰国' ;不是这样的' ;真:'真'；假:'假'；空格 : (' ' | '\t' | '\r' | '\n') {$channel=HIDDEN;} ;

上面的语法产生了一个 AST，它可以提供给下面的 tree-walker:

文件:ExpWalker.g

树语法ExpWalker;选项 {tokenVocab=Exp;ASTLabelType=普通树；语言=JavaScript；}//`walk` 返回一个字符串步行返回 [expr]: exp {expr = ($exp.expr == 1) ?'真假';};//`exp` 返回 1(真)或 0(假)exp 返回 [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；}|真{expr = 1;}|假 {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.gjava -cp antlr-3.3.jar org.antlr.Tool ExpWalker.g

并使用以下 html 文件对其进行测试:

<头><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">函数初始化(){var evalButton = document.getElementById("eval");evalButton.onclick = evalExpression;}函数 evalExpression() {document.getElementById("answer").innerHTML = "";var expression = document.getElementById("exp").value;如果(表达式){var lexer = new ExpLexer(new org.antlr.runtime.ANTLRStringStream(expression));var tokens = new org.antlr.runtime.CommonTokenStream(lexer);var parser = new ExpParser(tokens);var 节点 = 新 org.antlr.runtime.tree.CommonTreeNodeStream(parser.parse().getTree());节点.setTokenStream(令牌)；var walker = new ExpWalker(nodes);var value = walker.walk();document.getElementById("answer").innerHTML = 表达式 + " = " + 值；}别的 {document.getElementById("exp").value = "先在这里输入一个表达式";}}<body onload="init()"><input id="exp" type="text" size="35"/><button id="eval">evaluate</button><div id="答案"></div></html>

看看结果:

I'm having trouble figuring out the antlr3 API so I can generate and use a parse tree in some javascript code. When I open the grammar file using antlrWorks (their IDE), the interpreter is able to show me the parse tree, and it's even correct.

I'm having a lot of difficulties tracking down resources on how to get this parse tree in my code using the antlr3 runtime. I've been messing around with the various functions in the runtime and Parser files but to no avail:

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);

Since antlrWorks can display the parse tree without any tree grammar from myself, and since I have read that antlr automatically generates a parse tree from the grammar file, I'm assuming that I can access this basic parse tree with some runtime functions that I am probably not aware of. Am I correct in this thinking?

解决方案

HugeAntlrs wrote:

Since antlrWorks can display the parse tree without any tree grammar from myself, and since I have read that antlr automatically generates a parse tree from the grammar file, I'm assuming that I can access this basic parse tree with some runtime functions that I am probably not aware of. Am I correct in this thinking?

No, that is incorrect. ANTLR creates a flat, 1 dimensional stream of tokens.

ANTLRWorks creates its own parse tree on the fly when interpreting some source. You have no access to this tree (not with Javascript or even with Java). You will have to define the tokens that you think should be the roots of your (sub) trees and/or define the tokens that need to be removed from your AST. Checkout the following Q&A that explains how to create a proper AST: How to output the AST built using ANTLR?

EDIT

Since there's no proper JavaScript demo on SO yet, here's a quick demo.

The following grammar parses boolean expression with the following operators:

  • or
  • and
  • is
  • not

where not has the highest precedence.

Of course there are true and false, and the expressions can be grouped using parenthesis.

file: 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;} ;

The grammar above produces an AST which can be fed to the tree-walker below:

file: 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;}
  ;

(apologies for the messy JavaScript code inside { ... }: I have very little experience with JavaScript!)

Now download ANTLR 3.3 (no earlier version!) and the JavaScript runtime files:

Rename antlr-3.3-complete.jar to antlr-3.3.jar and unzip antlr-javascript-runtime-3.1.zip and store all files in the same folder as your Exp.g and ExpWalker.g files.

Now generate the lexer, parser and tree-walker:

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

And test it all with the following html file:

<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>

And behold the result:

这篇关于antlr3 - 生成解析树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
其他开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆