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

#parsing #grammar #lalr #lr

#синтаксический анализ #грамматика #lalr #lr

Вопрос:

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

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

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

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

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

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

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

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

1. Да, это домашнее задание (своего рода). «Помочь с чем именно?» -> В этом случае мне нужна помощь с преобразованием правил грамматики в таблицы синтаксического анализа. Я создал несколько разных грамматик, но мне сложно преобразовать их в таблицы синтаксического анализа (для LR (k)).

Ответ №1:

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

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

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

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