Как реализовать LOOP в FORTH-подобном языковом интерпретаторе, написанном на C - PullRequest
6 голосов
/ 05 августа 2011

Я пишу простой основанный на стеке язык на C, и мне было интересно, как мне следует реализовывать какую-либо структуру цикла и / или символы предпросмотра.Поскольку код для этой страницы немного длинный (более 200 строк), я поместил его в репозиторий GitHub .

РЕДАКТИРОВАТЬ: основная программа находится в файле stack.c.

РЕДАКТИРОВАТЬ: код только вводит в words, вроде как FORTH.Он использует scanf и работает слева направо.Затем он использует серию if s и strcmp s, чтобы решить, что делать.Это действительно так.

Ответы [ 4 ]

10 голосов
/ 05 августа 2011

Forth подход заключается в добавлении отдельного стека цикла вместе со стеком данных. Затем вы определяете операции, которые работают с этим стеком цикла. Например:

5 0 DO I . LOOP

Распечатает

0 1 2 3 4

Как это работает:

  • DO перемещает индекс (0) и элемент управления (5) в стек циклов.
  • I копирует вершину стека цикла в стек данных.
  • LOOP увеличивает индекс (вершина стека цикла). Если индекс меньше, чем элемент управления (один ниже вершины стека цикла), он перезапускает команды с DO обратно до LOOP. Если индекс равен> =, то он извлекает индекс и элемент управления из стека цикла, и элемент управления возобновляет работу в обычном режиме.
6 голосов
/ 05 августа 2011

Очевидный способ добавить управляющие структуры к языку на основе стека - добавить «стек управления». Я опишу механизм Postscript, потому что это то, что я знаю, но у Forth есть аналогичное поведение (с небольшими различиями, чтобы быть уверенным).

Самым простым контролируемым циклом является цикл repeat. Технически, бесконечный loop проще, но для его использования требуется явная команда exit и объяснение того, что может усложнить ситуацию.

Синтаксис для повтора:

int proc  **repeat**  -

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

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

В качестве конкретного примера предположим, что интерпретатор выполняется из входного потока. И стеки выглядят так:

operand: -empty-
execute: <stdin>

Пользователь вводит 2 {(Hello World!\n) print} repeat.

Целое число 2 помещается в стек.

operand: 2
execute: <stdin>

Тело процедуры в кавычках (*) помещается в стек.

operand: 2 {(Hello World!\n) print}
execute: <stdin>

Команда repeat выполняется.

operand: 2 {(Hello World!\n) print}
execute: <stdin> repeat

Repeat: expects operands: int proc
    if int<0 Error
    if int==0 return //do nothing
    push `repeat` itself on exec stack
    push quoted proc on exec stack
    push int-1 on exec stack
    push "executable" proc on exec stack

Выполнение процедуры повтора (один раз) оставляет стеки так:

operand: -empty-
execute: <stdin> repeat {(Hello World!\n) print} 1 **{(Hello World!\n) print}**

Интерпретатор выполняет процедуру над стеком exec, печатая «Hello World!», Затем находит целое число, которое он помещает в стек op.

operand: 1
execute: <stdin> repeat {(Hello World!\n) print}

Интерпретатор выполняет процедуру в кавычках, нажимая на стек операций.

operand: 1 {(Hello World!\n) print}
execute: <stdin> repeat

И мы вернулись в начале! Готов к следующей итерации (или завершению, если целое число упало до нуля).

Надеюсь, это поможет.

Редактировать;

После того, как я действительно посмотрел ваш код, у меня есть другое предложение, возможно, трамплин к чему-то, что я описал выше. Я думаю, вы должны на время забыть код и сосредоточиться на структурах данных. У вас есть хорошая таблица для переменных, но все команды являются встроенными литералами, разбросанными по коду!

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

struct object {
    int type;
    union {
        int i;
        void (*command)(context *);
    } u;
};

struct dict {
    int sz;
    struct rec {
        char *key;
        object val;
    }  data[]; //think resizable!
};

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

Тогда вам понадобится другой тип для хранения последовательностей команд. Массив или список должен работать. Когда вы можете определить последовательности, вы можете повторять последовательности гораздо проще.

Бонусом здесь является то, что вы находитесь всего в одной конструкции от Turing Complete . Последовательности, итерации, решения (или выбор): это все, что вам нужно для программирования любой вычислимой функции!


*. Как обнаружил комментатор, Postscript на самом деле не имеет той же концепции цитирования , которую я использую здесь в своем описании. Здесь я заимствую концепцию из терминологии Lisp. В PostScript вместо этого есть литерал / исполняемый флаг , который можно установить cvx cvlit или проверить xcheck. Исполняемый массив в стеке исполнения будет выполнен. Таким образом, для "цитируемого" тела процедуры это на самом деле литерал тело процедуры (т. Е. Массив). Из-за этого repeat также должен принудительно вызвать вызов cvx для выполнения до следующей итерации. Итак, более правильный псевдокод для постскриптной реализации repeat:

Repeat: expects operands: int proc
    if int<0 Error
    if int==0 return //do nothing
    push `repeat` itself on exec stack
    push 'cvx' on the exec stack
    push cvlit(proc) on exec stack
    push int-1 on exec stack
    push "executable" proc on exec stack

Выполняет необходимый поворот флага, чтобы передать процедуру в качестве данных в стеке выполнения.

Другой способ реализации этой структуры управления - две функции: repeat, одна и та же точка входа, и внутренний оператор продолжения, который в теории не нуждается в имени. Я думаю, что ghostscript называет это что-то вроде @ repeat-continue @. С отдельной функцией continue вам не нужно быть очень осторожным с порядком содержимого в стеке, и вам не нужно вертеть флаг literal . Вместо этого вы можете хранить некоторые постоянные данные ниже рекурсивного вызова в стеке exec; но ты тоже должен его почистить.

Таким образом, альтернатива repeat будет:

int proc  **repeat**  -
    if int<0 Error
    if int==0 return //do nothing
    push null on exec stack   <--- this marks our "frame"
    push int-1 on exec stack
    push proc on exec stack
    push '@repeat-continue' on exec stack
    push executable proc on exec stack

Продолжение также имеет более простую работу.

@repeat-continue
    peek proc from exec stack
    peek int from exec stack
    if int==0 clear-to-null and return
    push '@repeat-continue' on exec stack
    push executable proc on exec stack

Наконец, оператор exit тесно связан с циклами, он очищает стек exec до «кадра» оператора цикла. Для стиля с двумя функциями это объект null или аналогичный. Для стиля с 1 функцией это сам оператор цикла.

2 голосов
/ 05 августа 2011

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

Глядя на свой код, добавьте untilв качестве слова условного перезапуска-оценки.То есть добавьте его как обычное слово вместе с вашими range и jump, сделайте так, чтобы оно вытолкнуло стек, и, если вершина стека была истинной, установите cmd stack.c обратно в начало.

0
dup . 1 + dup 5 > until
.

на вашем языке выдаст вывод 0 1 2 3 4 5 6 через три оценки и повторную оценку второй строки несколько раз.Это предполагает, что вы сохраняете состояние во всех оценках, и что оценка ориентирована на строки.Вы можете найти LSE64 , чтобы узнать больше подобных идей.

1 голос
/ 10 августа 2012

Вот запись в блоге, в которой DO / LOOP, BEGIN / UNTIL, WHILE / REPEAT и т. Д. Используются в моем маленьком проекте TransForth: http://blogs.msdn.com/b/ashleyf/archive/2011/02/06/loopty-do-i-loop.aspx

С тех пор я изменил свое мнение и полагаюсьполностью на рекурсии без таких зацикленных слов.

Надеюсь, это поможет, повеселиться!

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...