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




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

Разбор считается законченным (алгоритм завершается), если считывающая головка автомата обозревает символ ^н и при этом больше не может быть выполнена свертка. Решение о принятии цепочки зависит от содержимого стека. Автомат принимает цепочку, если в результате завершения алгоритма он находится в конечном состоянии, когда в стеке находятся начальный символ грамматики 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 Нарушение авторских прав и Нарушение персональных данных


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