Расширить грамматику для поддержки unar операций

Question

У меня очень простая грамматика:

E->E+T|T
T->T*F|F
F->(E)|id

И я хочу расширить его для поддержки операций unar (ИМХО, это правильная грамматика, но она может быть неправильной, потому что я настоящий n00b в грамматиках, парсерах, лексерах и т. Д.):

E->E+T|T
T->T*F|F
F->+F|(E)|id

Настоящая проблема возникает, когда я пытаюсь обновить таблицу разбора:

Итак, вопрос : как мне отредактировать эту таблицу, чтобы обеспечить поддержку унарных операций (на основе описанной грамматики)?

P.S. В любом случае, я буду очень признателен за любую помощь в разборе арифметического выражения в Java (или любом другом языке OO) с использованием синтаксического анализатора LR (k) (или LALR) ^ _ ^

P.S.2. Генераторы парсеров в этом случае не подходят.

Answer 1

Чтобы понять, как настроить таблицу синтаксического анализа, вам необходимо знать, какие наборы элементов LR предназначены для каждого состояния, и понять, как ваше добавление к грамматике меняет наборы элементов - каждый новый элемент частичного анализа в наборе элементов состояния дает вам дополнительное действие для разбора таблицы. Например, в состоянии 7 исходный набор элементов (до добавления правила F -> + F) был:

T -> T * . F
F -> . ( E )
F -> . id

(в данном случае я игнорирую прогноз, поскольку это не имеет значения, но для общего LR (k) вам нужно следить за ним.)

Таким образом, ваше новое правило добавляет элемент F -> . + F, который дает вам новое действие для состояния 7 (сдвиг на входе +.) Это, в свою очередь, дает вам совершенно новое состояние для вашей таблицы.