Разница в удалении левой рекурсии для + и - или * или /?

Чтобы удалить левую рекурсию

E->E+T|E-T|T
T->T*F|T/F|F

для + и *, я уверен, что это должно быть

E->TE'
E'->+TE'|(e) (e) is empty string
T->FT'
T'->*FT'|(e)

но для - или / я не уверен, как убрать левую рекурсию, и я придумал следующую, подходит ли она для - и /? Возьмем пример: для плюса a+b = b+a, а для минуса a - b != b -a. Итак, если мы используем следующую правую рекурсию, получим ли мы проблему, подобную a-b?

E->TE'
E'->+TE'|-TE'|(e) 
T->FT'
T'->*FT'|/FT'|(e)

Кто-нибудь знает, что компилятор объясняет мне? Заранее спасибо.


compiler-construction grammar left-recursion
person David    schedule 25.10.2015    source источник
comment
Что вы имеете в виду под 4-3? У вас есть интерпретатор, который интерпретирует эту грамматику? И он возвращает -1 вместо 1? Проблема, вероятно, не в грамматике, а в интерпретаторе. Если да, то вам следует предоставить дополнительную информацию о генераторе синтаксического анализатора и коде интерпретатора.   -  person CoronA    schedule 25.10.2015
comment
Я думаю, вы имели в виду T->T*F|T/F|F (а не E/T)   -  person rici    schedule 25.10.2015
comment
@rici да, это то, что я имею в виду   -  person David    schedule 25.10.2015
comment
@CoronA дело не в переводчике. Я отредактировал свой вопрос.   -  person David    schedule 25.10.2015
comment
Непонятно, в чем заключается ваш вопрос - да, окончательная грамматика, которую вы показываете, является правильной левой факторизацией вашей исходной грамматики. Он может анализировать +, -, * или / точно так же, как исходная грамматика, и распознает точно такой же язык. Очевидно, что дерево синтаксического анализа для любого заданного ввода будет другим.   -  person Chris Dodd    schedule 25.10.2015
comment
@David: синтаксическое дерево может иметь неправильную ассоциативность. Но обычно семантический анализ преобразует синтаксическое дерево таким образом, что достигается правильная ассоциативность. И это не баг грамматики, а семантического анализа/интерпретатора. Кроме того - исправьте правило 2, как рекомендовал Ричи.   -  person CoronA    schedule 25.10.2015

Ответы (1)


arrow_upward
3
arrow_downward

Устранение левой рекурсии позволяет синтаксическому анализатору LL правильно распознавать язык, но результирующий синтаксический анализатор не создает правильное дерево синтаксического анализа. В частности, он заменяет левоассоциативный анализ для таких операторов, как - и /, на правоассоциативный анализ.

Чтобы использовать синтаксический анализ для фактической интерпретации проанализированных строк, вам необходимо восстановить правильное дерево синтаксического анализа, фактически обратив ассоциативность для левоассоциативных операторов.

В качестве альтернативы вы можете просто использовать восходящий парсер, такой как парсер LALR(1), сгенерированный yacc/bison. Или вы можете написать или адаптировать алгоритм приоритета операторов (см. «Маневровая станция»).

Если вы собираетесь использовать грамматику LL в синтаксическом анализаторе рекурсивного спуска, этой проблемы можно избежать, поскольку синтаксический анализатор рекурсивного спуска обычно имеет явный цикл вместо рекурсии в право-рекурсивном производстве (в псевдокоде):

parse_term(): 
  f = parse_factor()
  while peek() is in ('*', '/'):
    op = token()
    f2 = parse_factor()
    f = apply_operator(op, f, f2)
  return f
person rici    schedule 25.10.2015
comment
Спасибо за ваш ответ, я отредактировал свой вопрос. Изначально это сбивало с толку. - person David; 25.10.2015
comment
@David: я думаю, что мой ответ все еще правильный. В основном: да, проблема в том, что дерево синтаксического анализа некорректно, но с этим можно справиться; ответ пытается сделать несколько предложений о том, как это сделать. - person rici; 26.10.2015