当前位置： 文江博客 话题详情

antlr3 - 生成解析树

发布于 2024-11-07 00:38:48 字数 739 浏览 7 评论 0 原文

我无法弄清楚 antlr3 API，因此我可以在一些 javascript 代码中生成和使用解析树。当我使用antlrWorks（他们的IDE）打开语法文件时，解释器能够向我显示解析树，而且它甚至是正确的。

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

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自动从语法生成解析树文件中，我假设我可以使用一些我可能不知道的运行时函数来访问这个基本的解析树。我的这个想法正确吗？

原文

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?

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（1）

帥小哥 2024-11-14 00:38:48

HugeAntlrs 写道：

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

不，那是不正确的。 ANTLR 创建扁平的一维标记流。

ANTLRWorks 在解释某些源代码时会动态创建自己的解析树。您无权访问该树（无法使用 Javascript，甚至无法使用 Java）。您必须定义您认为应该是（子）树的根的标记和/或定义需要从 AST 中删除的标记。查看以下问答，了解如何创建正确的 AST：如何输出使用 ANTLR 构建的 AST？

编辑

由于目前还没有合适的 JavaScript 演示，这里有一个快速演示。

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

  • or
  • 和
  • is
  • not

，其中 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>

看看结果：

enter image此处描述

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:

enter image description here

回复 原文
~没有更多了~

关于作者

过期情话

暂无简介

0 文章
0 评论
24 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

胡图图

文章 0 评论 0

zt006

文章 0 评论 0

z祗昰~

文章 0 评论 0

冰葑

文章 0 评论 0

野の

文章 0 评论 0

天空

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文