Файл: Отчеты оформляются в виде файлов формата Microsoft Word (файлы других форматов не принимаются), размер шрифта 1214.docx

1. 
   Изучить технологию разработки систем регулярных определений пакета ВебТрансБилдер, ориентируясь на свой вариант задания на курсовую работу. Освоить использование простых регулярных выражений (один символ, перечень символов, диапазон символов) и квантификаторов «?», «*» и «+», операций группировки «( …)» и конкатенации (не имеющей знака операции).
   
2. 
   Разработать и сохранить систему правил для всех групп слов языка(или, как минимум, для идентификаторов, констант, знаков операций, пробельных последовательностей), заданного в курсовой работе.
   
3. 
   Построить вручную недетерминированный граф состояний и переходов по разработанной системе правил как результат выполнения первого этапа алгоритма преобразования системы регулярных определений в конечный автомат (см. п. 2.4.2.1 в [1]). Граф необязательно рисовать, его можно включить в отчет в форме списка вершин и выходящих из вершин маркированных дуг наподобие того, как это делает ВебТрансБилдер.
   
4. 
   Освоить построение транслятора как совокупности лексического анализатора (сканера) и синтаксического анализатора (парсера, пока - заглушки) средствами пакета ВебТрансБилдер (пункт меню «Построить») и просмотра визуального представления его элементов: графа состояний и переходов и управляющей таблицы (пункты меню «Показать/Сканер, управляемый таблицей» и «Показать/Сканер, управляемый графом»).
   
5. 
   Построить простейший транслятор, освоить запуск транслятора при использовании инструментального языка JavaScript (пункт меню «Запустить»), освоить выгрузку и сохранение кода построенного транслятора при использовании других инструментальных языков (пункт меню «Скачать»). Изучить код построенного транслятора (пункт меню «Показать/Код транслятора»), найти в нем вставленное расширение (var ignoreLastWord;) и разобраться в том, как в сканере (лексическом анализаторе) используется определяемая в нем переменная.
   
6. 
   Проверить работоспособность построенного транслятора на примере нескольких последовательностей правильных слов заданного языка (тех слов, которые определены разработанной и сохраненной системой правил), убедиться, что транслятор не воспринимает неправильные слова.
   
7. 
   Подготовить, сдать и защитить отчет к лабораторной работе.
   

5. 
   Требования к содержанию отчета.
   

Отчет должен содержать:

• 
  цель работы;
  
• 
  перечень групп слов учебного языка, заданного на курсовую работу;
  
• 
  примеры правильных слов заданного языка;
  
• 
  результаты разработки фрагмента системы правил языка, заданного на курсовую работу, описание разработанных регулярных выражений;
  
• 
  граф состояний и переходов недетерминированного конечного автомата (результат выполнения пункта 4.5);
  
• 
  граф состояний и переходов сканера, построенного ВебТрансБилдером по разработанному фрагменту, описание алгоритма работы автомата, управляемого графом;
  
• 
  управляющая таблица сканера, построенного ВебТрансБилдером по разработанному фрагменту, описание алгоритма работы автомата, управляемого таблицей;
  
• 
  результаты тестирования транслятора (пока – только лексического анализатора, т.е. сканера), построенного ВебТрансБилдером по разработанной системе правил;
  
• 
  выводы и заключение.
  

---

6. 
   Контрольные вопросы.
   
   1. 
      Опишите состав и назначение компонентов учебного пакета автоматизации проектирования трансляторов ВебТрансБилдер.
      
   2. 
      Перечислите основные функции пакета ВебТрансБилдер.
      
   3. 
      С помощью каких пунктов (и подпунктов) меню осуществляются основные операции пакета ВебТрансБилдер?
      
   4. 
      Как можно создать новое правило?
      
   5. 
      Где пишутся действия в лексических правилах?
      
   6. 
      Что такое регулярное выражение?
      
   7. 
      Что такое квантификатор?
      
   8. 
      Какие квантификаторы можно использовать в пакете ВебТрансБилдер?
      
   9. 
      Что такое шаблон построения транслятора?
      
   10. 
       Какие знаки операций можно использовать в регулярных выражениях?
       
   11. 
       Как в регулярном выражении определить диапазон символов?
       
   12. 
       Может ли внутри одной пары квадратных скобках быть записано несколько диапазонов символов?
       
   13. 
       Как можно изменить личные настройки в пакете ВебТрансБилдер?
       
   14. 
       Может ли быть создано несколько одноименных регулярных определений?
       
   15. 
       Как можно задать лексическое правило для слова, содержащего метасимволы языка регулярных выражений, такие как '[', ']', '\', …?
       
   16. 
       Каковы приоритеты знаков операций в языке регулярных выражений пакета ВебТрансБилдер?
       
   17. 
       Для чего предназначен пункт меню «Показать»?
       
   18. 
       Что такое действие в лексическом правиле?
       
   19. 
       Как с помощью действий можно заблокировать возврат правильно распознанного слова из лексического анализатора?
       
   20. 
       На какие части разделено основное окно клиентской части пакета ВебТрансБилдер?
       

---

Лабораторная/практическая работа № 2

1. 
   Название работы: «Лексика языков программирования. Конечные автоматы без памяти для обнаружения слов в тексте программы».
   
2. 
   Цели работы: изучение конечных автоматов (КА) без памяти, способов определения КА в трансляторах – графового и табличного, методов построения недетерминированного КА по системе регулярных выражений, методов эквивалентных преобразований недетерминированных КА в оптимальные полностью определенные КА – лексические акцепторы.
   
3. 
   Основные теоретические сведения:
   

1. 
   Конечные автоматы без памяти
   

Конечный автомат без памяти есть совокупность

K = {A, C, С₀, G, F},

где A – алфавит входных символов; C – конечное множество состояний; С₀ – начальное состояние; G – функция переходов, которая по текущему состоянию автомата и входному символу формирует его состояние в следующий момент времени; F – конечное множество состояний останова (финальных состояний).

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

• 
  имеет определенный набор рабочих состояний C, среди которых выделено особое начальное (стартовое) состояние С₀ и некоторый набор состояний останова (финальных состояний)F;
  
• 
  имеет один вход и не имеет ни одного выхода;
  
• 
  в любой момент времени на входе имеет либо в точности один символ входного алфавита A, либо пустую цепочку ε;
  
• 
  функционирует в дискретном времени t₀, t₁, t₂, ...;
  
• 
  при запуске, т. е. в момент времени t₀, всегда оказывается в начальном состоянии С₀, на входе в этот момент находится самый первый символ входной цепочки;
  
• 
  в любой момент времени t_i по текущему состоянию и символу, находящемуся на входе, в соответствии с функцией G определяет номер рабочего или финального состояния, в котором автомат окажется в момент времени t_i+1;
  
• 
  если по каким-либо причинам номер следующего состояния не может быть определен, то автомат останавливается по ошибке (для остановов по ошибке подразумевается существование особого финального состояния, не принадлежащего множеству F);
  
• 
  при любом переходе в рабочее состояние или состояние останова по ошибке текущий входной символ заменяется следующим символом из входной цепочки;
  
• 
  при переходе в финальное состояние обнаружения правильного слова входной символ автомата не изменяется (такой переход выполняется по пустой цепочке ε; действия со входным символом при переходе по пустой цепочке состоят в чтении символа со входа + обнаружении того, что символ не принадлежит текущему слову + возврате этого символа на вход автомата);
  
• 
  каждому финальному состоянию, не являющемуся состоянием останова по ошибке, поставлена в соответствие группа правильных слов, возможно, не единственная; останов автомата в таком состоянии понимается как обнаружение им правильного слова этой группы (или слова, принадлежащего нескольким группам).
  

---

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

BinaryNumber : [01] +

Space : [ ] +

Существует как минимум три способа определения конечного автомата без памяти, способного распознавать такие слова.

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

{текущее состояние; входной символ; следующее состояние}

Пример такого определения автомата:

{0,ε,-1} {0,\d32,1} {0,0,2} {0,1,2} {1,\d32,1} {1, ε,-2} {2,0,2} {2,1,2} {2,ε,-3}

Алфавит входных символов может быть извлечен из функции переходов, это символы 0, 1, пробел (символ с десятичным кодом \d32). Любые другие символы, которые могут появиться на входе автомата, здесь обозначены пустой цепочкой ε, их обработка состоит в переходе автомата в финальные состояния.

Состояния 0, 1 и 2 являются рабочими, поскольку для них определены переходы в другие состояния по входным символам. Состояния -1, -2 и -3 – финальные, поскольку из них не существует ни одного перехода. Состояние -1 соответствует обнаружению конца цепочки символов, содержащей только правильные слова, т.е. двоичные числа и последовательности пробелов. Останов автомата в состоянии -2 означает обнаружение последовательности пробелов, а в состоянии -3 – обнаружение двоичного числа.

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

2. 
   Графом состояний и переходов (ГСП) конечного автомата без памяти (далее просто конечного автомата - КА) называется помеченный ориентированный граф, вершины которого сопоставлены состояниям, а дуги – переходам.
   

Разметка вершин обычно производится целыми числами, обозначающими номера состояний. Имеется особая начальная вершина (имеющая обычно номер 0), в которую не входит ни одна дуга. Дуги графа могут быть помечены обозначением пустой цепочки ε, одиночным символом, перечнем или диапазоном символов.

---

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

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

0:		EOF-> -1 [\d32] -> 1 [01]-> 2
1:		[other]-> -2 [\d32] -> 1
2:		[other]-> -3 [01]-> 2

Разметка дуг графа производится с помощью указания одного из символов входного алфавита того языка, для распознавания слов которого построен данный автомат либо обозначения пустой цепочки символов ε, которому здесь соответствует [other]. Это обозначение надо понимать так: любой символ, не принадлежащий разметке какой-либо дуги, выходящей из данного состояния. Поэтому в разных состояниях [other] обозначают разные множества символов. Для состояния 1 это не пробел, а для состояния 2 – любой символ кроме двоичных цифр. Если дуга помечена символом входного алфавита, то при переходе по этой дуге автомат заменяет данный входной символ следующим символом из входной цепочки. При переходе по дуге, помеченной обозначением пустой цепочки ε, символ на входе автомата не изменяется.

3. 
   Еще одним способом определения конечного автомата без памяти является табличный способ. Автомат задается прямоугольной таблицей, строки которой обычно соответствуют состояниям, а столбцы – входным символам. Номера состояний и входные символы показаны в заголовках строк и столбцов, однако следует помнить, что заголовки строк и столбцов не являются элементами таблицы. В клетках таблицы указываются номера состояний перехода (из состояния, в строке которого находится клетка по символу, указанному в заголовке столбца). Пример управляющей таблицы (УТ) автомата, предназначенного для акцепта двоичных чисел, формируемой пакетом ВебТрансБилдер показан в табл. 2.1.
   

Таблица 2.1

	0	1	2
[ ► ]	-1	-2	-3
[ \d32 ]	1	1	-3
[ 01 ]	2	-2	2

---