Материал: Методические указания по выполнению лабораторных работ № 9-11 по дисциплине «Системное программное обеспечение». Кремер О.Б

Продолжение таблицы

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

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

Таким образом, алгоритм работы простейшего сканера можно описать так:

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

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

• при успешном распознавании информация о выделенной лексеме заносится в таблицу лексем, и алгоритм возвращается к первому этапу;

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

Работа программы-сканера продолжается до тех пор, пока не будут просмотрены все символы программы на исходном языке из входного потока.

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

1.  Входной язык содержит арифметические выражения, разделенные символом ;(точка с запятой). Арифметические выражения состоят из идентификаторов, десятичных чисел с плавающей точкой, знака присваивания (:=), знаков операций +, -, *, / и круглых скобок.

2.  Входной язык содержит логические выражения, разделенные символом ;(точка с запятой). Логические выражения состоят из идентификаторов, констант true и false, знака присваивания (:=), знаков операций or, xor, and, not и круглых скобок.

3.  Входной язык содержит операторы условия типа if … then … else и if … then, разделенные символом ;(точка с запятой). Операторы условия содержат идентификаторы, знаки сравнения <, >, =, десятичные числа с плавающей точкой, знак присваивания (:=).

4.  Входной язык содержит операторы цикла типа for … do, разделенные символом ;(точка с запятой). Операторы цикла содержат идентификаторы, знаки сравнения <, >, =, десятичные числа с плавающей точкой, знак присваивания (:=).

5.  Входной язык содержит арифметические выражения, разделенные символом ;(точка с запятой). Арифметические выражения состоят из идентификаторов, римских чисел, знака присваивания (:=), знаков операций +, -, *, / и круглых скобок.

6.  Входной язык содержит логические выражения, разделенные символом ;(точка с запятой). Логические выражения состоят из идентификаторов, констант 0 и 1, знака присваивания (:=), знаков операций or, xor, and, not и круглых скобок.

7.  Входной язык содержит операторы условия типа if … then … else и if … then, разделенные символом ;(точка с запятой). Операторы условия содержат идентификаторы, знаки сравнения <, >, =, римские числа, знак присваивания (:=).

8.  Входной язык содержит операторы цикла типа for … do, разделенные символом ;(точка с запятой). Операторы цикла содержат идентификаторы, знаки сравнения <, >, =, римские числа, знак присваивания (:=).

9.  Входной язык содержит арифметические выражения, разделенные символом ;(точка с запятой). Арифметические выражения состоят из идентификаторов, шестнадцатеричных чисел, знака присваивания (:=), знаков операций +, -, *, / и круглых скобок.

10.  Входной язык содержит логические выражения, разделенные символом ;(точка с запятой). Логические выражения состоят из идентификаторов, шестнадцатеричных чисел, знака присваивания (:=), знаков операций or, xor, and, not и круглых скобок.

11.  Входной язык содержит операторы условия типа if … then … else и if … then, разделенные символом ;(точка с запятой). Операторы условия содержат идентификаторы, знаки сравнения <, >, =, шестнадцатеричные числа, знак присваивания (:=).

12.  Входной язык содержит операторы цикла типа for … do, разделенные символом ;(точка с запятой). Операторы цикла содержат идентификаторы, знаки сравнения <, >, =, шестнадцатеричные числа, знак присваивания (:=).

Примечание:

-       римскими числами считать последовательности больших латинских букв X, V и I;

-       шестнадцатеричными числами считать последовательность цифр и символов ‘a’, ‘b’, ‘c’,’d’, ’e’ и ‘f’, начинающуюся с цифры (например: 89, 45ac9, 0abc4);

Ход выполнения работы:

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

2. Текст на входном языке задается в виде символьного (текстового) файла.

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

4. Длину идентификаторов и строковых констант считать ограниченной 32 символами.

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

Оформить отчет в электронном виде и сдать.

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

1. Что такое трансляция, компиляция, транслятор, компилятор?

2. Из каких процессов состоит компиляция? Расскажите об общей структуре компилятора.

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

4. Как связаны лексический и синтаксический анализ?

5. Дайте определение цепочки, языка. Что такое синтаксис и семантика языка?

6. Какие существуют методы задания языков? Какие дополнительные вопросы необходимо решить при задании языка программирования?

7. Что такое грамматика? Дайте определения грамматики.

8. Как выглядит описание грамматики в форме Бэкуса-Наура.

9. Какие классы грамматик существуют? Что такое регулярные грамматики?

10. Дайте определения контекстно-свободной грамматики, выводимости цепочки, непосредственной выводимости, длины вывода.

11. Что такое конечный автомат? Дайте определение детерминированного и недетерминированного конечных автоматов.

12. Какие проблемы необходимо решить при построении сканера на основе конечного автомата?

Вопросы к колоквиуму

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

2. Представить схему грамматики, описывающей идентификаторы.

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

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

5. Представить схему грамматики для арифметических выражений, допускающих применение вложенных скобок.

6. Представить схему грамматики для описания целых и вещественных переменных. Описание переменных определенного типа должно начинаться указателем типа 'real' или 'int'. В полном тексте описания переменных определенного типа могут повторяться.

7. Составить таблицу идентификаторов и таблицу лексем для следующего фрагмента исходного кода:

begin

for I := 1 to N do m := m + 5

8. Составить таблицу идентификаторов и таблицу лексем для следующего фрагмента исходного кода:

If I > 10 then d := 20

Else d := 30

9. Составить таблицу идентификаторов и таблицу лексем для следующего фрагмента исходного кода:

Dim A As String, B As Integer

A = 20 : B = 10

Приложение

Таблица кодов виртуальных клавиш

Продолжние приложения

Продолжние приложения