Контекстно-свободные грамматики

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

Метод разбора (распознавания) является детерминированным, если при разборе данной грамматики не требуется делать возврат. Некоторые грамматики можно разбирать детерминированно только с помощью одного из методов разбора. Разбор цепочки означает построение вывода и, возможно, синтаксического дерева для нее. Программу разбора называют также распознавателем, так как она распознает только цепочки рассматриваемой грамматики. Если в процессе вывода цепочки правила грамматики применяются только к самому левому нетерминалу, говорят, что получен левый разбор цепочки. Аналогично определяется правый разбор цепочки.

Различают два класса алгоритмов разбора контекстно-свободных грамматик:

- низходящий;

- восходящий.

К первому классу относятся те, которые строят деревья выводов начиная с корня и вершин, соответствующим наиболее крупным синтаксическим единицам. В этом случае входная цепочка просматривается многократно. Этот класс алгоритмов наиболее универсален, к нему относятся LL-грамматики.

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

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

Две буквы L означают, что строки разбираются слева направо и используются левые выводы. Цифра k означает количество предварительно просмотренных символов.

Пример. Рассмотрим LL(1) - грамматику:

(1) S → aAS

(2) S → b

(3) A → a

(4) A → bSA

Работой алгоритма разбора руководит управляющая таблица, в которой содержится:

- правая часть применяемого правила;

- маркер выброса символа из стека;

- маркер допуска цепочки символов;

- маркер ошибки.

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

Управляющая таблица для заданной грамматики имеет вид:

С помощью этой таблицы проанализируем входную цепочку abbab. В стеке находится маркер конца стека и начальный символ S.

Таблица разбора цепочки

Получаем, что цепочка допущена.

Алгоритм анализа входной цепочки следующий: на каждом шаге определяется аванцепочка (это цепочка из k символов впереди) и верхний символ стека. По этим данным определяется элемент управляющей матрицы. Возможны следующие варианты действий:

- верхний символ магазина заменяется цепочкой (применение правой части правила) и к списку применяемых правил добавляется новый номер правила;

- верхний символ стека совпадает с текущим входным символом, следовательно, он выбрасывается из магазина;

- входная цепочка пуста и стек пуст, то работа прекращается и цепочка считается допущенной;

- при возникновении ошибки разбор прекращается и выдается сообщение об ошибки.

Ко второму классу относятся распознаватели, которые читая входную цепочку строят ее дерево вывода начиная с вершин, соответствующих наиболее мелким конструкциям, и кончая корнем. В этом случае детерминированный разбор реализуется в терминах “сдвиг” и “свертка”. Сдвиг – это перенос символа из входной цепочки в магазин(стек), а свертка – применение к вершине магазина какого-либо правила грамматики. Проблема в этом случае состоит в выборе между сдвигом и сверткой и в выборе правила для свертки.

LR-грамматика и грамматики предшествования наиболее часто используемые из грамматик восходящего разбора. LR(k) – грамматикой называется грамматика, при использовании которой в качестве основы для анализатора все конфликты типа сдвиг – свертка и свертка – свертка можно разрешать на основании уже прочитанного текста и фиксированного числа предварительно просматриваемых символов.

Буква L показывает, что строки читаются слева направо, а R – что получается правосторонний разбор. На практике k принимает значение 0 или 1. Читая входную цепочку слева направо, анализатор пытается свернуть ее в начальный символ.

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

Рассмотрим пример LR(0) – грамматики. При разборе строки LR(0) языка аванцепочка не используется. Просмотренные символы правила, расположенные левее текущей позиции (обозначается “_”) называют активным префиксом.

(1) S → aSS

(2) S → b

При рассмотрении LR – грамматик используют “пополненные грамматики”. Добавляем новый начальный символ и получаем следующую грамматику:

(1) S′ → S

(2) S → aSS

(3) S → b

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

0 V(e) [S′ → _S], [S → _aSS], [S → _b]

1 V(a) [S → a_SS], [S → _aSS], [S → _b]

2 V(b) [S → b_]

3 V(S) [S′ → S_]

4 V(aS) [S → aS_S], [S → _aSS], [S → _b]

5 V(aSS) [S → aSS_]

Если текущая позиция стоит перед S, то во множество ситуаций входят все ситуации с правилами для S. Если во множестве ситуаций правила не закончены, то дальнейшее действие – сдвиг. После сдвига в состоянии 1 возможны следующие активные префиксы: aa, aS,ab. Когда правило закончено (состоянии 2 и 5) необходима свертка. Состояние 3 говорит о получении начального символа, следовательно, разбор закончен. Множество ситуаций конечно, так как получаемые в дальнейшем с помощью сдвига активные префиксы будут повторять уже описанные ситуации.

Построенное множество ситуаций называется канонической LR(0) –системой. В ней нет конфликтов типа сдвиг-свертка и свертка-свертка. По данным состояниям можно осуществлять разбор предложений языка и,следовательно, грамматика обладает свойством LR(0).

Составим управляющую таблицу для LR(0) разбора. Количество строк в таблице равно числу состояний, количество столбцов – число терминалов и нетерминалов в грамматике плюс три. Первый столбец – номер состояния, далее столбец с активным префиксом, затем столбец действия по данному состоянию. Далее следует несколько столбцов для задания переходов по символам правил. Для вышеуказанного примера таблица имеет следующий вид:

В начале работы в стеке содержится фиктивный элемент с состоянием V(0). В процессе работы по текущему состоянию (вершине стека) выбирается действие. Если действие “сдвиг”, то очередной символ из входной строки помещается в стек. По текущему состоянию и этому символу вычисляется новое состояние, которое записывается на вершину стека. Если действие “свертка”, то из стека извлекается нужное количество символов. По состоянию на новой вершине стека и полученному при свертке нетерминалу вычисляется новое состояние, которое вместе с нетерминалом записывается на вершину стека.

Грамматики предшествования являются подклассами LR(k) – грамматик. При разборе данного типа грамматик используется понятие “основа цепочки”. Основа правовыводимой цепочки – это ее любая подцепочка которая является правой частью некоторого правила, причем после замены ее левой частью этого правила, тоже получается правовыводимая цепочка. Таким образом, если цепочку abw можно свернуть в цепочку aAw с помощью правила A®b, то b - основа цепочки abw.

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

·> - конец основы, выполняется между последним символом цепочки b и первым символом цепочки w;

<· - начало основы, выполняется между последним символом цепочки a и первым символом цепочки b;

=· - выполняется между смежными символами основы.

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

Грамматика является грамматикой простого предшествования, если она приведенная, не содержит е-правил и для любой пары символов выполняется не более одного отношения предшествования.

Рассмотрим грамматику, состоящую из правил:

S®aSSb½c

В качестве начала и конца цепочки используются маркеры # или $. Найдем отношения предшествования.

1) =· Просматриваем правые части правил, получаем a =· S, S =· S, S =· b.

2) <· Ищем в правых частях правил пары смежных символов ХС, таких что Х находится в отношении <· с самым левым символом цепочки, выводимой из С.

Рассмотрим пару aS, получим a <· a, a <· c. Рассмотрим пару SS, получим S <· a, S <· c. Рассмотрим начальный маркер, получим $ <· a, $ <· c.

3) ·> Ищем в правых частях правил пары смежных символов СХ. Затем ищем символы Y, которые могут оказаться на правом конце цепочки, выводимой из С за один или более шагов, и терминалы d, которые могут находиться в начале цепочки, выводимой из Х за нуль и более шагов. В нашем случае это пары:

SS: b ·> a, b ·> c, c ·> a, c ·> c; Sb: b ·> b, c ·> b; конечный маркер: b ·> $, c ·> $.

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

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

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

f(x,a) – перенос (сдвиг), если х <· a или х =· а.

f(x,a) – свертка, если х ·> a.

f(x,a) – ошибка в противоположных случаях.

f($S$) – допуск цепочки.

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

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

Рассмотрим отношения:

a =· b, если есть правило A®…ab… или A®…aBb…

a <· b, если есть правило A®…aB и B®b… или B®Cb…

a ·> b, если есть правило A®…Bb… и B®…a или B®…aC

$ <· a, если есть правило S®Ca… или S®a…

a ·> $, если есть правило S®…aC или S®…a

Пример: рассмотрим грамматику арифметических формул

S®S + T | T

T®T * E | E

E®(S) | a

Управляющая таблица имеет следующий вид:

Алгоритм разбора цепочки по управляющей таблице аналогичен предыдущему.

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

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

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

Варианты заданий

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

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

3. Язык арифметических выражений с операциями языка Си (+, -, *, /, + +, - -, %), без скобок, с операндами в форме идентификаторов и констант (целых, с фиксированной и плавающей запятой).

4. Язык арифметических выражений с операциями языка Си (+, -, *, /, + +, - -, %), со скобками, с операндами в форме идентификаторов и констант (целых).

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

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

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

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

9. Язык логических выражений с операциями.NOT.,.OR.,.AND., без скобок, с операндами в форме идентификаторов, константами.TRUE.,.FALSE. и операциями отношений в синтаксисе ФОРТРАНа (.GE.,.LE.,.NE.,.EQ.,.GT.,.LT.).

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

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

12. Язык адресных выражений языка Си с операциями ссылок (&, *), без скобок, с операндами в форме идентификаторов и элементов массива.

13. Язык адресных выражений языка Си с операциями ссылок (*, &, ®), со скобками, с операндами в форме идентификаторов.

14. Язык выражений с побитовыми операциями логики языка Си, со скобками, с операндами в форме идентификаторов и целыми константами (в двоичной форме).

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

16. Язык арифметических выражений в инфиксной форме с операциями сложения, вычитания, умножения, деления со скобками, с операндами в форме идентификаторов и элементов массива.

17. Язык функциональных выражений. Каждая функция имеет один аргумент. Аргументами являются идентификаторы, элементы массива и константы.

18. Язык функциональных выражений с произвольным количеством аргументов и неограниченной вложенностью. Аргументы – идентификаторы: f(g(x,e(y,z))).

19. Язык арифметических выражений в постфиксной форме с операциями сложения, вычитания, умножения, деления без скобок, с операндами в форме идентификаторов и элементов массива.

20. Язык арифметических выражений в префиксной форме с операциями сложения, вычитания, умножения, деления без скобок, с операндами в форме идентификаторов и элементов массива.

21. Язык арифметических выражений с одноместными операциями языка программирования Си (++, --, =, +=, -=, *=, /=, %=), с операндами в форме идентификаторов и элементов массива.

22. Язык арифметических выражений в инфиксной форме с операциями сложения, вычитания, умножения, деления без скобок, с операндами в форме идентификаторов и элементов массива.

23. Язык арифметических выражений в инфиксной форме с операциями сложения, вычитания, умножения, деления со скобками, с операндами в форме идентификаторов и элементов массива.

24. Язык выражений в синтаксисе Си, включающий присваивание, префиксный и постфиксный инкремент и декремент, сложение, вычитание, умножение, деление, с операндами в форме идентификаторов и констант.

25. Язык выражений в синтаксисе Си, включающий присваивание, префиксный и постфиксный инкремент и декремент, сложение, вычитание, умножение, деление, с операндами в форме идентификаторов и функциональных вызовов. Допустимы вызовы функций с произвольным количеством аргументов в форме идентификаторов.