Действия анализатора со сдвигом аналогичны операциям получения преемника. Поэтому действия со сдвигом в таблицу разбора могут вноситься на основании информации о размещении состояний в грамматике (табл. 5.2). Позиция элементов таблицы вытекает непосредственно из вышеприведенной грамматики. Например, правило (2) означает: "из состояния 2 при чтении 1DL1ST перейти в состояние 5", "из состояния 5 при чтении запятой перейти в состояние 6" и т. д. Задача внесения в таблицу действий приведения довольно сложна. Осуществление приведения может в целом зависеть от текущего левого контекста и предварительно просматриваемого символа. Однако единственные состояний, в которых приведения возможны, - это состояния, соответствующие окончаниям правил (в нашем примере состояния 3,4,5 и 7). В особом случае LR(0)-грамматики предварительно просматриваемый символ не имеет к этому отношения, и действия по приведению могут помещаться в каждый столбец таблицы в любом состоянии, соответствующем окончанию правила. Если бы данная грамматика была LR(0)-грамматикой, мы могли бы поместить R4 во все столбцы состояния 3, R3 - во все столбцы состояния Н, R1 - во все столбцы состояния 5 и R2 - во все столбцы состояния 7. Однако в состоянии 5 в одном столбце уже имеется элемент сдвига. Мы не можем помещать элемент приведения в ту же графо-клетку, и у нас возникает конфликт сдвиг/приведение. Алгоритм построения LR(0) не срабатывает (так как грамматика не обладает признаком LR(0)), и мы должна: попробовать что-нибудь другое. Проблема здесь возникает лишь в связи с состоянием 5, поэтому фактически все остальные элементы приведения мы можем внести и получить табл. 5.3.

Состояние 5 называется неадекватным. Попттаемся разрешить эту проблему, задавая предварительно просматриваемые символы, которые показали бы приведение в состоянии 5, а не сдвиг. Из правил (1) и (2) видим, что такими символами могут быть только "1" и ",", а приведение возможно лишь в том случае, если символом окажется "1", в то время как анализатор осуществит сдвиг в состояние 5, если следующим символом будет ",". Поэтому мы вносим R1 в пятую строку столбца, соответствующего знаку "1". Это не вызывает никакого конфликта, и неадекватность состояния снимается. В ситуациях, когда все неадекватности можно разрешить, таким образом, грамматику считают простой LR(1)- или SLR(l)-грамматикой.

Таблица 5.3

Аналогичным образом, рассмотрев предварительно символы, можно исключить из таблицы несколько действий приведения в состояниях 3, 4 и 7. Если этого не сделать, то некоторые синтаксические ошибки будут обнаружены на более поздних шагах анализа (но не позднее в смысле считанного исходного текста). Исключение этих элементов и включение элемента НАLT дает нам табл. 5.4., с которой мы уже встречались ранее.

Т а б л и ц а 5.4

Включению элемента HALT способствует добавление к грамматике . дополнительного правила:

S SHALT1

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

(1, 0), 1

а состояние 6

с помощью двух конфигураций: (2, 2), ("1", ",") (4, 0), ("1", ",")

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

К счастью, полная универсальность от алгоритма построения LR(1) требуется редко, и на практике большинство языков программирования имеют свойства SLR(l). Как видно из рис.5.1, SLR(l)-грамматики включают грамматики со слабым предшествованием и с простым предшествованием, а также LL(1)-грамматики.

Даже в тех случаях, когда грамматика не обладает признаком SLR(l), полная LR(1)-обработка требуется не всегда. Если состояния, которые являются идентичными, за исключением множеств символов-следователей, сливаются в единое состояние, где различные следователи объединяются в единое множество, и если при организации

LR(1)

LALR(1)

SLR(1)

со слабым

предшествованием LR(0) LL(1)

с простым предшествованием

Рис. 5.1. Иерархия грамматик

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