Синтаксический парсер на Си++

2020-01-18 15:26
vak: (Default)
[personal profile] vak
Про лексический сканер я уже писал, теперь черёд синтаксического парсера. Есть много современных инструментов для Си++, от ANTLR до PEGTL, но я покажу, как задействовать для этой задачи старый добрый YACC, точнее bison.

Будем решать простейшую задачу: подсчитывать количество букв и слов в тексте. Я нашёл этот пример в интернете и переиначил его на свой лад. Парсер делаем в виде класса Parser с двумя методами. Функция parse() разбирает входной поток и накапливает счётчики. Функция print() печатает результат. Всё это поместим в пространство имён Demo. Функция main() выглядит тривиально, файл main.cc:
#include "parser.hh"

int main()
{
    Demo::Parser parser;
    parser.parse();
    parser.print();
    return 0;
}
Объявим класс Parser, файл parser.hh:
#include "grammar.tab.hh"

namespace Demo {

class Parser {
    unsigned chars, words, lines, uppercase, lowercase;

    int get_next_token(Grammar::semantic_type *const lval,
                       Grammar::location_type *location);
public:
    void parse();
    void print();

    friend class Grammar;
};

} // namespace Demo
Результат обработки входного потока будем накапливать в счётчиках chars, words и прочее. Функция get_next_token() реализует лексический сканер: выдаёт следующий токен из входного потока. В этом примере для простоты я сделал сканер без применения flex, чтобы не затуманивать суть дела.

Бизон будет порождать код в виде класса Grammar. Чтобы из грамматики иметь прямой доступ к счётчикам в классе Parser, я объявляю Grammar как friend class.

Реализуются методы класса Parser довольно прямолинейным образом, файл parser.cc:
#include <iostream>
#include "parser.hh"

namespace Demo {

void Parser::parse()
{
    chars = 0;
    words = 0;
    lines = 0;
    uppercase = 0;
    lowercase = 0;

    Grammar grammar(*this);
    if (grammar.parse() != 0) {
        std::cerr << "Parse failed!\n";
    }
}

void Parser::print()
{
    std::cout << "Lines: " << lines << std::endl;
    std::cout << "Words: " << words << std::endl;
    std::cout << "Characters: " << chars << std::endl;
    std::cout << "Uppercase: " << uppercase << std::endl;
    std::cout << "Lowercase: " << lowercase << std::endl;
}

int Parser::get_next_token(Grammar::semantic_type *lval, location *loc)
{
    // Берём первый символ.
    char c0;
    std::cin.get(c0);
    if (std::cin.eof()) {
        return Grammar::token::END;
    }
    if (c0 == '\n') {
        loc->lines();
        return Grammar::token::NEWLINE;
    }
    if (!isalpha(c0)) {
        return Grammar::token::CHAR;
    }

    // Проверяем следующий символ.
    char c;
    std::cin.get(c);
    if (std::cin.eof() || !isalpha(c)) {
        if (!std::cin.eof())
            std::cin.unget();

        if (isupper(c0)) {
            return Grammar::token::UPPER;
        } else {
            return Grammar::token::LOWER;
        }
    }

    // Проходим до конца слова.
    std::string text;
    text += c0;
    for (;;) {
        text += c;
        std::cin.get(c);
        if (!isalpha(c)) {
            std::cin.unget();
            break;
        }
    }
    lval->build(text);
    return Grammar::token::WORD;
}

} // namespace Demo
Функция get_next_token() считывает по одному символу из входного потока и классифицирует лексемы как буквы, слова и прочие символы. Она возвращает целочисленный тип токена, как определено в грамматике. Для слов, строка запоминается в первом параметре lval. При обнаружении конца строки номер строки увеличивается вызовом метода второго параметра loc.
 
Теперь собственно грамматика, файл grammar.yy:
%skeleton "lalr1.cc"
%require  "3.2"
%debug
%defines
%define api.namespace { Demo }
%define api.parser.class { Grammar }
%define api.value.type variant
%define parse.assert
%locations

// Добавляем параметр для конструктора Grammar().
%code requires {
    namespace Demo {
        class Parser;
    }
}
%parse-param { Demo::Parser &parser }

// Для чтения входного потока используем метод  get_next_token().
%code {
    #include "parser.hh"
    #undef yylex
    #define yylex parser.get_next_token
}

// Определяем нужные типы токенов.
%token               END    0     "end of file"
%token               UPPER
%token               LOWER
%token <std::string> WORD
%token               NEWLINE
%token               CHAR

%%

list_option : END | list END;

list
    : item
    | list item
    ;

item
    : UPPER {
                // Единичная буква, прописная.
                parser.uppercase++;
                parser.chars++;
                parser.words++;
            }
    | LOWER {
                // Единичная буква, строчная.
                parser.lowercase++;
                parser.chars++;
                parser.words++;
            }
    | WORD {
                // Слово как последовательность букв.
                parser.words++;
                parser.chars += $1.length();
                for (const char &c : $1) {
                    if (isupper(c)) {
                        parser.uppercase++;
                    } else {
                        parser.lowercase++;
                    }
                }
            }
    | NEWLINE {
                // Разделитель строки.
                parser.lines++;
                parser.chars++;
            }
    | CHAR {
                // Другой символ.
                parser.chars++;
            }
    ;

%%

// В случае синтаксической ошибки выдаём сообщение.
void Demo::Grammar::error(const location_type &loc, const std::string &message)
{
    std::cerr << "Error: " << message << " at " << loc << "\n";
}
Компилируем, при этом бизон из грамматики grammar.yy породит файлы grammar.tab.cc и grammar.tab.hh (ещё location.hh, но это отдельная тема):
bison -d grammar.yy
c++ -std=c++11 -c main.cc
c++ -std=c++11 -c parser.cc
c++ -std=c++11 -c grammar.tab.cc
c++ main.o parser.o grammar.tab.o -o wcount
Запускаем:
$ echo 123 fooo BAR | ./wcount
Lines: 1
Words: 2
Characters: 13
Uppercase: 3
Lowercase: 4
Вот такой простой способ создавать парсеры. При этом можно комбинировать bison и flex, что удобно, хотя и не обязательно.
Tags:
OSZAR »