Грамматики предшествования




Большинство конструкций языков программирования может быть отнесено в один из классов КС-языков, для которых разработаны алгоритмы разбора, линейно зависящие от длины входной цепочки.

КС-языки делятся на классы в соответствии со структурой правил их грамматик. В каждом из классов налагаются дополнительные ограничения на допустимые правила грамматики.

Одним из таких классов является класс грамматик предшествования. Они используются для синтаксического разбора цепочек с помощью алгоритма “сдвиг-свертка”. Выделяют следующие типы грамматик предшествования:

· простого предшествования;

· расширенного предшествования;

· слабого предшествования;

· смешанной стратегии предшествования;

· операторного предшествования.

Далее будут рассмотрены ограничения на структуру правил и алгоритмы разбора для двух типов - грамматик простого и операторного предшествования.

Грамматикой простого предшествования называют такую КС-грамматику G (VN, VT, P,S), V = VTÈ VN в которой:

1. Для каждой упорядоченной пары терминальных и нетерминальных символов выполняется не более чем одно из трех отношений предшествования:

· Si = Sj (" Si,SjÎ V), если и только если $ правило U® xSiSjy Î P, где UÎ VN, x,yÎ V *;

· Si < Sj (" Si,SjÎ V), если и только если $ правило U® xSiDy Î P и вывод DÞ *Sjz, где U,DÎ VN, x,y,zÎ V *;

· Si > Sj (" Si,SjÎ V), если и только если $ правило U® xCSjy Î P и вывод CÞ *zSi или $ правило U® xCDy Î P и выводы CÞ *zSi и DÞ *Sjw, где U,C,DÎ VN, x,y,z,wÎ V *.

1. Различные порождающие правила имеют разные правые части.

Отношения =, < и > называют отношениями предшествования для символов. Отношение предшествования единственно для каждой упорядоченной пары символов. При этом между какими-либо двумя символами может и не быть отношения предшествования - это значит, что они не могут находиться рядом ни в одном элементе разбора синтаксически правильной цепочки. Отношения предшествования зависят от порядка, в котором стоят символы, и в этом смысле их нельзя путать со знаками математических операций - например, если Si > Sj, то не обязательно, что Sj < Si (поэтому знаки предшествования иногда помечают специальной точкой: =×, <×, × >)

Метод предшествования основан на том факте, что отношения предшествования между двумя соседними символами распознаваемой строки соответствуют трем следующим вариантам:

· Si < Si+1, если символ Si+1 - крайний левый символ некоторой основы;

· Si > Si+1, если символ Si - крайний правый символ некоторой основы;

· Si = Si+1, если символы Si и Si+1 принадлежат одной основе.

Исходя из этих соотношений выполняется разбор строки для грамматики предшествования.

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

Матрицу предшествования грамматики можно построить, опираясь непосредственно на определения отношений предшествования, но удобнее воспользоваться двумя дополнительными множествами - множеством крайних левых и множеством крайних правых символов относительно нетерминалов грамматики. Эти множества определяются следующим образом:

· L (U) = {T | $ UÞ *Tz}, U,TÎ V, zÎ V * - множество крайних левых символов относительно нетерминального символа U (цепочка z может быть и пустой цепочкой);

· R (U) = {T | $ UÞ *zT}, U,TÎ V, zÎ V * - множество крайних правых символов относительно нетерминального символа U.

Тогда отношения предшествования можно определить так:

· Si = Sj (" Si,SjÎ V), если $ правило U® xSiSjy Î P, где UÎ VN, x,yÎ V *;

· Si < Sj (" Si,SjÎ V), если $ правило U® xSiDy Î P и SjÎ L (D), где U,DÎ VN, x,yÎ V *;

· Si > Sj (" Si,SjÎ V), если $ правило U® xCSjy Î P и SiÎ R (C) или $ правило U® xCDy Î P и SiÎ R (C), SjÎ L (D), где U,C,DÎ VN, x,yÎ V *.

Такое определение отношений удобнее на практике, так как не требует построения выводов, а множества L (U) и R (U) могут быть построены для каждого нетерминального символа UÎ VN по очень простому алгоритму:

Шаг 1. Для каждого нетерминального символа U ищем все правила, содержащие U в левой части. Во множество L (U) включаем самый левый символ из правой части правил, а во множество R (U) - самый крайний символ правой части. Переходи к шагу 2.

Шаг 2. Для каждого нетерминального символа U: если множество L (U) содержит нетерминальные символы грамматики U’,U”,..., то его надо дополнить символами, входящими в соответствующие множества L (U’), L (U”),... и не входящими в L (U). Ту же операцию надо выполнить для R (U).

Шаг 3. Если на предыдущем шаге хотя бы одно множество L (U) или R (U) для некоторого символа грамматики изменилось, то надо вернуться к шагу 2, иначе построение закончено.

После построения множеств L (U) и R (U) по правилам грамматики создается матрица предшествования. Матрицу предшествования дополняют символами ^ н и ^ к (начало и конец цепочки). Для них определены следующие отношения предшествования:

^ н < a, " aÎ V, если $ SÞ *ax, где SÎ VN, xÎ V * или (с другой стороны) если aÎ L (S);

^ к > a, " aÎ V, если $ SÞ *xa, где SÎ VN, xÎ V * или (с другой стороны) если aÎ R (S).

 

Грамматикой операторного предшествования называется приведенная КС-грамматика без l-правил, в которой правые части продукций не содержат смежных нетерминальных символов. Для грамматики операторного предшествования отношения предшествования можно задать на множестве терминальных символов (включая символы ^ н и ^ к).

Отношения предшествования для грамматики операторного предшествования G (VN, VT, P,S) задаются следующим образом:

· a = b, если и только если существует правило U® xaby Î P или правило U® xaCby, где a,bÎ VT, U,CÎ VN, x,yÎ V *;

· a < b, если и только если существует правило U® xaCy Î P и вывод CÞ *bz или вывод CÞ *Dbz, где a,bÎ VT, U,C,DÎ VN, x,y,zÎ V *;

· a > b, если и только если существует правило U® xCby Î P и вывод CÞ *za или вывод CÞ *zaD, где a,bÎ VT, U,C,DÎ VN, x,y,zÎ V *.

В грамматике операторного предшествования различные порождающие правила имеют разные правые части. Для грамматики операторного предшествования тоже строится матрица предшествования, но она содержит только терминальные символы грамматики.

Для построения этой матрицы удобно ввести множества крайних левых и крайних правых терминальных символов относительно нетерминального символа U - L t(U) или R t(U):

· L t(U) = {t | $ UÞ *tz или $ UÞ *Ctz }, где tÎ VT, U,CÎ VN, zÎ V *;

· R t(U) = {t | $ UÞ *zt или $ UÞ *ztC }, где tÎ VT, U,CÎ VN, zÎ V *.

Тогда определения отношений операторного предшествования будут выглядеть так:

· a = b, если $ правило U® xaby Î P или правило U® xaCby, где a,bÎ VT, U,CÎ VN, x,yÎ V *;

· a < b, если $ правило U® xaCy Î P и bÎ L t(C), где a,bÎ VT, U,CÎ VN, x,yÎ V *;

· a > b, если $ правило U® xCby Î P и aÎ R t(C), где a,bÎ VT, U,CÎ VN, x,yÎ V *.

В данных определениях цепочки символов x,y,z могут быть и пустыми цепочками.

Для нахождения множеств L t(U) и R t(U) используется следующий алгоритм:

Шаг 1. Для каждого нетерминального символа грамматики U строятся множества L (U) и R (U).

Шаг 2. Для каждого нетерминального символа грамматики U ищутся правила вида U® tz и U® Ctz, где tÎ VT, CÎ VN, zÎ V *; терминальные символы t включаются во множество L t(U). Аналогично для множества R t(U) ищутся правила вида U® zt и U® ztC.

Шаг 3. Просматривается множество L (U), в которое входят символы U’,U”,... Множество L t(U) дополняется символами, входящими в L t(U’), Lt (U”),... и не входящими в L t(U). Аналогичная операция выполняется и для множества R t(U) на основе множества R (U).

Для практического использования матрицу предшествования дополняют символами ^ н и ^ к (начало и конец цепочки). Для них определены следующие отношения предшествования:

^ н < a, " aÎ VT, если $ SÞ *ax или $ SÞ *Cax, где S,CÎ VN, xÎ V * или если aÎ L t(S);

^ к > a, " aÎ VT, если $ SÞ *xa или $ SÞ *xaC, где S,CÎ VN, xÎ V * или если aÎ R t(S).

 

Алгоритм “сдвиг-свертка” для грамматик простого и операторного предшествования

Алгоритм “сдвиг-свертка” для грамматики простого предшествования. Данный алгоритм выполняется МП-автоматом с одним состоянием. Отношения предшествования служат для того, чтобы определить в процессе выполнения алгоритма, какое действие - сдвиг или свертка - должно выполняться на данном шаге и однозначно выбрать правило при свертке. В начальном состоянии автомата считывающая головка обозревает первый символ, в конец цепочки помещен символ ^ к.

Разбор считается законченным (алгоритм завершается), если считывающая головка автомата обозревает символ ^ н и при этом больше не может быть выполнена свертка. Решение о принятии цепочки зависит от содержимого стека. Автомат принимает цепочку, если в результате завершения алгоритма он находится в конечном состоянии, когда в стеке находятся начальный символ грамматики S и символ ^ н. Выполнение алгоритма может быть прервано, если на одном из его шагов возникнет ошибка. Тогда входная цепочка не принимается.

Алгоритм состоит из следующих шагов:

Шаг 1. Поместить в верхушку стека символ ^ н.

Шаг 2. Сравнить символ, находящийся на вершине стека, с текущим символом ленты.

Шаг 3. Если имеет место отношение < или =, то произвести перенос и вернуться к шагу 2.

Шаг 4. Если имеет место отношение >, то произвести свертку, то есть найти на вершине стека все символы, связанные отношением = (основу) и заменить их на левую часть соответствующего правила грамматики (если символов, связанных отношением =, на верхушке стека нет, то для правила используется один, верхний символ). Если разбор не закончен, то вернуться к шагу 2.

Ошибка в процессе выполнения алгоритма возникает, когда невозможно выполнить очередной шаг - например, если не установлено отношение предшествования между двумя сравниваемыми символами (на шагах 2 и 4) или если не удается найти нужное правило в грамматике (на шаге 4). Тогда выполнение алгоритма немедленно прерывается.

Алгоритм “сдвиг-свертка” для грамматики операторного предшествования в целом похож на алгоритм для грамматик простого предшествования. Он выполняется тем же МП-автоматом и имеет те же условия завершения и обнаружения ошибок. Основное отличие состоит в том, что при работе со стеком в этом алгоритме не принимаются во внимание находящиеся в нем нетерминальные символы, и при сравнении ищется ближайший к верхушке стека терминальный символ. Однако после выполнения сравнения и определения границ основы при поиске правила в грамматике нетерминальные символы следует, безусловно, принимать во внимание.

Шаг 1. Поместить в верхушку стека символ ^ н.

Шаг 2. Сравнить символ, находящийся на вершине стека, игнорируя все нетерминальные символы, с текущим символом ленты.

Шаг 3. Если имеет место отношение < или =, то произвести перенос и вернуться к шагу 2.

Шаг 4. Если имеет место отношение >, то произвести свертку, то есть найти на вершине стека (опять же игнорируя нетерминальные символы) все символы, связанные отношением = (основу) и заменить их на левую часть соответствующего правила грамматики (при выборе правила нетерминальные символы должны учитываться). Если разбор не закончен, то вернуться к шагу 2.

Конечная конфигурация автомата совпадает с конфигурацией при распознавании цепочек грамматик простого предшествования.

 

Пример построения распознавателя для грамматики операторного предшествования.

Рассмотрим в качестве примера грамматику G ({S,B,T,J},{ -, &, ^, (, ), p }, P,S) (терминальные символы выделены жирным шрифтом):

P: S ® - B (правило 1)
B ® T | B & T (правила 2 и 3)
T ® J | T ^ J (правила 4 и 5)
J ® ( B ) | p (правила 6 и 7)

Видно, что эта грамматика является грамматикой операторного предшествования.

Построим множества крайних левых и крайних правых символов L (U), R (U) относительно всех нетерминальных символов грамматики. Результат построения приведен в табл. 2.

На основе полученных множеств построим множества крайних левых и крайних правых терминальных символов L t(U), R t(U) относительно всех нетерминальных символов грамматики. Результат (второй и третий шаги построения) приведен в табл. 3.

Таблица 2.

Множества крайних правых и крайних левых символов грамматики (по шагам построения)

Символ Шаг 1 (начало построения) Последний шаг (результат)
(U) L(U) R(U) L(U) R(U)
J (p ) p (p ) p
T J T J J T (p J) p
B T B T T B J (p T J) p
S - B - B T J) p
                   

Таблица 3.

Множества крайних правых и левых терминальных символов грамматики (по шагам построения)

Символ Шаг 1 (начало построения) Последний шаг (результат)
(U) Lt(U) Rt(U) Lt(U) Rt(U)
J (p ) p (p ) p
T ^ ^ ^ (p ^) p
B & & & ^ (p & ^) p
S - - - - & ^) p
                   

На основе этих множеств и правил грамматики G построим матрицу предшествования грамматики (табл. 4).

Таблица 4.

Матрица предшествования грамматики

Символы - & ^ ( ) p ^ к
-   < < <   < >
&   > < < > < >
^   > > < > < >
(   < < < = <  
)   > >   >   >
p   > >   >   >
^ н <            

Посмотрим, как заполняется матрица предшествования в табл. 4 на примере символа &. В правиле грамматики B ® B & T (правило 3) этот символ стоит слева от нетерминального символа T. В множество L t(T) входят символы: ^ (p. Ставим знак < в клетках матрицы, соответствующих этим символам, в строке для символа &. В то же время в этом же правиле символ & стоит справа от нетерминального символа B. В множество R t(B) входят символы: & ^) p. Ставим знак > в клетках матрицы, соответствующим этим символам, в столбце для символа &. Больше символ & ни в каком правиле не встречается, значит заполнение матрицы для него закончено, берем следующий символ и продолжаем заполнять матрицу таким же методом.

Алгоритм разбора цепочек грамматики операторного предшествования игнорирует нетерминальные символы. Поэтому имеет смысл преобразовать исходную грамматику таким образом, чтобы оставить в ней только один нетерминальный символ. Тогда получим следующий вид правил:

P: E ® - E (правило 1)
E ® E | E & E (правила 2 и 3)
E ® E | E ^ E (правила 4 и 5)
E ® ( E ) | p (правила 6 и 7)

Это преобразование не ведет к созданию эквивалентной грамматики и выполняется только после построения всех множеств и матрицы предшествования. Само преобразование выполняется только с целью более эффективного выполнения алгоритма разбора, в который уже заложены необходимые данные о порядке применения правил при создании матрицы предшествования.

Рассмотрим работу алгоритма распознавания на примерах. Последовательность разбора будем записывать в виде последовательности конфигураций МП-автомата из трех составляющих: не просмотренная автоматом часть входной цепочки, содержимое стека и последовательность правил грамматики. Так как автомат имеет только одно состояние, то для определения его конфигурации достаточно двух составляющих - положения считывающей головки во входной цепочке и содержимого стека, - но последовательность номеров правил несет дополнительную полезную информацию, которая должна быть затем использована компилятором на последующих этапах для семантической обработки и для генерации кода объектной программы. (Кроме того, последовательность примененных правил делает пример более наглядным).

Будем обозначать такт автомата символом ¸. Введем также дополнительное обозначение ¸ п, если на данном такте выполнялся перенос, и ¸ с, если выполнялась свертка.

Последовательности разбора цепочек входных символов будут, таким образом, иметь вид:

Пример 1. Входная цепочка -p&p^(p).

{ -p&p^(p)^ к; ^ н; Æ } ¸ п { p&p^(p)^ к; ^ н -; Æ } ¸ п { &p^(p)^ к; ^ н -p; Æ } ¸ с { &p^(p)^ к; ^ н - E; 7} ¸ п { p^(p)^ к; ^ н - E &; 7} ¸ п { ^(p)^ к; ^ н - E &p; 7} ¸ с { ^(p)^ к; ^ н - E & E; 7,7} ¸ п { (p)^ к; ^ н - E & E ^; 7,7} ¸ п { p)^ к; ^ н - E & E ^(; 7,7} ¸ п { )^ к; ^ н - E & E ^(p; 7,7} ¸ с { )^ к; ^ н - E & E ^( E; 7,7,7} ¸ п
{^ к; ^ н - E & E ^( E ); 7,7,7} ¸ c {^ к; ^ н - E & E ^ E; 7,7,7,6} ¸ с {^ к; ^ н - E & E; 7,7,7,6,5} ¸ п
{^ к; ^ н - E; 7,7,7,6,5,3} ¸ с {^ к; ^ нE; 7,7,7,6,5,3,1}

Пр имер 2. Входная цепочка -p^p(p).

{ -p^p(p)^ к; ^ н; Æ } ¸ п { p^p(p)^ к; ^ н -; Æ } ¸ п { ^p(p)^ к; ^ н -p; Æ } ¸ с { ^p(p)^ к; ^ н - E; 7} ¸ п
{ p(p)^ к; ^ н - E ^; 7} ¸ п { (p)^ к; ^ н - E ^p; 7} - ошибка! (нет отношения для пары символов { p, ( })

Пример 3. Входная цепочка -p^p&p.

{ -p^p&p^ к; ^ н; Æ } ¸ п { p^p&p^ к; ^ н -; Æ } ¸ п { ^p&p^ к; ^ н -p; Æ } ¸ с { ^p&p^ к; ^ н - E; 7} ¸ п
{ p&p^ к; ^ н - E ^; 7} ¸ п { &p^ к; ^ н - E ^p; 7} ¸ с { &p^ к; ^ н - E ^ E; 7,7} ¸ с { &p^ к; ^ н - E; 7,7,5} ¸ п
{ p^ к; ^ н - E &; 7,7,5} ¸ п {^ к; ^ н - E &p; 7,7,5} ¸ с {^ к; ^ н - E & E; 7,7,5,7} ¸ с {^ к; ^ н - E; 7,7,5,7,3} ¸ c
{^ к; ^ нE; 7,7,5,7,3,1}

Пример 4. Входная цепочка -p&p^p.

{ -p&p^p^ к; ^ н; Æ } ¸ п { p&p^p^ к; ^ н -; Æ } ¸ п { &p^p^ к; ^ н -p; Æ } ¸ с { &p^p^ к; ^ н - E; 7} ¸ п
{ p^p^ к; ^ н - E &; 7} ¸ п { ^p^ к; ^ н - E &p; 7} ¸ с { ^p^ к; ^ н - E & E; 7,7} ¸ п { p^ к; ^ н - E & E ^; 7,7} ¸ п
{^ к; ^ н - E & E ^p; 7,7} ¸ с {^ к; ^ н - E & E ^ E; 7,7,7} ¸ с {^ к; ^ н - E & E; 7,7,7,5} ¸ п {^ к; ^ н - E; 7,7,7,5,3} ¸ c
{^ к; ^ нE; 7,7,7,5,3,1}

Два последних примера наглядно демонстрируют, что приоритет операций, установленный в грамматике, влияет на последовательность разбора и последовательность применения правил.

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-27 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: