如何从 JISON 解析器中获取抽象语法树 (AST)？

Question

我已经通过JISON生成了一个解析器：

// mygenerator.js
var Parser = require("jison").Parser;

// a grammar in JSON
var grammar = {
    "lex": {
        "rules": [
           ["\\s+", "/* skip whitespace */"],
           ["[a-f0-9]+", "return 'HEX';"]
        ]
    },

    "bnf": {
        "hex_strings" :[ "hex_strings HEX",
                         "HEX" ]
    }
};

// `grammar` can also be a string that uses jison's grammar format
var parser = new Parser(grammar);

// generate source, ready to be written to disk
var parserSource = parser.generate();

// you can also use the parser directly from memory

// returns true
parser.parse("adfe34bc e82a");

// throws lexical error
parser.parse("adfe34bc zxg");

我的问题是，我现在该如何检索AST？我可以看到可以对输入运行解析器，但如果成功则仅返回true，否则返回失败。

值得一提的是，我正在使用JISON: http://zaach.github.com/jison/docs/

- Tower

---

你需要这个吗 - http://nolanlawson.github.io/jison-debugger/？ - anatoly techtonik

Answer 1

我发现了一种比其他答案中提到的更简单、更清晰的方法。

这篇文章分为两个部分：

• 通用方法：阅读如何实现我的方法。
• 实际答案：一个特定于OP请求的之前描述的方式的实现。

通用方法

1. 在您的起始规则中添加一个return语句。

   例如:

start
    : xyz EOF
        {return $1;}
    ;

xyz是另一条产生式规则。 $1访问关联产生式规则的第一个符号(终结符或非终结符)的值。在上面的代码中，$1包含来自xyz的结果。

将$$ = ...语句添加到所有其他规则中。

警告：使用$$ = ...，不要使用return！return会立即通过返回指定的值来终止进一步执行，正如其名称所示。

例子：

multiplication
    : variable '*' variable
        {$$ = {
            type: 'multiplication',
            arguments: [
              $1,
              $3
            ]
          };
        }
    ;

以上生产规则将对象 $$ 传递给更高层级（即使用此规则的生产规则）。

为了实现可运行的示例，让我们补充乘法规则：

/* lexical grammar */
%lex
%%

\s+                   /* skip whitespace */
[0-9]+("."[0-9]+)?\b  return 'NUMBER'
[a-zA-Z]+             return 'CHARACTER'
"*"                   return '*'
<<EOF>>               return 'EOF'
.                     return 'INVALID'

/lex

%start start
%% /* language grammar */

start
    : multiplication EOF
        {return $1;}
    ;

multiplication
    : variable '*' variable
        {$$ = {
            type: 'multiplication',
            arguments: [
              $1,
              $3
            ]
          };
        }
    ;

variable
    : 'NUMBER'
        {$$ = {
              type: 'number',
              arguments: [$1]
            };
         }
    | 'CHARACTER'
        {$$ = {
              type: 'character',
              arguments: [$1]
            };
         }
    ;

你可以在线尝试：http://zaach.github.io/jison/try/。在此编辑时（12.02.2017），在线生成器会出现错误 - 不管您输入何种Jison文件。请参见第3步后的补充说明，以获取有关如何在本地计算机上生成解析器的提示。

如果例如输入a*3，则会得到以下对象结构：

{
  "type": "multiplication",
  "arguments": [
    {
      "type": "character",
      "arguments": ["a"]
    },
    {
      "type": "number",
      "arguments": ["3"]
    }
  ]
}

通过注入自定义对象来清理代码和生成AST

使用Jison生成的解析器时，您可以将任意对象注入到语法文件中的“代码块”作用域中：

const MyParser = require('./my-parser.js');
MyParser.parser.yy = {
   MultiplicationTerm
   /*, AdditionTerm, NegationTerm etc. */
};

let calculation = MyParser.parse("3*4");
// Using the modification below, calculation will now be an object of type MultiplicationTerm

如果 MultiplicationTerm 有一个接受两个因子的构造函数，那么乘法运算的新部分将如下所示:

如果MultiplicationTerm有一个接受两个因子的构造函数，那么乘法的新部分将如下所示:

multiplication
    : variable '*' variable
        {$$ = new yy.MultiplicationTerm($1, $3);}
    ;

关于如何创建Jison解析器的补充说明：

下载Jison NPM模块。然后，您可以通过使用Jison的命令行或在构建文件中运行new jison.Generator(fileContents).generate()来创建Jison解析器，并将返回的字符串写入您首选的文件，例如my-parser.js。

实际答案

应用上述规则会产生下面的Jison文件。
据我所知，Jison文件格式和JavaScript API（如问题中所述）是可以互换的。

还要注意，这个Jison文件只生成一个平整树（即列表），因为输入格式也只是一个列表（否则，您如何以逻辑方式嵌套连接的十六进制字符串呢？）。

/* lexical grammar */
%lex
%%

\s+                   /* skip whitespace */
[a-f0-9]+             return 'HEX'
<<EOF>>               return 'EOF'
.                     return 'INVALID'

/lex

%start start
%% /* language grammar */

start
    :  hex_strings EOF
        {return $1;}
    ;

hex_strings
    : hex_strings HEX
        {$$ = $1.concat([$2]);}
    | HEX
        {$$ = [$1];}
    ;

- ComFreek

---

{$$ = {your:"在此处描述解析树节点",as:"一个对象"} 这正是我要找的。谢谢！ - Flion

Answer 2

我对Jison的内部工作不是很熟悉，因此不知道任何可以做到这一点的方法。

但是如果你对使用暴力解决这个问题感兴趣，可以尝试以下方法：

首先，创建一个对象来保存AST。

function jisonAST(name, x) { this.name = name; this.x = x; }

// return the indented AST
jisonAST.prototype.get = function(indent){
  // create an indentation for level l
  function indentString(l) { var r=""; for(var i=0;i<l;i++){r+="  "}; return r }

  var r = indentString(indent) + "["+this.name+": ";
  var rem = this.x;
  if( rem.length == 1 && !(rem[0] instanceof jisonAST) ) r += "'"+rem[0]+"'"; 
  else for( i in rem ){ 
      if( rem[i] instanceof jisonAST ) r += "\n" + rem[i].get(indent+1);
      else { r += "\n" + indentString(indent+1); r += "'"+rem[i]+"'"; }
    }
  return r + "]";
}

为Jison的BNF添加一个小助手函数。

function o( s ){
    r = "$$ = new yy.jisonAST('"+s+"',[";
    for( i = 1; i <= s.split(" ").length; i++ ){ r += "$"+i+"," }
    r = r.slice(0,-1) + "]);";
    return [s,r];
}

有了这个之后，继续看示例代码（稍作修改）：

var Parser = require("jison").Parser;

// a grammar in JSON
var grammar = {
    "lex": {
        "rules": [
           ["\\s+", "/* skip whitespace */"],
           ["[a-f0-9]+", "return 'HEX';"]
        ]
    },
    "bnf": {
        // had to add a start/end, see below
        "start" : [ [ "hex_strings", "return $1" ] ],
        "hex_strings" :[ 
            o("hex_strings HEX"), 
            o("HEX") 
        ]
    }
};

var parser = new Parser(grammar);
// expose the AST object to Jison
parser.yy.jisonAST = jisonAST

现在你可以尝试解析：

console.log( parser.parse("adfe34bc e82a 43af").get(0) );

这将给你：

[hex_strings HEX: 
  [hex_strings HEX: 
    [HEX: 'adfe34bc']  
    'e82a']  
  '43af']

小提示: 我不得不添加一个“起始”规则，以便只有一个语句返回结果。这样做并不干净（因为BNF在没有它的情况下也可以正常工作）。将其设置为入口点以确保......

- arlimus