Системное программное обеспечение. Лабораторный практикум

6. Сдать работающую программу преподавателю.

Требования к оформлению отчета

Отчет должен содержать следующие разделы:

• Задание по лабораторной работе.

• Краткое изложение цели работы.

• Запись заданной грамматики входного языка в форме Бэкуса—Наура (если для построения синтаксического распознавателя используется механизм, требующий преобразования исходной грамматики входного языка, то эти преобразования и полученная в результате их грамматика должны быть отражены в отчете).

• Множества крайних правых и крайних левых символов с указанием шагов построения.

• Множества крайних правых и крайних левых терминальных символов.

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

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

• Текст программы (оформляется после выполнения программы на ЭВМ).

Основные контрольные вопросы

• Какую роль выполняет синтаксический анализ в процессе компиляции?

• Какие проблемы возникают при построении синтаксического анализатора и как они могут быть решены?

• Какие типы грамматик существуют? Что такое КС-грамматики? Расскажите об их использовании в компиляторе.

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

• Поясните правила построения дерева вывода грамматики.

• Что такое грамматики простого предшествования?

• Как вычисляются отношения предшествования для грамматик простого предшествования?

• Что такое грамматика операторного предшествования?

• Как вычисляются отношения для грамматик операторного предшествования?

• Расскажите о задаче разбора. Что такое распознаватель языка?

• Расскажите об общих принципах работы распознавателя языка.

• Что такое перенос, свертка? Для чего необходим алгоритм «перенос-свертка»?

• Расскажите, как работает алгоритм «перенос-свертка» в общем случае (с возвратами).

• Как работает алгоритм «перенос-свертка» без возвратов (объясните на своем примере)?

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

Варианты исходных грамматик

Далее приведены варианты грамматик. Во всех вариантах символ S является начальным символом грамматики; S, F, T и Е обозначают нетерминальные символы.

Терминальные символы выделены жирным шрифтом. Вместо символа а должны подставляться лексемы.

1. S → a:= F;

F → F+T |Т

Т → Т·Е | TIE | Е

Е → (F) | – (F) | а

2. S → a:= F;

F → F or Т | F хог T | T

T → Т and E | Е

Е → (F) | not (F) | a

3. S → F;

F → if E then T else F| if E then F| a:= a

T → if E then T else T | a:= a

E → aa | a=a

4. S → F;

F → for (T) do F | a:= a

T → F;E;F |;E;F | F;E; |;E;

E → aa I a=a

Исходные грамматики и типы допустимых лексем

Ниже в табл. 3.1 приведены номера заданий. Для каждого задания указана соответствующая ему грамматика и типы допустимых лексем.

Таблица 3.1. Номера заданий для выполнения лабораторной работы

Примечание.

• Римскими числами считать последовательности больших латинских букв X, V и I.

• Шестнадцатеричными числами считать последовательность цифр и символов «а», «Ь», «с», «d», «е» и «f», начинающуюся с цифры (например: 89, 45ас9, 0abc4).

• Для выполнения работы рекомендуется использовать лексический анализатор, построенный в ходе выполнения лабораторной работы № 2.

Пример выполнения работы

Задание для примера

Для выполнения лабораторной работы возьмем тот же самый язык, который был использован для выполнения лабораторной работы № 2.

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

G({if,then,else,a,=,or,xor,and,(,),},{S,F,E,D,C},P,S) с правилами P:

S → F;

F → if E then T else F | if E then F | a:= E

T → if E then T else T | a:= E

E → E or D | E xor D | D

D → D and C | C

C → a | (E)

Жирным шрифтом в грамматике и в правилах выделены терминальные символы.

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

Построение матрицы операторного предшествования

Построение множеств крайних правых и крайних левых символов

Построение множеств крайних левых и крайних правых символов выполним согласно описанному ранее алгоритму.

На первом шаге возьмем все крайние левые и крайние правые символы из правил грамматики G. Получим множества, представленные в табл. 3.2.

Таблица 3.2. Множества крайних левых и крайних правых символов. Шаг 1