Определение LL(k)-грамматики

Определение КС-грамматика обладает свойством LL (k) для некоторого k >0, если на каждом шаге вывода для однозначного выбора очередной альтернативы МП-автомату достаточно знать символ на верхушке стека и рассмотреть первые k символов от текущего положения считывающей головки во входной строке.

Определение КС-грамматика называется LL (k) - грамматикой, если она обладает свойством LL (k) для некоторого k >0.

В основе распознавателя LL (k) - грамматик лежит левосторонний разбор строки языка. Исходной сентенциальной формой является начальный символ грамматики, а целевой – заданная строка языка. На каждом шаге разбора правило грамматики применяется к самому левому нетерминалу сентенции. Данный процесс соответствует построению дерева разбора цепочки сверху вниз (от корня к листьям). Отсюда и произошла аббревиатура LL (k): первая «L» (от слова «left») означает левосторонний ввод исходной цепочки символов, вторая «L» - левосторонний вывод в процессе работы распознавателя.

Определение Для построения распознавателей для LL (k) - грамматик используются два множества:

- FIRST (k, a) – множество терминальных цепочек, выводимых из цепочки a Î(V_T È V_N)*, укороченных до k символов;

- FOLLOW (k, A) – множество укороченных до k символов терминальных цепочек, которые могут следовать непосредственно за A Î V_N в цепочках вывода.

Формально эти множества можно определить следующим образом:

- FIRST (k, a) = { w Î V_T* | $ вывод a Þ* w и | w | £ k или $ вывод a Þ* wx и | w | = k; x, a Î (V_T È V_N)*, k > 0};

- FOLLOW (k, A) = { w Î V_T * | $ вывод S Þ* aAg и w Î FIRST (k, g); a, g Î V*, A Î V_N, k >0}.