- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
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.01.2018 00:39 # 0
subaru 18.01.2018 00:44 # +3
Dummy00001 18.01.2018 01:42 # +3
сам так далеко не заходил (лень). и твой код не читал (TL;DR).
на практике. сначала строится AST. AST для интертрепации можно использовать, но оно слегка рекурсивное и поэтому слегка неудобно.
поэтому часто/типично из AST делается линейное плоское представление: часто те же самые AST ноды, но списком вместо дерева + jump/goto & return для управление контролем.
теперь, когда у тебя есть плоский список нодов (часто называемых BB - basic block) для исполнения, можно начинать делать и оптимизации. tail recursion - это когда у тебя вызов самое себя, с последующим ретурном. вместа ретурна - впиливаешь goto на начало списка нодов aka начало функции.
Dummy00001 18.01.2018 01:52 # +1
к слову, самый простой/убогий способ постоения плоского представления, это tracing: почти как бы интерпретируешь код рекурсивно, но заходишь во все бранчи нодов, и вместо исполнения этих нодов, ты их складываешь в список. но нужно будет еще и гото генерировать, при выходе из рекурсии, на конец родительского(?) нода.
ЗЫ я пошёл пиво. ждите бормандов и комманду функциональщиков - они вам лучше/больше расскажут.
vistefan 18.01.2018 10:20 # 0
Вообще вышло смешно, учебник 2003-го года, я только написал интерпретаторы для языка с метками и функционального языка, как узнал, что пару месяцев назад вышло второе издание книги, где всё поменялось.
roman-kashitsyn 18.01.2018 11:31 # +1
Так ты проверяй области видимости и строй окружение заранее, пока AST есть.
vistefan 18.01.2018 11:36 # 0
Мне сразу всю "память" исполняемой программы создать, со всеми переменными, для каждой функции, а потом при разворачивании дерева в линию запомнить, какая функция какой области соответствует?
Вряд ли ты это имел ввиду, тогда рекурсию не получится сделать, функция сама на себя сайд-эффектить будет.
roman-kashitsyn 18.01.2018 12:10 # +4
Что-то я ничего не понимаю. Область видимости нужна только для компилятора, при исполнении ничего проверять уже не надо.
Под все переменные функции можно вообще один список выделить (назовём его VARS). Во время прохода по дереву
для каждого объявления переменной (x) можно добавлять новую запись в VARS (n = len(VARS) + 1),
(x = 5) превращать в (VARS[n] = 5)
(y = x + z) превращать в (VARS[i] = VARS[n] + VARS[j]).
Для проверки областей видимости таскаешь стек мап-скопов, при входе в нод с объявлениями переменных добавляешь новую мапу в стек, при выходе — выкидываешь мапу.
После прохода все имена переменных будут заменены индексами в VARS. Никаких "областей видимости" уже не будет, всё было проверено при обходе AST. Этот VARS можно на стеке разместить при желании.
Если захочется нормальные замыкания сделать, модель надо усложнять.
vistefan 18.01.2018 12:14 # 0
Dummy00001 18.01.2018 13:07 # 0
отделение "переменной" от "значения переменной" + правильные syntax/run-time контексты + GC. (для простоты от синтакс контекстов можно отказатся.) давно руки чешутся попробовать поковырять. но лень, потому что для полноты надо гц прикручивать, что бы контекст и его содержимое освобождать.
bormand 18.01.2018 18:27 # 0
Ну сделай с подсчетом ссылок.
Dummy00001 18.01.2018 18:57 # 0
у меня ассоциация с гц это графы. а графы я не люблю.
Dummy00001 19.01.2018 19:51 # +1
интересно как они тогда гц делали.
roman-kashitsyn 19.01.2018 19:54 # +1
сегфолтились, когда память кончалась
Dummy00001 18.01.2018 01:45 # 0
учись писать FSMы, или пользуйся yacc/bison/этц - потому что что-то путное сделать будет и нудно и трудно и много писанины.
для питона какие-то либы парсеры то же есть.
vistefan 18.01.2018 10:11 # +1
Я, можно сказать, с этой целью и взялся за интерпретатор. А как их писать? Кучу кейсов я написал, что-то не очень. Наверное лучше делать массив токенов для каждой существующей в языке структуры и проверять, не выпадает ли из него код.
Расскажите, чуваки, как кодят конечные автоматы на С обычно?
Xom94ok 18.01.2018 11:29 # +2
Каждая регулярка - детерминированный конечный автомат.
Все ДКА для токенов собираются в один "пучок", минимизируются и приводятся к недетерминированному конечному автомату.
Этот НКА и работает лексическим анализатором. По сути, он ищет самый длинный встретившийся токен, применяя все регулярки разом.
Делать это руками - то еще удовольствие; если нет академического интереса - лучше взять готовый инструмент, в противном случае придется спать в обнимку с книгой дракона. Как мне кажется, никакой источник информации лучше не расскажет.
В общем, удачи :) Да пребудут с тобой анал, минет, кордебалет.
vistefan 18.01.2018 11:32 # 0
Как из ДКА получается НКА, и как он вообще лексический анализ делает, если он недетерминированный, не пойму?
> если нет академического интереса
Ох как есть
> книга дракона
Это про LLVM что-то? Линкани.
roman-kashitsyn 18.01.2018 11:36 # +2
Xom94ok 18.01.2018 11:45 # +3
Это книга про построение компилятора, от начала до конца. Первых глав хватит, чтобы построить простенький интерпретатор.
Различие ДКА и НКА в том, что первый может находиться в нескольких состояниях, а второй - в одном.
Входной поток подает автомату символ - он переходит в новое состояние. Дошел до конечного состояния - сгенерировал токен, сбросился до начального состояния.
Лучше скачай книгу, там есть ответы на твои вопросы с примерами. Я уже не особо много помню, да и не описать все это в комментариях.
vistefan 18.01.2018 12:06 # +3
А ты их не перепутал? Наоборот, детерминированный -- в одном.
Xom94ok 18.01.2018 19:23 # +2
vistefan 18.01.2018 19:41 # +3
bormand 18.01.2018 20:23 # 0
Хех, надо всё-таки прочитать эту книгу...
Недавно хотел по-быстрому выдрать данные из скриптов factorio, а получился кривой интерпретатор lua с вот таким говнищем вместо парсера:
syoma 18.01.2018 23:13 # 0
roman-kashitsyn 18.01.2018 23:21 # 0
syoma 18.01.2018 23:34 # 0
vistefan 19.01.2018 00:20 # +3
syoma 19.01.2018 00:32 # −4
vistefan 19.01.2018 00:39 # 0
syoma 19.01.2018 01:21 # 0
bormand 19.01.2018 06:50 # 0
Токены регулярками откусываются, AST из них собирается вон теми говноифами и потом интерпретируется через метод execute прикрученный прямо к нодам AST...
Хуяк-хуяк и распарсен.
bormand 19.01.2018 07:17 # 0
vistefan 19.01.2018 09:24 # 0
3oJIoTou_xyu 19.01.2018 10:03 # 0
vistefan 19.01.2018 10:15 # 0
А почему ты спрашиваешь, золотой хуй?
Dummy00001 19.01.2018 20:20 # +1
по аст исполнение медленее, чем по плоскому списку.
на плоском списке делается как минимум гото оптимизация - в то время как просто обход аст, и скипание чисто синтаксических конструкций, тоже время отъедает.
или тупо: в два раза меньше нодов обходить - в два раза быстрее интертрепация. :-)
ЗЫ и это уже не говоря об обработке ошибок где в глубине аст.
bormand 19.01.2018 20:39 # 0
> обработке ошибок где в глубине аст
В обработчиках нод возвращаешь результат/ошибку. На интересных нодах (вызовы функций) пополняешь бектрейс ошибки инфой о координатах ноды в исходнике... Терпимо, в принципе.
З.Ы. Ну и при прямом исполнении AST goto довольно сложно реализовать, в отличие от структурных while/for/if (х.з., минус ли это).
Dummy00001 19.01.2018 23:25 # 0
Dummy00001 18.01.2018 12:51 # 0
поэтому народ и чинит уже 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 - но у меня до него так руки и не дошли.
CHayT 18.01.2018 21:48 # 0
Генераторы парсеров у меня как-то не зашли. С парсер-комбинаторами, практика показывает, возни на порядок меньше. Да, DSL не такой DSистый, но зато затрат на интеграцию с остальным кодом нет.
Dummy00001 19.01.2018 16:20 # 0
бизону в 3й версии вроде бы прикрутили поддержку крестов: он генерит теперь класс - с вставками твоего кода. и вроде даже с какими-то exception-safe гарантиями. (это теоретически решает мою старую проблему невозможности вернуть ошибку или просто остановится на ошибке - кроме как exit().)
ЗЫ сам еще не пробовал - https://www.gnu.org/software/bison/manual/html_node/C_002b_002b-Parsers.html#C_002b_002b-Parsers
надо будет поковырять, потому что само-писаные парсеры мне тоже больше нравятся (их можно отлаживать/этц) но когда дело доходит до расширения языка, то там хоть удавись.
Desktop 19.01.2018 19:57 # 0
roman-kashitsyn 19.01.2018 20:05 # +3
Desktop 19.01.2018 20:16 # 0
Или побаловаться и написать такое на Свифте.
inho 20.01.2018 11:59 # 0
на хуиксинах
P.S. хаха, а ты похоже хуиксинщик http://govnokod.ru/23641
Desktop 20.01.2018 12:04 # 0
MacFerden 19.01.2018 15:41 # +1
bormand 19.01.2018 18:24 # +4
Особенно прикольно компилить простенькую грамматику по 30 секунд и искать номер строки с опечаткой в километровой портянке с ошибками...
Dummy00001 19.01.2018 23:34 # 0
моя проблема была в том что оно множит бойлер-плейт крестовый (переиспользование кода == тучи мелких функций), и не сильно читабельно по сравнению с тем же yacc/bison (nested syntax highlighting специально для спирита сделать в редакторе будет не тривиально, учитывая что там будет еще крестовый код везде подмешан).
с другой стороны, если пишешь что-то неправильно, то понять что именно от тебя хочет спирит - какая несовместимость типов - не тривиально. я с какой-то простой модификацией демы пол часа протрахался. другая модификация почему-то вообще игнорировалась. оно там как-то хитрожопо реализовано, потому что (если память не изменяет) сгенереная функция парсера относительно маленькая (и я так хер и понял в чем была моя ошибка).
CHayT 20.01.2018 00:02 # +4
g0cTb 20.01.2018 00:39 # +3
CHayT 19.01.2018 23:59 # +6