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

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

… S + T * …,

в цепочку вида

… S * …

В этой цепочке сразу после нетерминала S следует знак операции умножения *. Однако множество последователей нетерминала S содержит только символы +, ) и ►. Символа * в этом множестве нет.

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

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

Используя множества последователей нетерминалов, применим модифицированный шаг 3 процедуры преобразования таблицы конфигураций в управляющую таблицу автомата к грамматике G_a1. Теперь не возникают ранее фиксировавшиеся конфликты типа сдвиг/свертка, и управляющая таблица автомата получает вид, показанный в табл. 5.6.

Теперь автомат является детерминированным.

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

N : ▼

M : ▼,

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

Таблица 5.6.

0

1

2

3

4

5

6

7

8

9

S

T

V

+

*

(

)

i

c

►

0

G1

G2

G3

S4

S5

S6

1

S7

Stop

2

R1,0

S8

R1,0

R1,0

3

R1,1

R1,1

R1,1

R1,1

4

G9

G2

G3

S4

S5

S6

5

R1,2

R1,2

R1,2

R1,2

6

R1,2

R1,2

R1,2

R1,2

7

G10

G3

S4

S5

S6

8

G11

S4

S5

S6

9

S7

S12

10

R3,0

S8

R3,0

R3,0

11

R3,1

R3,1

R3,1

R3,1

12

R3,2

R3,2

R3,2

R3,2

---

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

Использование множеств последователей для занесения знаков операций свертки в управляющую таблицу восходящего синтаксического акцептора автоматически разрешает вопрос о возможности использования в грамматике правил вида N : ε.

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

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

9. 
   LR(0)- и SLR(1)-грамматики и автоматы
   

Если при преобразовании грамматики G в управляющую таблицу восходящего синтаксического акцептора не возникает ни одного конфликта типа сдвиг/свертка или свертка/свертка даже без использования множеств последователей нетерминальных символов для расстановки знаков операций свертки, то G называется LR(0)-грамматикой.

Здесь буква L является сокращением английского слова Left и означает, что входная цепочка символов обрабатывается слева направо. Буква R есть сокращение слова Right и означает, что история работы автомата отражает процесс восстановления так называемого обратного правого дерева грамматического разбора. Число в скобках обозначает наименьшую длину подцепочек входных символов, необходимых для разрешения или предотвращения всех конфликтов типа сдвиг/свертка или свертка/свертка.


Таблица 5.7.

Грамматика Ga0
0	Z : S 
1	S : T
2	S : S + T
3	T : ( S )
4	T : ident
5	T : const

---

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

Однако синтаксис типичных языков программирования не может быть определен LR(0)-грамматикой. Этот класс грамматик слишком узок и может представлять собой только теоретический интерес.

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

Буква S в этом обозначении означает сокращение английского слова Simple – простая.

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

Поскольку при этом все конфликты были предупреждены, данная грамматика относится к классу SLR(1).

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

Этот класс грамматик называют LR(1)-грамматиками.

10. 
    Ожидаемый правый контекст и LR(1)-автоматы
    

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

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

---

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

N :  ▼ , { t }

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

1. 
   Ожидаемый правый контекст базовой конфигурации нулевого состояния состоит из псевдотерминального символа ► конца текста (файла). Действительно, если входное предложение является правильным и восходящему акцептору удалось свернуть его в начальный нетерминал грамматики, то после этой свертки на входе автомата никаких других символов быть не может.
   
2. 
   Перенос маркера через любой символ (образование базы другого состояния, а при работе автомата – выполнение операции Shift или Go) порождает конфигурацию, правый контекст которой совпадает с правым контекстом исходной конфигурации. Действительно, если взять базовую конфигурацию нулевого состояния и перенести маркер через начальный нетерминал (выполнить операцию Go после свертки правильного предложения в начальный нетерминал грамматики), то на входе автомата должен появиться псевдотерминал конца текста.
   
3. 
   Осталось выяснить, каким образом формируется ожидаемый правый контекст при выполнении замыкания базового набора конфигураций произвольного состояния. Суть процесса замыкания, как определялось в разделе 3.3.4 ранее, состоит в следующем.
   

Если имеется конфигурация вида N :  ▼ X  , то каждое правило для нетерминала X превращается в конфигурацию путем установки маркера перед первым символом правой части и добавляется к множеству конфигураций данного состояния, если ее в нем еще нет:

X : γ₁ → X : ▼ γ₁

X : γ₂ → X : ▼ γ₂

...

X : γ_n → X : ▼ γ_n

При построении таблицы канонических расширенных конфигураций с любой исходной конфигурацией N :  ▼ X  связан правый контекст, содержащий символ t₀, ожидаемый на входе автомата после свертки цепочки  X  в нетерминал N:

N :  ▼ X  , {t₀ }.

Очевидно, что после свертки любой из цепочек γ_i в нетерминал X на входе автомата ожидаются символы, входящие в множество предшественников цепочки , а если эта цепочка состоит только из аннулируемых нетерминалов или вообще пуста – еще и символ

---

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

M_опк(X : ▼γ_i) = M_пред(),

если  – цепочка, содержащая хотя бы один терминал или неаннулируемый нетерминал;

M_опк(X : ▼γ_i) = {t₀ },

если  – пустая цепочка;

M_опк(X : ▼γ_i) = M_пред() ⋃ {t₀ },

если  – цепочка, состоящая только из аннулируемых нетерминалов.

Получив множество символов ожидаемого правого контекста M_опк( ▼ X , {t₀ }) = { t₁, t₂ … t_k}, легко можно построить все дочерние по отношению к исходной канонические конфигурации:

M : ▼γ₁ , { t₁} M : ▼γ ₁, { t₂} … M : ▼γ ₁ , { t_k}

M : ▼γ₂ , { t₁} M : ▼γ ₂ , { t₂} … M : ▼γ ₂ , { t_k}

...

M : ▼γ_n , { t₁} M : ▼γ _n , { t₂} … M : ▼γ _n , { t_k}

Теперь окончательно сформулируем правила построения таблицы канонических конфигураций.

1. 
   Базой нулевого состояния является конфигурация вида
   

Z : ▼S ► , {►},

где S – начальный нетерминал грамматики; ► – псевдотерминал «конец файла».

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

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

Однако грамматика G_LR на самом деле относится к промежуточному между SLR(1)- и LR(1)- грамматиками классу грамматик – так называемым LALR(1)-грамматикам. Буквы LA в названии класса грамматик являются сокращением от английского термина «lookahead», который переводится как «предварительный просмотр». В данном случае речь идет о предварительном (выполняемом при построении управляющей таблицы автомата) просмотре множеств символов ожидаемого правого контекста для разрешения или предупреждения возможных конфликтов «сдвиг/свертка» и «свертка/свертка».

---