Исключение леворекурсивных правил
- Возможность построения для LL(1) грамматики детерминированного автомата определяет значение этих грамматик для практических применений. Однако, при построении грамматики для заданного языка не всегда удается получить грамматику, принадлежащую классу LL(1). Это может случиться потому, что неудачно выбраны правила грамматики, или потому, что для заданного языка принципиально нельзя построить LL(1) грамматику. В первом случае полученную грамматику можно попытаться преобразовать таким образом, чтобы она удовлетворяла условиям LL(1) грамматики. Известно несколько приемов преобразований, которые в некоторых случаях, но не всегда, позволяют получить грамматику требуемого вида.
-
Допустим, что в схеме заданной грамматики имеются правила: <A>
® <B>
| <A><B>. Первое условие определения LL(1) грамматики говорит о том, что функции ПЕРВ для правил с одинаковой левой частью не должны иметь одинаковых элементов, но для заданной грамматики это не так, поскольку
-
Возьмем другие правила, обеспечивающие получение такого же множества цепочек, что и в первом случае : <A> ®
<A><B> | $.
Первый вид преобразований заключается в исключении правил, содержащих левую рекурсию. Необходимость исключения таких правил можно показать с помощью следующих рассуждений.
- ПЕРВ(<A><B>) = ПЕРВ(<A>) = ПЕРВ(<B>).
Следовательно, грамматика, содержащая рассматриваемые правила, не является LL(1) грамматикой.
Первое условие выполняется, но имеем:
СЛЕД ( <A> ) = ПЕРВ (<B>) и ПЕРВ (<A>) = ПЕРВ (<B>),
поскольку A можно заменить $.
Эти равенства показывают, что нарушается второе условие из определения LL(1) грамматики.
Из приведенных рассуждений можно сделать вывод о том, что LL(1) грамматика не должна содержать леворекурсивных правил. Конечно, лучше не использовать леворекурсивные правила еще на этапе построения грамматики, но если уж они появились, то их можно исключить, пользуясь приемом, описанным в предыдущем разделе.
Пред.Страница
След.Страница Раздел Содержание