Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
 Парсер математических выражений  [new]
jenya7
Member

Откуда:
Сообщений: 1159
Скажем есть выражение
автор
IF DIR0==2 AND POS0>POS1 AND POS0-POS1>20 THEN VAR0-=100 AND VAR1+=100;

Я разбиваю на лемксемы.
автор
Name: IF Type: If
Name: DIR0 Type: Alphanumeric Var Type: 3 Num: 0
Name: == Type: Compare
Name: 2 Type: Number
Name: AND Type: Logic
Name: POS0 Type: Alphanumeric Var Type: 4 Num: 0
Name: > Type: Compare
Name: POS1 Type: Alphanumeric Var Type: 4 Num: 1
Name: AND Type: Logic
Name: POS0 Type: Alphanumeric Var Type: 4 Num: 0
Name: - Type: Operator
Name: POS1 Type: Alphanumeric Var Type: 4 Num: 1
Name: > Type: Compare
Name: 20 Type: Number
Name: THEN Type: Then
Name: VAR0 Type: Alphanumeric Var Type: 12 Num: 0
Name: -= Type: Operator
Name: 100 Type: Number
Name: ; Type: End

И потом работаю с массивом лексем.
for (i = 0; i < expr_count; i++)
{
    switch (script_state)
    {
        case ST_IF:
            script_state = ST_IN_EXPR;
        break;
        case ST_IN_EXPR:
            switch (expr[i].type)
            {
                case EXPR_TYPE_THEN:
                    if (result == true) //if (true) – goto then
                        script_state = ST_OUT_EXPR;
                    else  //goto next if
                       script_state = ST_IF; 
                break;
                case EXPR_TYPE_OPERATOR: operator = expr[i].val;  break;
                case EXPR_TYPE_COMPARE:   compare = expr[i].val;  break;
                case EXPR_TYPE_LOGIC:        logic = expr[i].val;        break;
                case EXPR_TYPE_END:           script_state = ST_IF;   break;

                default:  //variable or number

                    variable = GetVar(expr[i].type, expr[i].num);

                    if (compare == 0)
                    {
                        switch (operator)
                        {
                           case 0: g_val = variable; break; //first variable?
                           case OP_PLS:    g_val = g_val + variable; break;
                           case OP_MIN:    g_val = g_val - variable;  break;
                           case OP_MUL:   g_val = g_val * variable;  break;
                           case OP_DIV:    g_val = g_val / variable;  break;
                           case OP_BAND: g_val = g_val & variable; break;
                           case OP_BOR:   g_val = g_val | variable;  break;
                        }
                        operator = 0;
                     }
                     else
                     {
                        switch (compare)
                        {
                            case 0: break;
                            default:
                                result = ProcessCompare(g_val, variable, compare);
                            break;
                        }
                        compare = 0;
                     }

                     if (logic == NONE || logic == OP_LOR)
                         result |= result;
                     else if (logic == Defines.OP_LAND)
                         result &= result;

                     break;
            break;
         
         }

        break;       
    }
}


При простом выражении, cкажем POS0>POS1 AND POS0-POS1>20, все работает хорошо.
Но вот такое выражение VAR0=POS0+POS1 уже не работает. Правая часть не присваевается аккумулятивно.
Как мне улучшить алгоритм?
23 май 19, 15:48    [21892178]     Ответить | Цитировать Сообщить модератору
 Re: Парсер математических выражений  [new]
Изопропил
Member

Откуда:
Сообщений: 31190
jenya7
Как мне улучшить алгоритм?

Написать заново
Начать с описания грамматики языка
24 май 19, 09:51    [21892757]     Ответить | Цитировать Сообщить модератору
 Re: Парсер математических выражений  [new]
jenya7
Member

Откуда:
Сообщений: 1159
Изопропил
jenya7
Как мне улучшить алгоритм?

Написать заново
Начать с описания грамматики языка

вот поэтому обратился. нужен хороший алгоритм разбирать лексемы.
24 май 19, 10:09    [21892783]     Ответить | Цитировать Сообщить модератору
 Re: Парсер математических выражений  [new]
Изопропил
Member

Откуда:
Сообщений: 31190
jenya7,

Рекурсивный спуск
24 май 19, 10:23    [21892808]     Ответить | Цитировать Сообщить модератору
 Re: Парсер математических выражений  [new]
ЕвгенийВ
Member

Откуда: Москва
Сообщений: 4779
jenya7,
Посмотри в сторону ANTLR.
27 май 19, 10:29    [21894483]     Ответить | Цитировать Сообщить модератору
 Re: Парсер математических выражений  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
jenya7
Скажем есть выражение
IF DIR0==2 AND POS0>POS1 AND POS0-POS1>20 THEN VAR0-=100 AND VAR1+=100;

При простом выражении, cкажем POS0>POS1 AND POS0-POS1>20, все работает хорошо.
Но вот такое выражение VAR0=POS0+POS1 уже не работает. Правая часть не присваевается аккумулятивно.
Как мне улучшить алгоритм?

Смотри. Математическое выражение это
1+2*3

В студенческих лабах обычно ограничиваются решением этой задачки черезе ПОЛИЗ.
Это просто трансфомация инфиксной формы в стековую (кажется постфикс).
И лаба сдаётся.

То что ты написал - выходит далеко за рамки просто выражения. Это почти язык где есть conditions.
Языки пишутся на генераторах парсеров (lex/yacc/bison/antlr/javacc). Это тема нудная и сложная.
Вряд-ли у тебя хватит квалификации быстро это сделать (если это не курсовой проект конечно).

Поэтому тебе надо срочно идти к преподу и спрашивать как глубоко тебе надо это делать.

Если все-все выражения который к тебе придут будут иметь вид.
IF condition [AND condition] THEN operator [AND operator];

Тогда твою задачу наверное можно решить на регулярках или на тех псевдо-парсерах как ты делаешь.
Но надо точно знать какие еще варианты придут на вход. Это сильно повлияет на твою лабу или курсовую.

Комплексность решения сильно зависит от этих кейсов.
27 май 19, 10:40    [21894493]     Ответить | Цитировать Сообщить модератору
 Re: Парсер математических выражений  [new]
Малыхин Сергей
Member

Откуда: г. Курск
Сообщений: 719
Лексемы в массив это совсем не вариант.

Выражение имеет иерархическую суть.Чета раньше чета позже чета в скобках чета нет. Следовательно бинарные деревья тебе в руки
к примеру https://www.google.com/search?q=syntax tree&oq=syntax tree&aqs=chrome..69i57j0l5.1095j0j7&sourceid=chrome&ie=UTF-8

А проще взять что нибудь готовое например http://esprima.org/demo/parse.html#
27 май 19, 11:41    [21894563]     Ответить | Цитировать Сообщить модератору
 Re: Парсер математических выражений  [new]
jenya7
Member

Откуда:
Сообщений: 1159
Малыхин Сергей
Лексемы в массив это совсем не вариант.

Выражение имеет иерархическую суть.Чета раньше чета позже чета в скобках чета нет. Следовательно бинарные деревья тебе в руки
к примеру https://www.google.com/search?q=syntax tree&oq=syntax tree&aqs=chrome..69i57j0l5.1095j0j7&sourceid=chrome&ie=UTF-8

А проще взять что нибудь готовое например http://esprima.org/demo/parse.html#

ну почему не вариант?
+

public void Run(Expr[] expr, int expr_count, int idx, int trig, RichTextBox rtb)
        {
            int i = idx;
            int variable;

            switch (script_state)
            {
                case ST_IDLE:
                case ST_IF:
                    if (expr[i].type == Defines.EXPR_TYPE_IF)
                    {
                        if (rtb != null)
                            rtb.AppendText("IF ");

                        script_params.result = false;
                        script_params.oper = 0;
                        script_params.compare = 0;

                        var_state = VAR_ST_LGROUP;
                        script_state = ST_IN_EXPR;
                    }
                   
                    if (expr[i].type == Defines.EXPR_TYPE_THEN)
                    {
                        if (rtb != null)
                            rtb.AppendText(" THEN ");

                        script_state = ST_IN_EXPR;
                    }
                    break;

                case ST_IN_EXPR:
                    switch (expr[i].type)
                    {
                        case Defines.EXPR_TYPE_THEN:
                            if (script_params.result == true)
                            {
                                if (rtb != null)
                                    rtb.AppendText(" THEN ");

                                var_state = VAR_ST_LGROUP;
                                script_params.oper = 0;
                            }
                            else
                            {
                                if (rtb != null)
                                    rtb.AppendText(" FALSE" + Environment.NewLine);

                                script_state = ST_IF;
                            }
                            break;

                        case Defines.EXPR_TYPE_STGR:
                            if (rtb != null)
                                rtb.AppendText("(");
                            script_params.group_oper = script_params.oper;
                            script_params.oper = 0;
                            var_state = VAR_ST_RGROUP;
                            break;

                        case Defines.EXPR_TYPE_ENDGR:
                            if (rtb != null)
                                rtb.AppendText(")");
                            var_state = VAR_ST_LGROUP;
                            break;

                        case Defines.EXPR_TYPE_END:
                            rtb.AppendText(";" + Environment.NewLine);
                            script_state = ST_IF;
                            break;

                        case Defines.EXPR_TYPE_OPER:  //get operator
                            script_params.oper = expr[i].val;

                            if (rtb != null)
                                rtb.AppendText(parser.OperatorToStr(script_params.oper));
                            break;

                        case Defines.EXPR_TYPE_COMP:  //get compare
                            script_params.compare = expr[i].val;

                            if (rtb != null)
                                rtb.AppendText(parser.CompareToStr(script_params.compare));

                            break;

                        case Defines.EXPR_TYPE_LOG:  //get logic
                            script_params.logic = expr[i].val;

                            if (rtb != null)
                                rtb.AppendText(" " + parser.LogicToStr(script_params.logic) + " ");
                            break;

                        default:  //variable or number

                            if (rtb != null)
                            {
                                if (expr[i].type == Defines.EXPR_TYPE_NUM)
                                    rtb.AppendText(expr[i].val.ToString());
                                else
                                    rtb.AppendText(parser.VarToStr(expr[i].type, expr[i].num));
                            }

                            if (expr[i].type == Defines.EXPR_TYPE_NUM)
                                variable = expr[i].val;
                            else
                                variable = GetVar(expr[i].type, expr[i].num);

                            ProcessVariable(expr[i].type, expr[i].num, variable, expr[i + 1].type);

                            break;
                    }
                    break;
            }
        }


Вполне себе работает. Одна проблема - много места занимает. Даже если хранить в текстовом варианте и парсить при поднятии микроконтролера. Оригинально скрипт должен бежать на микроконтролере.
29 май 19, 09:22    [21896321]     Ответить | Цитировать Сообщить модератору
Все форумы / Программирование Ответить