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

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

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

1. Получить вариант задания у преподавателя.

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

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

4. Подготовить и защитить отчет.

5. Написать и отладить программу на ЭВМ.

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 → a

Ниже в табл. 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 видно, что множества L(U) для символов S, Е, D, а также множества R(U) для символов F, Т, Е, D содержат другие нетерминальные символы, а потому должны быть дополнены. Например, L(S) должно быть дополнено L(F), так как символ F входит в L(S): F е L(S), а R(F) должно быть дополнено R(E), так как символ Е входит в R(F): Е е R(F).