Формальные языки, грамматики и основы построения трансляторов. Кревский И.Г - 50 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

50
9. ПРЕОБРАЗОВАНИЕ ГРАММАТИК В LL(1) ФОРМУ
"Очевидной" грамматикой для большинства языков программирования
является не LL(1)-грамматика. Однако обычно очень большое число
контекстно-свободных средств языка программирования можно представить
с помощью LL(1)-грамматики. Проблема заключается в том, чтобы, имея
грамматику, которая не обладает признаком LL(1), найти эквивалентную ей
LL(1)-грамматику. Не существует универсального алгоритма преобразования
любой КС-грамматики в LL(1) форму (а
также определения самой
возможности такого преобразования). Однако существует ряд приемов,
позволяющих выполнить такое преобразование во многих частных случаях.
Устранение левой рекурсии
Грамматика, содержащая левую рекурсию, не является LL(1)-
грамматикой. Рассмотрим правила
A
→
Aa (левая рекурсия в A)
A
→
a
Здесь a символ-предшественник для обоих вариантов нетерминала A.
Аналогично грамматика, содержащая левый рекурсивный цикл, не может
быть LL(1)-грамматикой, например
A
→
BC
B
→
CD
C
→
AE
Грамматику, содержащую левый рекурсивный цикл, можно
преобразовать в грамматику, содержащую только прямую левую рекурсию, и
далее, за счет введения дополнительных нетерминалов, левую рекурсию
можно исключить полностью (в действительности она заменяется правой
рекурсией, которая не представляет проблемы в отношении LL(1)-свойства).
В качестве примера рассмотрим грамматику с порождающими правилами 
                                                                        50
       9. ПРЕОБРАЗОВАНИЕ ГРАММАТИК В LL(1) ФОРМУ
     "Очевидной" грамматикой для большинства языков программирования
является не LL(1)-грамматика. Однако обычно очень большое число
контекстно-свободных средств языка программирования можно представить
с помощью LL(1)-грамматики. Проблема заключается в том, чтобы, имея
грамматику, которая не обладает признаком LL(1), найти эквивалентную ей
LL(1)-грамматику. Не существует универсального алгоритма преобразования
любой КС-грамматики в LL(1) форму (а также определения самой
возможности такого преобразования). Однако существует ряд приемов,
позволяющих выполнить такое преобразование во многих частных случаях.


                         Устранение левой рекурсии


     Грамматика, содержащая левую рекурсию, не является LL(1)-
грамматикой. Рассмотрим правила
     A → Aa (левая рекурсия в A)
     A→ a
     Здесь a символ-предшественник для обоих вариантов нетерминала A.
Аналогично грамматика, содержащая левый рекурсивный цикл, не может
быть LL(1)-грамматикой, например
     A→ BC
     B → CD
     C → AE
     Грамматику,   содержащую      левый   рекурсивный    цикл,   можно
преобразовать в грамматику, содержащую только прямую левую рекурсию, и
далее, за счет введения дополнительных нетерминалов, левую рекурсию
можно исключить полностью (в действительности она заменяется правой
рекурсией, которая не представляет проблемы в отношении LL(1)-свойства).
В качестве примера рассмотрим грамматику с порождающими правилами

Страницы