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

Question

Здесь S - нетерминальный начальный символ; A, B, C - нетерминальные символы; x, y, являются терминальными символами

S → A B A C | A C A B
A → A x | A y
B → B x x | B y y
C → x y | y x

Посмотрев видео, я понимаю простые примеры устранения левой рекурсии в производственных правилах, таких как

S → a S a
S → b S b
S → ε

но я не понимаю, как устранить левую рекурсию в правилах, показанных выше. Может кто-нибудь объяснить или указать мне в направлении объяснения?

Answer 1

Во втором примере нет левой рекурсии, поэтому удаление левой рекурсии тривиально.

В вашей первой грамматике вам необходимо коэффициент левой , прежде чем вы сможете занятьсяустранение рекурсии.(Действительно, название вашего вопроса гласит «оставленный фактор», так что вы уже имели эту подсказку в домашнем задании / викторине.)

Ссылка, приведенная выше, является одной из сотен, найденных Google с поисковым термином"грамматика левого фактора", но я бы посоветовал вам хотя бы подумать о том, что материалы вашего курса являются лучшим источником информации, чем поиски в Google (или случайные видео на Youtube).