real А, Вф, C1

входной символ - IDLIST, сдвиг в состояние 5:

входной символ - сдвиг в состояние 6:

real А, Вф, C1

входной символ - С, сдвиг в состояние 3:

real А, В, Cф1

входной символ - "1", приведение посредством правила (4): real А, В, Cф1

входной символ - ID, сдвиг в состояние 7: real А, В, Cф1

входной символ - "1", приведение посредством правила (2):

real A, B, Сф1

входной символ - 1dl1st, сдвиг в состояние 5:

real A, B, Сф1

входной символ - "1", приведение посредством правила (1):

real А, B, Сф1

входной символ - S, поэтому halt (останов). Разбор успешно завершен.

Заметим, что после сдвига входным символом всегда является следующий символ, а после приведения - символ, к которому только что привело действие.

5.4. ПОСТРОЕНИЕ LR-ТАБЛИЦЫ РАЗБОРА

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

(1) s.real idlist

(2) idlist Midlist, id

(3) idlist 1d

(4) idajbIcId

точка соответствует конфигурации (1, 0), т.е. правилу (1) позиции 0; конфигурация (1, 1) соответствовала бы точке, появляющейся сразу после real в правиле (1), а (2, 0) - точке, появляющейся перед 1dl1st в правой части правила (2). Конфигурации будут использоваться для представления продвижения в разборе. Так, конфигурация (2, 2) покажет нам, что правая часть правила (2) распознана по запятую включительно. На любом, этапе разбора может быть частично распознано некоторое число правтх частей правил.

Состояния в таблице разбора примерно соответствуют конфигурациям в грамматике с той лишь разницей, что конфигурации, которые неразличимы для анализатора, представляются одним и тем же состоянием, например, если (1,0) соответствует состоянию 1, а (1, 1) - состоянию 2, то в вышеприведенной грамматике (2, 0), (3, 0) и (4, 0) будут также соответствовать состоянию 2. Мы говорим, что множество конфигураций

{(1, /), (2. 0), (3, 0) (4.0)}

образуют замыкание (1,1). Из заданного состояния, не соответствующего концу правила, можно перейти в другое состояние, введя терминальный или нетерминальный символ. Это состояние называют преемником первоначального состояния. Чтобы построить таблицу разбора, необходимо прежде найти все состояния в грамматике. Поэтому мы начинаем с конфигурации (1, 0) и последовательно выполняем операции замыкания и образования преемника до тех пор, пока все конфигурации не окажутся включенными в какие-либо состояния. Там, где ряд конфигураций содержится в одном замыкании, каждая из них будет соответствовать одному и тому же состоянию. Новая конфигурация, которая получается при операции образования преемника, называется базовой. Если за базовой конфигурацией следует нетерминал, то все конфигурации, соответствующие помещению точки слева от каждой правой части правила для данного нетерминала (и т. д. рекурсивно), сконцентрируются в замыкании этой базовой конфигурации. Так, в предыдущей грамматике четко видны семь состояний, которые можно описать следующим образом:

Эти состояния расположены в грамматике следующим образом:

(1) s1real2idlist5

(2) idlist2idlist5,6idy

(3) idlist 2id4

(4) id(2,6) a/b/c\d3

Заметим, что конфигурация может соответствовать более чем одному состоянию, и в базе может быть более одной конфигурации, если преемники двух конфигураций в одном и том же замыкании неразличимы. Например, в вышеприведенном примере за конфигурациями (1, 1) и (2, 0) следует idlist, что делает (1, 2) и (2, 1) неразличимыми, пока не осуществится операция замыкания (которая в нашем случае не дает дополнительнтх конфигураций). Число состояний в анализаторе соответствует числу множеств неразличимых конфигураций в грамматике. Причина того, что два или более состояний соответствуют одной конфигурации, раскрывается в ходе разбора. Так, в каком-то состоянии может содержаться информация "левого контекста". Тем не менее, в конце правила (4) появляется только одно состояние (состояние 3), поскольку мы не допускаем более одного состояния для одного и того же множества конфигураций. Таким образом, со стояние 3 не содержит какой-либо информации левого контекста. Из рассмотреннтх выше множеств базы и замыкания вытекает, что состояния 2 и 6 не соответствуют одному и тому же множеству конфигураций.

Таблица 5.2