Книга: Системное программное обеспечение. Лабораторный практикум

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

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

Алгоритм «сдвиг-свертка» для грамматики операторного предшествования выполняется МП-автоматом с одним состоянием. Для моделирования его работы необходима входная цепочка символов и стек символов, в котором автомат может обращаться не только к самому верхнему символу, но и к некоторой цепочке символов на вершине стека.

Этот алгоритм для заданной КС-грамматики G(VT,VN,P,S) при наличии построенной матрицы предшествования можно описать следующим образом:

1. Поместить в верхушку стека символ «начало строки», считывающую головку МП-автомата поместить в начало входной цепочки (текущим входным символом становится первый символ входной цепочки). В конец входной цепочки надо дописать символ «конец строки».

2. В стеке ищется самый верхний терминальный символ s_j (если на вершине стека лежат нетерминальные символы, они игнорируются и берется первый терминальный символ, находящийся под ними), при этом сам символ s_j остается в стеке. Из входной цепочки берется текущий символ a_i (справа от считывающей головки МП-автомата).

3. Если символ s_j – это символ начала строки, а символ a_i – символ конца строки, то алгоритм завершен, входная цепочка символов разобрана.

4. В матрице предшествования ищется клетка на пересечении строки, помеченной символом s_j, и столбца, помеченного символом a_i (выполняется сравнение текущего входного символа и терминального символа на верхушке стека).

5. Если клетка, найденная на шаге 3, пустая, то значит, входная строка символов не принимается МП-автоматом, алгоритм прерывается и выдает сообщение об ошибке.

6. Если клетка, найденная на шаге 3, содержит символ «=.» («составляет основу») или «<.» («предшествует»), то необходимо выполнить перенос (сдвиг). При выполнении переноса текущий входной символ a_i помещается на верхушку стека, считывающая головка МП-автомата во входной цепочке символов сдвигается на одну позицию вправо (после чего текущим входным символом становится следующий символ a_i+1, i:= i+ 1). После этого надо вернуться к шагу 2.

7. Если клетка, найденная на шаге 3, содержит символ «.>» («следует»), то необходимо произвести свертку. Для выполнения свертки из стека выбираются все терминальные символы, связанные отношением «=.» («составляет основу»), начиная от вершины стека, а также все нетерминальные символы, лежащие в стеке рядом с ними. Эти символы вынимаются из стека и собираются в цепочку ? (если в стеке нет символов, связанных отношением «=.», то из него вынимается один самый верхний терминальный символ и лежащие рядом с ним нетерминальные символы).

8. Во всем множестве правил Р грамматики G(VT,VN,P,S) ищется правило, у которого правая часть совпадает с цепочкой ? (по условиям грамматик предшествования все правые части правил должны быть различны, поэтому может быть найдено или одно такое правило, или ни одного). Если правило найдено, то в стек помещается нетерминальный символ из левой части правила, иначе, если правило не найдено, это значит, что входная строка символов не принимается МП-автоматом, алгоритм прерывается и выдает сообщение об ошибке. Следует отметить, что при выполнении свертки считывающая головка автомата не сдвигается и текущий входной символ a_i остается неизменным. После выполнения свертки необходимо вернуться к шагу 2.

После завершения алгоритма решение о принятии цепочки зависит от содержимого стека. Автомат принимает цепочку, если в результате завершения алгоритма он находится в состоянии, когда в стеке находятся начальный символ грамматики S и символ

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

Алгоритм «сдвиг-свертка» для грамматики операторного предшествования игнорирует нетерминальные символы. Поэтому имеет смысл преобразовать исходную грамматику таким образом, чтобы оставить в ней только один нетерминальный символ. Это преобразование заключается в том, что все нетерминальные символы в правилах грамматики заменяются на один нетерминальный символ (чаще всего – целевой символ грамматики).

Построенная в результате такого преобразования грамматика называется остовной грамматикой, а само преобразование – остовным преобразованием [1, 7].

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

По результатам остовного разбора можно построить соответствующий ему вывод на основе правил исходной грамматики. Однако эта задача не представляет практического интереса, поскольку остовной вывод отличается от вывода на основе исходной грамматики только тем, что в нем отсутствуют шаги, связанные с применением цепных правил, и не учитываются типы нетерминальных символов. Для компиляторов же распознавание цепочек входного языка заключается не в нахождении того или иного вывода, а в выявлении основных синтаксических конструкций исходной программы с целью построения на их основе цепочек языка результирующей программы. В этом смысле типы нетерминальных символов и цепные правила не несут никакой полезной информации, а напротив, только усложняют обработку цепочки вывода. Поэтому для реального компилятора нахождение остовного вывода является даже более полезным, чем нахождение вывода на основе исходной грамматики. Найденный остовной вывод в дальнейших преобразованиях уже не нуждается.[4]

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

1. На основе множества правил грамматики Р построить множества крайних левых и крайних правых символов для всех нетерминальных символов грамматики

2. На основе множества правил грамматики Р и построенных на шаге 1 множеств L(U) и R(U) построить множества крайних левых и крайних правых терминальных символов для всех нетерминальных символов грамматики

: L_t(U) и R_t(U).

3. На основе построенных на шаге 2 множеств L_t(U) и R_t(U) для всех терминальных символов грамматики

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

4. Исходная грамматика G(VT,VN,P,S) преобразуется в остовную грамматику G'(VT,{S},P,S) с одним нетерминальным символом.

5. На основе построенной матрицы предшествования и остовной грамматики строится распознаватель на базе алгоритма «сдвиг-свертка» для грамматик операторного предшествования.

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

Далее в примере выполнения работы проиллюстрирован именно такой подход к построению распознавателя.

Оглавление книги