III Международная студенческая научная конференция Студенческий научный форум - 2011
ПРИМЕР ПРОГРАММИРОВАНИЯ КОНЕЧНОГО АВТОМАТА ДЛЯ ПОИСКА И ПРЕОБРАЗОВАНИЯ ДАТ НА ЯЗЫКЕ С++
КомментарииПолная версия работы доступна во вкладке "Файлы работы" в формате PDF
Рассмотрим применение конечных автоматов на примере такой задачи, как удаление всех комментариев из текста программы на языке c++.
В файле могут быть комментарии типа:
- 1) // комментарий до конца строки после двух слэшей
- 2) /* многострочный комментарий в таких вот скобках */
Так же существуют строковые константы типа
- 1) "в двойных кавычках"
- 2) ´в одиночных кавычках´
В этих константах могут встречаться символы комментариев // или /* */,но комментарии в таком случае включаться не должны. Также в строковой константе может встретиться символ « », означающий спецсимвол, следующий после него (перевод строки, табуляцию и т. д.). Среди спецсимволов есть " и ´, которые не закрывают открытые кавычки, а должны выводится на экран (например: printf(" кавычки " и ´ "); ).
Для решения этой задачи через конечные автоматы определим все возможные состояния, в которых может находиться автомат:
enum STATE
{
STATE_BASIC, // 1. базовое состояние(обычный текст)
STATE_SLASHSTAR, // 2. комментарии типа /* вфывыфвфы */
STATE_SLASHSLASH, // 3. комментарии типа // авырпворп
STATE_SINGLEQUOTES, // 4. текст ´sadsadasdas´
STATE_DOUBLEQUOTES, // 5. текст "выфвыфвыф"
STATE_BASIC_SLASH, /* 6. состояние при первом слэше в базовом состоянии * /*/
STATE_SINGLEQUTES_SLASH, // 7. состояние при первом слэше в тексте внутри кавычек
STATE_DOUBLEQUOTES_SLASH, // 8. состояние при первом слэше в тексте внутри кавычек
STATE_SLASHSTAR_STAR // 9. состояние при звезде в комментариях типа /* */
};
Изобразим переходы состояний автомата в виде графа (рис. 1), в котором:
из 1 состояния автомат может перейти:
- - в 4 при встреченной одиночной кавычке
- - в 5 при двойной кавычке
- - в 6 при «слэше»
- - остаться в 1 во всех остальных случаях
из 5 состояния автомат может перейти:
- - в 8 при «обратном слэше»
- - обратно в 1 при двойных кавычках или переводе строки
- - остаться в 5 во всех остальных случаях
из 4 состояния автомат может перейти:
- - в 7 при «обратном слэше»
- - обратно в 1 при двойных кавычках или переводе строки
- - остаться в 4 во всех остальных случаях
из 6 состояния автомат может перейти:
- - в 3, если снова встретился «слэш»
- - во 2, если «звездочка»
- - в 1 во всех остальных случаях
из 8 состояния автомат может перейти:
- - в 5, в любом случае
из 7 состояния автомат может перейти:
- - в 1, если встретился символ «перевод строки»
- - в 4 во всех остальных случаях
из 3 состояния автомат может перейти:
- - в 1, если встретился символ «перевод строки»
- - остаться в 3 во всех остальных случаях
из 2 состояния автомат может перейти:
- - в 8, если встретился символ «звездочка»
- - остаться в 2 во всех остальных случаях
из 8 состояния автомат может перейти:
- - в 1, если встретится «слэш»
- - во 2 во всех остальных случаях
Получилась, практически, готовая программа. Осталось только при переходах из состояния в состояние добавить необходимые действия (в нашем случае, вывод символов в выходной файл, где надо).
Получившаяся программа:
#include
#include
#include
enum STATE
{
STATE_BASIC, // базовое состояние(обычный текст)
STATE_SLASHSTAR, // комментарии типа /* вфывыфвфы */
STATE_SLASHSLASH, // комментарии типа //
STATE_SINGLEQUOTES, // текст ´sadsadasdas´
STATE_DOUBLEQUOTES, // текст "выфвыфвыф"
STATE_BASIC_SLASH, /* состояние при первом слэше в базовом состоянии * /*/
STATE_SINGLEQUTES_SLASH, // состояние при первом слэше в тексте внутри кавычек
STATE_DOUBLEQUOTES_SLASH, // состояние при первом слэше в тексте внутри кавычек
STATE_SLASHSTAR_STAR // состояние при звезде в комментариях типа /* */
};
int main()
{
std::ifstream file_in;
std::ofstream file_out;
file_in.open("main.cpp");
if (!file_in)
{ std::cout << "Error // open "main.cpp"" << std::endl; return 1;
}
file_out.open( "main_out.cpp");
if (! file_out )
{ std::cout << "Error // open "main_out.cpp"" << std::endl; file_in.close(); return 1;
}
STATE state = STATE_BASIC; // начальное состояние
char ch; // текущий считанный из входного файла символ
while ( 1 )
{
file_in.get(ch);
if ( file_in.eof() )
{
if (state == STATE_BASIC_SLASH)
file_out.put( ´/´ ); // на случай если конец файла пришелся на состоние
// STATE_BASIC_SLASH и поэтому не напечатался символ "/"
break;
}
switch( state )
{
case STATE_BASIC:
switch(ch)
{
case ´"´: state = STATE_DOUBLEQUOTES; file_out.put( ch ); break;
case ´´´: state = STATE_SINGLEQUOTES; file_out.put( ch ); break;
case ´/´: state = STATE_BASIC_SLASH; break;
default: file_out.put( ch ); break;
}
break;
case STATE_BASIC_SLASH:
switch(ch)
{
case ´/´: state = STATE_SLASHSLASH; break;
case ´*´: state = STATE_SLASHSTAR; break;
default: file_out.put( ´/´ ); file_out.put( ch ); break;
}
break;
case STATE_DOUBLEQUOTES:
switch(ch)
{
case ´"´:
case ´ ´: state =STATE_BASIC; file_out.put( ch ); break;
case ´´: state =STATE_DOUBLEQUOTES_SLASH;file_out.put( ch );break;
default: file_out.put( ch ); break;
}
break;
case STATE_DOUBLEQUOTES_SLASH: state =STATE_DOUBLEQUOTES;file_out.put( ch ); break;
case STATE_SINGLEQUOTES:
switch(ch)
{
case ´´´:
case ´ ´: state = STATE_BASIC; file_out.put( ch ); break;
case ´´: state = STATE_DOUBLEQUOTES_SLASH; file_out.put( ch ); break;
default: file_out.put( ch ); break;
}
break;
case STATE_SINGLEQUTES_SLASH:
switch(ch)
{
case ´ ´: state = STATE_BASIC; file_out.put( ch ); break;
default: file_out.put( ch ); break;
}
break;
case STATE_SLASHSLASH:
switch ( ch )
{
case ´ ´: state = STATE_BASIC; file_out.put( ch ); break;
default: break;
}
break;
case STATE_SLASHSTAR:
switch ( ch )
{
case ´*´: state = STATE_SLASHSTAR_STAR; break;
default: break;
}
break;
case STATE_SLASHSTAR_STAR:
switch( ch )
{
case ´/´: state = STATE_BASIC; break;
default: state = STATE_SLASHSTAR; break;
}
break;
}
}
file_in.close();
file_out.close();
}
Преимуществом использования конечных автоматов является:
- - простота разработки (достаточно определить все состояния и переходы между ними), как следствие, скорее всего, все сразу заработает как надо, без отладки
- - скорость работы (переход в нужную ветку обработки в зависимости от входных данных происходит за фиксированное время)