Как получить абстрактное синтаксическое дерево (AST) из синтаксического анализа JISON?

Поэтому я создал синтаксический анализатор через 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 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");

Мой вопрос: как мне получить АСТ сейчас? Я вижу, что я могу запустить парсер против ввода, но он просто возвращает true, если он работает или терпит неудачу, если нет.

Для записи я использую JISON: http://zaach.github.com/jison/docs/

Ответ 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']

Небольшое примечание: мне пришлось добавить правило "start", чтобы иметь только один оператор, который возвращает результат. Это не чисто (поскольку BNF отлично работает без него). Установите его как точку входа, чтобы быть уверенным...

Ответ 2

Я обнаружил более простой и понятный способ, чем тот, который был в другом ответе.

Этот пост делится на 2 части:

Общий способ: прочитать, как реализовать свой путь.
Фактический ответ: реализация описанного выше способа, специфичного для запроса OP.

Общий путь

Добавьте оператор возврата в свое начальное правило.

Пример:
```
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 был конструктор, принимающий оба фактора, новая часть для умножения будет выглядеть так:
```
multiplication
    : variable '*' variable
        {$$ = new yy.MultiplicationTerm($1, $3);}
    ;
```

Добавление о том, как создать парсер Jison:

Загрузите модуль Jison NPM. Затем вы можете создать Jison-parser либо с помощью командной строки new jison.Generator(fileContents).generate() либо с помощью new jison.Generator(fileContents).generate() в файле сборки и напишите возвращенную строку в ваш предпочтительный файл, например 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];}
    ;

Ответ 3

Вы можете улучшить свою грамматику, используя что-то похожее на кофе-скрипт DSL: http://coffeescript.org/documentation/docs/grammar.html

Выглядит очень приятно:

Body: [
    o 'Line',                                   -> Block.wrap [$1]
    o 'Body TERMINATOR Line',                   -> $1.push $3
    o 'Body TERMINATOR'
  ]