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

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

S -> SAS|S|a|b

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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-й столбец – номер альтернативы. Для рассматриваемой строки таблица разбора выглядит следующим образом.

Важно проследить как в данном конкретном примере происходит выбор нужной продукции. Поскольку разбор «сверху вниз» всегда начинается с начального символа грамматики – 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 и в окне «Выходная строка» наблюдайте процесс формирования выходной строки.

Тема:

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

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

Pascal ABC, Grammatic.exe