如何从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,否则返回true.

为了记录在案,我使用JISON:http://zaach.github.com/jison/docs/

Answer 1

我对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工作正常).将其设置为切入点以确保...

Answer 2

我发现了一种比另一种答案更简单,更清洁的方法.

这篇文章分为两部分:

• 一般方法:阅读如何实现我的方式.
• 实际答案:特定于OP请求的先前描述方式的实现.

一般方式

1. 将return语句添加到起始规则.

   例:

   start
       : xyz EOF
           {return $1;}
       ;
   

   xyz是另一个生产规则.$1访问相关生产规则的第一个符号(终端或非终端)的值.在上面的代码中$1包含了结果xyz.

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

   警告:使用$$ = ...,不要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"]
       }
     ]
   }
   

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有一个构造函数接受这两个因素,乘法的新部分将如下所示:

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

关于如何创建Jison解析器的附录:

下载Jison NPM模块.然后,您可以使用Jison的命令行或new jison.Generator(fileContents).generate()在构建文件中运行来创建Jison-parser ,并将返回的字符串写入首选文件,例如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];}
    ;