[AK1]LL(k) - Грамматики.
    
    Определение LL(k)-грамматик.
    Для начала предположим, что G=(N,E,P,S) - однозначная грамматика и w=a1,a2...an - цепочка из L(G). Тогда существует единственная последовательность левовыводимых цепочек b0,b1..bm, для которой S=b0,bi,pi ==> bi+1 при 0wb`a`==>wx (2) S==>wAa`==>wc`a`==>wy для которых FIRST(x)=FIRST(y), вытекает что b`=c`. Иначе это определение выражает то, что для имеющейся цепочки и зная следующие k символов можно применить не более одного правила вывода. Грамматика называется LL- грамматикой, если она LL(k)- грамматика для некоторого k.
    ПРМ: Пусть G состоит из правил S?aAS|b, A?a|bSA. Интуитивно G является LL(1)- грамматикой, потому что, коль скоро дан самый левый нетерминал С в левовыводимой цепочке и следующий входной символ с, существует не более одного правила, применимого к С и приводящего к терминальной цепочке, начинающейся символом с. Переходя к определению LL(1)- грамматики, мы видим, что если S==>wSa`==>wb`a`==>wx и S==>wSa`==>wc`a`==>wy и цепочки x и y начинаются одним и тем же символом , то должно быть b`=c`. В данном случае если x и y начинаются символом a, то в выводе участвовало правило S?aAS и b`=c`=aAS. Альтернатива S?b здесь невозможна. С другой стороны, если x и y начинаются с b, то должно применяться правило S?b и b`=c`=b. Заметим, что случай x=y=e здесь невозможен, так как из S в грамматике G не выводится e.
    Когда рассматриваются два вывода S==>wAa`==>wc`a`==>wy рассуждение аналогично. Грамматика G служит примером так называемой простой LL(1)- грамматики (или разделенной грамматики).
    ОПР: КС-грамматика G=(N,E,P,S) без e-правил называется простой LL(k) - грамматикой ( или разделенной грамматикой ), если для каждого A?N все его альтернативы начинаются различными терминальными символами.
    
    Предсказывающие алгоритмы разбора.
    Разбор для LL(k)-грамматики очень удобно осуществлять с помощью так называемого k- предсказывающего алгоритма разбора. k-предсказывающий алгоритм использует входную ленту, магазин и выходную ленту. Алгоритм пытается проследить вывод цепочки, записанной на его входной ленте. При чтении анализируемой цепочки входная головка может "заглядывать" вперед на очередные k символа. Эти символы называют аванцепочкой. Алгоритм имеет конфигурацию представляемую тройкой (x,Xa,n), где
    x - неиспользованная часть входной цепочки
    Xa - цепочка в магазине и Х - верхний символ
    n - цепочка на выходной ленте
    Работой k- предсказывающего алгоритма руководит управляющая таблица, которая задает соответствие между множеством
    {(верхний символ магазина)Х(аванцепочка)}
    и множеством
    {(правая часть правила и его номер)|ошибка|выброс|допуск}.
    Алгоритм является корректным для грамматики, если для любой цепочки из этой грамматики алгоритм позволяет получить упорядоченный список правил для ее разбора. Если работой некоего алгоритма руководит какая-то таблица и этот алгоритм оказывается корректным для рассматриваемой грамматики, то таблицу называют корректной.
    ПРМ:
    Пусть дана грамматика с правилами : (1) S?aAS (2) S?b (3) A?a (4) A?bSA
    Для такой грамматики будет построена таблица: аванцепочка a b e верхний S aAS,1 b,2 ошибка символ A a,3 bSA,4 ошибка магазина a выброс ошибка ошибка b ошибка выброс ошибка
     $ ошибка ошибка допуск
    По такой таблице будет проведен анализ:
    (abbab,S$,e) |-( abbab,aAS$,1)
    |-( bbab,AS$,1)
    |-( bbab,bSAS$,14)
    |-( bab,SAS$,14)
    |-( bab,bAS$,142)
    |-( ab,AS$,142)
    |-( ab,aS$,1423)
    |-( b,S$,1423)
    |-( b,b$,14232)
    |-( e,$,14232)
    k- предсказывающий алгоритм разбора КС-грамматики G можно моделировать на детерминированном МП- преобразователе с концевым маркером на входной ленте. ............