Синтаксический анализ с использованием конечных автоматов и регулярных выражений

@ilna · Регистрация: 13.01.2019

Author24 — интернет-сервис помощи студентам

Добрый день, господа!

Есть такое задание:
На вход программы подается единственная строка символов. Данная строка задает присваивание переменной значения арифметического выражения в виде
ПЕРЕМЕННАЯ = ВЫРАЖЕНИЕ.
Выражение может включать:
• знаки сложения и умножения («+» и «*»);
• круглые скобки («(» и «)»);
• константы (например, 5; 3.8; 1e+18, 8.41E-10);
• имена переменных (последовательности букв и цифр, начинающиеся с буквы).
Программа должна с помощью ДКА или ДМПА построить дерево, соответствующее заданному во входном файле выражению, и выдать для данного выражения:
1) таблицу имен;
2) неоптимизированный код;
3) оптимизированный код.

Есть такой код:

Кликните здесь для просмотра всего текста

C++ (Qt)

#include <algorithm>
#include <fstream>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
 
using namespace std;
 
struct Node
{
    Node* left, *right;
    string op;
    string cn;
 
    Node(string op = "", Node* l = 0, Node* r = 0)
    {
        this->left = l;
        this->right = r;
        this->op = op;
    }
 
    void addLeft(Node* l)
    {
        this->left = l;
    }
 
    void addRight(Node* r)
    {
        this->right = r;
    }
 
    void addOp(string o)
    {
        this->op = o;
    }
};
 
vector<string> split(string s, string delimiter)
{
    size_t pos_start = 0, pos_end, delim_len = delimiter.length();
    string token;
    vector<string> res;
 
    while ((pos_end = s.find(delimiter, pos_start)) != string::npos)
    {
        token = s.substr(pos_start, pos_end - pos_start);
        pos_start = pos_end + delim_len;
        res.push_back(token);
    }
 
    res.push_back(s.substr(pos_start));
    return res;
}
 
void loadExpression(string fname, string& result)
{
    std::ifstream t(fname);
    std::stringstream buffer;
    buffer << t.rdbuf();
    result = buffer.str();
}
 
int FSM(int state, string s, vector<char> memory, string id, vector<string>& v)
{
    if (s == "" && (state == 3 || state == 4 || state == 7 || state == 8 || state == 9))
    {
        if ((memory.size() == 1 && memory[0] == '.') || (memory.size() == 0))
        {
            if (id != "")
                v.push_back(id);
            return 1;
        }
        else
            return -1;
    }
    else if (s == "")
        return -1;
 
    switch (state)
    {
        case 0:
            if (isalpha(s[0]))
            {
                id += s[0];
                return FSM(1, s.substr(1), memory, id, v);
            }
            else
                return -1;
        case 1:
        {
            if (isalnum(s[0]))
            {
                id += s[0];
                return FSM(1, s.substr(1), memory, id, v);
            }
            else if (s[0] == '=')
            {
                if (id != "")
                {
                    v.push_back(id);
                }
                id = "";
                std::remove(memory.begin(), memory.end(), '.');
                return FSM(2, s.substr(1), memory, id, v);
            }
            else
                return -1; 
        }
        case 2:
        {
            if (id != "")
                v.push_back(id);
            id = "";
            if (isdigit(s[0]))
            {
                id += s[0];
                return FSM(3, s.substr(1), memory, id, v);
            }
            else if (isalpha(s[0]))
            {
                id += s[0];
                return FSM(4, s.substr(1), memory, id, v);
            }
            else if (s[0] == '(')
            {
                memory.push_back('(');
                return FSM(2, s.substr(1), memory, id, v);
            }
            else
                return -1;
        }
        case 3:
            if (s[0] == '+' || s[0] == '*')
            {
                if (id != "")
                {
                    v.push_back(id);
                }
                id = "";
                std::remove(memory.begin(), memory.end(), '.');
                return FSM(2, s.substr(1), memory, id, v);
            }
            else if (isdigit(s[0]))
            {
                id += s[0];
                return FSM(3, s.substr(1), memory, id, v);
            }
            else if (s[0] == '.')
            {
                if (std::find(memory.begin(), memory.end(), '.') != memory.end())
                    return -1;
                else
                {
                    id += s[0];
                    memory.push_back('.');
                    return FSM(5, s.substr(1), memory, id, v);
                }
            }
            else if (s[0] == ')')
            {
                int i = memory.size() - 1;
                for (i; i > -1; i--)
                    if (memory[i] == '(')
                        break;
                if (i > -1)
                    memory.erase(memory.begin() + i);
                else
                    return -1;
                return FSM(8, s.substr(1), memory, id, v);
            }
            else if (s[0] == 'E' || s[0] == 'e')
                return FSM(6, s.substr(1), memory, id, v);
            else
                return -1;
        case 4:
            if (isalnum(s[0]))
            {
                id += s[0];
                return FSM(4, s.substr(1), memory, id, v);
            }
            else if (s[0] == '+' || s[0] == '*')
            {
                if (id != "")
                {
                    v.push_back(id);
                }
                id = "";
                std::remove(memory.begin(), memory.end(), '.');
                return FSM(2, s.substr(1), memory, id, v);
            }
            else if (s[0] == ')')
            {
                int i = memory.size() - 1;
                for (i; i > -1; i--)
                    if (memory[i] == '(')
                        break;
                if (i > -1)
                    memory.erase(memory.begin() + i);
                else
                    return -1;
                return FSM(8, s.substr(1), memory, id, v);
            }
            else
                return -1;
        case 5:
            if (isdigit(s[0]))
            {
                id += s[0];
                return FSM(9, s.substr(1), memory, id, v);
            }
            else
                return -1;
        case 6:
            if (s[0] == '+' || s[0] == '-')
            {
                id += s[0];
                return FSM(7, s.substr(1), memory, id, v);
            }
            else
                return -1;
        case 7:
            if (isdigit(s[0]))
            {
                id += s[0];
                return FSM(7, s.substr(1), memory, id, v);
            }
            else if (s[0] == ')')
            {
                int i = memory.size() - 1;
                for (i; i > -1; i--)
                    if (memory[i] == '(')
                        break;
                if (i > -1)
                    memory.erase(memory.begin() + i);
                else
                    return -1;
                return FSM(8, s.substr(1), memory, id, v);
            }
            else if (s[0] == '+' || s[0] == '*')
            {
                int k = 0;
                if (id != "")
                {
                    v.push_back(id);
                }
                id = "";
                std::remove(memory.begin(), memory.end(), '.');
                return FSM(2, s.substr(1), memory, id, v);
            }
            else
                return -1;
        case 8:
            if (s[0] == '+' || s[0] == '*')
            {
                if (id != "")
                {
                    v.push_back(id);
                }
                id = "";
            }
            else if (s[0] == ')')
            {
                int i = memory.size() - 1;
                for (i; i > -1; i--)
                    if (memory[i] == '(')
                        break;
                if (i > -1)
                    memory.erase(memory.begin() + i);
                else
                    return -1;
                return FSM(8, s.substr(1), memory, id, v);
            }
            else
                return -1;
        case 9:
            if (s[0] == '+' || s[0] == '*')
            {
                if (id != "")
                {
                    v.push_back(id);
                }
                id = "";
                std::remove(memory.begin(), memory.end(), '.');
                return FSM(2, s.substr(1), memory, id, v);
            }
            else if (s[0] == 'E' || s[0] == 'e')
            {
                id += s[0];
                return FSM(6, s.substr(1), memory, id, v);
            }
            else if (isdigit(s[0]))
            {
                id += s[0];
                return FSM(9, s.substr(1), memory, id, v);
            }
            else if (s[0] == ')')
            {
                int i = memory.size() - 1;
                for (i; i > -1; i--)
                    if (memory[i] == '(')
                        break;
                if (i > -1)
                    memory.erase(memory.begin() + i);
                else
                    return -1;
                return FSM(8, s.substr(1), memory, id, v);
            }
            else
                return -1;
        default:
            return -1;
    }
}
 
int height(Node* n)
{
    if (!n)
        return 0;
    else
        return 1 + max(height(n->left), height(n->right));
}
 
void code(string s, Node* n, vector<string> table)
{
    int parent = 0;
    int i = 0;
    while (i < s.size())
    {
        if ((parent == 0) && (s[i] == '=' || s[i] == '*' || s[i] == '+'))
        {
            n->op = s[i];
            n->left = new Node();
            n->right = new Node();
            code(s.substr(0, i), n->left, table);
            code(s.substr(i + 1), n->right, table);
            if (s[i] == '=')
                n->cn = "LOAD " + n->right->cn + "\n" + "STORE " + n->left->cn;
            else if (s[i] == '+')
            {
                n->cn = n->right->cn + "\n" + "STORE $" + to_string(height(n) - 1)
                    + "\n" + "LOAD " + n->left->cn + "\n" + "ADD $" 
                    + to_string(height(n) - 1);
            }
            else
            {
                n->cn = n->right->cn + "\n" + "STORE $" + to_string(height(n) - 1)
                    + "\n" + "LOAD " + n->left->cn + "\n" + "MPY $"
                    + to_string(height(n) - 1);
            }
            break;
        }
        else if (s[i] == '(')
            parent++;
        else if(s[i] == ')')
            parent--;
        i++;
    }
 
    if (i == s.size() && s[0] == '(' && s[s.size() - 1] == ')')
    {
        s.erase(0, 1);
        s.pop_back();
        code(s, n, table);
    }
    else if (i == s.size())
    {
        n->op = s;
        n->cn = s;
    }
}
 
vector<string> optimize(Node* n)
{
    string cn = n->cn;
    auto v = split(cn, "\n");
    int i = 0;
    while (i + 1 < v.size())
    {
        if (v[i].substr(0, 4) == "LOAD" && v[i + 1].substr(0, 3) == "ADD")
            if (count(v.begin(), v.end(), v[i + 1]) == 1)
            {
                string t = "LOAD " + v[i + 1].substr(4);
                v[i + 1] = "ADD " + v[i].substr(5);
                v[i] = t;
            }
        if (v[i].substr(0, 4) == "LOAD" && v[i + 1].substr(0, 3) == "MPY")
            if (count(v.begin(), v.end(), v[i + 1]) == 1)
            {
                string t = "LOAD " + v[i + 1].substr(4);
                v[i + 1] = "MPY " + v[i].substr(5);
                v[i] = t;
            }
        i++;
    }
 
    i = 0;
    while (i + 1 < v.size())
    {
        if (v[i].substr(0, 5) == "STORE" && v[i + 1].substr(0, 4) == "LOAD")
            if (v[i].substr(6) == v[i + 1].substr(5))
            {
                v.erase(v.begin() + i);
                v.erase(v.begin() + i);
            }
        i++;
    }
 
    i = 0;
    while (i + 1 < v.size())
    {
        if (v[i].substr(0, 4) == "LOAD" && v[i + 1].substr(0, 5) == "STORE")
        {
            bool b = false;
            for (int k = i + 2; k < v.size(); k++)
            {
                if (v[k].substr(0, 4) == "LOAD")
                {
                    b = true;
                    break;
                }
            }
 
            if (b)
            {
                if (count(v.begin(), v.end(), v[i + 1]) == 1)
                {
                    string a = v[i].substr(5);
                    string b = v[i + 1].substr(6);
                    for (int k = i + 2; k < v.size(); k++)
                    {
                        if (v[k].substr(0, 4) == "LOAD" && v[k].substr(5) == b)
                            v[k] = "LOAD " + a;
                        else if (v[k].substr(0, 3) == "ADD" && v[k].substr(4) == b)
                            v[k] = "ADD " + a;
                        else if (v[k].substr(0, 3) == "MPY" && v[k].substr(4) == b)
                            v[k] = "MPY " + a;
                    }
                    v.erase(v.begin() + i);
                    v.erase(v.begin() + i);
                }
            }
        }
        i++;
    }
 
    return v;
}
 
int main()
{
    setlocale(LC_CTYPE, "Russian");
 
    string expr;
    loadExpression("input.txt", expr);
 
    ofstream out("output.txt");
 
    vector<string> table;
    FSM(0, expr, std::vector<char>(), "", table);
 
    out << "Таблица имен:" << std::endl;
    for (auto name : table)
        if (isdigit(name[0]))
        {
            if (find(name.begin(), name.end(), '.') == name.end())
                if (find(name.begin(), name.end(), 'E') == name.end())
                    if (find(name.begin(), name.end(), 'e') == name.end())
                        out << name << " - " << "Целочисленная константа" << endl;
                    else
                        out << name << " - " << "Константа с плавающей точкой" << endl;
                else
                    out << name << " - " << "Константа с плавающей точкой" << endl;
            else
                out << name << " - " << "Константа с плавающей точкой" << endl;
        }
        else
            out << name << " - " << "Переменная" << endl;
 
    Node* tree = new Node();
    code(expr, tree, table);
    out << "Неоптимизированный код:" << endl << tree->cn << endl;
    
    auto opt = optimize(tree);
    
    out << "Оптимизированный код:" << endl;
    for (auto c : opt)
        out << c << endl;
}

И есть такая рецензия:
...в программе явной реализации ДКА или ДМПА нет.

Может кто-то подсказать, где ошибка?

@3D Homer · 09.04.2021, 22:15

Думаю, вопросы о реализации лексера и парсера на C++ нужно задавать в форуме по C++. В этом форуме вы можете попробовать обсудить любые из десятков вопросов по теории, которые возникают при написании такой программы. Для каждого такого вопроса нужна отдельная тема.

Не по теме:

И вообще, анализ программы из 500 строк без единого комментария не тянет на бесплатный вопрос.

@assemberist · 10.04.2021, 12:19

Сообщение от ilna

...в программе явной реализации ДКА или ДМПА нет.

Я не изучал конечные автоматы, но насколько могу судить, основная претензия к тому, что анализ реализован через рекурсию.
Преподаватель же скорее всего ожидает увидеть что-то вроде следующей конструкции.

C++

enum state{ // мое предложение использовать энумы вместо числовых значений, но если нужно,
    STEP1 = 0, // можно каждому из них таких символов присвоить и число
    STEP2,
    ...
    STEPn
};
 
state FSM(state oldState, char sym, stack& Stack){ // получаем символ и на основе старого состояния
    ...
    return newState; // получаем новое
}
 
int main(){
    stack Stack; // стэк
    state State = ...; // Выставляем начальный стейт
    
    while(){ // пока не закончились символы
        char sym = ... // получаем символ
        State = FSM(State, sym, Stack); // получаем следующее состояние
    }
}

К тому же рекурсия отъедает стэк (потому что приходится хранить параметры для каждого ее витка) и при парсинге очень сложных выражений ему может "сорвать крышу".

Добавлено через 10 минут
Ну и я бы в силу привычки разделил программу на 3 файла:
1) Основной файл в котором мы исполняем только main().
2) Заголовочник со всеми определениями структур и объявлениями доступных для main функций.
3) Файл с реализацией функций.

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1151 Регистрация: 01.09.2014 Сообщений: 9,660
	09.04.2021, 22:15	2
	Думаю, вопросы о реализации лексера и парсера на C++ нужно задавать в форуме по C++. В этом форуме вы можете попробовать обсудить любые из десятков вопросов по теории, которые возникают при написании такой программы. Для каждого такого вопроса нужна отдельная тема. Не по теме: И вообще, анализ программы из 500 строк без единого комментария не тянет на бесплатный вопрос. 0

	10.04.2021, 12:19