Файл: Отчеты оформляются в виде файлов формата Microsoft Word (файлы других форматов не принимаются), размер шрифта 1214.docx

3. 
   Понятие конфигурации. Связь между конфигурациями, состояниями и операциями восходящего парсера
   

Для иллюстрации процессов, протекающих при построении восходящего парсера, будем использовать грамматику языка арифметических выражений G _a1 с добавленным специальным правилом вида Z : S ► (табл. 5.1.)


Таблица 5.1.

Грамматика Ga1
0	Z : S EOF
1	S : S + T
2	S : T
3	T : T * V
4	T : V
5	V : ( S )
6	V : ident
7	V : const

Под конфигурацией понимается правило грамматики, в котором в произвольной точке правой части помещен дополнительный метасимвол – маркер. Маркером отмечается возможное разбиение правой части правила в процессе восходящего синтаксического анализа на две цепочки: «прочитанную/обработанную» (находящуюся слева от маркера) и еще не обработанную, находящуюся справа от маркера. Ясно, что если правая часть правила содержит ровно k символов (k = 0, 1, 2, …), то из этого правила может быть образовано в точности k+1 различных конфигураций. Например, из правила S : S + T можно образовать следующие конфигурации (в качестве маркера используется символ ▼):

S : ▼ S + T

S : S ▼ + T

S : S + ▼ T

S : S + T ▼

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

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

4. 
   Связи между конфигурациями и операциями.
   

---

Если в некоторой конфигурации маркер находится перед терминалом (N :  ▼t ), то в состоянии номер m, которому соответствует эта конфигурация, должна выполняться операция Shift, осуществляющая переключение автомата в такое состояние, которому соответствует конфигурация с маркером, размещенным после этого терминала (N :  t▼ ),. Знак этой операции должен находиться в той клетке управляющей таблицы, которая расположена на пересечении строки состояния m со столбцом, помеченным терминальным символом t (или номером, приписанным этому терминалу).

Если маркер в конфигурации N :  ▼M  находится перед нетерминалом, то в соответствующем ей состоянии m должна выполняться операция Go, осуществляющая переключение автомата в такое состояние, которому соответствует конфигурация с маркером, размещенным после этого нетерминала, т. е. N :  M▼ . Знак этой операции должен находиться в той клетке управляющей таблицы, которая расположена на пересечении строки состояния m со столбцом, помеченным нетерминальным символом M (или его номером).

И, наконец, если маркер в конфигурации находится после последнего символа правила, то в соответствующем этой конфигурации состоянии должна выполняться операция свертки Rk,n, удаляющая из стека k номеров состояний (ровно столько символов в правой части соответствующего правила), переключающая автомат в состояние, номер которого оказался на верхушке стека после этого удаления, и готовящая номер столбца n управляющей таблицы для последующей операции Go.

5. 
   Связи между конфигурациями и состояниями автомата.
   

Допустим, что каким-либо образом некоторому состоянию поставлена в соответствие определенная конфигурация. Если эта конфигурация имеет вид

N :  ▼ M  ,

где M – нетерминальный символ, и в грамматике есть правила:

M : γ₁

M : γ₂

...

M : γ_n ,

то все конфигурации вида M : ▼ γ₁ , M : ▼ γ₂ , ... M : ▼ γ_n также должны быть поставлены в соответствие этому состоянию автомата.

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

---

N :  ▼ M .

Поскольку входная цепочка правильна, ее продолжение (а автомат в этот момент находится перед первым символом этого продолжения) обязано выводиться из цепочки M . Следовательно, оно выводится из одной из цепочек вида γ_i .

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

Конфигурации вида M : ▼ γ_i называются дочерними по отношению к исходной (родительской) конфигурации вида N :  ▼ M .

Если в какой-либо из вновь образованных конфигураций вида M : ▼ γ_i маркер находится перед нетерминалом L (цепочка γ_i начинается с этого нетерминала), то данному состоянию автомата должны быть поставлены в соответствие и все конфигурации вида L : ▼ λ_j (дочерние по отношению к M : ▼ γ_i).

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

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

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

Каждая из конфигураций последнего подмножества (если оно не пусто), имеющая вид X : χ ▼, указывает на необходимость выполнения автоматом, оказавшимся в данном состоянии, операции свертки вида

---

Rk,n_x. Здесь k – длина цепочки χ, а n_x – номер колонки управляющей таблицы автомата, поставленной в соответствие нетерминальному символу X.

Наличие нескольких различных конфигураций в этом подмножестве является причиной возникновения конфликтов типа свертка/свертка.

Вернемся к таким конфигурациям данного состояния, в которых маркер находится перед одним и тем же символом w. Очевидно, что если автомат в процессе работы оказался в данном состоянии и его текущим входным символом является w, то должна быть выполнена операция Shift, если w – терминал, или Go, если w – нетерминал. Выполнение такой операции переключает автомат в некоторое другое состояние С, номер которого заносится на верхушку стека.

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

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

В силу того что база начального состояния автомата всегда известна – ею является конфигурация Z : ▼ S ►, на основе рассмотренных связей между состояниями, операциями и конфигурациями может быть построена процедура преобразования грамматики в управляющую таблицу восходящего синтаксического акцептора.

Эта процедура выполняется в два этапа.

Этап 1. Формирование подмножеств конфигураций, соответствующих состояниям автомата. Определение набора состояний.

Этап 2. Преобразование таблицы конфигураций в управляющую таблицу восходящего акцептора.

6. 
   Этап 1. Определение набора состояний восходящего акцептора
   

Подмножества конфигураций, соответствующих состояниям автомата, будем формировать в табличном представлении.

Начальное состояние таблицы подмножеств конфигураций (далее – просто таблицы конфигураций) для любой грамматики (с точностью до наименования начального нетерминала грамматики) определяется добавочным правилом и выглядит, как показано в табл. 5.2.

---

Таблица 5.2.

Состояние	Образовано		База	Конфигурация	Символ	Отм.
	Из	Через
0			Да	Z : ▼ S ►	S

Назначение колонок таблицы конфигураций.

Состояние – содержит номер, присвоенный состоянию автомата, определяемому подмножеством конфигураций.

Образовано – показывает, из подмножества конфигураций какого состояния образовано данное состояние путем переноса маркера через какой символ (эти сведения понадобятся при формировании знаков операций).

База – просто отметка Да, если конфигурация, записанная в строке, является базовой для данного состояния.

Конфигурация – пояснения не требуется.

Символ – вспомогательная колонка, содержащая тот символ грамматики, перед которым в данной конфигурации находится маркер.

Отм. – также вспомогательная колонка. Ее назначение станет ясно из описания процедуры.

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

Шаг 1. Замыкание. Просматриваются все конфигурации нового состояния автомата, и если в какой-либо из них маркер находится перед нетерминалом, то каждое правило грамматики, имеющее этот нетерминал в левой части, преобразуется в конфигурацию путем помещения маркера перед первым символом правой части. Для каждой вновь образованной конфигурации просматриваются все строки таблицы данного состояния. Если вновь образованной конфигурации нет ни в одной такой строке, то формируется новая строка. Новая конфигурация заносится в соответствующую клетку этой строки, а в клетку колонки, обозначенной Символ, заносится первый символ правой части правила (если правило имеет вид N : ε, то эта клетка остается пустой), все остальные клетки новой строки оставляются пустыми. Этот шаг выполняется для данного состояния до тех пор, пока не перестанут добавляться новые строки.

---