6. Машино- зависимая оптимизация кода.

6. Ll(1) грамматики. Проверка свойств ll(1). Переходов.

LL(1)-грамматика - это такая КС(1)-грамматика, в которой множества выбора правил с одинаковыми левыми частями не пересекаются.

Если возможно написать детерминированный анализатор, осуществляющий разбор сверху вниз, для языка, генерируемого s-грамматикой, то такой анализатор принято называть LL(1)-грамматикой.

Обозначения в написании LL(1)-грамматики означают:

L – строки разбираются слева направо;

L – используются самые левые выводы;

1 – варианты порождающего правила выбираются с помощью одного предварительного просмотра символа.

Т.е. грамматику называют LL(1)-грамматикой, если для каждого нетерминала, появляющегося в левой части более одного порождающего правила, множество направляющих символов, соответствующих правым частям альтернативных порождающих правил, – непересекающиеся.

Множество терминальных символов предшественников определяется следующим образом.

,где А – нетерминал;

 - строка терминалов и/или нетерминалов;

- множество символов предшественников А.

Пример.

PAc PBd Aa

AAa Bb BbB

символы а и b – символы предшественники для Р.

Определение.

Если А – нетерминал, то его направляющими символами (DS) будут +(все символы, следующие за А, если А может генерировать пустую строку).

В общем случае для заданного варианта  и нетерминала Р (P) имеем

,

где F(P) есть множество символов, которые могут следовать за Р.

Пример.

TAB APQ ABC PpP Pe QqQ

Qe BbB Bd CcC Cf

Эта грамматика дает , , и .

Из определения LL(1)-грамматики следует, что эти грамматики можно разбирать детерминирован сверху вниз.

Синтаксический LL-анализатор (LL parser) — нисходящий синтаксический анализатор для подмножества контекстно-свободных грамматик. Он анализирует входной поток слева направо, и строит левый вывод грамматики. Класс грамматик, для которых можно построить LL-анализатор, известен как LL-грамматики.

Синтаксический LL-анализатор (LL parser) — нисходящий синтаксический анализатор для подмножества контекстно-свободных грамматик. Он анализирует входной поток слева направо, и строит левый вывод грамматики. Класс грамматик, для которых можно построить LL-анализатор, известен как LL-грамматики.

Далее описывается анализатор, в основе которого лежит построение таблиц; альтернативой может служить анализатор, построенный методом рекурсивного спуска, который обычно пишется вручную (хотя существуют и исключения, например, генератор синтаксических анализаторов ANTLR для LL(*) грамматик).

LL-анализатор называется LL(k)-анализатором, если данный анализатор использует предпросмотр на k токенов (лексем) при разборе входного потока. Грамматика, которая может быть распознана LL(k)-анализатором без возвратов к предыдущим символам, называется LL(k)-грамматикой. Язык, который может быть представлен в виде LL(k)-грамматики, называется LL(k)-языком. Существуют LL(k)-языки, которые не являются LL(k+n)-языками. Следовательно, не все контекстно-свободные языки являются LL(k)-языками.

LL(1)-грамматики очень распространены, потому что соответствующие им LL-анализаторы просматривают поток только на один символ вперед при принятии решения о том, какое правило грамматики необходимо применить. Языки, основанные на грамматиках с большим значением k, традиционно считались трудными для распознавания, хотя при широком распространении генераторов синтаксических анализаторов, поддерживающих LL(k) грамматики с произвольным k, это замечание уже неактуально.

LL-анализатор называется LL(*)-анализатором, если нет строгого ограничения для k и анализатор может распознавать язык, если токены принадлежат какому-либо регулярному множеству (например, используя детерминированные конечные автоматы).

Существуют противоречия между так называемой «Европейской школой» построения языков, которая основывается на LL-грамматиках, и «Американской школой», которая предпочитает LR-грамматики. Такие противоречия обусловлены традициями преподавания и деталями описания различных методов и инструментов в конкретных учебниках; кроме того, свое влияние оказал Н. Вирт из ETHZ, чьи исследования описывают различные методы оптимизации LL(1) распознавателей и компиляторов.

Синтаксический анализатор предназначен для разрешения проблемы принадлежности строки заданной грамматике и построения дерева вывода в случае принадлежности.

Синтаксический анализатор состоит из:

-Ленты (входного буфера) — содержит анализируемую строку

-Стек — служит для сохранения промежуточных данных синтаксического анализа

-Таблица синтаксического анализа — таблица, задающая однозначное соответствие правила грамматики для символа магазинного алфавита, находящегося на вершине стека, и текущего читаемого символа на ленте, или содержащая информацию об отсутствии такого правила для заданной пары символов.

В строках таблицы располагаются символы магазинного алфавита, а в столбцах — символы терминального алфавита.

При запуске синтаксического анализа, стек уже содержит два символа:[ S, $ ]

Где '$' — специальный терминал, служащий для указания конца стека, а 'S' — аксиома грамматики. Синтаксический анализатор пытается при помощи правил грамматики заменить в стеке аксиому на цепочку символов, аналогичную цепочке, находящейся на входной ленте, и затем полностью прочитать ленту, опустошая стек.