ИДЗ2, LL(1)-грамматики

В ИДЗ 2 вы должны составить грамматику для языка, который получили в условии, и написать программу, которая проверяет, принадлежит ли слово языку. Программа просит пользователя ввести строку, и выдает результат: либо строка принадлежит языку, либо указывается, начиная с какой позиции в строке возникла ошибка разбора.

Обратите внимание, что это не задание по программированию, и от вас требуется только превратить вашу грамматику в код в соответствии с формальными правилами преобразования. Вам не нужно самостоятельно сочинять код для исправления каких-нибудь ошибок, это будет означать, что вы неправильно превратили грамматику. Если сделанная вами программа не заработает или будет работать неправильно, значит ошибка либо изначально была в грамматике, либо вы неправильно ее превратили.

Разберем создание программы на примере языка C++ и вот такого языка: “арифметические выражения из переменных “a”, сложений и скобок”:

a
a + a
a + (a + a)
(a + (a + a) + a)

неправильные слова

a + 
a + a)
(a + a + (a)
b
()

Грамматика:

1) <expr> ::= <item><ending>

2) <ending> ::=
3) <ending> ::= + <expr>

4) <item> ::= a
5) <item> ::= ( <expr> )

Если вы пишете на C++, то можете оставить всю программу, заменив только то, что написано между “НАЧАЛО” и “КОНЕЦ” функций разбора.

#include <iostream>
#include <string>

using namespace std;

//строка, введенная пользователем
string input;
//текущая позиция чтения символа
int pos;

//Возвращает текущий символ. Символ конца строки заменяется на $
char read() {
    char ch = input[pos];
    if (! ch)
        return '$';
    else
        return ch;
}

//Перемещает указатель чтения символа вперед
void next() {
    pos++;
}

//Сообщает об ошибке
void error() {
    throw exception();
}

//Читает терминальный символ, проверяет, что прочитала именно тот, который нужно
void read_terminal(char ch) {
    if (read() != ch)
        error();
    else
        next();
}

// НАЧАЛО ФУНКЦИЙ РАЗБОРА

// Грамматике соответствуют только следующие функции. Все остальное в этом файле нужно только, чтобы программу можно было запустить и проверить.

/*
Перечисление заголовков функций. Необходимо, чтобы можно было вызывать функцию до того, как
описан ее код. Без этого получается, что read_expr() вызывает read_item(), read_item() вызывает
read_expr() и невозможно выбрать, какую функцию описывать раньше.
PASCAL программисты тоже должны описывать функции заранее, для этого используется следующий синтаксис:
  procedure read_expr; forward;
Тело функции не описывается, оно будет описано позже.
*/
void read_expr();
void read_ending();
void read_item();

void read_expr() {
    switch (read()) {
        case 'a' :       //два case подряд означают, что прочитанный символ либо a, либо (
        case '(' :
            //правило 1
            //читаем <item>
            read_item();
            //читаем <ending>
            read_ending();
            break;
        default :       //во всех остальных случаях - error
            error();
    }
}

void read_ending() {
    switch (read()) {
        case '$':
        case ')':
            //правило 2
            break;
        case '+' :
            //правило 3
            //читаем символ +
            read_terminal('+');
            //читаем <expr>
            read_expr();
            break;
        default :
            error();
    }
}

void read_item() {
    switch (read()) {
        case 'a':
            //правило 4
            //читаем символ a
            read_terminal('a');
            break;
        case '(':
            //правило 5
            //читаем символ (
            read_terminal('(');
            //читаем выражение
            read_expr();
            //читаем символ )
            read_terminal(')');
            break;
        default:
            error();
    }
}

// КОНЕЦ ФУНКЦИЙ РАЗБОРА

int main() {
    cout << "Введите строку:\n";
    //читаем строку
    getline(cin, input);
    //устанавливаем текущий символ в начало строки
    pos = 0;

    try {
        //читаем выражение
        read_expr();

        //проверяем, что чтение дошло до конца
        if (read() != '$')
            error();

        //если не произошло ошибок, сообщаем, что строка корректна
        cout << "строка корректна";
    } catch (exception& ignored) {
        //если функцией error() было брошено исключение, сообщаем об ошибке и позиции.
        cout << "ошибка в позиции " << (pos + 1); // + 1, чтобы считать позиции с 1, а не с 0
    }
    
    cout << "\n";

    return 0;
}