Теория формальных языков, грамматик и автоматов. Ишакова Е.Н. - 32 стр.

    6 Лабораторная работа № 6. Моделирование функциониро-
вания распознавателя для LL(1)-грамматик

     Цель: - закрепить понятие «LL(k) –грамматика», необходимые и доста-
точные условия LL(k) –грамматики;
           - сформировать умения и навыки построения множеств FIRST(k, α)
и FOLLOW(k, α), распознавателя для LL(1)-грамматик.
                                Основы теории

       Определение 6.1. КС-грамматика обладает свойством LL(k) для некото-
рого k>0, если на каждом шаге вывода для однозначного выбора очередной
альтернативы МП-автомату достаточно знать символ на верхушке стека и рас-
смотреть первые k символов от текущего положения считывающей головки во
входной строке.
       Определение 6.2. КС-грамматика называется LL(k)-грамматикой, если
она обладает свойством LL(k) для некоторого k>0.
       В основе распознавателя LL(k)-грамматик лежит левосторонний разбор
строки языка. Исходной сентенциальной формой является начальный символ
грамматики, а целевой – заданная строка языка. На каждом шаге разбора пра-
вило грамматики применяется к самому левому нетерминалу сентенции. Дан-
ный процесс соответствует построению дерева разбора цепочки сверху вниз (от
корня к листьям). Отсюда и произошла аббревиатура LL(k): первая «L» (от сло-
ва «left») означает левосторонний ввод исходной цепочки символов, вторая «L»
- левосторонний вывод в процессе работы распознавателя.
       Определение 6.3. Для построения распознавателей для LL(k)-грамматик
используются два множества:
       - FIRST(k, α) – множество терминальных цепочек, выводимых из цепоч-
ки α∈(VT∪VN)*, укороченных до k символов;
       - FOLLOW(k, A) – множество укороченных до k символов терминальных
цепочек, которые могут следовать непосредственно за A∈VN в цепочках вывода.
       Формально эти множества можно определить следующим образом:
       - FIRST(k, α) = {ω ∈ VT* | ∃ вывод α ⇒*ω и |ω| ≤ k или ∃ вывод α ⇒*ωx
и |ω| = k; x, α ∈ (VT∪VN)*, k > 0};
       - FOLLOW(k, A) = {ω ∈VT* | ∃ вывод S⇒*αAγ и ω∈FIRST(k, γ); α, γ∈V*,
A∈VN, k>0}.

      Теорема 6.1. Необходимое и достаточное условие LL(1)-грамматики

      Для того чтобы грамматика G(VN, VT, P, S) была LL(1)-грамматикой необ-
ходимо и достаточно, чтобы для каждого символа А∈VN, у которого в грамма-
тике существует более одного правила вида А→α1 | α2 |…| αn, выполнялось тре-
бование:

     FIRST(1, αiFOLLOW(1, A)) ∩ FIRST(1, αjFOLLOW(1, A)) = ∅,

32