Об ассоциативностях

Вообщем, почитал я немного Книгу Дракона. Думал, что это нечто страшное типа "Искусства Программирования" Кнута. Оказалось, что совсем не так, книга написа довольно внятным языком и легка для восприятия, жалею что раньше не прочитал её.

Я понял, почему мне так не удалось сходу написать калькулятор. Проблема, как я и думал, лежала в математической области. О ней и хочу поговорить. Но обо всём по порядку. Начну я с ассоциативности.

И так, что такое ассоциативность и зачем она нам нужна?

Пусть есть некоторая бинарная операция @
Значит некоторой сущности 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)

Очень маленькая, простенькая и без левых рекурсий!