Разработка компиляторов

       

Пример конфликта перенос-свертка


Итак, имеется следующая входная цепочка: if E1 then if E2 then S1 else S2. Рассмотрим работу анализатора пошагово:

Содержимое стекаНеобработанная часть входной цепочкиДействие
$if E1 then if E2 then S1 else S2 shift
$ifE1 1 then if E2 then S1 else S2 shift
$ if E 1 then if E2 then S1 else S2 shift
$ if E1 thenif E2 then S1 else S2 shift
$ if E1 then ifE2 then S1 else S2 shift
$ if E1 then if E2 then S1 else S2 shift
$ if E1 then if E2 thenS1 else S2 shift
$ if E1 then if E2 then S1 else S2 shift

После последнего шага возникают две альтернативы: либо (а) применить свертку по правилу 1 к последовательности if E2 then S1 на вершине стека, либо (б) перенести символ else на вершину стека. Обе альтернативы легко угадываются из вида правил 1 и 2. Грамматики с правилами такого типа называются грамматиками с "висящим" (dangling) else .

Для подавляющего большинства языков программирования, имеющих условные операторы описанного вида, действие (б) предпочтительно. Общепринятым правилом для данной ситуации является соотнесение каждого else с "ближайшим" then . Это правило может быть формализовано с использованием однозначной грамматики. Идея в том, чтобы установить соответствие между then и else , что эквивалентно требованию, чтобы между then и else могли появиться только оператор, не являющийся условным оператором, или условный оператор с обязательным else ( if expr then stmt else stmt ).



Содержание раздела