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

Cинтаксический анализ для LL(1)-грамматики

Алгоритм синтаксического анализа на основе LL(K)-грамматики относится к классу алгоритмов нисходящего разбора.

Строкам управляющей таблицы М для грамматики G(V,T,P,S) /1/ ставятся в соответствие элементы множества VUTU$ ($-маркер дна стека), столбцам-элементы множества T U "lambda"("lambda" - пустая строка). Перед началом работы алгоритма в рабочий стек заносятся символы $ и S. Возможные значения элементов таблицы и их интерпретация алгоритмом разбора приведены в таблице 3.2.

Таблица 3.2

Для построения управляющей таблицы М по заданной LL(1)-грамматике G(V,T,P,S) можно воспользоваться следующим алгоритмом /1/.

1.Если <A>::=r-правило номер i заданной грамматики, то M(<A>,a)=i для всех a (кроме "lambda"), являющихся терминальными префиксами цепочек, выводимых из r. Если таким префиксом может быть "lambda", то М(<A>,b)=i для всех b, являющихся терминальными символами, которые могут встречаться непосредственно справа от <A>.

2.M(a,a)="сдвиг" для всех a, принадлежащих Т.

3.M($,"lambda")="допуск".

4.Оставшиеся незаполненными элементы таблицы М получают значение "ошибка".

Пример

Грамматика G(V,T,P,S) рассмотренного выше примера не обладает свойством LL(1),поскольку обе правые части для нетерминала<E> (правила 2 и 3) порождают цепочки, начинающиеся одним и тем же терминалом i. То же можно сказать и о правилах для терминала <T>.Преобразуем грамматику G(V,T,P,S) к грамматике G1(V1,T,P1,S), обладающей свойством LL(1).Правила последней примут вид :

1) <S>::=<E> 2) <E>::=<T><X> 3) <X>::=+<E> 4) <T>::=<F><Y>

5) <Y>::=*<T> 6) <F>::=i 7) <X>::="lambda" 8) <Y>::="lambda"

В соответствии с приведенным алгоритмом теперь можно построить управляющую таблицу для LL(1)-анализатора (таблица 3). Таблица 3

Незаполненные элементы таблицы имеют значение "ошибка". Проанализируем входную цепочку i*i с помощью алгоритма LL(1)-анализатора. При этом, для облегчения формирования выходного стека, при записи символа в рабочий стек будем снабжать его указателем на символ, являющийся его предком в синтаксическом дереве разбора. Процесс анализа проиллюстрируем таблицей 4.

Таблица 3.4

В результате анализа получено синтаксическое дерево разбора (рис.3.4.).

Рис.3.4. Синтаксическое дерево разбора

В выходном стеке это дерево представляется таблицей 3.5.

Таблица 3.5

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

Алгоритм синтаксического анализа на основе грамматики пред­шествования относится к классу алгоритмов восходящего разбора.

Строкам и столбцам управляющей таблицы М (матрицы отношений предшествования) ставятся в соответствие элементы множества T U V U $ (в строке - символ в вершине рабочего стека, в столбце - входной символ).

Каждую запись рабочего стека представим парой: (символ, знак отношения предшествования символа предыдущей записи стека с данным символом). Перед началом работы алгоритма в стек записывается пара ($,0).

Возможные значения элементов таблицы и их интерпретация ал­горитмом разбора приведены в таблице 4.1.

Таблица 4.1

Отношения предшествования Вирта-Вебера <., =., >. для КС- грамматики G(V,T,P,S) определяются на множестве V U T следующим образом /1/:

1) X<.Y, если в Р есть такое правило <A>::=rX<B>q, что Y является головным символом хотя бы одной из цепочек, выводимых из <B>;

2) X=.Y, если в Р есть правило <A>::=rXYq;

3) X>.a, если a - терминал, и в Р есть правило <A>::=r<B>Yq такое, что X является хвостовым символом хотя бы одной из цепочек, выводимых из <B>, а Y=at, или a является головным символом хотя бы одной из цепочек, выводимых из Y.

Для анализа входной цепочки методом предшествования удобно добавлять к ней левый и правый концевые маркеры ($). Будем считать, что $<.X для всех X, являющихся головными символами цепочек, выводимых из <S>, и Y>.$ для всех Y, являющихся хвостовыми символами таких цепочек.

КС-грамматика G(V,T,P,S) называется грамматикой предшествования, если она приведенная, не содержит "lambda"-правил, и для любой пары символов из T U V выполняется не более одного отношения предшествования Вирта-Вебера. Обратимая грамматика предшествования называется грамматикой простого предшествования.

Пример

Анализируя грамматику G(V,T,P,S) из п.1.1, заметим, что она не удовлетворяет определению грамматики предшествования, поскольку <T> =. + в соответствии с правилом 2) и <T>>. + в соответствии с правилами 2) и 4). Чтобы избавиться от этого конфликта, преобразуем эту грамматику к грамматике G2(V2,T,P2,S) с правилами:

1) <S>::=<E>

2) <E>::=<X>+<E>

3) <E>::=<X>

4) <T>::=<F>*<T>

5) <T>::=<F>

6) <F>::=i

7) <X>::=<T>

Матрица отношений предшествования для грамматики G2 представлена таблицей 4.2

Таблица4.2

Незаполненные элементы матрицы соответствуют парам символов грамматики, для которых не определены отношения предшествования. При использовании этой матрицы в качестве управляющей таблицы в алгоритме синтаксического анализа можно считать, что эти элементы содержат значение "ошибка", а M(<S>,$)="допуск".

Проанализируем входную цепочку i*i с использованием метода предшествования. Результат анализа представлен в таблице 4.3.

Таблица 4.3

В результате анализа получено синтаксическое дерево разбора (рис.4.1).

Рис.4.1. Синтаксическое дерево разбора

В выходном стеке это дерево представляется таблицей 4.4.

Таблица 4.4