Карпов - Основы построения трансляторов (2005), страница 35

В 1 А1 К(1с)-анализаторах для той же цели используется другой, более тонкий анализ контекста в состояниях ЬК(0) — анализатора, которые содержат конфликты. ЬАЬК(1)-анализаторы оказались наиболее оптимальными для трансляции„и именно они используются сейчас для разработки трансляторов современных языков программирования. Мы рассмотрим 1 А1 Й(1.)-анализаторы ниже. 226 Глава 6 6.4.1. 8~ЙОц-анализаторы Вернемся к построению анализатора для грамматики 6~ 4. 064. О. У-+ФМ 1.

Я вЂ” +а5'с 2. 5 — +е Построим ЬК(0)-анализатор (как мы видели, он будет содержать конфликты): (дО): [<У вЂ” +еФЛФ>] Ф ==> а1 П если следующий символ Ф, то переходим в состояние а1; (д1): [<У-+ФеЯ> 5 ==> д2 <Я-+е а5'с> а ==> дЗ <5 — +е> 1 ? (д2): [<У вЂ” +дЬеФ> ~ Ф ==> д4 5'=э д5 а ==> а3 ? (а3): [<5-+аеЛ'с> <Я-+е аЛ'с> <Я вЂ” +е> (а4): [<У вЂ” +Фее>'1 Редукция 0 (д5): [<Я вЂ” +алисе>1 Редук ция 1 Для разрешения этого конфликта применим простой способ: определим множество ГОЬЬ0%®, т. е. множество всех тех терминальных символов, которые в сентенциальных формах могут встретиться после символа Я.

Это легко можно сделать по исходной грамматике. Очевидно, что для грамматики бб 1.ОЬЬ0%® = ® с~. Но в состоянии а1 (так >ке„как и в состоянии аЗ) мы ожидаем для продолжения анализа ~сдвига ло входной цепочке~ только символы Я или а, поскольку именно они стоят непосредственно после метки 'е' в других ситуациях ситуационных множеств а1 и аЗ. Поэтому состояния д1 и дЗ можно дополнить новым переходом: если следующий символ анализируе- Этот Ьй.(0)-распознаватель, однако, не может работать. В состояниях а1 и а3 существуют конфликты сдвиг/редукция: достигнув этих состояний, мы не знаем, следует ли выполнять сдвиг — переход в следующие состояния по очередным входным символам Я или а — или >ке нужно выполнить редук~~ию Я <== е, вставив нетерминал Я в сентенциальную форму непосредственно в той позиции, до которой автомат дошел при анализе, не принимая во внимание никакие следующие символы.

Восходящие алгоритмы синтаксического анализа 1А1.К(1с)-анализатор можно построить и другим способом, а именно непосредственно из 1.К®-анализатора, объединяя те состояния, в которых неучет контекста не повлечет конфликта. На рис. б.7 показан 1 Л1 К(1)-анализатор для грамматики 66~, который получен из 1 К(1)-анализатора той же грамматики, представленного на рис. б.5. Преобразование выполнено так, что состояния 07, д8 и о9 объединены соответственно с состояниями ~~3. ~~5 и сааб. Контекст оставлен только в состояниях д1 и д3. где он позволяет разрешить конфликты сдвиг~редукгуия. Заметьте, что этот анализатор в точности совпадает с 1 АЬК(1)-анализатором, построенным из ЬК(0)-анализатора с последующим дополнительным анализом контекста в конфликтных ситуациях, Рис.

6.7. ~А~В(1)-анализатор для грамматики бб, ПРИМЕР 6.1. Построим 1 К(0)-анализатор для классической грамматики арифметических выражений: С'65 (О) У вЂ” +Е 3 (3) Т вЂ” э ТхР (1) Š— эЕ+Т (4) ТэР (2) Š— эТ (5) Р— и' Последовательно строим ситуационные множества, представляющие собой состояния 1.К(О)-анализатора для 66 .

(~УО) 1<5' — >еЕ 3 > <Е -э1рЕ+Т) Е ==> о1 <Š— эе ~-> <7 — эе ТхР> <Т вЂ” эе1'> <Р-+е ~>~ Р =Ф су3 г:=> д4 (01) ~<5 — +Ее$ > 3 ==> Ассер1 <Š— эЕе+Т>~ + ==> 05 230 Глава б (о2) 1<Š— +Те> ? <Т вЂ” +ТехР>~ х:=> дб (д3) ~<Т вЂ” +Ре> 1 (Ч4) Г<Р— и' е> 1 Редукция 4 Редукция 5 Т==~ д7 (д5) ~ -Š— ьЕ+е Т> <Т вЂ” +е ТхР> <Т вЂ” +еР= <Р— ~е у.> Р==: дЗ г=- и4 (Чб) ~<Т вЂ” Ф Тхер> <Р-+е с> Р ==: гУ8 г=- д4 (д7) ~<Š— ьЕ+Те> ? <Т вЂ” ~ТехР>1 х ==> дб (о8) 1<Т вЂ” 'э ТхРе>1 Редукция 3 Эта грамматика не относится к классу 1 К(0): в построенном нами ЕК(0)- распознавателе имеется два конфликта.

В состоянии о2 существует конфликт ре~)укция/сдвиг: конфликтуют возможность свертки в соответствии с ситуацией <Š— +Уе> и продолжения анализа в соответствии с ситуацией <Т вЂ” +ТехР>. Аналогичный конфликт и в состоянии у~7. Попробуем разрешить эти конфликты с помощью контекста длиной 1, Использование множества ГОП.О%(Е) = ~3, +, х~~ не помогает однозначно разрешить конфликты, поскольку туда входит символ х, а по этому символу в состоянии д2 определен переход в состояние цб. Иными словами„если в состоянии гу2 анализатора следующим символом встретится х, то нет однозначного ответа, что делать: то ли выполнять свертку, то ли продолжать анализ.

Следовательно, данная грамматика не является Я К(1)-грамматикой. Проведем более тонкий анализ контекста для этой грамматики, который состоит в следующем. Нам нужно найти контекст для ситуации <Š— +Уе> в состоянии о2. Эта ситуация появилась здесь только из ситуации <Š— +еУ'- в состоянии дО. В свою очередь, в дО эта ситуация была порождена от двух ситуаций: от ситуации <У вЂ” ~еЕ 3> и от ситуации <Š— ~ Е+Т> в этом же состоянии (поскольку ситуация <Е-+еЕ+У~, включенная в ситуационное множество. рекурсивно требует включения в это же множество дополнительно ситуаций <Š— +еЕ+У- и <Е-+еУ'- ).

Поэтому правый контекст ситуации <Е-+Те> в состоянии д2 есть ~3, +~. Этот же контекст будет и у ситуации Восходящие алгоритмы синтаксического анализа Добавив необходимые действия — редукцию Е <== Т при следующих символах ~3, +~ в состоянии 02 и редукцию Е с= Е+Т при тех же следующих символах ~3, +~ в состоянии д7, мы получим 1А1.К(1)-анализатор для нашей грамматики. Для единообразия подобным же образом можно построить контексты и для каждого терминального состояния.

Состояния 1.А1.К(1)-анализатора с явно определенными контекстами, при которых выполняются редукции, представлены ниже. (д2) ~<Š— +Те> (+, 3~ ==> Редуигия 2 <Т-+ТехР>1 х ==. дб ~+, х, 3~ ==: Редукция 4 (д3) ~<Т вЂ” ~Ре>1 (04) ~<Р— и' ° >~ ~+, х, 3~ ==> Редукг1ия 5 (+, 3~~ => Редукция 1 х ==» дб (д7) ~<Š— ьЕ+ Те> <Т вЂ” ь ТехР>1 (д8) 1'<Т вЂ” +ТхРе>~ (+, х, 3~ ==> Редукггия 3 ПРИМЕР 6.2.

Рассмотрим грамматику: 66 6 (0) Л"-+Я (3) Е-+Е+г (1) 5 — +Е~ Е (4) Š— и' (2) 5 — и Построим по этой грамматике 1 К(0)-распознаватель: (дО) ~<У вЂ” ЭеЯ> <5-+еЕ ~ Е> <5 +ег <Е +еЕ+г> <Š— +ег.'» 1 <Š— +Е+Те> в состоянии д7. Следовательно, оба конфликта разрешаются, поскольку эти контексты не включают символ х, по которому они конфликтовали с ситуацией <Т вЂ” +ТехР> в каждом из состояний. Действительно, возьмем состояние о2.

Наш анализ показал, что в этом состоянии требуется свертка в соответствии с входящей в 02 терминальной ситуацией <Е-+Те> только при наличии в анализируемой цепочке следующего символа 3 или +. Если же следующим символом анализируемой строки в этом месте анализа будет х, то должен выполняться переход в состояние дб в соответствии с ситуацией <Т вЂ” + ТехР>. Глава 6 (су1) ~<У вЂ” +Бей>~ 3 ==> д4 (о2) 1<5 — +Ее~Е> ~ ==> Ч5 <Š— +Ее+ай> 1 + =~ ф (дЗ) ~<Я вЂ” и' е> <Š— и' е> (д4) ~<У вЂ” +Яе>1 Редукция О (д5) ~<5 — +Е~еЕ> Е == д7 <Š— +еЕ+г- г ==> д8 (дб) ~<Š— +Е+ег>1 ю' ==> д9 (07) ~<5-+Е ~ Ее> ? <Š— +Ее+~>1 + ==> дб (д8) ~<Š— не>~ (д9) ~<Е-+Е+~е>1 Редукция 3 (дЗ) ~<5 — и е> <Š— и'е>~ 3 ==> Редукция 2 ~+, ~~ ==> Редукция 4 В состоянии д7 конфликт разрешается также контекстом длины 1: (07) 1"<Я-+Е ~ Ее> $ ==> Редукция 1 <Š— +Ее+ай>1 + ==> об Таким образом, эта грамматика принадлежит классу 1 А1 К(1).

Построением 1.К(1)-анализатора и последующим объединением эквивалентных состояний после выбрасывания несущественной контекстной информации можно полу- чить тот же анализатор. В этом распознавателе в двух состояниях имеются конфликты: в состоянии дЗ это конфликт редукция/редукиия, а в состоянии д7 конфликт редукция/сдвиг.

Для разрешения конфликтов можно построить множество контекстов длиной к для каждого из возможных вариантов решений. Такое построение проводи~ся в точности так, как строился контекст для распознавателя грамматики С 65. В состоянии о3 два разных множества контекстов длины 1 разрешают конфликт: Восходящие алгоритмы синтаксического анализа 6.5.

В(О)-, ВВ(1)-, ЫВ(1)- и ~Й(1)-анализаторы Чем отличаются между собой все перечисленные в заглавии данного раздела анализаторы? Очевидно, что мощности этих анализаторов различны: множества грамматик, языки которых могут быть распознаны этими анализаторами, строго включаются одно в другое: Х.К(0)-грамматики с: Я К(1)-грамматики с: 1 А1 К(1)- грамматики с: 1.К(1)-грамматики.