Вообщем, почитал я немного Книгу Дракона. Думал, что это нечто страшное типа "Искусства Программирования" Кнута. Оказалось, что совсем не так, книга написа довольно внятным языком и легка для восприятия, жалею что раньше не прочитал её.
Я понял, почему мне так не удалось сходу написать калькулятор. Проблема, как я и думал, лежала в математической области. О ней и хочу поговорить. Но обо всём по порядку. Начну я с ассоциативности.
И так, что такое ассоциативность и зачем она нам нужна?
Пусть есть некоторая бинарная операция @
Значит некоторой сущности x мы можем поставить в соответсвие y @ z
x = y @ z
Но y и z сами могут быть результатами выполнения операции @.
y = a @ b
x = (a @ b) @ z
или
z = b @ c
x = y @ (b @ c)
Ну и дальше по индукции, рекурсивно расширяя до какого угодно количества членов в выражении.
Назовём операцию @ лево-ассоциативной, если запись a @ b @ c эквивалентна выражению (a @ b) @ c. Если же a @ b @ c эквивалентно выражению a @ (b @ c), то операция @ является право-ассоциативной.
Можно запомнить, что если оператор стоит слева от терминального операнда(того, который нельзя разбить на под-выражения), то операция — лево-ассоциативная, иначе она право-ассоциативная. То есть, с какой стороны операция прилепливается к терминальному операнду, такая и ассоциативность у неё.
Пример.
Во многих языках программирования операция присваивания является право-ассоциативной. То есть a = b = c => a = (b = c). Это вполне резонно, так как вычесление операндов идёт справа и в конечном итоге доходит до самого левого.
Но арифметические операции являются лево-ассоциативными.
a - b - c => (a - b) - c.
Тут вычесление идет начиная с самого левого операнда.
Перейдёт к собственно проблеме.
Вот как выглядят грамматики для выражений с операторами с разной ассоциативностью.
expr -> term op expr — право-ассоциативная операция
expr -> expr op term — лево-ассоциативная операция
Тут term это операнд, который в контексте данной операции не разбивается на составные части, хотя он может разбиваться на них для операции с более высоким приоритетом.
Вот тут-то уже можно увидеть проблему. Заметим, что грамматика для лево-ассоциативной операции образует, так называемую, левую рекурсию. Но я хотел реализовть парсинг выражений за один проход слева направо. То есть predictive parser.
Одной из особенностей таких парсеров является то, что они не поддерживают грамматики с левой рекурсией. Но зато их очень просто реализовать, особенно на функциональных языках.
Так что делать? Неужели для такой простой задачки, как разбор арифмитических выражений придётся писать сложный bottom-up парсер с бэктрейсингом? Ну уж нет. Я так просто не сдамся!
Тут нам на помощь приходит математика. Оказывается есть простой способ избавления от левой рекурсии путём добавления новых нетреминальных символов в грамматику.
Если есть грамматика вида
A -> Aa | Ab | c
то мы можем трансформировать её в грамматику с правой рекурсией
A -> cR
R -> aR | bR | eps
Вот пример:
expr -> expr + term |
expr - term |
term
заменяется на
expr -> term rest
rest -> +term rest |
-term rest |
eps
А эта грамматика очень легко парсится на predictive parser.
Ну и приведу полную грамматика для арифметических выражений.
expr -> term rest_e
rest_e -> (+ | -) term rest_e | eps
term -> factor rest_t
rest_t -> (* | / | ^) factor rest_t | eps
factor -> -factor | +factor | (expr) | function | number
function -> unary_func_name (expr) |
binary_func_name(expr, expr)
Очень маленькая, простенькая и без левых рекурсий!
