Удаление прямой и косвенной левой рекурсии в грамматике

Опубликовано: 19 Декабря, 2021

Предварительное условие - классификация контекстно-свободных грамматик, неоднозначности и синтаксических анализаторов
Левая рекурсия:
Грамматика формы,

 S -> S / а / б

Он называется леворекурсивным, где S - любой не Терминал, а a и b - любой набор терминалов.

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

Алгоритм удаления левой рекурсии на примере:
Предположим, у нас есть грамматика, которая содержит левую рекурсию:

 S -> S a / S b / c / d
  1. Проверьте, содержит ли данная грамматика левую рекурсию, если она есть, отделите производство и начните работать над ним.
    В нашем примере

     S -> S a / S b / c / d
  2. Введите новый нетерминал и напишите его в конце каждого терминала. Мы производим новый нетерминал S'и записываем новое производство как,
     S -> cS '/ dS'
  3. Запишите вновь созданный нетерминал в LHS, а в RHS он может либо произвести, либо он может создать новую продукцию, в которой терминалы или нетерминалы, которые следовали за предыдущим LHS, будут, наконец, заменены новым нетерминалом.
     S '->? / aS '/ bS'

    Таким образом, после конверсии новая эквивалентная продукция

     S -> cS '/ dS'
S '->? / aS '/ bS'

Косвенная левая рекурсия:
Говорят, что грамматика имеет косвенную левую рекурсию, если, начиная с любого символа грамматики, можно получить строку, заголовок которой является этим символом.

Например,

 А -> Br 
B -> Cd
C -> При

Где A, B, C - нетерминалы, а r, d, t - терминалы.
Здесь, начиная с A, мы можем снова получить A, заменив C на B и B на A.

Алгоритм удаления косвенной рекурсии на примере:

 A1 -> A2 A3
A2 -> A3 A1 / b
A3 -> A1 A1 / а

Где A1, A2, A3 не являются терминалами, а a, b - терминалами.

  1. Определите продукты, которые могут вызвать косвенную левую рекурсию. В нашем случае
     A3 - & gt A1 A1 / a
  2. Заменить его производство в месте присутствия терминала любым другим производственным заменителем A1–> A2 A3 в производстве A3. A3 -> A2 A3 A1.
    Теперь в этой продукции замените A2–> A3 A1 / b, а затем замените это на,
     A3 -> A3 A1 A3 A1 / b A3 A1
  3. Теперь новая продукция преобразована в форму прямой левой рекурсии, решите это методом прямой левой рекурсии.
    Исключив прямую левую рекурсию в приведенном выше,
     A3 -> а | b A3 A1 | aA '| b A3 A1A ' 
A '-> A1 A3 A1 | A1 A3 A1A '

    В результате получается грамматика:

     A1 -> A2 A3
A2 -> A3 A1 | б
A3 -> а | b A3 A1 | aA '| b A3 A1A ' 
A '-> A1 A3 A1 | A1 A3 A1A '

РЕКОМЕНДУЕМЫЕ СТАТЬИ