Тема 4. Синтаксические анализаторы

Тема 4. Синтаксические анализаторы

4.1. Основные принципы работы синтаксических анализаторов. 2

4.1.1. Назначение синтаксического анализатора. 2

4.1.2. Обработка синтаксических ошибок. 4

4.1.3. Стратегии восстановления после ошибок. 5

4.2. Контекстно-свободные языки. 7

4.2.1. Свойства и распознаватели КС-языков. 7

4.2.1.1.   Автоматы с магазинной памятью – распознаватели КС-языков. 7

4.2.1.2.   Свойства КС-языков. 10

4.2.1.3.   Контрольные вопросы.. 12

4.2.2. Преобразование КС-грамматик. 12

4.2.2.1.   Цели преобразований грамматик. 12

4.2.2.2.   Приведённые грамматики. 13

4.2.2.3.   Контрольные вопросы.. 18

4.2.3. КС-грамматики в нормальной форме. 19

4.2.3.1.   Нормальная форма Хомского. 19

4.2.3.2.   Левая рекурсия. Нормальная форма Грейбах. 21

4.2.3.3.   Контрольные вопросы.. 24

4.3. Виды распознавателей КС-языков. 24

4.3.1.  Распознаватели КС-языков с возвратом.. 24

4.3.1.1.   Нисходящий распознаватель с возвратом.. 25

4.3.1.2.   Распознаватель на основе алгоритма «сдвиг-свёртка». 30

4.3.2.  Табличные распознаватели КС-языков. 35

4.3.3.  Распознаватели КС-языков без возвратов – основные принципы.. 39

4.3.4.  Контрольные вопросы.. 39

4.4. Специальные классы КС-языков и грамматик. 40

4.4.1.  Нисходящие распознаватели без возвратов. 40

4.4.1.1.   Метод рекурсивного спуска. 40

4.4.1.2.   Разбор для LL(k)-грамматик. 44

4.4.2.  Восходящие распознаватели без возвратов. 53

4.4.2.1.   LR(k)-грамматики. 53

4.4.2.2.   Грамматики предшествования. 57

4.4.3.  Контрольные вопросы.. 60

 

 

Основные принципы работы синтаксических анализаторов

Синтаксис конструкций языка про­граммирования может быть описан с помощью контекстно-свободных грамматик. Грамматики обеспечивают значительные преимущества разработ­чикам языков программирования и создателям компиляторов.

· Грамматика дает точную и при этом простую для понимания синтаксиче­скую спецификацию языка профаммирования.

· Для некоторых классов грамматик мы можем автоматически построить эффективный синтаксический анализатор, который определяет синтакси­ческую структуру исходной программы. Дополнительным преимуществом автоматического создания анализатора является возможность обнаружения синтаксических неоднозначностей и других сложностей, которые иначе могли бы остаться незамеченными на начальных фазах создания языка и его компилятора.

· Правильно построенная грамматика придает языку программирования структуру, которая способствует облегчению трансляции исходной программы в корректный объектный код и выявлению ошибок.

· Грамматика позволяет языку итеративно эволюционировать, обогащаясь новыми конструкциями для решения новых задач. Добавление этих новых конструкций в язык оказывается более простой задачей, если существую­щая реализация языка основана на его грамматнческом описании.

Стратегии восстановления после ошибок

После того как ошибка обнаружена, каким обратом должно выполниться вос­становление синтаксического анализатора? Хотя универсальной стратегии не су­ществует, все же несколько методов применяются чаще других. Простейший подход состоит в том, что синтаксический анализатор завершает работу при первой же обнаруженной ошибке, выводя о ней информативное сообщение. Если же син­таксический анализатор может восстановить некоторым образом свое состояние до такого, когда работа может быть продолжена, то имеется определенная надеж­да на то, что будут обнаружены и другие ошибки, а также что информация о них окажется достаточно корректной. Если же восстановление не совсем корректное и количество обнаруженных ошибок растет, как снежный ком, то будет лучше, если компилятор после некоторого предельного количества ошибок прекратит вывод раздражающих сообщении об этих "фальшивых" ошибках.

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

Продукции ошибок

Знание наиболее распространенных ошибок позволяет расширить грамматику языка продукциями (правилами), порождающими ошибочные конструкции. Синтаксический анализатор, построенный на основе такой расширенной продукциями ошибок грамматики языка, обнаруживает ошибку при использовании "ошибочной" про­дукции. Таким образом, он может сгенерировать корректное диагностическое со­общение для распознанной во входном потоке ошибки.

Глобальная коррекция

В идеальном случае при обработке некорректной входной строки компилятор должен вносить минимально возможное количество изменений. Существует ряд алгоритмов, которые позволяют выбрать минимальную последовательность вно­симых изменений для проведения коррекции. По заданной некорректной строке х в грамматике G такие алгоритмы находят дерево разбора для строки у, такой, что количество вставок, удалений и изменений токенов, требуемых для преобра­зования х в у, минимально возможное. К сожалению эти методы в общем случае слишком дорогостоящи для применения в компиляторах в силу высоких требований к памяти и времени работы, а потому представляют в настоящее время, в основном, теоретический интерес.

Следует заметить, что ближайшая к исходной исправленная программа может оказаться вовсе не тем, что хотел получить программист. Тем не менее понятие минимальной коррекции дает нам критерий оценки качества различных техноло­гий восстановления после ошибок и используется для поиска оптимальной замены строки при восстановлении на уровне фразы.

В основе синтаксического анализатора лежит распознаватель текста исходной программы, построенный на основе грамматики входного языка. Как правило, синтаксические конструкции языков программирования могут быть описаны с помощью КС-грамматик, реже встречаются языки, которые могут быть описа­ны с помощью регулярных грамматик.

Контекстно-свободные языки

Свойства КС-языков

Основное свойство КС-языков: Класс КС-языков замкнут относительно операции подстановки. Это означает, что, если в каждую цепочку символов КС-языка вместо некоторого символа подставить цепочку символов из другого КС-языка, то полученная цепочка также будет принадлежать КС-языку.

Класс КС-языков замкнут относительно операций объединения, конкатенации, итерации, изменения имен символов.

Замечание:

Класс КС-языков не замкнут относительно операции пересечения и операции дополнения.

Пример 2.  

Пусть есть два языка L₁={aⁿbⁿcⁱ½n>0, i>0} и L₂={aⁱbⁿcⁿ½n>0, i>0}. Оба эти языка являются КС, но, если взять их пересечение, то получим язык L=L₁ÇL₂={aⁿbⁿcⁿ½n>0}, который уже не является КС-языком.

Для КС-языков разрешимы проблемы пустоты языка и принадлежности заданной цепочки языку – для их решения достаточно построить МПА, распознающий данный язык. Но проблема эквивалентности двух произвольных грамматик является неразрешимой. Неразрешима и более узкая проблема – эквивалентности заданной произвольной КС-грамматики и произвольной регулярной грамматики. Тем не менее, для некоторых КС-грамматик можно построить эквивалентную им однозначную грамматику.

Детерминированные КС-языки представляют собой более узкий класс в семействе КС-языков. Этот класс не замкнут относительно операций объединения и пересечения, хотя, в отличие от всех КС-языков в целом, замкнут относительно операции дополнения.

Для класса детерминированных КС-языков разрешима проблема однозначности. Доказано, что, если язык может быть распознан с помощью ДМПА, он может быть описан с помощью однозначной КС-грамматики. Поэтому данный класс используется для построения синтаксических конструкций языков программирования.

Как и в случае с регулярными языками, для проверки того факта, что некоторый язык не принадлежит классу КС-языков, служит лемма о разрастании КС-языков. Она выполняется для любого КС-языка. Если лемма не выполняется, то это означает, что язык не относится к типу контекстно-свободных.

Лемма о разрастании КС-языков:

Если взять достаточно длинную цепочку символов, принадлежащую произвольному КС-языку, то в ней всегда можно выделить две подцепочки, длина которых в сумме больше нуля, таких, что, повторив их сколь угодно большое число раз, можно получить новую цепочку символов, принадлежащую данному языку.

Формальная запись: Если L – это КС-язык, то $ k>0, kÎN ½если ½a½³ k и aÎL, то a=bdgjm, где dj¹e, ½dgj½£ k и bdⁱgj ⁱmÎL " i ³0.

Пример 3.

Проверим, является ли язык L={aⁿbⁿcⁿ½n>0} КС-языком. Пусть это так, тогда для него должна выполняться лемма о разрастании КС-языков. Значит, существует некоторая константа k, о которой идет речь в этой лемме. Возьмем цепочку этого языка a=a^kb^kc^k, ½a½> k. Если её записать в виде a=bdgjm, то по условиям леммы ½dgj½£ k, следовательно, цепочка dgj не может содержать вхождения всех трех символов ‘a’, ‘b’, ‘c’, т.е. в ней нет или ‘a’, или ‘c’. Рассмотрим цепочку bd⁰gj⁰m=bgm. По условиям леммы, она должна принадлежать языку L, но она содержит либо k символов ‘a’, либо k символов ‘c’. Но ½bgm½< 3k, следовательно, какие-то из символов языка входят в цепочку меньшее число раз, чем другие. Такая цепочка не может принадлежать заданному языку. Следовательно, язык L не является КС-языком.

4.2.1.3. Контрольные вопросы

1. Чем отличается автомат с магазинной памятью от конечного автомата и что у них общего?

2. В чём особенность такта работы МПА в случае, когда не принимается во внимание входной символ?

3. Чем отличается конфигурация МПА от конфигурации КА?

4. Может ли МПА работать при пустом стеке? А при пустой входной цепочке?

5. Что такое расширенный МПА?

6. Какие МПА являются эквивалентными?

7. К каким способам задания языка относится МПА?

8. Языки какого типа задают автоматы с магазинной памятью?

9. Какие действия со стеком может выполнять МПА на одном такте работы?

10. Построить ДМП-автоматы с опустошением стека, допускающие следующие языки: а) {0 ^k 1 ⁿ ½ k ³ n > 0}; б) {0 ^k 1 ⁿ ½ 0 < k £ n}; в) {w½wÎ{a, b}^* и количество символов ’а’ и ’b’ одинаково}; г) {0 ⁿ 1 ⁿ 0 ^k 1 ^k}; д) {w½wÎ{a, b}^* и количество символов ’а’ и ’b’ четно}.

11. Как можно установить, относится ли язык к контекстно-свободному типу?

12. В чём отличие леммы о разрастании КС-языков от соответствующей леммы для регулярных языков?

4.2.2. Преобразование КС-грамматик

4.2.2.1. Цели преобразований грамматик

В общем случае для КС-грамматик невозможно проверить их однозначность и эквивалентность. Но для конкретных случаев бывает можно и нужно привести заданную грамматику к некоторому определённому виду таким образом, чтобы получить грамматику, эквивалентную исходной. Заранее определённый вид зачастую позволяет упростить работу с языком и построение распознавателей для него. Итак, преобразования грамматик могут преследовать две цели:

1) упрощение правил грамматики;

2) облегчение создания распознавателя языка.

Не всегда эти цели удается совместить, тогда необходимо исходить из того, что является главным в конкретной задаче. В теории языков программирования основой является создание компилятора для языка, поэтому главной становится вторая цель. Следовательно, можно пренебречь упрощением правил (и даже смириться с некоторым их усложнением), если при этом удастся упростить построение распознавателя языка.

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

1. исключение из грамматики тех правил и символов, без которых она может существовать (позволяет упростить правила);

2. изменение вида и состава правил грамматики. При этом могут появиться новые правила и нетерминальные символы (упрощений правил нет).

Приведённые грамматики

Приведёнными (или грамматиками в каноническом виде) называются грамматики, которые не содержат недостижимых и бесплодных символов, циклов и пустых правил (e-правил).

Рассмотрим некоторую грамматику G(V_T,V_N,P,S) и дадим необходимые определения.

Нетерминальный символ AÎV_N называется бесплодным (или бесполезным), если из него нельзя вывести ни одной цепочки терминальных символов, т.е. {a½AÞ*a, aÎV_T^*}=Æ.

В простейшем случае символ является бесплодным, если во всех правилах, где он находится в левой части, он встречается также и в правой части. В более сложных случаях бесполезные символы могут находиться в некоторой взаимной зависимости, порождая друг друга. Если из правил грамматики удалить такие символы, то эти правила станут проще.

Символ x Î(V_TÈV_N) называется недостижимым, если он не встречается ни в одной сентенциальной форме грамматики G. Это значит, что он не может появиться ни в одной цепочке вывода. Для исключения всех недостижимых символов не обязательно рассматривать все сентенциальные формы грамматики, достаточно воспользоваться специальным алгоритмом удаления недостижимых символов. После удаления таких символов правила также упрощаются.

e -правилами, или правилами с пустой цепочкой, называются все правила грамматики вида A®e, AÎV_N. Грамматика G называется грамматикой без e -правил, если в ней нет правил вида (A®e), AÎV_N, A¹S, и существует только одно правило (S®e)ÎP, если eÎL(G) и при этом S не встречается в правой части ни одного правила грамматики G. Для упрощения процесса построения распознавателя цепочек языка L(G) любую грамматику целесообразно привести к виду без e-правил.

Циклом в грамматике G называется вывод вида AÞ*A, AÎV_N. Очевидно, что такой вывод бесполезен, поэтому в распознавателях КС-языков рекомендуется избегать возможности появления циклов.

Циклы возможны в случае существования в грамматике цепных правил вида A®B, A,BÎV_N. Достаточно устранить цепные правила из набора правил грамматики, чтобы исключить возможность появления циклов.

Для того чтобы преобразовать произвольную КС-грамматику к каноническому виду, необходимо выполнить следующие действия (причём именно в том порядке, каком они перечислены):

§ удалить все бесплодные символы;

§ удалить все недостижимые символы;

§ удалить e-правила;

§ удалить цепные правила.

Для каждого из названных действий существует свой алгоритм. Рассмотрим эти алгоритмы в том порядке, каком требуется их реализовывать.

Пример 5.

Рассмотрим грамматику G({a,b,c},{A,B,C,S},P,S), где P:

S®AaB½aB½cC

A®AB½a½b½B

B®Ba½e

C®AB½c

Удалим e-правила:

1. W₀={B}, i:=1.

2. W₁={B,A}, W₁¹W₀, i:=2.

3. W₂={B,A,C}, W₂¹W₁, i:=3.

4. W₃={B,A,C}, W₃=W₂.

5. V_T¢=V_T, V_N¢=V_N, в P¢ входят все правила из P, кроме правила B®e.

6. Рассмотрим отдельно каждое из правил множества P¢.

S®AaB½aB½cC. Нужно исключить все комбинации A,B,C. Получим: S®Aa½aB½a½a½c. Добавим новые правила, исключая дубликаты. Получим: S®AaB½aB½cC½Aa½a½c.

A®AB½a½b½B. Исключая все комбинации A и B, получим A®A½B. Добавлять нечего, т.к. правило A®B в множестве P¢ уже есть, а A®A не имеет смысла.

B®Ba. Исключив из этого правила B, получим B®a, следовательно, окончательно B®Ba½a.

C®AB½c. Исключив все комбинации A и B, получим C®A½B, после добавления в P¢ получится C®AB½A½B½c.

7. SÏW₃, поэтому не нужно добавлять новый символ S¢, S¢=S.

В итоге получим грамматику G¢({a,b,c},{A,B,C,S},P¢,S), где правила P¢ имеют вид:

S®AaB½aB½cC½Aa½a½c

A®AB½a½b½B

B®Ba½a

C®AB½A½B½c.

Построенная грамматика эквивалентна исходной и не содержит e-правил.

Нормальная форма Хомского

Нормальная форма Хомского, или бинарная нормальная форма – одна из предопределённых форм для правил КС-грамматики. В нормальную форму Хомского можно преобразовать любую КС-грамматику, но сначала её необходимо привести к каноническому виду.

КС-грамматика G(V_T,V_N,P,S) называется грамматикой в нормальной форме Хомского, если в её множестве правил P присутствуют только правила следующего вида:

1. A®BC, где A, B, CÎV_N.

2. A®a, где AÎV_N, aÎV_T.

3. S®e, если eÎL(G) и S не должно встречаться в правых частях других правил.

Никакие другие правила не могут встречаться среди правил грамматики в нормальной форме Хомского.

Грамматика в нормальной форме Хомского называется также грамматикой в бинарной нормальной форме (БНФ), т.к. на каждом шаге нетерминальный символ может быть заменен только на два других нетерминальных символа.

Для преобразования грамматики к БНФ сначала требуется преобразовать её к приведенному виду. Соответствующий алгоритм был рассмотрен выше, поэтому будем считать, что КС-грамматика уже находится в каноническом виде.

Алгоритм 5. Преобразование грамматики к БНФ (Хомского).

Сначала множество нетерминальных символов новой грамматики строится на основе множества нетерминальных символов исходной грамматики: V_N¢=V_N.

Затем алгоритм работает с правилами P исходной грамматики и в зависимости от их вида строит множество правил P¢ и пополняет множество нетерминальных символов V_N¢.

1. Правила вида A®a, A®BC, S®e, где A, B, CÎV_N, aÎV_T, переносятся во множество P¢ без изменений.

2. Если встречается правило вида (A®aB)ÎP, где A, BÎV_N, aÎV_T, то во множество правил P¢ добавляются правила A®<AaB>B и <AaB>®a, а новый символ <AaB> добавляется во множество нетерминальных символов V_N¢.

3. Если встречается правило вида (A®Ba)ÎP, выполняется аналогичное действие: во множество правил P¢ добавляются правила A®B<ABa> и <ABa>®a, а новый символ <ABa> добавляется во множество нетерминальных символов V_N¢.

4. Если встречается правило вида (A®ab)ÎP, где AÎV_N, a, bÎV_T, то во множество правил P¢ добавляются правила A®<Aa><Ab> и <Aa>®a, <Ab>®b, а новые символы <Aa>, <Ab> добавляются во множество нетерминальных символов V_N¢.

5. Если встречается правило вида (A®X₁X₂…X_k)ÎP, где k>2, AÎV_N, "i X_iÎV_TÈV_N, то во множество правил P¢ добавляются правила A®X₁¢<X₂¢…X_k¢>,
<X₂¢…X_k¢>®X₂¢<X₃¢…X_k¢>,
…
<X_k–1¢X_k¢>®X_k–1¢X_k¢,
где все новые нетерминальные символы <…> добавляются во множество нетерминальных символов V_N¢. Что касается символов X_i¢, то их вид зависит от того, чем являлся исходный символ X_i. Если для некоторого i X_iÎV_N, то X_i¢ºX_iÎV_N¢; если X_iÎV_T, то X_i¢ – новый нетерминальный символ, т.е. X_i¢ÎV_N¢ и в P¢ нужно добавить правило X_i¢®X_i.

Проиллюстрируем данный алгоритм на примере.

Пример 6. Преобразование КС-грамматики к БНФ.

Дана грамматика G({a,b,c},{A,B,C,S},P,S) в каноническом виде, где P:

S®AaB½Aa½bc

A®AB½a½aC

B®Ba½b

C®AB½c

Первоначально множество нетерминальных символов V_N¢={A,B,C,S}, затем оно может пополняться. Последовательно рассматриваем правила P и анализируем каждое из них.

1) S®AaB – относится к пункту 5 алгоритма. Следовательно, в P¢ включаем S®A<aB>, <aB>®<a>B, <a>®a, а в множество V_N¢ добавляем <aB>,<a>.

2) S®Aa – относится к 3 пункту алгоритма. Следовательно, в P¢ нужно включить S®A<a¢>, <a¢>®a, а в множество V_N¢ добавить <a¢>. Но ранее уже появился нетерминал <a>, из которого выводился символ a, поэтому можно использовать его, тогда можно ограничиться правилом S®A<a>.

3) S®bc – относится к 4 пункту. Следовательно, в P¢ нужно включить S®<b><c>, <b>®b, <c>®c, а в множество V_N¢ добавить <b>, <c>.

4) A®AB и A®a – в соответствии с первым пунктом алгоритма включается в P¢ без изменений.

5) A®aC – относится ко 2 пункту. Следовательно, в P¢ нужно включить A®<a>C, причем замечание из (2) справедливо и в данном случае.

6) B®Ba – аналогично (2), добавляется правило B®B<a>.

7) B®b, а также C®AB, C®c соответствуют требуемому виду правил и переносятся в грамматику без изменений.

Таким образом, получаем грамматику G¢({a,b,c},{A,B,C,<aB>,<a>, <b>,<c>,S},P¢,S) в нормальной форме Хомского, где P¢:

S®A<aB>½A<a>½<b><c>

A®AB½a½<a>C

B®B<a>½b

C®AB½c

<aB>®<a>B

<a>®a

<b>®b

<c>®c

Хотя эта грамматика содержит большее количество правил, чем исходная, но построение распознавателя для неё значительно упрощается.

Пример 7.

Пусть дана грамматика для арифметических выражений:

G ({+,–,/,*,a,b,(,)}, {S,T,E}, P, S), где правила P имеют вид:

(1) S ® S+T½S–T½T (2) T ® T*E½T/E½E (3) E ® (S)½a½b.

Эта грамматика леворекурсивная. Выполним эквивалентные преобразования и построим нелеворекурсивную грамматику G¢.

Шаг 1. Обозначим множество нетерминальных символов V_N={A₁,A₂,A₃}, i:=1. Тогда правила грамматики примут вид:

A₁ ® A₁+A₂½A₁–A₂½A₂

A₂ ® A₂*A₃½A₂/A₃½A₃

A₃ ® (A₁)½a½b.

Шаг 2. Правила для A₁: A₁ ® A₁+A₂½A₁–A₂½A₂ запишем в виде A₁®A₁a₁½A₁a₂½b₁, где a₁= +A₂, a₂= –A₂, b₁=A₂. Согласно алгоритму, запишем в P¢ новые правила для A₁:

A₁ ® A₂½A₂A₁¢, A₁¢ ® +A₂½–A₂½+A₂A₁¢½–A₂A₁¢. Символы A₁ и A₁¢ заносим в V_N¢. Получим V_N¢={A₁, A₁¢}.

Шаг 3. Поскольку i=1<3, i:=i+1=2, j:=1, переходим на следующий шаг.

Шаг 4. Для символа A₂ во множестве правил P нет правила вида A₂®A₁a, поэтому на этом шаге никаких действий не выполняется.

Шаг 5. Так как j=1=i–1, переходим на шаг 2.

Шаг 2. Правила для A₂: A₂ ® A₂*A₃½A₂/A₃½A₃ запишем в виде A₂®A₂a₁½A₂a₂½b₁, где a₁=*A₃, a₂=/A₃, b₁=A₃. Согласно алгоритму, запишем в P¢ новые правила для A₂:

A₂ ® A₃½A₃A₂¢, A₂¢ ® *A₃½/A₃½*A₃A₂¢½/A₃A₂¢. Символы A₂ и A₂¢ добавим в V_N¢. Получим V_N¢={A₁, A₁¢, A₂, A₂¢}.

Шаг 3. Поскольку i=2<3, то i:=3, j:=1, переходим на следующий шаг.

Шаг 4. Для символа A₃ во множестве правил P нет правила вида A₃®A₁a, поэтому на этом шаге никаких действий не выполняется.

Шаг 5. Так как j=1< i–1, то j:=j+1=2 и переходим на шаг 4.

Шаг 4. Для символа A₃ во множестве правил P нет правила вида A₃®A₂a, поэтому на этом шаге никаких действий не выполняется.

Шаг 5. Так как j=2=i–1, переходим на шаг 2.

Шаг 2. Правила для A₃: A₃ ® (A₁)½a½b не содержат левой рекурсии, поэтому поместим их в P¢ без изменений. Символ A₃ добавим в V_N¢. Получим V_N¢={A₁, A₁¢, A₂, A₂¢, A₃}.

Шаг 3. Поскольку i=3, построение грамматики закончено.

В итоге получили нелеворекурсивную грамматику G ({+,–,/,*,a,b,(,)}, {A₁, A₁¢, A₂, A₂¢, A₃}, P, A₁), где правила P имеют вид:

A1 ® A2½A2A1¢,	A2 ® A3½A3A2¢,
A1¢ ® +A2½–A2½+A2A1¢½–A2A1¢.	A2¢ ® *A3½/A3½*A3A2¢½/A3A2¢.
	A3 ® (A1)½a½b.

Грамматика называется грамматикой в нормальной форме Грейбах, если она не является леворекурсивной и в её множестве правил присутствуют только правила следующего вида:

1. A®aa, где aÎV_T aÎV_N^*.

2. S®e, если eÎL(G) и S не встречается в правых частях правил.

Нормальная форма Грейбах удобна для построения нисходящих левосторонних распознавателей.

Алгоритм 7. Преобразование приведенной КС-грамматики без левой рекурсии к нормальной форме Грейбах с применением линейного порядка:

Вход: Нелеворекурсивная приведенная КС-грамматика G = (V_N, V_T, Р, S).

Выход: Эквивалентная КС-грамматика G' в нормальной форме Грейбах. Описание алгоритма:

Шаг 1. Построить такой линейный порядок (<) на N, что каждое A-правило начинается либо с терминала, либо с такого нетерминала В, что А < В. Упорядочить N = {А₁, А₂,..., А_п) так, что А₁< А₂<... < А _n. Причем правила, начинающиеся с нетерминала A_N < A_T правил, начинающихся с терминала. Между правилами вида A_T порядок значения не имеет.

Шаг 2. Положить i = п’, где n’ –число правил, начинающихся с терминала

Шаг 3. Если i = 0, то перейти к шагу 5 алгоритма. В противном случае заменить каждое правило вида A_i®А_j a, где j > i, правилами А_i ® b₁a | b₂a

| … | b_ma,  где A_j®b₁ | b₂| … | b_m –все правила A_j

Шаг 4. Положить i= i-1 и перейти к шагу 3.

Шаг 5. Теперь правая часть каждого правила начинается терминальным символом. В каждом правиле А ® аХ_i...X_k заменить X_jÎV_T  новым нетерминалом X'_j.

Шаг 6. Для новых нетерминалов X'_j, введенных на 5-ом шаге,

добавить правила X'_j ® X_j

Пример 8. G={{*,n},{S,A,B},{S→B*A, B→n | A*B, A→n},S}

1. Упорядочим символы S<B<A, i=2 (шаги 1,2)

2. Заменяем правило B→n | A*B на B→n | n*B, подставляя из A→n (шаг 3)

3. i=1 (шаг 4)

4. Заменяем правило S→B*A на S→ n*A |n*B*A, подставляя из B→n | n*B

5. i=0 (шаг 4)

6. Введем нетерминальный символ <*> (шаг 5)

7. Заменим * на <*>

P’: S→ n<*>A |n<*>B<*>A

    B→n | n<*>B

A→n

<*>→*

              G’= ({*,n},{S,A,B, <*>},P’, S)

4.2.3.3. Контрольные вопросы

1. Какого типа грамматики могут быть приведены к нормальной форме Хомского?

2. Каковы требования на правила грамматики в БНФ?

3. Обязательно ли наличие рекурсии в правилах грамматики? Какого вида рекурсия в них может использоваться? Может ли в правилах одной грамматики присутствовать рекурсия разных видов?

4. От какого вида рекурсии в правилах грамматики принято избавляться и для чего это делается?

Метод рекурсивного спуска

Самым простым способом является выбор одной из множества альтернатив на основании текущего входного символа. Необходимо найти альтернативу, где этот символ присутствует в начале цепочки, находящейся в правой части правила грамматики – на этом принципе основан метод рекурсивного спуска.

Алгоритм разбора по методу рекурсивного спуска

Для каждого нетерминального символа исходной грамматики на основании правил строится процедура разбора, на вход которой подаётся цепочка символов a  и положение считывающей головки в этой цепочке i. Если для символа AÎV_N в грамматике задано несколько правил, то при разборе выбирается то правило, в котором первый (терминальный) символ правой части совпадает с текущим входным символом: a_i=a, (A®ab)ÎP, aÎV_T, bÎ(V_NÈV_T)^*. Если такого правила нет, цепочка не принимается. Если оно есть или для символа A в грамматике существует единственное правило A®b, то фиксируется номер правила. Если a_i=a в найденном правиле, то считывающая головка передвигается – увеличивается номер i, а для каждого нетерминального символа из цепочки b рекурсивно вызывается процедура его разбора.

Для начала разбора входной цепочки необходимо вызвать процедуру разбора для символа S с параметром i=1. Если в итоге разбора входной цепочки считывающая головка остановится на символе с номером n+1, то разбор закончен, цепочка принята, а выданная последовательность номеров правил представляет собой цепочку вывода.

Данный метод накладывает жёсткие ограничения на правила задающей язык грамматики. Для каждого нетерминального символа A грамматики G разрешаются только два вида правил:

1) (A®b)ÎP, bÎ(V_NÈV_T)^*, и это единственное правило для A;

2) A®a₁b₁½a₂b₂½…½a_nb_n, "i a_iÎV_T, bÎ(V_NÈV_T)^*, и a_i¹a_j, если i¹j, т.е. все a_i различны.

Таким образом, для каждого нетерминала либо должно существовать единственное правило вывода, либо – если их несколько – все правые части правил вывода должны начинаться с разных терминальных символов. Таким условиям удовлетворяет незначительное количество реальных грамматик. Возможно, что грамматика может быть приведена к требуемому виду путём некоторых преобразований.

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

1. Исключение пустых правил.

2. Исключение левой рекурсии.

3. Преобразование к нормальной форме Грейбах?????

4. Добавление новых нетерминальных символов (факторизация). Например, если существует правило A®aa₁½aa₂½…½aa_n½b₁b₁½b₂b₂½…½b_mb_m, то заменяем его на два: A®aA¢½b₁b₁½b₂b₂½…½b_mb_m, A¢® a₁½a₂½…½a_n.

5. Замена нетерминальных символов в правилах на цепочки их выводов. Например, если есть правила A®B₁½B₂½…½B_n½b₁b₁½b₂b₂½…½b_mb_m,
B₁®a₁₁½a₁₂½…½a_1k,
…
B_n®a_n1½a_n2½…½a_nk, то заменяем первое правило на
A®a₁₁½a₁₂½…½a_1k½…½a_n1½a_n2½…½a_nk½b₁b₁½b₂b₂½…½b_mb_m

Алгоритм рекурсивного спуска эффективен и прост в реализации, но имеет очень ограниченную применимость.

Рассмотрим пример.

Дана грамматика G({a,b,c},{A,B,C,S},P,S), где правила P имеют вид:

S®aA ₍₁₎|bB ₍₂₎

A ® a ₍₃₎| bA ₍₄₎| cC ₍₅₎

B ® b ₍₆₎| aB ₍₇₎| cC ₍₈₎

C ® AaBb ₍₉₎

Правила грамматики удовлетворяют требованиям метода рекурсивного спуска. Построим для каждого нетерминала процедуру разбора. Будем использовать псевдокод.

Процедура Rule(num);

Записать в вывод номер правила num;

Процедура Proc_S(str,k); {входная строка и номер текущего символа}

 Выбор str[k] из:

 a: Rule(1);

вернуть Proc_A(str,k+1);

 b: Rule(2);

вернуть Proc_B(str,k+1);

 иначе вернуть 0;

 

Процедура Proc_A(str,k);  Выбор str[k] из:  a: Rule(3); вернуть k+1;  b: Rule(4); вернуть Proc_A(str,k+1);  c: Rule(5); вернуть Proc_C(str,k+1);  иначе вернуть 0;	Процедура Proc_B(str,k);  Выбор str[k] из:  a: Rule(7); вернуть Proc_B(str,k+1);  b: Rule(6); вернуть k+1;  c: Rule(8); вернуть Proc_C(str,k+1);  иначе вернуть 0;
Процедура Proc_C(str,k); Rule(9); i:=Proc_A(str,k); если i=0 вернуть 0; если str[i]≠’a’ вернуть 0; i:=Proc_B(str,i+1); если i=0 вернуть 0; если str[i]≠’b’ вернуть 0; вернуть i+1;	Пусть цепочка a = ‘acbaabb’. Разбор начинается с вызова Proc_S(a,1). Дальнейшие вызовы и вывод номеров использованных правил будут происходить в следующем порядке:

Proc_S(a,1) (символ ‘a’, вывод 1) Þ Proc_A(a,2) (‘c’, вывод 5) Þ Proc_C(a,3) (вывод 9) Þ Proc_A(a,3) (‘b’, вывод 4) Þ Proc_A(a,4) (‘a’, вывод 3, в Proc_C верн. i=5) Þ Proc_B(a,6) (‘b’, вывод 6, в Proc_C верн. i=7) Þ вернули 8=n+1 Þ stop(+). Правила вывода 1, 5, 9, 4, 3, 6.

S Þ₍₁₎ aA Þ₍₅₎ acC Þ₍₉₎ acAaBb Þ₍₄₎ acbAaBb Þ₍₃₎ acbaaBb Þ₍₆₎ acbaabb.

Метод рекурсивного спуска позволяет выбирать альтернативу на основе текущего символа входной цепочки. Если же имеется возможность обозревать не один, а несколько символов вперед от текущего положения входной головки, то область применения этого метода может быть расширена. Тогда можно искать подходящие правила на основе некоторого терминального символа, входящего в правую часть правила (т.е. этот символ не обязан быть первым). Выбор и в таком случае должен осуществляться однозначно, т.е. для каждого нетерминального символа левой части необходимо, чтобы в правой части разных правил не встречалось двух одинаковых терминальных символов.

Поскольку один и тот же терминальный символ может встречаться во входной цепочке неоднократно, то в зависимости от типа рекурсии требуется искать либо его крайнее левое, либо крайнее правое вхождение, т.е. метод требует анализа типа использованной в грамматике рекурсии.

Для применения метода рекурсивного спуска требуется осуществлять неформальный анализ правил исходной грамматики G. При наличии большого количества правил такой анализ практически нереализуем, поэтому данный метод хотя и нагляден, но слабо применим.

Существуют распознаватели, основанные на строго формализованном подходе. Подготовка данных (правил грамматики) может быть строго формализована и автоматизирована.

Разбор для LL(k)-грамматик

Логическим продолжением идеи рекурсивного спуска является попытка использовать для выбора единственной из множества альтернатив не один, а несколько символов входной цепочки. Сложность заключается в том, что эти несколько соседних символов цепочки могут быть получены с применением не одного, а нескольких правил.

Грамматика обладает свойством LL(k) (называется LL(k)-грамматикой) для k>0, если на каждом шаге вывода для однозначного выбора очередной альтернативы автомату с магазинной памятью необходимо знать один верхний символ стека и рассмотреть k символов входной цепочки справа от положения считывающей головки.

Существуют LL(1), LL(2), LL(3), … грамматики. Все они в совокупности образуют класс LL-грамматик. В этом обозначении (LL) первая L означает, что входная цепочка считывается в направлении слева направо, а вторая L – что выполняется левосторонний разбор. Число k показывает, сколько символов справа от считывающей головки нужно рассмотреть для однозначного выбора альтернативы.

Алгоритм разбора входных цепочек для LL(k)-грамматик называется k-предсказывающим алгоритмом.  

Свойства LL(k)-грамматик.

§ Всякая LL(k)-грамматика для любого k>0 является однозначной.

§ Существует алгоритм проверки, является ли произвольная КС-грамматика LL(k)-грамматикой для строго определённого числа k.

§ Всякая грамматика, допускающая разбор по методу рекурсивного спуска, является LL(1)-грамматикой. Обратное не справедливо.

Проблемы LL(k)-грамматик:

§ Не существует алгоритма, позволяющего проверить, является ли произвольная КС-грамматика LL(k)-грамматикой для любого числа k.

§ Не существует алгоритма преобразования произвольной КС-грамматики к виду LL(k)-грамматики для некоторого k (либо доказывающего, что такое преобразование невозможно).

Для LL(k)-грамматик для любого k>1 не обязательно все k символов должны находиться в одной цепочке в правой части правила вывода. Если это так, то такая грамматика называется сильно LL(k)-грамматикой. Но обычно эти символы находятся в правых частях разных правил.

Особенности правил грамматики класса LL(1):

1) В правилах грамматики не может существовать для одного нетерминального символа двух или более правил с одинаковым первым терминальным символом в правой части.

2) В отличие от метода рекурсивного спуска допускаются правила вида A®Ba и пустые правила.

3) Правила грамматики не должны содержать левой рекурсии.

LL-грамматики позволяют построить распознаватели с линейной