Как построить график потока управления (CFG) из объекта JSON (AST)

Question

Я хочу построить граф потока управления (CFG) из AST, указанный в формате JSON. Таким образом, этот AST автоматически создается в TouchDevelop по каждому сценарию. И поскольку TouchDevelop не является объектно-ориентированным программированием, могу ли я использовать шаблон Visitor? Любые полезные указатели будут оценены.

Update1: Моя проблема в том, что я не понимаю с чего начать. Из Интернета я должен использовать шаблон посетителя, чтобы пройти через АСТ, чтобы посетить каждый узел и собрать информацию. И оттуда я могу построить CFG, а затем провести анализ потока данных. Но есть два вопроса:

1) AFAIK, мне нужна модель объектно-ориентированного программирования для использования шаблона посетителя (возможно, я ошибаюсь), который TouchDevelop НЕ.

2) AST, как указано ниже, не находится в формате AST, как я нахожу в Интернете. Это в формате JSON. Я думаю, что смогу разобрать JSON, чтобы преобразовать его в желаемую структуру AST, но я не уверен.

Исходный код образца сценария

meta version "v2.2,nothing"; 
meta name "DivideByZero"; 
// 
meta platform "current"; 

action main() { 
    (5/0)→post_to_wall; 
} 

(AST, причиненный в результате JSON отформатирован) приводится ниже:

{ 
    "type":"app", 
    "version":"v2.2,nothing", 
    "name":"DivideByZero", 
    "icon":null, 
    "color":null, 
    "comment":"", 
    "things":[ 
     { 
      "type":"action", 
      "name":"main", 
      "isEvent":false, 
      "outParameters":[ 
      ], 
      "inParameters":[ 
      ], 
      "body":[ 
       { 
        "type":"exprStmt", 
        "tokens":[ 
         { 
          "type":"operator", 
          "data":"(" 
         }, 
         { 
          "type":"operator", 
          "data":"5" 
         }, 
         { 
          "type":"operator", 
          "data":"/" 
         }, 
         { 
          "type":"operator", 
          "data":"0" 
         }, 
         { 
          "type":"operator", 
          "data":")" 
         }, 
         { 
          "type":"propertyRef", 
          "data":"post to wall" 
         } 
        ] 
       } 
      ], 
      "isPrivate":false 
     } 
    ] 

} 

Answer 1

я не нашел ссылку на язык сценариев TouchDevelop еще. Я не знаю, что вы можете с этим сделать, и что вы не можете.

Вам необязательно использовать шаблон посетителя. Шаблоны посетителей - это метод, используемый, когда ваше абстрактное синтаксическое дерево описывается экземплярами узлов из иерархии классов. Преобразование из AST в CFG является более общим, чем это. Абстрактное синтаксическое дерево представляет собой абстрактный тип данных, частный случай tree. Как и любой другой абстрактный тип данных, его можно представить разными способами. Неважно, как вы это делаете, но единственное, что вам нужно сделать, это перебрать это дерево. Итерационный метод зависит от языка, который вы используете. Это должно ответить на ваш вопрос 2 /: строка JSON может быть представлением AST. AST - это abstract data type, а строка JSON - это реализация этого абстрактного типа данных.

В JSON вы можете иметь значения, массивы или множества ассоциаций (ключ, значение). Я могу предположить, что ваши узлы AST будут набором ассоциаций (ключ, значение). Я также предполагаю, что каждый из этих узлов имеет ключ с именем type, который позволяет вам определить, какой именно узел.

Если я прав, ответ на вопрос: почему вам не нужен шаблон посетителя. Шаблон посетителя позволяет нам извлекать тип каждого узла. (это то, что называется «двойная отправка»). Но здесь вам это не нужно, поскольку тип каждого узла закодирован в поле type.

Как правило, преобразование из AST в CFG осуществляется с помощью набора функций: одна функция для каждого типа узлов в AST. Каждой из этих функций необходимо написать часть CFG, связанную с узлом, который он принимает в качестве параметра. Он будет рекурсивно вызывать функции преобразования для дочерних узлов. (Это будет шаблон посетителя в случае OO-AST)

Например, у вас будет функция ConvertNode. Эта функция будет считывать поле type узла и вызывать соответствующую функцию преобразования с узлом. У вашего корневого узла есть тип app. Затем функция ConvertNode отправит функцию ConvertApp.ConvertApp будет читать некоторые поля, такие как name, и будет перебирать массив things и вызывать ConvertNode для каждого из этих узлов. Затем снова ConvertNode отправит вызов соответствующей функции.

То, как будут вызываться эти функции преобразования, точно соответствует структуре AST. Как создается CFG, когда вы выполняете итерацию по дереву, зависит от языка ввода. Каждая из функций преобразования может возвращать сконструированный узел или переход вашего CFG, чтобы позволить вызывающему его повторно использовать. Или вызывающий может передать узел или переход в качестве параметра, чтобы позволить вызываемой функции продолжить построение оттуда. Вы можете выбрать подходящий способ создания CFG и нарушить общие правила: могут быть умные способы упрощения конструкции.