Слияние кода завершено, страница обновится автоматически
История разработки
Содержание
Парсер LL(1) парсер со специальной проверкой.
(var a,b,c)=[{b:nil},[1,2],func return 0;];
(a.b,b[0],c)=(1,2,3);
Эти два выражения имеют один и тот же первый набор, поэтому LL(1) бесполезен для этого языка. Мы добавили в него несколько специальных проверок. Проблемы, упомянутые выше, были решены давно, но недавно я обнаружил новую проблему здесь:
var f=func(x,y,z){return x+y+z}
(a,b,c)=(0,1,2);
Это будет распознано как это:
var f=func(x,y,z){return x+y+z}(a,b,c)
=(0,1,2);
и вызывает фатальную синтаксическую ошибку. И я попробовал эту программу в консоли flightgear nasal. Она также обнаружила, что это синтаксическая ошибка. Я думаю, что это серьёзный недостаток дизайна. Чтобы избежать этой синтаксической ошибки, измените программу следующим образом, просто добавьте точку с запятой:
var f=func(x,y,z){return x+y+z};
^ здесь
(a,b,c)=(0,1,2);
Первая полностью функциональная версия парсера. До версии 1.0 я много раз пытался создать правильный парсер. Наконец, я изучил LL(1) и LL(k) и написал парсер для математических формул в версии 0.16 (последнее обновление 2019/9/14). В версиях 0.17 (2019/9/15), 0.18 (2019/9/18), 0.19 (2019/10/1) я с удовольствием играл с парсером, а после этого написал версию 1.0. Этот проект начался 25 июля 2019 года.
Абстрактное синтаксическое дерево
Ast был завершён в этой версии.
Завершённый интерпретатор ast с незавершёнными библиотечными функциями.
Ast переработан и теперь его легче читать и поддерживать. Интерпретатор ast использует новые методы, поэтому он может выполнять коды более эффективно. Теперь вы можете добавлять свои собственные функции в качестве встроенных функций в этот интерпретатор! Я решил сохранить интерпретатор ast после выпуска v4.0. Потому что мне потребовалось много времени, чтобы подумать и написать...
Я передумал. AST-интерпретатор оставляет мне слишком много дел. Если я продолжу сохранять этот интерпретатор, мне будет сложнее сделать виртуальную машину байт-кода более эффективной.
Измените структуру ast. Теперь мы используем шаблон посетителя.
Виртуальная машина байт-кода
Я только что закончил первую версию интерпретатора байт-кода. Этот интерпретатор всё ещё находится на стадии тестирования. После этого теста я выпущу версию 4.0! Сейчас я пытаюсь найти скрытые ошибки в этом интерпретаторе. Надеюсь, вы сможете мне помочь! :) Вот пример кода байта ниже:
for(var i=0;i<4000000;i+=1);
.number 0
.number 4e+006
.number 1
.symbol i
0x00000000: pzero 0x00000000
0x00000001: loadg 0x00000000 (i)
0x00000002: callg 0x00000000 (i)
0x00000003: pnum 0x00000001 (4e+006)
0x00000004: less 0x00000000
0x00000005: jf 0x0000000b
0x00000006: pone 0x00000000
0x00000007: mcallg 0x00000000 (i)
0x00000008: addeq 0x00000000
0x00000009: pop 0x00000000
0x0000000a: jmp 0x00000002
0x0000000b: nop 0x00000000 **Версия 5.0 виртуальной машины (последнее обновление 2021/3/7)**
Я решил оптимизировать байт-код виртуальной машины в этой версии.
Потому что подсчёт от `0` до `4000000-1` занимает более 1,5 секунд. Это неэффективно!
**Обновление от 23 января 2021 года:** теперь подсчёт от `0` до `4000000-1` выполняется за 1,5 секунды.
**Версия 6.0 виртуальной машины (последнее обновление 2021/6/1)**
Используйте `loadg`/`loadl`/`callg`/`calll`/`mcallg`/`mcalll`, чтобы избежать ветвлений.
Удалите тип `vm_scop`.
Используйте константу `vm_num`, чтобы избегать частого создания и удаления объектов.
Измените сборщик мусора с подсчёта ссылок на пометки и очистку.
Операторы `vapp` и `newf` используют `.num` для уменьшения размера `exec_code`.
**Обновление от 3 апреля 2021 года**: теперь подсчёт от `0` до `4e6-1` выполняется за 0,8 секунды.
**Обновление от 19 апреля 2021 года**: теперь подсчёт от `0` до `4e6-1` выполняется за 0,4 секунды.
В этом обновлении я изменил глобальную и локальную область видимости с `unordered_map` на `vector`.
Поэтому генератор байт-кода сильно изменился.
```javascript
for(var i=0;i<4000000;i+=1);
.number 4e+006
0x00000000: intg 0x00000001
0x00000001: pzero 0x00000000
0x00000002: loadg 0x00000000
0x00000003: callg 0x00000000
0x00000004: pnum 0x00000000 (4e+006)
0x00000005: less 0x00000000
0x00000006: jf 0x0000000c
0x00000007: pone 0x00000000
0x00000008: mcallg 0x00000000
0x00000009: addeq 0x00000000
0x0000000a: pop 0x00000000
0x0000000b: jmp 0x00000003
0x0000000c: nop 0x00000000
Версия 6.5 виртуальной машины (последнее обновление 2021/6/24)
Обновление от 31 мая 2021 года:
Теперь сборщик мусора может правильно собирать мусор без повторной сборки, что может привести к фатальной ошибке.
Добавьте builtin_alloc, чтобы избежать пометки и очистки при выполнении встроенной функции, которая может пометить полезные элементы как бесполезный мусор для сбора.
Лучше использовать setsize и присваивание для получения большого массива, append в этом случае работает очень медленно.
Обновление от 3 июня 2021 года:
Исправлена ошибка, из-за которой сборщик мусора всё ещё повторно собирал мусор. На этот раз я использовал три состояния меток, чтобы убедиться, что мусор готов к сбору.
Изменил callf на callfv и callfh. И callfv извлекает аргументы из val_stack напрямую вместо использования vm_vec, что не очень эффективно.
Лучше используйте callfv, а не callfh, callfh будет извлекать vm_hash из стека и анализировать его, делая этот процесс медленным.
var f=func(x,y){return x+y;}
f(1024,2048);
.number 1024
.number 2048
.symbol x
.symbol y
0x00000000: intg 0x00000001
0x00000001: newf 0x00000007
0x00000002: intl 0x00000003
0x00000003: offset 0x00000001
0x00000004: para 0x00000000 (x)
0x00000005: para 0x00000001 (y)
0x00000006: jmp 0x0000000b
0x00000007: calll 0x00000001
0x00000008: calll 0x00000002
0x00000009: add 0x00000000
0x0000000a: ret 0x00000000
0x0000000b: loadg 0x00000000
0x0000000c: callg 0x00000000
0x0000000d: pnum 0x00000000 (1024)
0x0000000e: pnum 0x00000001 (2048)
0x0000000f: callfv 0x00000002
0x00000010: pop 0x00000000
0x00000011: nop 0x00000000
Обновление от 21 июня 2021 года: Теперь сборщик мусора не будет собирать nullptr. И функция присваивания завершена, теперь разрешены следующие виды присваиваний:
var f=func()
{
var _=[{_:0},{_:1}];
return func(x)
{
return _[x];
}
}
var m=f();
m(0)._=m(1)._=10;
[0,1,2][1:2][0]=0;
В старой версии парсер проверял это левое значение и сообщал, что эти виды левого значения не разрешены (плохое lvalue).
Но теперь это работает. И вы можете увидеть его использование, прочитав код выше. Чтобы убедиться, что это присваивание работает правильно, codegen сгенерирует байт-код с помощью codegen::call_gen(), а не codegen::mcall_gen(). А последний дочерний элемент ast будет сгенерирован с помощью codegen::mcall_gen(). Таким образом, байт-код теперь совершенно другой:
.number 10
.number 2
.symbol _
.symbol x
0x00000000: intg 0x00000002
0x00000001: newf 0x00000005
0x00000002: intl 0x00000002
0x00000003: offset 0x00000001
0x00000004: jmp 0x00000017
0x00000005: newh 0x00000000
0x00000006: pzero 0x00000000
0x00000007: happ 0x00000000 (_)
0x00000008: newh 0x00000000
0x00000009: pone 0x00000000
0x0000000a: happ 0x00000000 (_)
0x0000000b: newv 0x00000002
0x0000000c: loadl 0x00000001
0x0000000d: newf 0x00000012
0x0000000e: intl 0x00000003
0x0000000f:
``` В запросе представлен фрагмент программного кода, написанного на языке x86 Assembly. Это язык ассемблера для микропроцессоров семейства x86, который представляет собой машинно-ориентированный язык программирования низкого уровня.
В тексте запроса представлены команды, которые выполняют различные операции, такие как загрузка значений в регистры, вызов функций, сравнение значений и т. д. Однако, без контекста сложно понять, что именно делает этот код.
**Перевод текста запроса:**
Как видно из представленного байт-кода, частота использования операндов mcall, mcallv и mcallh будет уменьшаться, а call, callv, callh, callfv и callfh — наоборот.
Из-за новой структуры mcall, стек addr_stack, используемый для хранения адреса памяти, удаляется из виртуальной машины (vm), и теперь vm использует nas_val* mem_addr для хранения адреса памяти. Это не вызовет фатальных ошибок, поскольку адрес памяти используется *немедленно* после его получения.
### Версия 7.0 виртуальной машины (последнее обновление от 2021/10/8)
Обновление от 26 июня 2021 года:
Диспетчеризация инструкций изменена с вызова-потоков на вычисляемый переход (с встроенной функцией). После изменения способа диспетчеризации инструкций в виртуальной машине произошли значительные улучшения. Теперь виртуальная машина может запускать тесты/bigloop и test/pi за 0,2 секунды! А тест/fib выполняется за 0,8 секунды на Linux. Вы можете увидеть данные о времени выполнения ниже, в разделе «Тестовые данные».
Эта версия использует расширение g++ «метки как значения», которое также поддерживается clang++. (Но я не знаю, поддерживает ли это MSVC).
Также произошло изменение в сборщике мусора (gc): глобальный std::vector был удалён, теперь все глобальные значения хранятся в стеке (от val_stack+0 до val_stack+intg-1).
Обновление от 29 июня 2021 года:
Добавлены инструкции, выполняющие константные значения: op_addc, op_subc, op_mulc, op_divc, op_lnkc, op_addeqc, op_subeqc, op_muleqc, op_diveqc, op_lnkeqc.
Теперь байт-код теста/bigloop.nas выглядит так:
```x86asm
.number 4e+006
.number 1
0x00000000: intg 0x00000001
0x00000001: pzero 0x00000000
0x00000002: loadg 0x00000000
0x00000003: callg 0x00000000
0x00000004: pnum 0x00000000 (4000000)
0x00000005: less 0x00000000
0x00000006: jf 0x0000000b
0x00000007: mcallg 0x00000000
0x00000008: addeqc 0x00000001 (1)
0x00000009: pop 0x00000000
0x0000000a: jmp 0x00000003
0x0000000b: nop 0x00000000
И этот тестовый файл выполняется за 0,1 секунды после этого обновления. Большинство вычислений ускорено.
Кроме того, назначение байт-кода сильно изменилось. Теперь первый идентификатор, вызываемый при назначении, будет использовать op_load для назначения вместо op_meq, op_pop.
var (a,b)=(1,2);
a=b=0;
.number 2
0x00000000: intg 0x00000002
0x00000001: pone 0x00000000
0x00000002: loadg 0x00000000
0x00000003: pnum 0x00000000 (2)
0x00000004: loadg 0x00000001
0x00000005: pzero 0x00000000
0x00000006: mcallg 0x00000001
0x00000007: meq 0x00000000 (b=2 use meq,pop->a)
0x00000008: loadg 0x00000000 (a=b use loadg)
0x00000009: nop 0x00000000
Обновление от 8 октября 2021 года:
В этой версии vm_nil и vm_num теперь не управляются сборщиком мусора (gc), что снижает использование gc::alloc и повышает эффективность выполнения.
Добавлен новый тип значений: vm_obj. Этот тип зарезервирован для пользователей, чтобы они могли определять свои собственные типы значений. Соответствующий API будет добавлен в будущем.
Полностью функциональная замыкание: добавлены новые операнды, которые получают и устанавливают upvalues. Удалён старый... Operand op_offset.
Обновление от 13 октября 2021 года:
Формат вывода информации о байт-кодах изменяется следующим образом:
0x000002f2: newf 0x2f6
0x000002f3: intl 0x2
0x000002f4: para 0x3e ("x")
0x000002f5: jmp 0x309
0x000002f6: calll 0x1
0x000002f7: lessc 0x0 (2)
0x000002f8: jf 0x2fb
0x000002f9: calll 0x1
0x000002fa: ret
0x000002fb: upval 0x0[0x1]
0x000002fc: upval 0x0[0x1]
0x000002fd: callfv 0x1
0x000002fe: calll 0x1
0x000002ff: subc 0x1d (1)
0x00000300: callfv 0x1
0x00000301: upval 0x0[0x1]
0x00000302: upval 0x0[0x1]
0x00000303: callfv 0x1
0x00000304: calll 0x1
0x00000305: subc 0x0 (2)
0x00000306: callfv 0x1
0x00000307: add
0x00000308: ret
0x00000309: ret
0x0000030a: callfv 0x1
0x0000030b: loadg 0x32
Обновление от 22 января 2022 года:
Удалите op_pone и op_pzero.
Они не имеют смысла и будут заменены на op_pnum.
Версия 9.0 виртуальной машины (последнее обновление от 18 мая 2022 года):
Обновление от 12 февраля 2022 года:
Локальные значения теперь хранятся в стеке.
Поэтому вызов функций будет быстрее, чем раньше.
Потому что в версии 8.0 при вызове функции новый vm_vec выделяется сборщиком мусора, это заставляет сборщик мусора выполнять маркировку и очистку слишком много раз и занимает довольно много времени.
В тестовом файле test/bf.nas требуется слишком много времени для тестирования файла, потому что этот файл имеет слишком много вызовов функций (см. данные теста ниже в таблице «Версия 8.0 (R9-5900HX ubuntu-WSL 2022/1/23)»).
Значение upvalue теперь генерируется при создании первой новой функции в локальной области с использованием vm_vec.
И после этого при создании новых функций они совместно используют одно и то же значение upvalue, и значение upvalue синхронизируется с локальной областью каждый раз при создании новой функции.
Обновление от 27 марта 2022 года:
В обновлениях этого месяца мы меняем значение upvalue с vm_vec на vm_upval, специальный объект, управляемый сборщиком мусора, который имеет почти ту же структуру, что и объект upvalue в другом языке программирования Lua.
Сегодня мы изменяем формат вывода байт-кода.
Новый формат вывода выглядит как objdump:
0x0000029b: 0a 00 00 00 00 newh
func <0x29c>:
0x0000029c: 0b 00 00 02 a0 newf 0x2a0
0x0000029d: 02 00 00 00 02 intl 0x2
0x0000029e: 0d 00 00 00 66 para 0x66 ("libname")
0x0000029f: 32 00 00 02 a2 jmp 0x2a2
0x000002a0: 40 00 00 00 42 callb 0x42 <__dlopen@0x41dc40>
0x000002a1: 4a 00 00 00 00 ret
<0x29c>;
0x000002a2: 0c 00 00 00 67 happ 0x67 ("dlopen")
func <0x2a3>:
0x000002a3: 0b 00 00 02 a8 newf 0x2a8
0x000002a4: 02 00 00 00 03 intl 0x3
0x000002a5: 0d 00 00 00 68 para 0x68 ("lib")
0x000002a6: 0d 00 00 00 69 para 0x69 ("sym")
0x000002a7: 32 00 00 02 aa jmp 0x2aa
0x000002a8: 40 00 00 00 43 callb 0x43 <__dlsym@0x41df00>
0x000002a9: 4a 00 00 00 00 ret
<0x2a3>;
0x000002aa: 0c 00 00 00 6a happ 0x6a ("dlsym")
Версия 10.0 виртуальной машины (последнее обновление от 16 августа 2022 года):
Обновление от 19 мая 2022 года:
Теперь мы добавляем сопрограмму в эту среду выполнения:
var coroutine={
create: func(function){return __cocreate;},
resume: func(co) {return __coresume;},
yield: func(args...) {return __coyield; },
status: func(co) {return __costatus;},
running:func() {return __corun; }
};
coroutine.create используется для создания нового объекта сопрограммы с использованием функции.
Но эта сопрограмма не запустится немедленно.
coroutine.resume используется для продолжения работы сопрограммы.
coroutine.yield используется для прерывания работы сопрограммы и выдачи некоторых значений.
Эти значения будут приняты и возвращены coroutine.resume.
А coroutine.yield сам по себе возвращает vm_nil в функции сопрограммы.
coroutine.status используется для просмотра статуса сопрограммы.
Существует 3 типа статуса: suspended означает ожидание запуска,running означает запуск,dead означает завершение работы.
coroutine.running используется, чтобы определить, работает ли сейчас сопрограмма.
Внимание: сопрограмма не должна создаваться или работать внутри другой сопрограммы. Резюме и результаты работы здесь:
Когда вызывается op_callb, кадр стека выглядит следующим образом:
+----------------------+(main stack)
| old pc(vm_ret) | <- top[0]
+----------------------+
| old localr(vm_addr) | <- top[-1]
+----------------------+
| old upvalr(vm_upval) | <- top[-2]
+----------------------+
| local scope(var) |
| ... |
+----------------------+ <- local pointer stored in localr
| old funcr(vm_func) | <- old function stored in funcr
+----------------------+
В процессе выполнения op_callb следующий шаг кадра стека:
+----------------------+(main stack)
| nil(vm_nil) | <- push nil
+----------------------+
| old pc(vm_ret) |
+----------------------+
| old localr(vm_addr) |
+----------------------+
| old upvalr(vm_upval) |
+----------------------+
| local scope(var) |
| ... |
+----------------------+ <- local pointer stored in localr
| old funcr(vm_func) | <- old function stored в funcr
+----------------------+
Затем мы вызываем resume, эта функция изменит стек.
Как мы видим, в стеке сопрограммы уже есть некоторые значения,
но если мы впервые войдём в него, вершина стека будет vm_ret, а возвращаемый pc равен 0.
Поэтому для безопасного выполнения при первом вызове сопрограммы resume вернёт gc.top[0].
op_callb сделает top[0]=resume(), поэтому значение не изменится.
+----------------------+(coroutine stack)
| pc:0(vm_ret) | <- теперь gc.top[0]
+----------------------+
При вызове yield функция будет делать следующее.
И мы обнаруживаем, что op_callb поместил nil на вершину.
Но куда отправляется возвращённый local[1]?
+----------------------+(сопрограммный стек)
| nil(vm_nil) | <- push nil
+----------------------+
| старый pc(vm_ret) |
+----------------------+
| старый localr(vm_addr)|
+----------------------+
| старый upvalr(vm_upval)|
+----------------------+
| локальная область(var)|
| ... |
+----------------------+ <- локальный указатель, хранящийся в localr
| старая функция(vm_func)| <- старая функция, хранящаяся в funcr
+----------------------+
Когда builtin_coyield завершает работу, стек устанавливается в основной стек,
и возвращённый local[1], фактически, устанавливается на вершину основного стека с помощью op_callb:
+----------------------+(основной стек)
| возвращаемое значение(var)|
+----------------------+
| старый pc(vm_ret) |
+----------------------+
| старый localr(vm_addr) |
+----------------------+
| старый upvalr(vm_upval) |
+----------------------+
| локальная область(var) |
| ... |
+----------------------+ <- локальный указатель, хранящийся в localr
| старая функция(vm_func)| <- старая функция, хранящаяся в funcr
+----------------------+
Таким образом, основной прогресс воспринимает значение на вершине как возвращённое значение resume.
Но на самом деле возвращённое значение resume установлено в кадре стека сопрограммы.
Итак, мы делаем вывод:
resume (main->coroutine) возвращает coroutine.top[0]. coroutine.top[0] = coroutine.top[0];
yield (coroutine->main) возвращает вектор. main.top[0] = vector;
Я сделал большую ошибку в v8.0 выпуске:
в nasal_dbg.h:215: auto canary=gc.stack+STACK_MAX_DEPTH-1;
это вызовет некорректную ошибку stackoverflow.
пожалуйста, измените его на:
canary=gc.stack+STACK_MAX_DEPTH-1;
Если вы не измените эту строку, только отладчик будет работать неправильно. эта ошибка исправлена в v9.0.
Ещё одна ошибка заключается в том, что в nasal_err.h:class nasal_err мы должны добавить конструктор для этого класса:
nasal_err(): error(0) {}
Эта ошибка исправлена в v9.0. Поэтому мы рекомендуем не использовать v8.0.
Используйте C++ std=c++17.
Измените структуру ast, используя шаблон посетителя.
Новый формат информации о структуре дампа ast.
Измените способ экспорта модулей, разделите библиотеку на разные модули. Символы, начинающиеся с _, не будут экспортироваться.
Замените stl на std.
Добавьте интерпретатор REPL.
Улучшите структуру виртуальной машины, разделите глобальный стек символов (хранит значения глобальных символов) и стек значений (используется в процессе).
Вы можете оставить комментарий после Вход в систему
Неприемлемый контент может быть отображен здесь и не будет показан на странице. Вы можете проверить и изменить его с помощью соответствующей функции редактирования.
Если вы подтверждаете, что содержание не содержит непристойной лексики/перенаправления на рекламу/насилия/вульгарной порнографии/нарушений/пиратства/ложного/незначительного или незаконного контента, связанного с национальными законами и предписаниями, вы можете нажать «Отправить» для подачи апелляции, и мы обработаем ее как можно скорее.
Опубликовать ( 0 )