А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 71
Текст из файла (страница 71)
Имеется две причины, по которым использование неоднозначной грамматики может оказаться предпочтительнее. Во-первых, как мы увидим ниже, можно легко изменить ассоциативность и уровень приоритета операторов + и * без изменения продукций (4.3) или количества состояний получающегося синтаксического анализатора. Во-вторых, синтаксический анализатор для однозначной грамматики будет тратить значительную часть времени на свертку по продукциям Š— Т и Т вЂ” Е, единственная функция которых — определять приоритеты и ассоциативность операторов. Множества !.К (0)-пунктов для неоднозначной грамматики выражений (43), расширенной продукцией Е' — Е, показаны на рис.
4.48. Поскольку грамматика (4.3) неоднозначна, при попытке построить таблицу !.К-анализа по этому множеству возникают конфликты действий. В частности, такие конфликты порождают состояния, соответствующие множествам пунктов 1т и 1а. Предположим, что мы используем 8!.К-подход для построения таблицы действий синтаксического анализа. Конфликт порождается множеством 1т — между сверткой по продукции Š— Е + Е и переносом + или * — и не может быть разрешен, поскольку и ~-, и * принадлежат множеству РОЕЕОту (Е). Таким образом, для входных символов + и * могут выполняться оба действия. Подобный конфликт порождается множеством 1а — между сверткой Š— Е* Е и переносом при входных символах + и *.
Фактически эти конфликты порождаются при любом способе построения таблиц ЬК-анализа, а не только при Я.К.-подходе. Однако эти проблемы могут быть решены с использованием информации о приоритетах и ассоциативности операторов + и *. Рассмотрим входную строку Ы + Ы * !и, которая заставляет синтаксический анализатор, основанный на рис. 4.48, попасть в состояние 7 после обработки Ы + Ы; в частности, синтаксический анализатор достигает конфигурации ПРЕФИКС СТЕК ВХОД Е+Е 0 ! 4 7 *Ы5 Для удобства символы, соответствующие состояниям ), 4 и 7, показаны в столбце "Префикс".
Если приоритет оператора * выше приоритета +, мы знаем, что синтаксический анализатор должен выполнить перенос * в стек, подготавливая свертку * и соседних с этим оператором Ы в выражение. Эти же действия были совершены и 81,К-анализатором на рис. 4.37, основанном на однозначной грамматике для того же языка. С другой стороны, если приоритет 4- выше приоритета ~, синтаксический анализатор должен свернуть Е + Е к Е.
Таким образом, относительное старшинство ь, за которым следует *, однозначно определяет, каким образом 355 4.8. Использование неоднозначных грамматик 1о: Е' — Е Е- Е+Е Е- Е*Е Е- (Е) Е- Ы Е- Е+Е Е- ЕкЕ Е 1Е) Š— и$ 1~. Е'- Е Е- Е +Е Е- Е *Е 1а.
Е- Е— 1Е ) Е. 1Е Е вЕ Е (.Е) Š— ~ Е+Е Е- Е*Е (Е) Е- а 1т. ŠŠ— ~ Е+ Е. Е +Е Е *Е 18 ° Š— ~ Е* Е. Е +Е Е *ŠŠ— ~ 1з: Е Ы 14' Š— Е+ Е Е- Е+Е Е- .(Е) Е- Ы Рнс. 4.48. Множества 1.К (О)-пунктов расширенной грамматики выражений должен быть разрешен конфликт между сверткой Š— Е + Е и переносом * в состоянии 7.
Если входная строка имеет вид Ы + Ы + Ы, то синтаксический анализатор после обработки части строки Ы + Ы достигнет конфигурации, при которой содержимое стека — 0 1 4 7. При очередном входном символе + в состоянии 7 вновь возникает конфликт переноса1свергки.
Однако теперь способ разрешения возникшего конфликта определяется ассоциативностью оператора +. Если этот оператор левоассоциативен,правильным действием синтаксического анализатора будет свертка по продукции Š— Е + Е. Первыми должны быть сгруппированы Глава 4. Синтаксический анализ 356 !д, окружающие первый оператор +. Этот выбор вновь совпадает с действиями Я.Гх-анализатора для однозначной грамматики".
Итак, если оператор + левоассоциативен, действие в состоянии 7 для входного символа + должно приводить к свертке по продукции Š— Е + Е, а предположение о превосходстве приоритета оператора * над + ведет к переносу входного символа *. Аналогично, если оператор * левоассоциативен н старше оператора ч-, то можно доказать, что состояние 8, появляющееся на вершине стека только в том случае, когда три верхних символа представляют собой Е е Е, должно приводить к свертке по продукции Š— Е * Е как при очередном входном символе +, так и при *.
В случае входного символа + причина этого заключается в том, что оператор * старше оператора +, а в случае входного символа * — что оператор * левоассоцнативен. Продолжая рассмотрение, можно получить таблицу 1.К-анализа, показанную на рис. 4.49. Продукции 1-4 представляют собой соответственно Š— Е+ Е, Š— Е * Е, Š— (Е) н Š— !д. Интересно, что подобная таблица может бьп.ь получена путем устранения сверток согласно продукциям Š— Т и T — Е из Я.К-таблицы для однозначной грамматики (4.1). В контексте (.А(.К- и канонического (.й-анализа с неоднозначными грамматиками такого типа можно поступать аналогично. Рнс.
4.49. Таблица синтаксического анализа для грамматики (4.3) В принципе, левоассоциативность (правоассоциативность) можно рассматривать как превосходство приоритета аевого (правого) оператора одного и того же вида в случае их последовательного применения (естественно, отношения приоритетов операторов этого типа с другими операторами остаются в силе). — Прим. ред. 357 4.8.2 Неоднозначность "висящего е18е" Вновь обратимся к грамматике для условных инструкций: хгтг — Н ехрг гЬеп айаг е!ае агтг Н ехрг язеп ыт~ огЬег Как отмечалось в разделе 4.3.2, эта грамматика неоднозначна, поскольку не разрешает неоднозначности "висящего е!ае".
Для упрощения рассмотрим абстрактное представление приведенной выше грамматики, где г означает и ехрг г)зеп, е— ене, а — "все остальные продукции". Тогда рассматриваемая грамматика с расширяющей продукцией Я' — Ь может быть записана в виде У вЂ” Я Я вЂ” зЯеЯ(гЯ)а (4. 17) Множества ЕК (О)-пунктов для грамматики (4.17) показаны на рис. 4.50.
Неодно- значность грамматики (4.17) приводит к конфликту переноса/свертки в 14. Здесь пункт Я - гЬ' еЯ приводит к переносу е, а поскольку Рогз.очг (Я) = 1е, Э), пункт Я вЂ” Ж приводит к свертке по продукции Я вЂ” гЯ при входном символе е. 1о: Я вЂ” Иоео 5 — .гЯ Я- .а 14: Я- г'Я еЯ 1г . 'о — 1 ..зе.з Я вЂ” з Я Я- а 1в . Ь вЂ” гоев Я вЂ” гЯеЯ ;з' - го' Рис. 4.50. ).К(0)-состояния для расширенной грамматики (4.! 7) Если перевести это обратно в термины Н-Феп-е!ае, то, при наличии в стеке Н ехрг гйеп тт~ 4.8.
Использование неоднозначных грамматик 1а. .о- зле Я Ь вЂ” ~ гЯеЯ Я вЂ” ~ гЯ 358 Глава 4. Синтаксический анализ и е!яе в качестве первою входного символа, мы должны перенести е!яе в стек (те. выполнить перенос е) или свернуть 1! ехрг Фен зли! в ~тг (т.е. выполнить свертку по продукции Я- 1Я)? Ответ заключается в том, что мы должны перенести е!яе, так как оно "связано" с предыдущим Феп. В терминах грамматики (4.17) входной символ е (означающий е!яе) может быть только частью тела продукции, начинающегося с части гЯ, которая находится на вершине стека. Итак, мы приходим к заключению, что конфликт переноса/свертки в У» должен быть разрешен в пользу переноса входного символа е.
Таблица ЯЬК-анализа, построенная по множествам пунктов на рис. 4.50 с использованием описанного разрешения конфликта, показана на рис. 4.51. Здесь продукции 1-3 представляют собой соответственно Я вЂ” !ЯеЯ, Я вЂ” гЯ и Я вЂ” а. Рис. 4.51. Таблица ! й-анализа для грамматики с "висящим е1ае" Например, при входной строке Наел синтаксический анализатор выполняет действия, показанные на рис. 4.52, в соответствии с корректным разрешением проблемы "висящего е1зе". В строке (5) в состоянии 4 происходит перенос входного символа е, а в строке (9) в состоянии (4) при входном 8 выполняется свертка по продукции 5 — Ж В случае, когда мы не можем использовать неоднозначную грамматику для условных инструкций, можно воспользоваться более громоздкой грамматикой из примера 4.16.
4.8.3 Восстановление после ошибок в 1.К-анализе 1.а-анализатор обнаруживает ошибку при обращении к таблице АСТ1ОМ синтаксического анализа и нахождении в ней записи об ошибке (при обращении к таблице бОТО ошибки не выявляются). ЬК-анализатор сообщит об ошибке, как только не сможет обнаружить корректного продолжения уже отсканированной части входного потока. Канонический 1.а-анализ в этом случае даже не выполнит ни 359 4.8. Использование неоднозначных грамматик Рис. 4.52. Действия синтаксического анализа для входной строки йаеа одной свертки перед объявлением об ошибке; ЯЬК- н ЬАЬВ.-анализаторы могут произвести ряд сверток перед тем, как сообщить об ошибке, но никогда не будут переносить в стек неверный символ. При ЬК-анализе восстановление после ошибок "в режиме паники" реализуется следующим образом. Мы сканируем стек от вершины до состояния а с записью в таблице бОТО для некоторого нетерминала А.
После этого пропускаем нуль или несколько символов входного потока, пока не будет найден символ и, который при отсутствии ошибки может законным образом следовать за А. После этого синтаксический анализатор переносит в стек состояние сото(а, А) и продолжает обычный синтаксический анализ. При выборе нетерминала А возможны несколько вариантов. Обычно это нетерминалы, представляющие крупные фрагменты программы, такие как выражение, инструкция и блок. Например, если А— нетерминал запб а может быть символом; или ), помечающим конец последовательности инструкции.
При таком методе восстановления производится попытка выделить фразу, содержащую синтаксическую ошибку. Синтаксический анализатор определяет, что строка, порождаемая из А, содержит ошибку. Часть этой строки уже обработана, и результат этой обработки — последовательность состояний, находящаяся на вершине стека. Остаток строки все еще находится во входном потоке, и синтаксический анализатор пытается пропустить этот остаток, находя символ, который может следовать за А в корректной программе. Удаляя состояния из стека, пропуская часть входного потока и помещая в стек оото(а, А), синтаксический анализатор полагает, что им найден экземпляр А, и продолжает обычный процесс анализа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
