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

• Название: Отчеты оформляются в виде файлов формата Microsoft Word (файлы других форматов не принимаются), размер шрифта 1214
• Дата: 06.04.2023
• Размер: 452.53 Kb.
• Имя файла: LabJob23.docx
• Тип: Отчет; #1041909
• страница: 1 из 12

Лабораторный практикум

Основные требования к отчетам по лабораторным работам

1. 
   Отчеты оформляются в виде файлов формата Microsoft Word (файлы других форматов не принимаются), размер шрифта: 12-14.
   
2. 
   На титульном листе должны быть указаны вариант задания на курсовую работу и имя системы правил в личном каталоге, которую надо проверять.
   
3. 
   Перечень разделов, которые должны присутствовать в отчете, указан в каждом задании на работы 1-8.
   
4. 
   Тестовые программы в отчете должны быть приведены только в текстовом представлении (ни в коем случае не в виде скриншотов).
   
5. 
   Все элементы отчета, в первую очередь – скриншоты, должны быть легко читаемы (без поворотов страницы и изменения масштаба).
   

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

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

1. 
   Название работы: «Лексика языков программирования. Регулярные выражения».
   
2. 
   Цели работы: освоение основных навыков работы с учебным пакетом программ автоматизации разработки трансляторов ВебТрансБилдер, изучение и освоение пользовательского интерфейса пакета и форматов исходных данных/результатов работы, изучение метаязыка регулярных выражений и технологии разработки систем правил определения лексики языков программирования, изучение основных понятий теории конечных автоматов без памяти.
   
3. 
   Основные теоретические сведения:
   

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

Основой этого метаязыка являются первичные регулярные выражения. Первичным называется регулярное выражение, порождающее (описывающее) цепочки, состоящие ровно из одного символа. Это выражения вида:

• 
  [<произвольный символ>], например: [a]. Говорят, что такое регулярное выражение порождает единственную цепочку, состоящую только из этого символа ([a]  a).
  
• 
  [<перечень символов>], например [aA]. Такое выражение порождает несколько цепочек, каждая из которых содержит в точности один символ из указанного в квадратных скобках перечня ([aA]  а и [aA]  А).
  
• 
  [<диапазон символов>], например [0–9]. Это выражение можно считать сокращенной формой записи выражения вида [0123456789]. Оно порождает
  10 цепочек, каждая из которых содержит единственную десятичную цифру.
  

В описываемом диалекте языка регулярных выражений используются метасимволы «[», «]» и «–», не принадлежащие определяемым цепочкам символов. Существуют и другие метасимволы, которые будут определены позже.

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

Во-первых, для указания диапазона символов необходимо точно знать таблицу кодирования символов, чтобы быть уверенным, что в диапазон не попадут «лишние» символы. Например, при использовании кодировки ASCII запись вида [a–F] нельзя использовать для определения старших шестнадцатеричных цифр. Правильной будет запись [a–fA–F].

Во-вторых, считается, что после символа с максимальным значением кода следует символ с минимальным значением (в системе кодирования ASCII после символа с кодом 255 идет символ с кодом 0).

В третьих, метасимвол дефиса (минуса) нельзя определять «внутри» перечня. Если этот метасимвол нужно определить как символ алфавита описываемого языка, то в первичном выражении он должен быть записан либо сразу после метасимвола «[», либо непосредственно перед метасимволом «]».

Так, например, регулярные выражения [–+*/] или [+/*–] порождают каждое ровно по четыре цепочки: –,+,*,/, но выражение [+–*/] в системе кодирования ASCII порождает ровно 256 цепочек длины 1, т.е. цепочки, содержащие все символы этого алфавита.

С учетом умолчаний допускается записывать перечни и диапазоны последовательно без каких-либо разделителей между метасимволами «[» и «]». Поэтому регулярные выражения [abk–osx–z] и [abklmnosxyz] являются эквивалентными, т. е. порождают одно и то же множество цепочек символов.

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

Для них в метаязыке регулярных выражений используются общепринятые обозначения (заимствованные из С-подобных языков):

\t – символ табуляции,

\n – символ новой строки,

\r – символ перевода каретки.

Аналогичный способ (экранирование следующего символа) применяется для представления символов \, [, ], ", являющихся одновременно метасимволами языка регулярных выражений:

\\ – один символ \ ,

\[ – символ [ ,

\] – символ ] ,

\" – символ " .

Простым называется произвольное регулярное выражение, заключенное в круглые скобки. Например, выражение ([0–9]) – простое выражение.

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

1. 
   Операция «Пусто или в точности одно» (знак операции ?).
   

Запись вида [–+]? следует понимать, как возможно отсутствующий знак числа. Это выражение порождает либо пустую цепочку, либо один символ –, либо один символ +.

2. 
   Операция «Одно или несколько» (знак операции +).
   

Запись вида [0–9]+ является типичным определением целой десятичной константы без знака (порождает все возможные непустые цепочки из десятичных цифр произвольной длины);

3. 
   Операция «Пусто, одно или несколько» (знак операции *):
   

Запись вида [0–9a–zA–Z]* является типичной частью определения идентификаторов и порождает произвольную, возможно, пустую цепочку, состоящую из букв и/или цифр. Полное определение идентификатора может выглядеть так: [a–zA–Z][0–9a–zA–Z]*

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

К первичным выражениям, простым выражениям, и выражениям, построенным с использованием квантификаторов ?, + и * могут применяться еще две операции – конкатенации и выбора.

4. 
   Операция конкатенации (не имеет знака операции).
   

Два последовательно записанных первичных или простых регулярных выражения понимаются как выражение, порождающее цепочку из двух символов. Первый символ порождается первым выражением, второй символ – вторым. Например, выражение [/][*] порождает цепочку символов /*, понимаемую обычно как начало блочного (многострочного) комментария в С-подобных языках.

Операция конкатенации не коммутативна (выражение [*][/] порождает совсем другую цепочку символов */, отличную от цепочки, порождаемой выражением [/][*]). Операция конкатенации может применяться к результату другой конкатенации, например: [>][>][=] – это определение знака операции «сдвинуть вправо и присвоить» в языках С/С++.

Во многих диалектах метаязыка регулярных выражений допускаются выражения вида "<произвольная строка символов>", каждое из которых порождает цепочку, совпадающую с <произвольная строка символов>. Например, выражение "else" считается эквивалентным выражению [e][l][s][e].

5. 
   Операция выбора (знак операции | ).
   

Запись вида [*] | [/] порождает либо *, либо /. В некоторых случаях ее использование эквивалентно перечню [*/] (или диапазону). Однако существуют такие группы слов, при определении которых невозможно ограничиться только первичными регулярными выражениями, приходится использовать все или некоторые операции 1-5.

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

– метасимвол «.» для обозначения произвольного символа определяемого языка; вместо этого используется пустая пара квадратных скобок [] (следует помнить, что пробел – это тоже символ и выражение [] вовсе не эквивалентно выражению [ ]);

– знак операции инверсии перечня/диапазона символов «^»; вместо этого используются квантифицируемые выражения (или выражение []) в сочетании с выражениями, следующими за ними. Так например, запись вида [/][/][]*[\n] пакетом ВебТрансБилдер понимается и обрабатывается так: два символа «косая черта», за которыми следует произвольная цепочка, завершающаяся символом новой строки (это традиционная для С-подобных языков определение однострочного комментария). При использовании знака операции инверсии это выражение могло бы выглядеть так: [/][/][^\n]*[\n]

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

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

<наименование группы слов> : <регулярное выражение>

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

Ident	:	[a–zA–Z][0–9a–zA–Z]*
Const	:	[0–9]+([.][0–9]*)?
Const	:	[0–9]*[.][0–9]+
WordForFormatting	:	[ \r\n\t]+
SignOfOperation	:	[–+*/]
Delimiter	:	[;]
AssignSign	:	[=]

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

Система регулярных определений может быть преобразована в оптимальный конечный автомат без памяти, способный распознавать правильные слова всех заданных групп. Начальный этап алгоритма этого преобразования необходимо изучить по [1], стр. 103-107.

4. 
   Порядок выполнения работы (рекомендуется использовать в качестве примера систему правил Samples/Пример1):
   

1. 
   Изучить интерфейс пакета ВебТрансБилдер: запуск, регистрация, состав элементов основного окна, команды меню. Используя справку ВебТрансБилдера (команда меню «Помочь»), изучить структуру таблицы системы редактируемых правил основного окна, приемы и способы формирования/редактирования ее содержимого.
   
2. 
   Освоить:
   

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

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. 
       На какие части разделено основное окно клиентской части пакета ВебТрансБилдер?