Реализация goto в аст - PullRequest
Новая
       65

Реализация goto в аст

6 голосов
/ 27 декабря 2011

Предыстория: В качестве короткого проекта во время зимних каникул я пытаюсь реализовать язык программирования Ax (разработанный для графических калькуляторов) с использованием Python и PLY.Краткое замечание: язык допускает только глобальные переменные и интенсивно использует указатели.

Я пытаюсь реализовать goto на этом языке, но не знаю, как это сделать.

Мой общий метод заключается в том, чтобы сначала использовать PLY для анализа кода в ast, а затем пройтись по нему, выполняя все по ходу.

Например, выражение 

If 3
    Disp 4
    Disp 6
End

... превратится в ... 

['PROGRAM', 
  ['BLOCK', 
    ['IF', 
      ['CONDITION', 3], 
      ['BLOCK', 
        ['DISP', 4], 
        ['DISP', 6]
      ]
    ]
  ]
]

... который я буду выполнять рекурсивно (я добавил отступы для удобочитаемости).

Поскольку ast - это дерево, яне уверен, как прыгать между разными узлами.Возможно, я подумал о преобразовании дерева в массив с плоской изогнутостью ['IF', ['CONDITION', 3], ['DISP', 4], ['DISP', 6]], чтобы я мог использовать индексы массива с плоской изогнутой линией для перехода к конкретным строкам в коде, но, похоже, ему не хватает определенной элегантности, и он кажетсякак шаг назад (хотя я могу ошибаться).

Я смотрел на это , но не смог понять, как это работает.

Любая помощь или советыбудет оценена.

Ответы [ 3 ]

6 голосов
/ 27 декабря 2011

«выполнить рекурсивно» плохо сочетается с goto.Чтобы goto работал, вам нужен ПК, «программный счетчик», и каждый оператор в вашей программе должен иметь отдельный адрес.По мере выполнения адрес каждой инструкции присваивается ПК.Когда встречается goto, целевой адрес goto (его аргумент) помещается в ПК и оттуда возобновляется выполнение.

Этого практически невозможно достичь с помощью рекурсивного подхода на основе стека.У вас есть два варианта:

  • Свести ваш AST в последовательность, в которой вы можете назначить отдельный адрес для каждого оператора

  • Добавить «пропуск»режим для вашего переводчика.Когда встречается goto, выведите GotoException, который разбивает все кадры стека и возвращается к корню.Обрабатывайте операторы (пропускайте их без выполнения), пока не достигнете целевого адреса.

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

2 голосов
/ 27 декабря 2011

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

Вы не правы.Машинный код всегда плоский.Для создания машинного кода языки типа C сведены.

Калькулятор (как и другие простые машины) плоский.

Однако.Выравнивание вашего синтаксического дерева AX не является полностью необходимым .

Вам просто нужно применить метки исходного кода к каждому узлу в вашем дереве.

Затем «GOTO» просто ищет дерево для этой метки и возобновляет выполнение с этой меткой.

0 голосов
/ 27 марта 2015

Вы также можете выровнять AST к ориентированному графу (граф потока управления).Пример того, как это можно сделать для получения графика networkx, который может быть пройден интерпретатором, можно найти здесь Обратите внимание, что для этой цели вам придется написать несколько классов AST.

...