Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
(left - leftmost)
LL(1) - грамматики относятся к нисходящим грамматикам (сверху - вниз).
Они отличаются от q-грамматик тем, что правые части могут начинаться с нетерминальных символов, но таких, которые после подстановок терминальных символов обеспечивают однозначность выбора грамматических правил.
В LL(1) - грамматиках разворачиваются самые левые нетерминальные символы сентенциальной формы и анализируется очередной самый левый терминальный входной строки. Возможен анализ k самых левых символов входной строки, Тогда грамматику называют LL(k) - грамматикой. Но, поскольку грамматики LL(k) и LL(1) эквивалентны в плане порождаемых языков, остановимся на рассмотрении только последней.
F(a) - множество терминальных символов, стоящих первыми (First)) в цепочках, выводимых из строки a.
N(А) - множество терминальных символов, следующих (Next) в цепочках за данным нетерминальным символом А.
Множество выбора для каждого правила формируется с учетом множества первых и множества следующих символов.
LL(1) - это такая грамматика, у которой для правил с одинаковыми левыми частями множества выбора не пересекаются.
1. S ® AbB E(1) = F(AbB) = {a, b, c, e}
2. S ® d E(2) = {d}
3. A ® CAb E(3) = F(CAb) = {a, e}
4. A ® B E(4) = F(B) È N(A) = {c} È {b} = {c, b}
5. B ® cSd E(5) = F(cSd) = {c}
6. B ® e E(6) = F(e) È N(B) = {Æ} È {b, d, ┤}
7. C ® a E(7) = {a}
8. C ® ed E(8) = {e}
Дата публикования: 2014-11-03; Прочитано: 995 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!