Нашли или выдавили из себя код, который нельзя назвать нормальным, на который без улыбки не взглянешь? Не торопитесь его удалять или рефакторить, — запостите его на говнокод.ру, посмеёмся вместе!
0
Alg Root;
arg x, y;
Root = getRoot(x, y, 1);
end;
Sub getRoot;
arg x, y, r;
if Power(r, x) < y then
getRoot = getRoot(x, y, r + 1);
else
if Power(r, x) = y then
getRoot = r;
else
getRoot = r - 1;
end;
end;
end;
Sub Power;
arg x, y;
if 0 < y then
Power = x * Power(x, y - 1);
else
Power = 1;
end;
end;
Написал напитоне простой интерпретатор функционального языка из учебника по теоретическим основам информатики, давайте обсудим
https://hastebin.com/ocadegapuv.py
сам учебник, в котором описывается язык и семантика (глава про функциональные программы)
http://www.ict.edu.ru/ft/003627/lect1.pdf
В оп-коде пример программы, которую ему можно скормить
(вычисляет целую часть корня степени x из числа y).
Подскажите, для начала, как распознать и развернуть в цикл хвостовую рекурсию.
И если кто напитоне работает, этот код вообще котируется, или есть явное палево?
Запостил: 
vistefan,
18 Января 2018
Follow us!
сам так далеко не заходил (лень). и твой код не читал (TL;DR).
на практике. сначала строится AST. AST для интертрепации можно использовать, но оно слегка рекурсивное и поэтому слегка неудобно.
поэтому часто/типично из AST делается линейное плоское представление: часто те же самые AST ноды, но списком вместо дерева + jump/goto & return для управление контролем.
теперь, когда у тебя есть плоский список нодов (часто называемых BB - basic block) для исполнения, можно начинать делать и оптимизации. tail recursion - это когда у тебя вызов самое себя, с последующим ретурном. вместа ретурна - впиливаешь goto на начало списка нодов aka начало функции.
к слову, самый простой/убогий способ постоения плоского представления, это tracing: почти как бы интерпретируешь код рекурсивно, но заходишь во все бранчи нодов, и вместо исполнения этих нодов, ты их складываешь в список. но нужно будет еще и гото генерировать, при выходе из рекурсии, на конец родительского(?) нода.
ЗЫ я пошёл пиво. ждите бормандов и комманду функциональщиков - они вам лучше/больше расскажут.
Вообще вышло смешно, учебник 2003-го года, я только написал интерпретаторы для языка с метками и функционального языка, как узнал, что пару месяцев назад вышло второе издание книги, где всё поменялось.
Так ты проверяй области видимости и строй окружение заранее, пока AST есть.
Мне сразу всю "память" исполняемой программы создать, со всеми переменными, для каждой функции, а потом при разворачивании дерева в линию запомнить, какая функция какой области соответствует?
Вряд ли ты это имел ввиду, тогда рекурсию не получится сделать, функция сама на себя сайд-эффектить будет.
Что-то я ничего не понимаю. Область видимости нужна только для компилятора, при исполнении ничего проверять уже не надо.
Под все переменные функции можно вообще один список выделить (назовём его VARS). Во время прохода по дереву
для каждого объявления переменной (x) можно добавлять новую запись в VARS (n = len(VARS) + 1),
(x = 5) превращать в (VARS[n] = 5)
(y = x + z) превращать в (VARS[i] = VARS[n] + VARS[j]).
Для проверки областей видимости таскаешь стек мап-скопов, при входе в нод с объявлениями переменных добавляешь новую мапу в стек, при выходе — выкидываешь мапу.
После прохода все имена переменных будут заменены индексами в VARS. Никаких "областей видимости" уже не будет, всё было проверено при обходе AST. Этот VARS можно на стеке разместить при желании.
Если захочется нормальные замыкания сделать, модель надо усложнять.
отделение "переменной" от "значения переменной" + правильные syntax/run-time контексты + GC. (для простоты от синтакс контекстов можно отказатся.) давно руки чешутся попробовать поковырять. но лень, потому что для полноты надо гц прикручивать, что бы контекст и его содержимое освобождать.
Ну сделай с подсчетом ссылок.
у меня ассоциация с гц это графы. а графы я не люблю.
интересно как они тогда гц делали.
сегфолтились, когда память кончалась
учись писать FSMы, или пользуйся yacc/bison/этц - потому что что-то путное сделать будет и нудно и трудно и много писанины.
для питона какие-то либы парсеры то же есть.
Я, можно сказать, с этой целью и взялся за интерпретатор. А как их писать? Кучу кейсов я написал, что-то не очень. Наверное лучше делать массив токенов для каждой существующей в языке структуры и проверять, не выпадает ли из него код.
Расскажите, чуваки, как кодят конечные автоматы на С обычно?
Каждая регулярка - детерминированный конечный автомат.
Все ДКА для токенов собираются в один "пучок", минимизируются и приводятся к недетерминированному конечному автомату.
Этот НКА и работает лексическим анализатором. По сути, он ищет самый длинный встретившийся токен, применяя все регулярки разом.
Делать это руками - то еще удовольствие; если нет академического интереса - лучше взять готовый инструмент, в противном случае придется спать в обнимку с книгой дракона. Как мне кажется, никакой источник информации лучше не расскажет.
В общем, удачи :) Да пребудут с тобой анал, минет, кордебалет.
Как из ДКА получается НКА, и как он вообще лексический анализ делает, если он недетерминированный, не пойму?
> если нет академического интереса
Ох как есть
> книга дракона
Это про LLVM что-то? Линкани.
Это книга про построение компилятора, от начала до конца. Первых глав хватит, чтобы построить простенький интерпретатор.
Различие ДКА и НКА в том, что первый может находиться в нескольких состояниях, а второй - в одном.
Входной поток подает автомату символ - он переходит в новое состояние. Дошел до конечного состояния - сгенерировал токен, сбросился до начального состояния.
Лучше скачай книгу, там есть ответы на твои вопросы с примерами. Я уже не особо много помню, да и не описать все это в комментариях.
А ты их не перепутал? Наоборот, детерминированный -- в одном.
Хех, надо всё-таки прочитать эту книгу...
Недавно хотел по-быстрому выдрать данные из скриптов factorio, а получился кривой интерпретатор lua с вот таким говнищем вместо парсера:
Токены регулярками откусываются, AST из них собирается вон теми говноифами и потом интерпретируется через метод execute прикрученный прямо к нодам AST...
Хуяк-хуяк и распарсен.
А почему ты спрашиваешь, золотой хуй?
по аст исполнение медленее, чем по плоскому списку.
на плоском списке делается как минимум гото оптимизация - в то время как просто обход аст, и скипание чисто синтаксических конструкций, тоже время отъедает.
или тупо: в два раза меньше нодов обходить - в два раза быстрее интертрепация. :-)
ЗЫ и это уже не говоря об обработке ошибок где в глубине аст.
> обработке ошибок где в глубине аст
В обработчиках нод возвращаешь результат/ошибку. На интересных нодах (вызовы функций) пополняешь бектрейс ошибки инфой о координатах ноды в исходнике... Терпимо, в принципе.
З.Ы. Ну и при прямом исполнении AST goto довольно сложно реализовать, в отличие от структурных while/for/if (х.з., минус ли это).
поэтому народ и чинит уже 3 десятилетия yacc/bison. туториалов там завались.
> Наверное лучше делать массив токенов для каждой существующей в языке структуры и проверять, не выпадает ли из него код.
это проблему не решает - тебе все равно придется писать кучи херни.
самый читабельный вариант который видел это калейдоскоп дема из llvm: https://llvm.org/docs/tutorial/LangImpl01.html
я лично для домашних мелких поделок продолжаю клепать парсеры FSMами с switch/case-ами, потому что там все фичи "доступны", как типа контекстно-зависимая токенизация. расширять их и переписывать мука - но это можно делать в code-monkey режиме. (парсер чего-то tcl/лиспо-образного - https://github.com/Kervius/ktr/blob/fork-minsk-001/Minsk/min.cc#L618 )
народ хвалит antlr - но у меня до него так руки и не дошли.
Генераторы парсеров у меня как-то не зашли. С парсер-комбинаторами, практика показывает, возни на порядок меньше. Да, DSL не такой DSистый, но зато затрат на интеграцию с остальным кодом нет.
бизону в 3й версии вроде бы прикрутили поддержку крестов: он генерит теперь класс - с вставками твоего кода. и вроде даже с какими-то exception-safe гарантиями. (это теоретически решает мою старую проблему невозможности вернуть ошибку или просто остановится на ошибке - кроме как exit().)
ЗЫ сам еще не пробовал - https://www.gnu.org/software/bison/manual/html_node/C_002b_002b-Parsers.html#C_002b_002b-Parsers
надо будет поковырять, потому что само-писаные парсеры мне тоже больше нравятся (их можно отлаживать/этц) но когда дело доходит до расширения языка, то там хоть удавись.
Или побаловаться и написать такое на Свифте.
на хуиксинах
P.S. хаха, а ты похоже хуиксинщик http://govnokod.ru/23641
Особенно прикольно компилить простенькую грамматику по 30 секунд и искать номер строки с опечаткой в километровой портянке с ошибками...
моя проблема была в том что оно множит бойлер-плейт крестовый (переиспользование кода == тучи мелких функций), и не сильно читабельно по сравнению с тем же yacc/bison (nested syntax highlighting специально для спирита сделать в редакторе будет не тривиально, учитывая что там будет еще крестовый код везде подмешан).
с другой стороны, если пишешь что-то неправильно, то понять что именно от тебя хочет спирит - какая несовместимость типов - не тривиально. я с какой-то простой модификацией демы пол часа протрахался. другая модификация почему-то вообще игнорировалась. оно там как-то хитрожопо реализовано, потому что (если память не изменяет) сгенереная функция парсера относительно маленькая (и я так хер и понял в чем была моя ошибка).