В первой части был написан лексер. Далее будет рассмотрена разработка парсера.
Парсер
Парсер будет реализован по алгоритму сортировочной станции, так как он достаточно прост и не нуждается в рекурсии. Сам алгоритм таков:
В начале даются пустой выходной поток и пустой стек. Начнём читать токены из входного потока по очереди.
- Если это число, то передать его в выходной поток.
- Если это лево ассоциативный оператор, то выталкиваем токены из стека в выходной поток до тех пор, пока он не опустеет, либо не его вершине не встретится скобка, или оператор с более низким приоритетом.
- Если это открывающая скобка, то положить её в стек.
- Если это закрывающая скобка, то выталкиваем токены из стека в выходной поток до обнаружения открывающей скобки. Вытолкнуть открывающую скобку из стека, но не передавать её в выходной поток. Если стек опустел, и скобка не найдена, то генерируем ошибку.
После достижения конца входного потока, вытолкнуть все оставшиеся в стеке операторы в выходной поток. Если в нём найдено что-либо кроме операторов, то генерируем ошибку.
Прикинем, какие тесты могут понадобиться для начала.
- При получении пустого списка, возвращается пустой список.
- При получении списка с одним числом, возвращается список с этим числом.
- При получении [1 + 2], возвращается [1 2 +].
- При получении [1 + 2 + 3], возвращается [1 2 + 3 +], так как оператор + является лево ассоциативным.
- При получении [1 * 2 + 3], возвращается [1 2 * 3 +].
- При получении [1 + 2 * 3], возвращается [1 2 3 * +], так как оператор * имеет больший приоритет.
Со скобками и ошибками разберёмся позднее. Итак, напишем первый тест из списка.
TEST_CLASS(ParserTests) {
public:
TEST_METHOD(Should_return_empty_list_when_put_empty_list) {
Tokens tokens = Parser::Parse({});
Assert::IsTrue(tokens.empty());
}
};
