Все вопросы к тесту (html) Системное программное обеспечение (курс 1)

Дана грамматика

S -> SAS|S|a|b

A -> +|-|*|/|^

Грамматика генерирует арифметические выражения без скобок

Создайте предиктивный рекурсивный анализатор для грамматики

S->aS|bA

A->c

Введите строку “aaabkc”. Получите количество прочитанных символов строки и номер последней используемой продукции.

ответ введите в формате: «___, ___»

Дана грамматика

S->(S)A(S)|SAS|a|b|2

A->+|-|*|/|^

Создайте предиктивный рекурсивный анализатор для грамматики

S->aS|bA

A->a|bB

B->bS|c

Введите строку “bbbba”. Получите значение n и err для данной строки.

ответ введите в формате: «n=___, err=___»

Дана грамматика

S->SAS|(S)|a|b

A->+|-|*|/|^

Создайте предиктивный рекурсивный анализатор для грамматики

S->aS|bA

A->bA|c

Введите строку “aaabbbc ”. Получите значение n и err для данной строки.

ответ введите в формате: «n=___, err=___»

Дана грамматика

S->SAS|(S)|a|b|2

A->+|-|*|/|^

Создайте предиктивный рекурсивный анализатор для грамматики

S->aS|bA

A->aA|bB

B->bB|c

Введите строку “abaaaabc”. Получите значение n и err для данной строки.

ответ введите в формате: «n=___, err=___»

Дана грамматика

S->SAS|(S)|a|b|2

A->+|-|*|/|^

Создайте предиктивный рекурсивный анализатор для грамматики

S->aS|bA

A->cA|d

Введите строку “abccd”. Получите значение n и err для данной строки.

ответ введите в формате: «n=___, err=___»

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

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

S->abA

A->bA|c

Напомним, что контекстно-свободной грамматикой называется грамматика, в левых частях продукций которой содержится только один нетерминальный символ. Здесь приняты обычные обозначения: нетерминальные символы обозначаются прописными буквами, терминальные – строчными, вертикальная черта разделяет различные альтернативы продукции. Очевидно, что данная грамматика генерирует строки вида abb…bbc, т.е. начинающиеся с символа ‘a’, заканчивающиеся символом ‘c’ и содержащие внутри произвольное количество символов ‘b’. Построим дерево разбора для строки “abbc”. Построение начинается с корня дерева, т.е. с начального символа грамматики S.

На 1-м шаге используется 1-я продукция, т.е. S заменяется на abA. На 2-м шаге используется 1-я альтернатива 2-й продукции, т.е. А заменяется на bA. И, наконец, на 3-м шаге используется 2-я альтернатива 2-й продукции - А заменяется на с. На рисунке узлы дерева, т.е. нетерминальные символы заключены в кружочки. Листья дерева т.е.терминальные символы формируют нужную строку.

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

Номер прохода

Номер продукции

Номер альтернативы

1

1

1

2

2

1

3

2

2

Важно проследить как в данном конкретном примере происходит выбор нужной продукции. Поскольку разбор «сверху вниз» всегда начинается с начального символа грамматики – S, а для S у нас имеется всего одна продукция, то выбор однозначен – это S->abA. Таким образом анализируемая строка должна начинаться с символов “ab”, в противном случае должно появляться сообщение об ошибке. На следующем шаге имеется выбор: выбрать 1-ю или 2-ю альтернативу. Для того, чтобы сделать правильный выбор, нужно знать следующий символ строки, идущий за “ab”. Поскольку следующим символом является ‘b’, то нужно выбрать 1-ю альтернативу. И, наконец, на 3-м шаге выбирается 2-я альтернатива, т.к. следующим символом в строке является ‘c’.

Постройте дерево разбора строки “abbc” с помощью программы Grammatic.exe. Для этого

• Запустите программу Grammatic.exe. На экране появится окно «Формальные грамматики», показанное на рисунке. Программа генерирует цепочки символов в соответствии с продукциями заданной грамматики. Продукции заносятся в ячейки таблиц «Левая часть продукции» и «Правая часть продукции». В окно «Количество продукций» заносится число используемых продукций. В окне «Временная задержка (мсек)» указывается величина временной задержки между тактами перебора продукций. Это позволяет проследить процесс генерации выходной цепочки. Сама результирующая цепочка появляется в окне «Выходная строка». Окно «Контрольное число» используется в самостоятельной работе.

Выходная строка формируется в соответствии с заданным деревом разбора, который задается в виде двух таблиц. В таблице «Номер прохода» указывается номер прохода (перебора) символов входной строки. В столбцах «Номер продукции» и «Номер альтернативы» необходимо указать какая альтернатива используется в данной продукции в данном проходе.

Кнопка «Start» используется для запуска процесса перебора продукций.

Кнопка «Clear» - для очистки содержимого таблиц и окон.

Кнопка «Close» - для закрытия окна.

• В окне «Количество продукций» укажите число используемых продукций (2)
• В 1-ю ячейку колонки «Левая часть продукции» введите левую часть используемой продукции (символ S).
• В 1-ю ячейку колонки «Правая часть продукции» введите правую часть 1-й используемой продукции (строка abA). Все строки вводятся без пробелов.
• В 2-ю ячейку колонки «Левая часть продукции» введите левую часть 2-й продукции (символ А).
• В 2-ю ячейку колонки «Правая часть продукции» введите правую часть используемой продукции (строка bА|с).
• Введите временную задержку выполнения продукций, которая позволяет проследить процесс формирования выходной цепочки символов. Введите задержку равной 1000мсек.
• Заполните колонки «Номер продукции» и «Номер альтернативы» в соответствии с вышеприведенной таблицей.
• Нажмите кнопку Start и в окне «Выходная строка» наблюдайте процесс формирования выходной строки.

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

Структура программы предиктивного анализа для рассмотренной выше грамматики имеет следующий вид. Т.к. грамматика содержит всего 2 нетерминальных символа S и A, то соответственно в программе должны присутствовать две процедуры для этих символов. Назовем их PS и PA. Кроме того для удобства введена дополнительная процедура match(t:char), которая осуществляет чтение очередного символа строки, сравнение его с символом t и если символы не совпадают выдает сообщение об ошибке. Каждая из процедур PS и PA осуществляет вызовы процедур match, PS, PA в соответствии с правой частью выбранной продукции. Выбор продукции зависит от очередного символа строки.

Ниже приведена блок - схема анализатора для выше рассмотренной грамматики.

В начале программы происходит описание используемых глобальных переменных. Поскольку, в общем случае, процедуры PS и PA являются рекурсивными, т.е. могут обращаться к самой себе или непосредственно или через другую процедуру, то необходимо указать, что данная процедура бeдет определена ниже, что делается с помощью ключевого слова forward. Далее идет непосредственное описание процедур, задействованных в анализаторе. После описания процедур идет головная программа, в которой задается входная анализируемая строка и начальные значения номера сканируемого символа и номера продукции. Заканчивается программа выводом результатов. Это может быть код ошибки – err, номер последнего сканируемого символа – n, последовательность номеров используемых продукций – массив Pr.

Рассмотрим как действует процедура PS. Работа процедуры начинается с того, что в элемент массива Pr[k] заносится номер используемой продукции (т.е. 1) после чего k увеличивается на 1. Поскольку для символа S у нас имеется одна продукция, а именно S->abA, то процедура PS должна проверить, что первые два символа входной строки – это “ab”. Это делается с помощью двукратного обращения к процедуре match (сначала match(‘a’) затем match(‘b’)). После каждого обращения проверяется код ошибки – err. В случае ошибки происходит выход из программы. Поскольку последним символом продукции является нетерминальный символ А, то последним оператором процедуры является оператор обращения к процедуре PA.

Рассмотрим как действует процедура PА. Вторая продукция грамматики A->bA|c содержит две альтернативы, будем считать их продукциями 2 и 3 соответственно. Если текущим символом строки является символ ‘b’, то используется первая альтернатива, т.е. продукция 2, если ‘с’, то вторая, т.е. продукция 3. В соответствии с этим работа процедуры РА должна начинаться с проверки текущего символа входной строки – A[n]. Если A[n]=’b’, то в Pr[k] заносится номер используемой продукции – 2, k увеличивается на 1, затем происходит обращение с процедуре match(‘b’) и, если нет ошибки (err не равно -1), то опять к процедуре РА. Если A[n]=’с’, то в Pr[k] заносится номер используемой продукции – 3, k увеличивается на 1, затем происходит обращение к процедуре match(‘с’) и, если нет ошибки (err не равно -1), то выход из процедуры. В случае, если A[n] ≠ ‘b’ и A[n] ≠ ‘c’ то err:=-1; и выход из программы.

Процедура match(‘t’) должна сравнивать текущий символ строки A[n] с символом ‘t’ и, если A[n]=’t’, то переходим к следующему символу строки (n:=n+1;), заносим в err 1 и выходим из процедуры. Если A[n] ≠ ‘t’, то заносим в err -1 и выходим из процедуры.

Для реализации программы предиктивного, рекурсивного анализа проделайте следующее:

• Двойным щелчком запустите программу Pascal ABC.
• В появившемся окне транслятора наберите текст программы в соответствии с блок-схемой программы и описанием процедур, приведенных выше.
• Задайте входную строку “abbbc” и запустите программу (зеленый треугольник на стандартной панели инструментов).

4. Проанализируйте полученные результаты. Анализ должен состоять в следующем. Если строка, как в данном случае, принимается грамматикой, то

a. n должно равняться длине строки + 1 (=6)

b. код ошибки err должен равняться 1

c. массив Pr содержит номера продукций, которые были использованы при разборе данной строки.

5. Сотрите результаты анализа, нажав Ctrl+del

6. Введите вместо строки “abbbc” заведомо ошибочную строку “abbcbbc” и запустите транслятор. Должны получиться следующие результаты.

n=5

err=1

Pr[1]=1, Pr[2]=2, Pr[3]=3,

Следовательно, строка не принимается грамматикой, поскольку не выполнено условие a. Так как n=5, то верны только первые 4 символа строки.

7. Сотрите результаты анализа, нажав Ctrl+del.

8. Введите ошибочную строку “absbbc” и запустите транслятор. Должны получиться следующие результаты

n=3

err=-1

Pr[1]=1

Следовательно, строка не принимается грамматикой, поскольку не выполнены условия a и b. В этом случае значение n указывает на номер ошибочного символа.

Тема:

Элементы теории трансляции. Разработка программы синтаксического анализатора методом рекурсивного спуска

Используемые программы:

Pascal ABC, Grammatic.exe