МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Лабораторная работа №2
по дисциплине «Системное программное обеспечение»
на тему: «Лексика языков программирования. Конечные автоматы без памяти для обнаружения слов в тексте программы»
Вариант № 4334223
Студент:
Группа: АМ-610
Преподаватель:
Новосибирск 2009 г.
Содержание
Цель работы.. 3
Задание. 4
Вариант задания. 5
Ход работы.. 6
Выводы.. 21
Цель работы
Изучение конечных автоматов (КА) без памяти, способов определения КА – канонического, графового и табличного, методов построения недетерминированного КА по системе регулярных выражений, методов эквивалентных преобразований недетерминированных КА в оптимальные полностью определенные КА – лексические акцепторы.
Задание
1. Используя пакет ВебТрансЛаб, освоить:
-создание лексических правил на языке регулярных выражений (РВ);
-использование операций «+, *, ?, конкатенации и выбора» языка РВ;
-преобразование системы РВ в одноавтоматный лексический акцептор;
-добавление правил и действий в систему РВ для построения мультиавтоматного лексического акцептора;
2. Разработать (доработать разработанный при выполнении работы №1) фрагмент системы регулярных выражений для всех (или выбранной самостоятельно части) групп слов языка, определенного заданием на курсовую работу. Построить по этому фрагменту:
-программный модуль, управляемый графом состояний и переходов;
- программный модуль, управляемый таблично;
3. Изучить структуру программных модулей, построенных ВебТрансЛабом, изучить алгоритмы работы лексического акцептора для графового и табличного способов реализации КА, сравнить реализации конечных автоматов, управляемых различными способами, между собой;
4. Изучить реализацию вызова действий, определенных в лексических правилах и алгоритм работы формирователя лексем.
5. Проверить функционирование конечных автоматов, построенных ВебТрансЛабом (подготовить тестовый пример, запустить каждый автомат на выполнение, протрассировать работу лексического акцептора в графовой и табличной реализации, убедиться в работоспособности автоматов, в противном случае – доработать систему РВ и добиться правильного функционирования лексического акцептора).
6. Изучить те элементы языка шаблонов, которые используются для преобразования внутреннего представления конечного автомата в программную реализацию лексического анализатора.
Вариант задания
II.1 Идентификаторы и константы
Вариант: | 4 |
Идентификаторы | <Б><Ц><пБЦ> |
Константы | целые вещественные символьные 7-ричные L_T / L_F |
II.2 Объявления примитивных типов (целое, вещественное, символьное, булево):
Вариант: | 3 |
long doub[l[e]] litera bool[e[a[n]]] |
II.3 Объявления объектов и создание/уничтожение экземпляров
Вариант: | 3 |
Классов | class |
Экземпляров | new / delete |
II.4 Оператор присваивания:
Вариант: | 4 |
<И> <= <В>; |
II.5 Условный оператор:
В-т: | 2 |
when <ЛВ> then <ОБ> [else <ОБ>] |
II.6 Переключатель
В-т: | 2 |
switch <В> { by <К>:<ОБ> …} |
II.7 Оператор цикла:
В-т: | 3 |
for<И>from<К> to<К> [step <К>] <ОБ> |
Ход работы
1. Были освоены следующие действия с использованием пакета ВебТрансЛаб:
· создание лексических правил на языке регулярных выражений;
· использование различных операций языка РВ: «+» (одно или несколько); «*» (пусто, одно или несколько); «?» (пусто или одно); операция конкатенации – объединение нескольких символов, которые ЛА будет воспринимать как целое. Например, оператор присваивания записан следующим образом: [<][=]; операция выбора ( | ) .
· преобразование системы РВ в одноавтоматный лексический акцептор. На начальном этапе выполнения работы ЛА является именно одноавтоматным, все действия описаны для автомата main; затем добавляются автоматы symb - для обработки символьных констант, ekran - для экранирования с помощью слэша ( \ ), comment - для обработки комментариев.
· добавление правил и действий в систему РВ для построения мультиавтоматного лексического акцептора (рис. 1). Построенный ЛА предполагает переход из автомата main в автомат, обрабатывающий символьную константу (symb), а из него – в автомат, обрабатывающий экранируемый слэш (ekran); также предусмотрен переход из main в автомат comment, обрабатывающий комментарии.
2. По полученной системе регулярных выражений были построены 2 программных модуля:
· управляемый графом состояний и переходов;
· программный модуль, управляемый таблично;
3. Также был изучен код программных модулей, построенных ВебТрансЛабом и алгоритмы работы лексического акцептора для графового способов реализации КА, сравнение которых приведено далее.
Рис.1. Система регулярных выражений
Код на основе шаблона lexAsGraphSyntAsManySA_to_jsp
Автомат был построен при помощи усовершенствованного шаблона lexAsGraphSyntAsManySA_to_jsp. Усовершенствование нужно для вывода групп слов - ti. put(Lexem. groupIndex, Lexem. textOfWord).
<%@page contentType="text/html; charset=Windows-1251"%>
<%@page import="AuxObjects.*"%>
<%@page import="lexAcceptor.*"%>
<%@page import="java. io.*"%>
<%@page import="java. util.*"%>
<%
//Построено 30.10.2009 13:14:24 по исходному файлу/шаблону asanov. xml/lexAsGraphSyntAsManySA_to_jsp
//end of Part_1
//Part_2: определения используемых классов
class fAutomat extends fAutomatAsGraph{
public fAutomat(int no, int stCnt, textReader tr){
super(no, stCnt, tr);
}
public fAutomat(int stCnt, textReader tr){
super(stCnt, tr);
}
}
//end of Part_2
//Part_3: глобальные переменные
final TraceInfo ti=new TraceInfo();
//end of Part_3
//Part_4: лексический анализатор
class lexAnalyzer{
fAutomat lexAcceptor; //текущий (активный) лексический акцептор
lexem Lexem=new lexem(); //текущая лексема
boolean ignoreLastWord; //флажок необходимости не возвращать (игнорировать) последнюю обнаруженную лексему
//Part_4_0: данные и методы из правил
//end of Part_4_0
//Part_4_1: мультиавтоматный ЛА
Stack lexStk=new Stack(); //стек индексов лексических акцепторов
fAutomat[] lexAcceptors=new fAutomat[4]; //массив лексических акцепторов
//Part_4_2: конструктор мультиавтоматного ЛА
public lexAnalyzer(textReader rdr){
faState state; //переменная для временного хранения состояния конечного автомата
//дальше идет создание автоматов, их состояний, выходящих из них дуг и запоминание всего этого в соответствующих местах
lexAcceptors[0]=new fAutomat(0,23,rdr);
state=new faState(13);
state. setArc(1,"0");
state. setArc(2,"");
state. setArc(3,"(){}");
state. setArc(4,"\'");
state. setArc(5," \r\u0009\n");
state. setArc(6,":;,");
state. setArc(7,"=");
state. setArc(8,"!");
state. setArc(9,"<");
state. setArc(10,"L");
state. setArc(11,"/");
state. setArc(12,"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKMNOPQRSTUVWXYZ");
state. setArc(13,"-+*");
lexAcceptors[0].setState(0,state);
state=new faState(4);
state. setArc(-2,"");
state. setArc(2,"");
state. setArc(14,"sS");
state. setArc(15,".");
lexAcceptors[0].setState(1,state);
state=new faState(3);
state. setArc(-2,"");
state. setArc(2,"");
state. setArc(15,".");
lexAcceptors[0].setState(2,state);
state=new faState(1);
state. setArc(-3,"");
lexAcceptors[0].setState(3,state);
state=new faState(1);
state. setArc(-4,"");
lexAcceptors[0].setState(4,state);
state=new faState(2);
state. setArc(-5,"");
state. setArc(5," \r\u0009\n");
lexAcceptors[0].setState(5,state);
state=new faState(1);
state. setArc(-6,"");
lexAcceptors[0].setState(6,state);
state=new faState(1);
state. setArc(16,"<>=");
lexAcceptors[0].setState(7,state);
state=new faState(1);
state. setArc(16,"=");
lexAcceptors[0].setState(8,state);
state=new faState(1);
state. setArc(17,"=");
lexAcceptors[0].setState(9,state);
state=new faState(2);
state. setArc(18,"_");
state. setArc(19,"");
lexAcceptors[0].setState(10,state);
state=new faState(2);
state. setArc(-7,"");
state. setArc(20,"/");
lexAcceptors[0].setState(11,state);
state=new faState(1);
state. setArc(19,"");
lexAcceptors[0].setState(12,state);
state=new faState(1);
state. setArc(-7,"");
lexAcceptors[0].setState(13,state);
state=new faState(1);
state. setArc(21,"0123456");
lexAcceptors[0].setState(14,state);
state=new faState(2);
state. setArc(-8,"");
state. setArc(15,"");
lexAcceptors[0].setState(15,state);
state=new faState(1);
state. setArc(-9,"");
lexAcceptors[0].setState(16,state);
state=new faState(1);
state. setArc(-10,"");
lexAcceptors[0].setState(17,state);
state=new faState(1);
state. setArc(22,"TF");
lexAcceptors[0].setState(18,state);
state=new faState(2);
state. setArc(-11,"");
state. setArc(19,"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ");
lexAcceptors[0].setState(19,state);
state=new faState(1);
state. setArc(-12,"");
lexAcceptors[0].setState(20,state);
state=new faState(2);
state. setArc(-13,"");
state. setArc(21,"0123456");
lexAcceptors[0].setState(21,state);
state=new faState(1);
state. setArc(-14,"");
lexAcceptors[0].setState(22,state);
lexAcceptors[1]=new fAutomat(1,3,rdr);
state=new faState(2);
state. setArc(1,"");
state. setArc(2,"\u0009\n");
lexAcceptors[1].setState(0,state);
state=new faState(2);
state. setArc(-2,"\u0009\n");
state. setArc(1,"");
lexAcceptors[1].setState(1,state);
state=new faState(1);
state. setArc(-3,"");
lexAcceptors[1].setState(2,state);
lexAcceptors[2]=new fAutomat(2,2,rdr);
state=new faState(1);
state. setArc(1,"");
lexAcceptors[2].setState(0,state);
state=new faState(1);
state. setArc(-2,"");
lexAcceptors[2].setState(1,state);
lexAcceptors[3]=new fAutomat(3,4,rdr);
state=new faState(3);
state. setArc(1,"");
state. setArc(2,"\\");
state. setArc(3,"\'");
lexAcceptors[3].setState(0,state);
state=new faState(1);
state. setArc(-2,"");
lexAcceptors[3].setState(1,state);
state=new faState(1);
state. setArc(-3,"");
lexAcceptors[3].setState(2,state);
state=new faState(1);
state. setArc(-4,"");
lexAcceptors[3].setState(3,state);
lexAcceptor=lexAcceptors[0]; //установим автомат с индексом 0 в качестве стартового лексического акцептора
lexStk. push(lexAcceptor); //и запомним это в стеке
}
//Part_4_3: распознавание слова и формирование лексемы
public lexem getLexem(){
if(lexStk. size()<=0){ //если стек пуст - вернуть лексему с ошибкой
Lexem. groupIndex=-;return Lexem;
}
ignoreLastWord=true; //временно установим флажок, чтобы войти в цикл
while(ignoreLastWord){ //пока флажок установлен - читаем очередное слово (игнорируя предыдущие, если цикл выполняется более одного раза)
ignoreLastWord=false; //перед чтением следующего слова сбросим флажок
//вызовем лексический акцептор и получим от него лексему:
Lexem=lexAcceptor. getLexem();
//для каждого автомата и каждой группы слов обеспечим возможность выполнения действий (имена автоматов и групп слов в примечаниях)
//индексы групп слов, имена которых используются в грамматике, преобразуются в те значения, который присвоил им построитель синтаксического акцептора
//в действиях, в частности, может быть взведен флажок ignoreLastWord и изменены поля лексемы, установленные акцептором
switch(lexAcceptor. getIndex()){
case 0: // Автомат main
switch(Lexem. groupIndex){
case -1: //EOF
Lexem. groupIndex=0;break;
case -2: //целые вещественные
break;
case -3: //скобки
break;
case -4: //символьная константа (вход)
ignoreLastWord=true;lexAcceptor=lexAcceptors[3];break;
case -5: //символы форматирования
ignoreLastWord=true;break;
case -6: //разделители
break;
case -7: //арифметические операции
break;
case -8: //вещественные
break;
case -9: //операции отношения
break;
case -10: //оператор присваивания
break;
case -11: //идентификатор
break;
case -12: //комментарии
ignoreLastWord=true;lexAcceptor=lexAcceptors[1];break;
case -13: //семиричные
break;
case -14: //константы выбора
break;
}
break;
case 1: // Автомат comment
switch(Lexem. groupIndex){
case -1: //EOF
Lexem. groupIndex=0;break;
case -2: //комментарии
break;
case -3: //комментарии (выход)
ignoreLastWord=true;lexAcceptor=lexAcceptors[0];break;
}
break;
case 2: // Автомат ekran
switch(Lexem. groupIndex){
case -1: //EOF
Lexem. groupIndex=0;break;
case -2: //экранируемый слэш
lexAcceptor=lexAcceptors[3];break;
}
break;
case 3: // Автомат symb
switch(Lexem. groupIndex){
case -1: //EOF
Lexem. groupIndex=0;break;
case -2: //символьная константа
break;
case -3: //экранирование
ignoreLastWord=true;lexAcceptor=lexAcceptors[2];break;
case -4: //символьная константа (выход)
ignoreLastWord=true;lexAcceptor=lexAcceptors[0];break;
}
break;
}
}
ti. put(Lexem. groupIndex, Lexem. textOfWord);
//вернем лексему
return Lexem;
}
}
//end of Part_4
//Part_6: синтаксический акцептор/анализатор
class parser{
lexAnalyzer la; //экземпляр лексического анализатора
lexem currentLexem; //текущая лексема
int cCnt=0;
//Part_6_4: заглушка для случая, когда нет синтаксических правил
public parser(String s){
la=new lexAnalyzer(new textReader(s)); //создание экземпляра лексического анализатора
}
private int getWordIndex(){
currentLexem=la. getLexem();
return currentLexem. groupIndex;
}
public String getStatistic(int i){
if(i==0)
return " "+cCnt+" ";
else
return"";
}
public boolean parse(){
int wi;
while(((wi=getWordIndex())!=0)&&(wi>-100))if(cCnt++>9998)break;
return wi==0;
}
}
//end of Part_5
//Part_7: обработка HTTP-запроса, создание экземпляра синтаксического акцептора/анализатора
//start:
decoderEscaped dE=new decoderEscaped();
String qs="";
if((qs=request. getParameter("inputText"))==null)
if(request. getQueryString()!=null)qs=new String(request. getQueryString());
if((qs!=null)&&(qs. length()>0))
qs=dE. decode(qs).toString();
else qs="";
textReader str=new textReader(qs);
parser p=new parser(qs);
//end of Part_6
//Part_7_1: HTML-часть страницы, вызов синтаксического анализатора, отображение результатов работы
response. setDateHeader("Expires",0);%>
<html><meta http-equiv="Content-Type" content="text/html; charset=Windows-1251">
<style type="text/css">
.bd {font-family:Arial, Helvetica, sans-serif;font-size:14;}
.RMn {font-family:Arial, Helvetica, sans-serif;font-size:14;border-collapse:collapse;}
.Hid {display:none}
</style>
</HEAD><body><div class='bd' align=center><u>Лексика</u>: автомат, управляемый графом состояний и переходов.</div>
<div class='bd' align=center><u>Синтаксис</u>: нисходящий автомат с несколькими состояниями.</div>
<div align=center><textarea id=inpTxt rows=30 cols=160 class=bd style='visibility:hidden'><%=qs%></textarea></div>
<form id=tst method='POST' align=center style='display:none' action='<%=request. getServletPath()%>'><textarea name=inputText style='display:none'></textarea>
<div align=center><input type=button align=center class=bd onclick='tst. inputText. value=escape(inpTxt. value);tst. submit()' value='Проверить'></div></form>
<div id=rez style='display:none'>
<%if(qs. length()>0){%><div class=bd align=center>Проверяемый текст лексически <%=(p. parse()?"правилен":"неверен")%>.</div>
<table border=1 align=center class=RMn cellspacing=0 cellpadding=0>
<tr><td align=right>Общее количество циклов: <td><%=p. getStatistic(0)%>
</table><%}%>
<table border=1 class=bd style='display:one;border-collapse:collapse'><%=ti. getTraceTable()%></table></div>
</body></html>
<!-- end of Part_7
<!-- Part_8: скрипты для браузера -->
<script><!--
function tresize(){
if(document. body. offsetWidth>100)
inpTxt. style. width=document. body. offsetWidth-40;
if(document. body. offsetHeight>500)
inpTxt. style. height=document. body. offsetHeight-400;
}
--></script>
<script for=window event=onload><!--
inpTxt. style. visibility="visible"
tst. style. display="block"
rez. style. display="block"
tresize();
--></script>
<script for=window event=onresize><!--
tresize();
--></script>
<!-- end of Part_8 -->
По результатам сравнения двух способов реализации конечных автоматов были сделаны следующие выводы:
· программная реализация обоих способов примерно одинаковой сложности;
· табличный способ более удобен для визуального восприятия.
Для получения наглядной картины целесообразно использовать оба способа представления.
Проверка функционирования ЛА
Для проверки функционирования конечных автоматов, построенных ВебТрансЛабом, была составлена тестовая программа, проверяющая все описанные в ЛА правила.
{
a8dassad<='\'';
w5h<=a4fg*3+2.36;
//asdsda
a5w<=L_T;
b8w<=L_F:
g8asd==7,
j8dzs=>0s4;
h9k!='c';
k9j<='\c';
}
С помощью модификации шаблона при проверке была получена следующая таблица (фрагмент см. на рис. 2):
Рис.2. Фрагмент проверочной таблицы
Выводы
В ходе выполнения данной лабораторной работы была изучена структура программных модулей, построенных ВебТрансЛабом. Также были изучены алгоритмы работы лексического акцептора для графового и табличного способа реализации КА и произведено их сравнение.
Доработанная и модифицированная система регулярных выражений была проверена на тестовом примере.
