Построение графа потока управления из AST с шаблоном посетителя с использованием Java - PullRequest
Новая
       28

Построение графа потока управления из AST с шаблоном посетителя с использованием Java

6 голосов
/ 19 декабря 2010

Я пытаюсь выяснить, как реализовать мой класс LEParserCfgVisitor для построения графа потока управления из абстрактного синтаксического дерева, уже сгенерированного с помощью JavaCC. Я знаю, что уже существуют инструменты, но я пытаюсь сделать это в рамках подготовки к финалу моего компилятора.

Я знаю, что мне нужна структура данных, которая хранит график в памяти, и я хочу иметь возможность хранить такие атрибуты, как IN, OUT, GEN, KILL в каждом узле, чтобы иметь возможность выполнять анализ потока управления позже.

Моя основная проблема заключается в том, что я не понял, как соединить различные блоки, чтобы иметь правильный край между каждым блоками в зависимости от их природы: ветви, петель и т. Д. Другими словами, я не нашел явный алгоритм, который мог бы помочь мне построить моего посетителя.

Вот мой пустой посетитель. Вы можете видеть, что он работает с базовыми выражениями языка, например if, while и базовыми операциями (+, -, x, ^, ...) 

public class LEParserCfgVisitor implements LEParserVisitor
{
  public Object visit(SimpleNode node, Object data) { return data; }

  public Object visit(ASTProgram node, Object data) { 
    data = node.childrenAccept(this, data);
    return data; 
  }

  public Object visit(ASTBlock node, Object data) {
  }

  public Object visit(ASTStmt node, Object data) {
  }

  public Object visit(ASTAssignStmt node, Object data) {
  }

  public Object visit(ASTIOStmt node, Object data) { 
  }

  public Object visit(ASTIfStmt node, Object data) {
  }

  public Object visit(ASTWhileStmt node, Object data) {
  }

  public Object visit(ASTExpr node, Object data) { 
  }

  public Object visit(ASTAddExpr node, Object data) {
  }

  public Object visit(ASTFactExpr node, Object data) {
  }

  public Object visit(ASTMultExpr node, Object data) { 
  }

  public Object visit(ASTPowerExpr node, Object data) {  
  }

  public Object visit(ASTUnaryExpr node, Object data) { 
  }

  public Object visit(ASTBasicExpr node, Object data) {
  }

  public Object visit(ASTFctExpr node, Object data) {
  }

  public Object visit(ASTRealValue node, Object data) { 
  }

  public Object visit(ASTIntValue node, Object data) { 
  }

  public Object visit(ASTIdentifier node, Object data) {
  }
}

Кто-нибудь может мне помочь?

Спасибо!

1 Ответ

11 голосов
/ 24 декабря 2010

Чтобы рассуждать о потоках данных (gen / kill / use / def), вам сначала необходим граф потока управления.

Чтобы построить один, в каждом узле дерева (например, внутри каждого конкретного посетителя узла), построить часть графа, который представляет узел; передать дугу точки входа и дугу этого графика родительскому «посетителю». Чисто независимые посетители не будут работать, потому что вам нужно передать информацию родителям. [Вы можете добавить слоты дуг входа / выхода для каждого узла, которые установлены посетителем и проверены родителем.]

Некоторые узлы (например, для «assignmentstmt») будут создавать узел действия, ссылающийся на AST для назначения (представьте себе «прямоугольник» на блок-схеме); нет никаких дуг подграфа, чтобы волноваться о. Некоторые узлы (например, для «если») будут создавать условный узел ветвления (ссылающийся на узел AST для выражения условия), (подумайте «ромб» на блок-схеме), узел присоединения потока и составлять структурированный (если подграфа then-else) путем объединения этого условного узла ветвления с подграфами для предложений then и else (представленных просто дугами въезда и выезда) с потоком join-node. Затем вы передаете дуги входа и выхода в этот составной подграф родительскому элементу.

Эта схема работает со структурированным потоком управления. Неструктурированный поток управления (например, «GOTO x») требует некоторых забавных настроек, например, сначала строит структурированную часть графика, связывает сгенерированный поток управления с метками, а затем возвращается назад и исправляет действия GOTO, чтобы иметь дугу к связанному этикетка.

Не забывайте беспокоиться об исключениях; они тоже GOTO, но, как правило, на более высокую точку в структурном графе потока управления. Они часто обрабатываются путем передачи самого внутреннего узла обработчика исключений вниз дерева; теперь ваши посетители должны просмотреть вверх дерево, чтобы увидеть этот самый последний обработчик исключений.

Более сложная схема, в которой используются сгенерированные висторы, называется http://en.wikipedia.org/wiki/Attribute_grammar">attribute грамматикой, которая, по сути, управляет всеми информационными потоками для вас, передавая интересующие значения (в данном случае дуги входа / выхода / исключения) и вниз по дереву в качестве параметров и результатов. Вам нужен инструмент грамматики атрибута, чтобы сделать это; и вы все равно должны указать логику построения узла. Мы используем атрибутные грамматики и, по существу, вышеприведенное построение графов потоков управления по частям с помощью нашего DMS Software Reengineering Toolkit , чтобы предоставить общие средства анализа потоков управления для многих языков.

Получив граф потока управления, вы можете реализовать решатель потока данных описанного вами типа, пройдя по графику потока управления. Вам нужно будет повторно посетить AST, на которые указывают узлы CF, чтобы собрать необработанную информацию об использовании / необработанном def.

Если ваш язык имеет только структурированный поток управления , то вы можете использовать узлы AST для представления узлов потока управления и напрямую вычислять поток данных.

Более подробную информацию об общем процессе можно найти здесь .

...