LINUX.ORG.RU

Работа с Bison. Синтаксически управляемое устранение лишних скобок в алгебраическом выражении.

 ,


0

2

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

S::=E

E::=E+T

E::=T

T::=T*F

T::=F

F::=a

F::=b

F::=(E)

S – аксиома

Необходимо с помощью восходящей трансляции на основе вычисления синтезируемых атрибутов убрать (ну, вернее, как я понимаю, правильно расставить) скобки в выражении.

Т.е. на входе строка: (((а))), на выходе = а. (((а + б) * а) * б) = (а + б) * а * б. Был вариант просмотра строки на поиск умножения до и после сложения, чтобы был смысл брать сложение в скобки. Но реализовать его не получается. Может быть у кого есть желание и возможность натолкнуть на подходящую мысль по данной задаче? спасибо.


Я бы начал с построения дерева операций, скобочные унарные узлы там будут лишними, выкинул бы их, а потом вставил заново в те связки, где чилдом идет например +, а парентом *, или любой другой оператор большего приоритета.

Вход (польский, дерево в уме):
* () + a b () () c
Без скобок:
* + a b c
Заново:
* () + a b c

В голове сложные примеры не прокручивал, но вроде должно получиться. По крайней мере можно будет тестить и смотреть что не так.

anonymous ()