Как получить Абстрактное Синтаксическое Дерево (AST) из парсера JISON? - PullRequest
Новая
       61

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

15 голосов
/ 12 декабря 2011

Итак, я сгенерировал парсер через 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 ]

12 голосов
/ 01 июля 2014

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

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

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

Общий способ

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

    * * 1 022 Пример: * 1 023 * 
    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 и 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];}
    ;
12 голосов
/ 08 февраля 2012

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

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

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

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

...