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

Строки таблиц должны содержать:
1. Номер шага.
2. Текущий входной символ.
3. Текущее состояние автомата.

Сравнить последовательности обнаруженных слов в построенных историях работы с теми, которые формируются при тестировании сканера, объяснить расхождения, если они имеются.

6. 
   Разработать полное описание лексики учебного языка, заданного на курсовое проектирование в качестве заготовки фрагмента расчетно-пояснительной записки к курсовой работе. Описание лексики должно включать все группы слов языка. Для каждой группы должны быть сформулированы:
   

- назначение (или способы использования) слов этой группы в программах на учебном языке;

- правила формирования слов языка из символов алфавита (или перечень допустимых слов);

- характеристики слов, если они имеют значение для синтаксического и семантического анализа (например – приоритеты знаков операций, диапазоны значений констант);

- примеры правильных слов.

7. 
   Подготовить, сдать и защитить отчет к лабораторной работе.
   

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

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

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

6. 
   Контрольные вопросы.
   

1. 
   Что такое конечный автомат без памяти?
   
2. 
   Какие существуют способы задания конечных автоматов без памяти?
   
3. 
   Что такое первичное регулярное выражение?
   
4. 
   Как можно задать перечень и диапазон символов в регулярном выражении?
   
5. 
   Что такое квантификаторы, какие квантификаторы можно использовать в системах правил для пакета ВебТрансБилдер?
   
6. 
   Что такое эквивалентность конечных автоматов без памяти?
   
7. 
   Что такое тупиковые, недостижимые и эквивалентные состояния конечного автомата без памяти?
   
8. 
   Что такое оптимальность конечного автомата?
   
9. 
   Перечислите основные этапы процесса преобразования системы регулярных выражений в конечный автомат без памяти.
   
10. 
    Что такое недетерминированность конечного автомата без памяти? Перечислите виды недетерминированности.
    
11. 
    Что такое полностью и неполностью определенные конечные автоматы без памяти?
    
12. 
    Опишите существо процесса эпсилон-замыкания множества вершин графа состояний и переходов при ликвидации недетерминированностей.
    
13. 
    Какие способы преобразования графа состояний и переходов соответствуют операциям языка регулярных выражений?
    
14. 
    Как осуществляется поиск и удаление тупиковых состояний конечного автомата без памяти?
    
15. 
    Как осуществляется поиск и удаление недостижимых состояний конечного автомата без памяти?
    
16. 
    Как осуществляется поиск и слияние эквивалентных состояний конечного автомата без памяти?
    
17. 
    Как осуществляется преобразование не полностью определенного конечного автомата без памяти в полностью определенный?
    
18. 
    Что такое рабочая зона управляющей таблицы конечного автомата без памяти?
    
19. 
    Что такое история работы управляющей таблицы конечного автомата без памяти?
    
20. 
    Как в метаязыке регулярных выражений определяются символы, не имеющие графического изображения?
    

---

---

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

1. 
   Название работы: «Синтаксис языков программирования. Формальные грамматики».
   
2. 
   Цели работы: изучение основных понятий метаязыка формальных грамматик, свойств грамматик и нетерминальных символов, рекурсивности и однозначности грамматик, недостижимости, бесплодности, аннулируемости и рекурсивности нетерминальных символов, отношений предшествования и последования между символами, приобретение навыков разработки формальных грамматик.
   
3. 
   Основные теоретические сведения:
   

1. 
   Формальные грамматики
   

Формальной грамматикой G называется совокупность

G = { A_t, A_n, S , P},

состоящая:

• 
  из алфавита терминальных символов A_t;
  
• 
  алфавита нетерминальных символов A_n;
  
• 
  начального нетерминального символа S;
  
• 
  системы правил подстановки P
  

Алфавит терминальных символов A_t есть конечное множество всех слов языка, порождаемого данной грамматикой. Понятие «терминальный» в данном случае обозначает неразложимость, элементарность таких символов с точки зрения синтаксических правил.

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

Наряду со словосочетанием «терминальный символ» будет использоваться просто слово «терминал».

В дальнейшем терминальные символы обозначаются либо одиночными литерами, представляющими собой отдельные слова в языках программирования (+, *, =, ;, {, }, …), либо терминами, называющими слово или группу слов (идентификатор, константа, id, const, …), либо просто малыми буквами латинского алфавита, обозначающими произвольный терминал (a, b, c, …).

---

Например: A_t={идентификатор, константа, +, –, *, /, =}

Алфавит нетерминальных символов A_n есть конечное множество названий синтаксических конструкций, например: <предложение>, <выражение>, <список аргументов>, <условный оператор>, <тело функции>. Нетерминальные символы используются только в метаязыке, на котором описывается язык программирования, никакой нетерминальный символ не может появиться в тексте правильной программы. Наряду со словосочетанием «нетерминальный символ» в дальнейшем будет использоваться просто «нетерминал». Нетерминальные символы принято обозначать либо словосочетаниями в угловых скобках, как в начале этого абзаца, либо словами, начинающимися с прописной буквы и содержащими буквы, цифры и символы подчеркивания (например – Function, ArgList, Const_16), либо просто большими буквами латинского алфавита в курсивном начертании A, B, C, ... Z.

Начальный нетерминальный символ S есть один из нетерминальных символов. Этим символом обычно обозначается наиболее общая синтаксическая конструкция, например: <правильная программа>.

Символы (как терминальные, так и нетерминальные) могут образовывать цепочки, которые будут обозначаться малыми буквами греческого алфавита α, β, γ, ... ω. Особое значение будет играть пустая цепочка символов ε.

Система правил подстановки P (иногда называемая системой порождающих правил или продукций) есть конечное множество пар цепочек вида α : β, причем цепочка α (левая часть правила) должна содержать хотя бы один нетерминальный символ.

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

Для иллюстрации приведем пример фрагмента грамматики С-подобного языка (пока будем считать этот фрагмент полноценной грамматикой G₁):

S : S + T

S : S – T

S : T

T : ident

T : const

Лексические правила для терминалов ident и const пока не будем считать частью этой грамматики. Эта грамматика порождает (определяет как правильные) предложения арифметические выражения, содержащие только идентификаторы, константы и знаки операций сложения и вычитания.

---

2. 
   Дерево грамматического разбора
   

Пусть дана грамматика G с системой порождающих правил P.

Цепочка ψ непосредственно выводится из цепочки σ (σ  ψ), если:

• 
  σ = ω α δ, где ω и δ – произвольные, возможно пустые цепочки;
  
• 
  ψ = ω β δ, где ω и δ – те же самые цепочки;
  
• 
  в системе порождающих правил P есть правило α : β.
  

Подстановка цепочки β вместо α в цепочке σ = ω α δ порождает ω β δ, т. е. цепочку ψ. Обратная подстановка не подразумевается, т.е. из возможности непосредственного вывода σ  ψ не следует возможность непосредственного вывода ψ  σ.

Например, в грамматике G₁ цепочка S + const непосредственно выводится из цепочки S + T путем подстановки правой части правила T : const вместо T.

Цепочка ψ выводится из цепочки σ обозначается (σ  ψ), если существует последовательность непосредственных выводов:

σ  ψ₁  ψ₂  ψ₃ ... ψ_n  ψ

Например, в грамматике G₁ цепочка x – 1 выводится из начального гнетерминала S путем выполнения такой последовательности непосредственных выводов: SS – TT – Tident – Tx – Tx – constx - 1.

Правильным предложением языка L, определяемого грамматикой G, называется цепочка, состоящая только из терминальных символов и выводимая из начального нетерминала S. Любая цепочка терминальных символов, для которой не существует вывода из начального нетерминала S грамматики G, является неправильным предложением языка L. Цепочка, содержащая символы, не входящие в алфавит терминальных символов A_t, в частности, нетерминальные символы, вообще не является предложением языка L.

Таким образом, грамматика G разбивает бесконечное множество всех возможных цепочек, содержащих только терминальные символы (слова языка), на два непересекающихся подмножества:

• 
  подмножество правильных предложений, которое собственно и является языком L, порождаемым грамматикой G;
  
• 
  подмножество неправильных предложений.
  

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

---