Реализовать парсер xml кода, используя ассоциативный массив

@MrMax836 · Регистрация: 30.07.2012

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

Нужно создать парсер.
Из потока берётся лексема и происходит поиск 'njq ktrctvs в ассоциативном массиве. Если лексема найдена(терминальный символ), тогда в очередь помещается код токена(нужно для дальнейшей проверки синтаксиса).
Не получается реализовать.
Помогите, пожалуйста.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <fstream>
#include <map>
#include <string>
#include <queue>
 
std::map < std::string, int> states = { { "div", 1 },
{ "class", 2 },
{ "hentry", 3 },
{ "strong", 4 },
{ ",", 5},
{ ".", 6},
{ ";", 7},
{ "(", 8},
{ ")", 9},
{ "{", 10},
{ "}", 11},
{ "=", 12},
{ "-", 13},
{ " ", 14},
{ "«", 18 },
{ "»", 19 },
{ "", 20},
};
 
 
 
 
int get_lexem(FILE* stream, char buffer[], std::map <std::string, int> states, std::queue<int>syntax)
{
    char ch = getc(stream);
    buffer[100];
 
    size_t i; 
    
 
 
    /* пропускаем все пробелы, табуляции и символы новой строки */
    while (isspace(ch))
        {
 
            ch = getc(stream);
            return ch;
        }
 
    /* конец файла */
    if (ch == EOF)
        return 404;
 
 
    /* идентификатор или ключевое слово */
    if (isalpha(ch))
        {
            i = 0;
 
            do
            {
                buffer[i++] = ch;
            } 
            while ((ch = getc(stream)) != EOF && (isalpha(ch)));
 
            std::string str = std::string(buffer, sizeof(buffer));
            int token = states.find(str)->second;
            syntax.push(token);
            return 0;
        }
    return 0;
}
 
 
int main(int argc, char* argv[])
{
 
std::ifstream stream("myfile.txt"); // открыли файл для чтения
 
std::queue<int>syntax; // очередь
 
int get_lexem(FILE* stream, char buffer, std::map <std::string, int> states, std::queue<int>syntax);
 
return 0;
}

MrGluck · 15.12.2016, 15:25

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

int token = states.find(str)->second;

Надо бы проверять, что токен вообще найден.

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

C++
1
std::map <std::string, int> states

Локально будет видно только переданный states. Даже, если вы потом глобальную переменную передаёте как аргумент, всё равно не хорошо, надо бы определиться: либо глобальная переменная, либо передача параметра. Лучше второй вариант.

Добавлено через 1 минуту
Почему бы просто не проходиться по файлу через std::istream_iterator<char> ? Зачем нужен сишный FILE*?

Добавлено через 21 секунду
Какая-то каша у вас в коде. Топора не хватает.

@MrMax836 · 15.12.2016, 15:37 **[ТС]**

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

надо бы определиться: либо глобальная переменная, либо передача параметра. Лучше второй вариант.

Конечно, параметром бы лучше передать... Только я не совсем понял, куда и как.

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

Почему бы просто не проходиться по файлу через std::istream_iterator<char> ? Зачем нужен сишный FILE*?

Это единственный вариант, который я нашёл(плохо искал, видимо)

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

Какая-то каша у вас в коде.

Приходится это кушать, к сожалению...

У меня стоит задача написать лексический анализатор без множественных IF-else и switch'ей.
Но кодить совершенно не умею(хоть и основной принцип парсера понял, надеюсь).

MrGluck · 15.12.2016, 15:47

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <fstream>
#include <map>
#include <string>
 
int GetToken(const std::string &str)
{
    static const std::map < std::string, int> states = {
        { "div", 1 },
        { "class", 2 },
        { "hentry", 3 },
        { "strong", 4 },
        { ",", 5},
        { ".", 6},
        { ";", 7},
        { "(", 8},
        { ")", 9},
        { "{", 10},
        { "}", 11},
        { "=", 12},
        { "-", 13},
        { " ", 14},
        { "«", 18 },
        { "»", 19 },
        { "", 20},
    };
    const auto it = states.find(str);
    return it != states.end() ? it->second : -1;
}
 
int main()
{
    std::ifstream ifs("input.txt");
    if (!ifs)
        return 1;
    for (std::string str; ifs >> str; std::cout << GetToken(str) << " ");
}

Добавлено через 1 минуту
Можно в map хранить набор соответствий строка - обработчик.

@MrMax836 · 15.12.2016, 15:59 **[ТС]**

Это так просто...
Спасибо большое)
Учиться и учиться!

MrGluck · 15.12.2016, 16:17

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <iterator>
#include <fstream>
#include <map>
#include <memory>
#include <string>
 
struct IMaker
{
    virtual ~IMaker() = default;
    virtual void parse() const = 0;
};
 
struct SimpleMaker : IMaker
{
    void parse() const override
    {
        std::cout << "Some work\n";
    }
};
 
struct DivMaker : IMaker
{
    void parse() const override
    {
        std::cout << "Div!\n";
    }
};
 
void Process(const std::string &str)
{
    static std::pair < const std::string, std::unique_ptr<IMaker>> init[] =
    {
        { "div", std::make_unique<DivMaker>() },
        { "class", std::make_unique<SimpleMaker>() },
        { "hentry", std::make_unique<SimpleMaker>() },
        { "strong", std::make_unique<SimpleMaker>() },
        { ",", std::make_unique<SimpleMaker>()},
        { ".", std::make_unique<SimpleMaker>()},
        { ";", std::make_unique<SimpleMaker>()},
        { "(", std::make_unique<SimpleMaker>()},
        { ")", std::make_unique<SimpleMaker>()},
        { "{", std::make_unique<SimpleMaker>()},
        { "}", std::make_unique<SimpleMaker>()},
        { "=", std::make_unique<SimpleMaker>()},
        { "-", std::make_unique<SimpleMaker>()},
        { " ", std::make_unique<SimpleMaker>()},
        { "«", std::make_unique<SimpleMaker>()},
        { "»", std::make_unique<SimpleMaker>()},
        { "",  std::make_unique<SimpleMaker>()},
    };
    static const std::map < std::string, std::unique_ptr<IMaker>> states {
        std::make_move_iterator(std::begin(init)), std::make_move_iterator(std::end(init)) };
 
    const auto it = states.find(str);
    if (it != states.end())
        it->second->parse();
}
 
int main()
{
    std::ifstream ifs("input.txt");
    if (!ifs)
        return 1;
    for (std::string str; ifs >> str; Process(str));
}

Добавлено через 17 минут

Не по теме:

Меня, кстати, всегда вымораживало отсутствие возможности нормально создать константный контейнер с unique_ptr внутри.

@MrMax836 · 15.12.2016, 18:56 **[ТС]**

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

for (std::string str; ifs >> str; std::cout << GetToken(str) << " ");

Полексемно проверяет, получается.
А что мне делать, если всё-таки нужно посимвольно?
Допустим, если в файле будет лежать "<class div" то выводится -1(отсутствие лексемы в списке, что логично) и 1(код лексемы).
А мне нужно, чтобы символ "<" считался лексемой.

MrGluck · 15.12.2016, 23:12

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

всё-таки нужно посимвольно?

Как тогда собираетесь проверять div, class, ... ?

@MrMax836 · 16.12.2016, 15:58 **[ТС]**

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

Как тогда собираетесь проверять div, class, ... ?

Всё-таки мне нужно сделать что-то похожее на мою кашу...
Только как это грамотно сделать, чтобы оно ещё и работало?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <fstream>
#include <map>
#include <string>
#include <queue>
 
struct queue
{
    std::queue<int>syntax;
};
int GetToken(std::ifstream ifs, struct queue)
  {
    static const std::map < std::string, int> states = {
        { "div", 1 },
        { "class", 2 },
        { "hentry", 3 },
        { "strong", 4 },
        { ",", 5 },
        { ".", 6 },
        { ";", 7 },
        { "(", 8 },
        { ")", 9 },
        { "{", 10 },
        { "}", 11 },
        { "=", 12 },
        { "-", 13 },
        { "<", 14 },
        { "«", 18 },
        { "»", 19 },
        { "", 20 },
    };
    static const std::map <char, int> symbols = {
        { ',', 5 },
        { '.', 6 },
        { ';', 7 },
        { '(', 8 },
        { ')', 9 },
        { '{', 10 },
        { '}', 11 },
        { '=', 12 },
        { '-', 13 },
        { '<', 14 },
        { '«', 18 },
        { '»', 19 },
        { '"', 20 },
    };
 
    int token = 0;
    char buffer[100];
    char ch = ifs.get();
    /* конец файла */
    if (ch == EOF)
        {
            {
              throw(std::invalid_argument("EOF"));
            }
          return 404;
        }
    /* пропускаем все пробелы, табуляции и символы новой строки */
    while (isspace(ch))
        {
            ch = ifs.get();
            return ch;
        }
    /* идентификатор или ключевое слово */
    if (isalpha(ch))
    {
        size_t i = 0;
        do
            {
                buffer[i++] = ch;
            }
        while ((ch = ifs.get()) != EOF && (isalpha(ch)));
 
        std::string str = std::string(buffer, sizeof(buffer));
        token = states.find(str)->second;
        }
        else
            {
                token = symbols.find(ch)->second;
            }
 
    return syntax.push(token);///эта строчка не работает(не определён syntax)
  }
 
 
int main()
{
    int token = 0;
    std::ifstream ifs("C:\\input.txt");
    if (!ifs)
        return 1;
    
    
    return 0;
}

MrGluck · 16.12.2016, 16:02

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

Всё-таки мне нужно сделать что-то похожее на мою кашу...

Можно использовать генератор парсеров типа bison.
В рамках "абстрактной задачи".
Вы бы хоть написали что конкретно хотите сделать, как обработать.

@MrMax836 · 16.12.2016, 16:14 **[ТС]**

Написать свой парсер, распарсить xml код. Распарсить на токены(отдельно скобки, кавычки, слэши и отдельно терминальные символы). Токены поместить в очередь(для дальнейшего синтаксического анализа).

MrGluck · 16.12.2016, 16:23

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

Написать свой парсер, распарсить xml код.

То есть надо именно xml научиться парсить?
Почему нельзя взять библиотеку для работы с xml, например pugi?

@MrMax836 · 16.12.2016, 16:28 **[ТС]**

Нужно именно посимвольно считывать поток, потом получать лексемы.
Без дополнительных библиотек

MrGluck · 16.12.2016, 16:40

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

именно посимвольно считывать поток

Так в задании написано или вы сами придумали?

Какой полный текст задания?

@MrMax836 · 16.12.2016, 19:06 **[ТС]**

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

Какой полный текст задания?

Даётся код(любой). Проверить, принадлежит ли он грамматике xml. Вот и всё задание.
Пока что я только на стадии парсера.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <fstream>
#include <map>
#include <string>
#include <queue>
 
struct queue
{
    std::queue<int>syntax;
};
 
int GetToken(std::ifstream &ifs, int &token)
  {
    static const std::map < std::string, int> states = {
        { "div", 1 },
        { "class", 2 },
        { "hentry", 3 },
        { "strong", 4 },
    };
    static const std::map <char, int> symbols = {
        { ',', 5 },
        { '.', 6 },
        { ';', 7 },
        { '(', 8 },
        { ')', 9 },
        { '{', 10 },
        { '}', 11 },
        { '=', 12 },
        { '-', 13 },
        { '<', 14 },
        { '«', 18 },
        { '»', 19 },
        { '"', 20 },
    };
 
    
    char buffer[100];
    char ch = ifs.get();
    /* конец файла */
    if (ch == EOF)
        {
            {
              throw(std::invalid_argument("EOF"));
            }
          return 404;
        }
    /* пропускаем все пробелы, табуляции и символы новой строки */
    while (isspace(ch))
        {
            ch = ifs.get();
        }
    /* идентификатор или ключевое слово */
    if (isalpha(ch))
    {
        size_t i = 0;
        do
            {
                buffer[i++] = ch;
            }
        while ((ch = ifs.get()) != EOF && (isalpha(ch)));
 
        std::string str = std::string(buffer, sizeof(buffer));
        token = states.find(str)->second;
    }
    else
        {
            token = symbols.find(ch)->second;
        }
 
    
    return token;
  }
 
 
int main()
{
    int token = 0;
    std::ifstream ifs("C:\\input.txt");
    if (!ifs)
        return 1;
    std::queue<int>syntax;
    while (ifs)
    {
        GetToken(ifs, token);
        syntax.push(token);
    }
    
    return 0;
}

Я немного подправил(но всё-равно некорректно работает). Получает первый токен, а потом программа завершается с кодом 3*(скорее всего цикл неправильно задал, ибо не знаю, как нужно).
*пишу в Visual Studio

MrGluck · 16.12.2016, 19:10

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

Проверить, принадлежит ли он грамматике xml

Если отбросить CDATA, то проверка сводится к простому контролю парных угловых скобок и кавычек.
С добавлением переменных-тегов в стек.

@MrMax836 · 16.12.2016, 19:45 **[ТС]**

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

проверка сводится к простому контролю парных угловых скобок и кавычек

К сожалению, нет. Нужно попробовать составить ll(1) грамматику и проверить весь код.

Добавлено через 26 минут
В этой части кода у меня ошибка.
Неправильно идёт считывание потока.

C++
1
2
3
4
5
6
7
8
9
10
11
12
 if (isalpha(ch))
    {
        size_t i = 0;
        do
            {
                buffer[i++] = ch;
            }
        while ((ch = ifs.get()) != EOF && (isalpha(ch))); 
 
        std::string str = std::string(buffer, sizeof(buffer));
        token = states.find(str)->second;
    }

MrGluck · 16.12.2016, 19:45

Примитивная функция проверки на валидность xml

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
bool Check(const std::string &str)
{
    std::stack<std::string> words;
    size_t i = 0;
    while (i < str.length())
    {
        i = str.find('<', i);
        if (i == std::string::npos)
            return words.empty();
        
        size_t endTag = str.find('>', i + 1);
        if (endTag == std::string::npos)
            return false;
        if (str[i + 1] == '/')
        {
            const std::string closeTag = str.substr(i + 2, endTag - i - 2);
            if (words.empty() || words.top() != closeTag)
                return false;
 
            words.pop();
        }
        else
        {
            const std::string openTag = str.substr(i + 1, endTag - i - 1);
            words.push(openTag);
        }
        i = endTag + 1;
    }
    return words.empty();
}

Осталось только добавить проверку атрибутов.

@MrMax836 · 19.12.2016, 18:33 **[ТС]**

Скажите, пожалуйста, а Вы знакомы с конечными автоматами(если я не ошибаюсь)?

Мне нужно составить таблицу переходов. для каждой лексемы.
Как я это понимаю:
1) Считываю символ из файла
2) Ищу этот символ в первом столбце двумерного массива.
3) Если нахожу этот символ, то перехожу по ссылке, содержащейся во втором столбце. Ссылка на следующий ожидаемый символ(а если может быть несколько вариантов?).
4) Возвращаемся к П.2
5) При разборе последнего символа лексемы, вместо ссылки на след. символ возвращаем код лексемы(токен).

Стоит двигаться в этом направлении?
Просто примеров реализации конечного автомата без Switch на C++ не нашёл(либо не понял реализации).

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .

@MrMax836 0 / 0 / 1 Регистрация: 30.07.2012 Сообщений: 59
	15.12.2016, 15:59 [ТС]
	Это так просто... Спасибо большое) Учиться и учиться! 0

@MrMax836 0 / 0 / 1 Регистрация: 30.07.2012 Сообщений: 59
	16.12.2016, 16:14 [ТС]
	Написать свой парсер, распарсить xml код. Распарсить на токены(отдельно скобки, кавычки, слэши и отдельно терминальные символы). Токены поместить в очередь(для дальнейшего синтаксического анализа). 0

@MrMax836 0 / 0 / 1 Регистрация: 30.07.2012 Сообщений: 59
	16.12.2016, 16:28 [ТС]
	Нужно именно посимвольно считывать поток, потом получать лексемы. Без дополнительных библиотек 0

@MrMax836 0 / 0 / 1 Регистрация: 30.07.2012 Сообщений: 59
	19.12.2016, 18:33 [ТС]
	Скажите, пожалуйста, а Вы знакомы с конечными автоматами(если я не ошибаюсь)? Мне нужно составить таблицу переходов. для каждой лексемы. Как я это понимаю: 1) Считываю символ из файла 2) Ищу этот символ в первом столбце двумерного массива. 3) Если нахожу этот символ, то перехожу по ссылке, содержащейся во втором столбце. Ссылка на следующий ожидаемый символ(а если может быть несколько вариантов?). 4) Возвращаемся к П.2 5) При разборе последнего символа лексемы, вместо ссылки на след. символ возвращаем код лексемы(токен). Стоит двигаться в этом направлении? Просто примеров реализации конечного автомата без Switch на C++ не нашёл(либо не понял реализации). 0