Как получить абстрактное синтаксическое дерево (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'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/

Источник

2 ответа

Решение

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

Но если вам нужна небольшая грубость для решения этой проблемы, попробуйте следующее:

Сначала создайте объект для хранения 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 + "]";
}

Добавьте небольшую вспомогательную функцию для JNS 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']

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

Источник

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

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

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

Общий способ

  1. Добавьте оператор возврата в ваше правило запуска.

    Пример:

    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-парсер либо с помощью командной строки Jison, либо запустив new jison.Generator(fileContents).generate() в вашем файле сборки и запишите возвращенную строку в ваш файл, например my-parser.js,

Актуальный ответ

Применение приведенных выше правил приводит к приведенному ниже файлу Jison.
Насколько мне известно, формат файла Jison и API JavaScript (как указано в вопросе) являются взаимозаменяемыми.

Также обратите внимание, что этот файл 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];}
    ;
Источник
Другие вопросы по тегам