[jcxz 224]

1 час назад, xvr сказал:

Для произвольного дерева OR/AND нужны полноценные условные переходы в байт-коде (код будет 'толще'). Для цепочек AND'ов связанных OR'ами достаточно 2х адресов (в 2х специальных регистрах) и набора команд Check* и Jmp

Какие переходы? Вы о чём? Скобки изменяют только последовательность операций (и последовательность занесения операндов в стек). И переходы не нужны.

[xvr 12]

18 hours ago, jcxz said:

Какие переходы? Вы о чём?

Об операции if. OR/AND используются в качестве условий в ней. Используется shoкtcut вычисления - если результат операции известен после вычисления первого условия, то второе не вычисляется. Для этого нужны переходы.

Если shortcut не делать, а вычислять как обычную арифметику, то можно сделать любые выражения. Но что нибудь такого типа: if a != 0 and b/a > 10 then ... уже не напишешь

 

Вопрос к ТС - shortcut нужны?

[jenya7 0]

1 hour ago, xvr said:

Об операции if. OR/AND используются в качестве условий в ней. Используется shoкtcut вычисления - если результат операции известен после вычисления первого условия, то второе не вычисляется. Для этого нужны переходы.

Если shortcut не делать, а вычислять как обычную арифметику, то можно сделать любые выражения. Но что нибудь такого типа: if a != 0 and b/a > 10 then ... уже не напишешь

 

Вопрос к ТС - shortcut нужны?

я думаю как в обычном С. если первое условие в AND не выполняется дальше не идем, выходим из выражения. 

[jcxz 224]

2 часа назад, xvr сказал:

Но что нибудь такого типа: if a != 0 and b/a > 10 then ... уже не напишешь

Почему не напишешь? Всё как в обычном си - и выражения в условии if возможны любые. А неполное вычисление вообще непонятно зачем нужно. И создаст только кучу проблем. Ведь кроме скобок есть ещё и приоритет операций.

19 минут назад, jenya7 сказал:

я думаю как в обычном С. если первое условие в AND не выполняется дальше не идем, выходим из выражения. 

В обычном си есть приоритет операций. По обработке это будет то же самое что скобки.

[xvr 12]

2 hours ago, jenya7 said:

я думаю как в обычном С. если первое условие в AND не выполняется дальше не идем, выходим из выражения. 

В С в выражениях возможны побочные эффекты. У вас в спецификации таких эффектов нет (за исключением деления на 0). Так что разница в полном/сокращённом вычислении только в скорости выполнения (с сокращенном выполнении она будет больше, т.к. не надо вычислять дополнительный код), и в размере байт кода (в полном он будет меньше, т.к. не нужны команды переходов).

Ну и компилятор и интерпретатор для режима полных вычислений будет проще

1 hour ago, jcxz said:

Почему не напишешь?

Потому что будет деление на 0. Если его доопределить до чего нибудь осмысленного, то можно написать.

 

[xvr 12]

Итак продолжаем.

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

Теперь описание байткода такое (файл opcodes.h):

Spoiler

#pragma once

enum Opcode {
    OP_Const0  = 0x00,
    MASK_Const0 = 0x80,
    OP_ReadVar = 0x80,
    OP_SetVar  = 0xA0,
    OP_AddVar  = 0xC0,
    MASK_Var   = 0xE0,
    OP_Const2  = 0xE0,
    OP_Const4,
    OP_JmpF1,
    OP_JmpF2,
    OP_EQ,
    OP_NE,
    OP_GT,
    OP_GE,
    OP_And,
    OP_Or,
    OP_Add,
    OP_Sub,
    OP_Mul,
    OP_Div,
    OP_Mod,
    OP_Neg,
    OP_Stop = 0xFF
};

 

Этот файл в таком виде используется как на стороне РС (в компиляторе), так и на стороне МК

Все опкоды начинаются с префикса OP_, префиксом MASK_ помечены маски, для выделения групп опкодов (на стороне интерпретатора)

Немного по самим опкодам:

• OP_ConstN - Константа (разной величины и длинны в байтах)
• OP_*Var - Работа с переменными (чтение, запись, инкремент). Может сопровождаться байтом с индексом переменной
• OP_JmpF1/2 - Снимает со стека число, и если оно равно 0 осуществляет переход по смещению, записанному в комманде (1 или 2 байта)
• OP_Stop - Останов интерпретатора
• OP_* - арифметика и логика

 

Компилятор пишем на С++

На стороне компилятора каждая строка скрипта преобразуется в дерево выражения (описывается структурой Node и её наследниками - см далее), затем дерево сериализуется в байткод через класс CodeGenerator (так же см ниже)

 

[xvr 12]

Итак классы Node:

Spoiler

struct Node {
    const Opcode opcode;

    Node(Opcode opc) : opcode(opc) {}
    virtual ~Node() {}
    virtual void generate_code(CodeGenerator&) = 0;
};


struct NodeConst : public Node {
    int32_t value;

    NodeConst(int32_t v) : Node(OP_Const0), value(v) {}
    virtual void generate_code(CodeGenerator&);
};

struct NodeVar : public Node {
    uint16_t index;
    Node* assign_value;
    Node* next;

    NodeVar(Opcode opc, uint16_t idx, Node* assign_val=NULL) : Node(opc), index(idx), assign_value(assign_val), next(NULL) {}
    ~NodeVar() {delete assign_value; delete next;}
    virtual void generate_code(CodeGenerator&);

    NodeVar* join(NodeVar*);
};

struct NodeOp : public Node {
    Node *left, *right;

    NodeOp(Opcode opc, Node* l, Node* r=NULL): Node(opc), left(l), right(r) {}
    ~NodeOp() {delete left; delete right;}
    virtual void generate_code(CodeGenerator&);
};

 

Node - базовый класс. Единственная виртуальная функция - generate_code занимается сериализацией себя в буфер кода

Наследники:

• NodeConst - Описывает константу
• NodeVar - Все операции с переменными. Поле assign_value хранит значение для операций = и +=. По полю next экземпляры этого класса связываются в список, который используется для представления тела оператора then
• NodeOp - Все остальные операции (как бинарные так и унарные)

 

Класс CodeGenerator содержит массив с бинарным образом (code_image) и опциональный файл (lst_file) куда выводится листинг в процессе генерации кода.

Spoiler

struct CodeGenerator {
    std::vector<uint8_t> code_image;
    FILE* lst_file;

    void push(int opc, int length, int32_t data, const std::string& asm_menmonic);
public:
    CodeGenerator(FILE* lst=NULL) : lst_file(lst) {}

    void push0(int opc, const std::string& asm_menmonic) {push(opc, 0, 0, asm_menmonic);}
    void push1(int opc, int32_t data, const std::string& asm_menmonic) {push(opc, 1, data, asm_menmonic);}
    void push2(int opc, int32_t data, const std::string& asm_menmonic) {push(opc, 2, data, asm_menmonic);}
    void push4(int opc, int32_t data, const std::string& asm_menmonic) {push(opc, 4, data, asm_menmonic);}

    const std::vector& get_image() const {return code_image;}
    const std::vector& finish()
    {
        if (code_image.empty() || *code_image.rbegin() != OP_Stop) code_image.push_back(OP_Stop);
        return code_image;
    }
};

 

Методы:

• push - Добавляет опкод и опциональные байты данных в бинарный образ. Так же выводит листинг (если есть файл для листинга)
• push* - Специализация для вывода с конкретной длинной данных. Используется для удобства, а так же что бы предотвратить ошибки, когда програмист меняет длинну выводимых данных не меняя при этом опкод. Интерпретатор не сможет такое декодировать
• get_image - Возвращает построенный байт код
• finish - Финализирует процесс компиляции (добавляя OP_Stop в конец, если его ещё не было) и так же возвращает образ кода

 

[Михась 2]

Практический работоспособный вариант видел для STM32F103 на осциллографе DS203 - Pawn. Пробовал писать приложения - жрать можно.

Но там не сырец загружается а байткод.

 

 

[xvr 12]

И наконец класс парсера.

Spoiler

class Parser {
    CodeGenerator code;
    const char* input;

    int yyparse();
    int yylex(void*);

    void add_if(Node* if_expression, NodeVar* then_expression);
    Node* new_unary(Opcode opcode, Node* left);
    Node* new_binary(Opcode opcode, Node* left, Node* right);

public:
    Parser(FILE* list_file) : code(list_file) {}

    void compile_line(const char* line) {input = line; yyparse();}
    const std::vector<uint8_t>& finish() {return code.finish();}
};

 

Переменная input хранит необработанную часть входной строки (для лексера). Инициализируется она из метода compile_line, который вызывается на каждую строку входного скрипта

Методы add_if, new_unary и new_binary вызываются из парсера, сгенерированого bison'ом (так же оттуда вызываются конструкторы NodeVar и NodeConst)

Методы:

• add_if - генерирует код для оператора if ... then. Для него не сделано отдельного узла в дереве выражений (потомка Node), так как он является последней стадией в разборе и ни с кем больше не сочетается
• new_unary и new_binary - создают новый узел. Внутри выполняют некоторые оптимизации (вычисление констант, выкидывание унарного '-')

[xvr 12]

bison'овский файл с грамматикой

Spoiler

%token tIF  "if"
%token tTHEN "then"

%token sEQ "=="
%token sNE "!="
%token sGE ">="
%token sLE "<="
%token sASSIGN_ADD "+="
%token sASSIGN_SUB "-="
%token sAND "&&"
%token sOR "||"

%token vID

%union {
    int32_t i_const;
    Node* any_node;
    VarNode* var_node;
}

%type <i_const> vID
%type <any_node> expression
%type <var_node> assign assign_list

%left UNARY
%left '*' '/' '%'
%left '+' '-'
%left sEQ sNE '<' sLE '>' sGE
%left sAND
%left sOR

%pure-parser

%%

prog:   | "if" expression "then" assign_list {add_if($2, $4);} ;

expression: vID                         {$$ = new NodeVar(OP_ReadVar, $1);}
        | '(' expression ')'            {$$ = $2;}
        | '-' expression %prec UNARY    {$$ = new_unary(OP_Neg, $2);}
        | expression '+' expression     { $$ = new_binary(OP_Add, $1, $3);}
        | expression '-' expression     { $$ = new_binary(OP_Sub, $1, $3);}
        | expression '*' expression     { $$ = new_binary(OP_Mul, $1, $3);}
        | expression '/' expression     { $$ = new_binary(OP_Div, $1, $3);}
        | expression '%' expression     { $$ = new_binary(OP_Mod, $1, $3);}
        | expression "==" expression    { $$ = new_binary(OP_EQ, $1, $3);}
        | expression "!=" expression    { $$ = new_binary(OP_NE, $1, $3);}
        | expression '>' expression     { $$ = new_binary(OP_GT, $1, $3);}
        | expression ">=" expression    { $$ = new_binary(OP_GE, $1, $3);}
        | expression '<' expression     { $$ = new_binary(OP_GT, $3, $1);}
        | expression "<=" expression    { $$ = new_binary(OP_GE, $3, $1);}
        | expression "&&" expression    { $$ = new_binary(OP_And, $1, $3);}
        | expression "||" expression    { $$ = new_binary(OP_Or, $1, $3);}
        ;

assign_list: assign
        | assign_list ';' assign { $$ = $1->join($3);}
        ;

assign:   vID '=' expression  { $$ = new NodeVar(OP_SetVar, $1, $3); }
        | vID "+=" expression { $$ = new NodeVar(OP_AddVar, $1, $3); }
        | vID "-=" expression { $$ = new NodeVar(OP_AddVar, $1, new_unary(OP_Neg, $3)); }
        ;

 

 

[jenya7 0]

18 hours ago, xvr said:

Класс CodeGenerator содержит массив с бинарным образом (code_image) и опциональный файл (lst_file) куда выводится листинг в процессе генерации кода.

 

Классы Node, CodeGenerator - это на стороне PC? А на С-шарп я могу написать?

Изменено 21 мая, 2019 пользователем jenya7

[_pv 64]

On 5/15/2019 at 6:09 PM, xvr said:

On 5/15/2019 at 5:13 PM, jenya7 said:

кстати интересно и очень поучительно.  но нужно переделывать под мои нужды. и я даже не представляю как.

C-interpreter под ваши нужды явный overkill (кстати как и pawn)

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

и четверть из этих 500 строк, если не треть, пожалуй можно выкинуть, так как эта хрень вообще сама себя собрать может, что ТСу не нужно совсем. Так же как и енумы, функции, указатели, комментарии, циклы и преинкременты/декременты.

и этот "компилятор" вполне можно и в МК засунуть, и скармливать ему исходники, без промежуточнонго шага компиляции на ПК.

без, о ужас!, бизона и даже без до-диеза.

[xvr 12]

4 hours ago, jenya7 said:

Классы Node, CodeGenerator - это на стороне PC?

Да

4 hours ago, jenya7 said:

А на С-шарп я могу написать?

Наверное да, но я не уверен что bison удастся подружить с C# Придётся искать другой генератор, или скрещивать C# и managed C++

 

1 hour ago, _pv said:

Там всего 500 строк кода на С и это не интерпретатор, а вполне себе компилятор в промежуточный байткод,

Скачал pawn, залез в диру compiler (это оно, я не ошибся?), запустил wc *.c - 22 тысячи строк. Кажется это немного больше, чем "500 строк кода на С" (Это я ещё *.h не считал)

 

[_pv 64]

5 minutes ago, xvr said:

Скачал pawn, залез в диру compiler (это оно, я не ошибся), запустил wc *.c - 22 тысячи строк. Кажется это немного больше, чем "500 строк кода на С" (Это я ещё *.h не считал)

я про https://github.com/rswier/c4

 

[xvr 12]

37 minutes ago, _pv said:

я про https://github.com/rswier/c4

Вы внутрь этого смотрели? Это только для сильных духом (И размер в 500 строк ужаса содержимого не компенсируют)