Разница между левым факторингом и левой рекурсией

Ответ 1

Левая факторизация устраняет общий левый множитель, который появляется в двух постановках того же нетерминального. Это делается для предотвращения обратного отслеживания парсером. Предположим, что синтаксический анализатор имеет перспективу, рассмотрим этот пример -

A → qB | Qc
где A, B, C - нетерминалы, q - предложение. В этом случае синтаксический анализатор будет запутан в отношении того, какое из двух постановок выбрать, и ему, возможно, придется отследить. После левого факторинга грамматика преобразуется в -

A → qD

D → B | С

В этом случае анализатор с опережением всегда будет выбирать правильную постановку.

Левая рекурсия - это случай, когда самый левый нетерминал при производстве нетерминала - это сам нетерминал (прямая левая рекурсия) или через некоторые другие нетерминальные определения, переписывает на нетерминальный снова (косвенная левая рекурсия). Рассмотрим эти примеры -

(1) A → Aq (прямой)

(2) A → Bq   B → Ar (косвенный)

Левая рекурсия должна быть удалена, если парсер выполняет синтаксический анализ сверху вниз

Ответ 2

Левый Факторинг - это метод преобразования грамматики. Он состоит в "выделении" префиксов, которые являются общими для двух или более производств.

Например, из:

A → α β | α γ

чтобы:

A → α A '

A '→ β | γ

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

Например:

A → A α

или же

A → B α

B → A γ

Существует метод преобразования грамматики под названием "Устранение левой рекурсии", который предоставляет метод для генерации с учетом левой рекурсивной грамматики другой грамматики, которая эквивалентна и не является левой рекурсивной.

Отношение/путаница между обоими терминами, вероятно, проистекает из того факта, что оба метода преобразования, возможно, должны быть применены к грамматике, прежде чем она сможет получить прогнозирующий анализатор сверху вниз для нее.

Ответ 3

Так я видел два используемых термина:

• Левая рекурсия: когда одна или несколько производств могут быть достигнуты сами по себе без использования токенов между ними.
• Левый факторинг: процесс преобразования, перевод грамматики из лево-рекурсивной формы в эквивалентную не леворекурсивную форму.

Ответ 4

левый фактор:

Пусть заданная грамматика: A--> ab1 | ab2 | ab3

1) мы видим, что для каждого производства есть общий префикс, и если мы выберем какое-либо производство здесь, это не подтвердит, что нам не нужно будет возвращаться назад.
2) оно не является детерминированным, потому что мы не можем выбирать какую-либо продукцию и быть уверены, что достигнем желаемой строки, создав правильное дерево разбора. но если мы переписываем грамматику способом, который является детерминированным и также оставляет нас достаточно гибкими, чтобы преобразовать ее в любую строку, которая возможна без возврата назад, это будет:

A → aA ', A' → b1 | b2 | b3

Теперь, если нас попросят создать дерево разбора для строки ab2, и теперь нам не нужно отслеживание назад. Потому что мы всегда можем выбрать правильную продукцию, когда получим A ', поэтому мы сгенерируем правильное дерево разбора.

Левая рекурсия:

A → Aa | b здесь ясно, что левый потомок A всегда будет A, если мы выберем первую продукцию, это левая рекурсия. потому что A вызывает себя снова и снова. сгенерированная строка из этой грамматики: ba *, поскольку это не может быть в грамматике... мы исключаем левую рекурсию, записывая:

A → bA 'A' → E | aA 'теперь у нас не останется рекурсии, а также мы можем генерировать ba *.

Ответ 5

Левая рекурсия: Грамматика остается рекурсивной, если она имеет нетерминал A такой, что существует вывод A → Aα | β, где α и β - последовательности терминалов и нетерминалов, которые не начинаются с A.

При проектировании верхнего вниз-парсера, если левая рекурсия существует в грамматике, тогда синтаксический анализатор попадает в бесконечный цикл, потому что A пытается совместить A, что невозможно. Мы можем устранить вышеупомянутую левую рекурсию, переписывая оскорбительное производство. Как -

A → βA '

A '- > αA' | эпсилон

Левый факторинг: Левый факторинг необходим для устранения недетерминизма грамматики. Предположим, что грамматика S → abS | ASB

Здесь S выводит один и тот же терминал a в производственном правиле (два альтернативных варианта для S), который следует за недетерминированностью. Мы можем переписать производство, чтобы отложить решение S как -

S → aS '

S '- > bS | Sb

Таким образом, S 'можно заменить на bS или Sb

Ответ 6

левая рекурсия: = когда левая нон-терминал такая же, как и правая не-терминальная. Пример: A- > A & B, где и является альфа. Мы можем удалить левый рикурсион, переписывая это производство как.

А- > В" А '- > & A' | €

Среднее значение левого фактора не должно быть недетерминированным., Пример: А → & A | & B | & С