Написание интерпретатора скриптов на С++. Часть 2: Лексический Анализатор.
Автор: Skeef
Часть 1
О чем речь:
Давайте посмотрим на небольшой, вполне корректный, скрипт на языке ESL:
Randomize();
int answ, done = 0, num = Random(1, 100);%this is comment
Write("Guess a number between 1 and 100 I thought!" + Char(10));
while(done ~ 0)
{
Write("I think it is "); answ = StrToInt(ReadString());
if(answ > num)
Write("No! It's less!");
else if(answ < num)
Write("No! It's bigger!");
else
{
Write("Yes! You've done it! Congratulations!");
done = 1;
}
Write(Char(10));
}
end;Как многие (или немногие?) уже догадались – это игра в отгадывание чисел. Теперь давайте представим, как этот код должен обрабатывать наш интерпретатор. Итак, с чего надо начать? Очевидно, с загрузки кода в какую-либо структуру, размещенную в оперативной памяти компьютера. Но что делать потом? Те, кто достаточно внимательно читал первую статью, ответят «надо превратить эту штуку в последовательность лексем». И будут правы. А если я спрошу что такое «последовательность лексем» и как в нее преобразовать скрипт? Самые «умные» читатели наверняка не потеряются и скажут что-нибудь высокопарно-отвлеченно-никому-непонятное, чтобы по прежнему казаться самыми «умными». Другая часть читателей, те которые поскромнее, ответят просто и ясно «хз». Ну а третья часть читателей, которая точно знает, что она все знает, может смело пропустить эту главу.
Определимся с понятиями:
Итак, что же такое лексический анализатор? Далее под этим понятием я буду подразумевать часть системы обработки сценариев, предназначенную для осуществления первичной обработки входных данных, а именно: разбиение текста на поток лексем и идентификация (определение типа) каждой лексемы.
Под лексемой понимается отдельный смысловой фрагмент текста (например, слово, или функциональный символ). Write – это лексема, «,» и « » - тоже лексемы.
Ну и последнее понятие – токен. Этим словом я буду обзывать лексему вместе с ее типом. Именно поток токенов (выше было сказано «поток лексем» - но это не совсем точно, корректнее – поток лексем с их типами – а это есть токен) и должен являться результатом работы лексического анализатора.
Реализация лексического анализатора и его вспомогательных классов будет находиться в отдельном модуле – файлах Lexer.h и Lexer.cpp.
Разберемся с токенами:
Реализовать класс токена можно примерно следующим образом:
Lexer.h: #include <string> using namespace std; class CToken { private: E_TOKEN_TYPES _Type;//тип лексемы string _Text;//текст лексемы public: E_TOKEN_TYPES Type(void)const {return _Type;} string Text( void)const {return _Text;} CToken( void); CToken( const CToken&); CToken( E_TOKEN_TYPES, const string&); };
Здесь E_TOKEN_TYPES характеризует типы лексем; давайте теперь разберемся с ними. Если внимательно посмотреть на код вначале статьи, то можно выделить семь видов лексем. Плюс я добавил один дополнительный вид для неопознанных лексем:
| Тип | Примеры | Тип | Примеры |
| Зарезервированные слова | int, end | Операторы | +, ~, = |
| Целые константы | 10, 100 | Строковые константы | «I think it is» |
| Переменные | answ, num | Функции | Write(), Char() |
| Разделители | «,», «;» | Неидентифицированный |
В таком случае E_TOKEN_TYPES принимает следующий вид:
enum E_TOKEN_TYPES { ttResWord = 0, //ключевое (зарезервированное) слово ttOperator, //оператор ttStrConstant, //строковая константа ttIntConstant, //числовая константа ttVariable, //переменная ttFunction, //функция ttDevider, //разделитель ttUnknown //тип не определен, либо не известен };
Реализация конструкторов класса CToken (файл Lexer.cpp):
CToken::CToken(void): _Type( ttUnknown) {}; CToken::CToken( const CToken& other): _Type( other._Type), _Text( other._Text) {}; CToken::CToken( E_TOKEN_TYPES type, const string& text): _Type( type), _Text( text) {};
Ну вот, первый вариант класса CToken определен. Далее я рассмотрю реализацию непосредственно лексического анализатора, попутно отвлекаясь на некоторые другие важные моменты.
Начнем с начала:
Для начала неплохо было бы определиться с общей схемой работы ЛА. В общем виде она может быть представлена следующим образом:
вход->пока не обработаны все данные: формировать очередной токен->помещать его в буфер токенов
формирование очередного токена: выделение очередной лексемы из входных данных->определение ее типа->помещение типа и текста лексемы в объект токена
Прежде всего, давайте разберемся с «выделением очередной лексемы из входных данных» - лексированием текста (авт.). В принципе это не проблема – достаточно знать все символы, которые могут разделять слова, а также операторы (которые по сути дела, тоже являются разделяющими символами). Думаю, удобнее всего будет хранить эти символы в двух строках (std::string, и вообще далее я постараюсь, по возможности, чаще прибегать к средствам стандартной библиотеки). Ну а зная разделители, достаточно последовательно пробежать по входным данным, выделяя фрагменты, заключенные между двумя соседними разделителями.
Исходя из вышесказанного, интерфейс ЛА можно реализовать, например, вот таким образом:
typedef vector<CToken> TokensArray; class CLexer { private: string _Operators, //операторы _Deviders; //разделители TokensArray _TokensBuffer; //токены, полученные при последнем //"лексировании" текста unsigned _OffSet; //позиция в текущем лексируемом тексте //возвращает очередной токен из передаваемого текста CToken SkanToken(const string&); public: const TokensArray& GetTokens( void)const {return _TokensBuffer;} void SaveTokens( ostream& os)const; //разбивает передаваемый текст на массив токенов bool Lex( const string&); };
Функция SaveTokens предназначена для контроля состояния _TokensBuffer. Она выводит каждый токен в указанный поток. Сейчас может показаться, что от нее нет никакого толку, но позже SaveTokens пригодится нам для отладки – с ней гораздо (с большой буквы Г) удобнее контролировать состояние буфера.
Прежде чем приступить к реализации функций CLexer’а,...
Лирическое отступление №1: «Логи»
Наверное каждый программист знает такое страшное слово: «отладка»; наверняка каждому этот длительный процесс немало потрепал нервы. Ну так вот, чтобы не мучаться потом, давайте думать о будущем сейчас. Наиболее простым способом для избавления от лишних проблем, на мой взгляд, является ведение лога по ходу работы программы. В нашей системе обработки сценариев лог будет в основном использоваться для вывода сообщений об ошибках/предупреждениях. Ниже я привожу public-интерфейс класса CLogFile; полный интерфейс и реализацию класса можно найти в прилагаемом к статье исходном коде.
//Utils.h: class CLogFile { private: std::ofstream _LogFile; //файловый поток вывода, в который пишется лог ... public: std::ofstream& LogFile(void) {return _LogFile;} //пишет в лог произвольное сообщение void WriteMessage( const char*, ...); //пишет в лог предупреждение void WriteWarning( const char*, ...); //пишет в лог сообщение об ошибке void WriteError( const char*, ...); //в конструкторе создается лог и туда помещаются необходимые данные CLogFile( const char*, const char*); //в деструкторе лог завершается и закрывается ~CLogFile( void); }; //Utils.cpp: CLogFile ESLLog( "ESLlog.htm","Global Log"); //Utils.h: extern CLogFile ESLLog; #ifndef _ESLNDEBUG /*макросы, описанные ниже предназначены для более удобной записи сообщения об ошибке в лог и возврата результата.*/ //err - текст ошибки, ret - возвращаемый результат #define MACRO_ERROR_RET( err,ret) {ESLLog.WriteError( ##err##);return( ##ret##);} //err - текст ошибки; осуществляется выход из вызывающей функции #define MACRO_ERROR_RET_VOID( err) {ESLLog.WriteError( ##err##);return;} #else #define MACRO_ERROR_RET( err,ret) {return( ##ret##);} #define MACRO_ERROR_RET_VOID( err) {return;} #endif
Продолжим:
Теперь можно приступить к реализации некоторых функций. Начнем с простого:
void CLexer::SaveTokens(ostream& os)const { if( os.bad( )) MACRO_ERROR_RET_VOID( "CLexer::SaveTokens error"); string types[] = {"ttResWord", "ttOperator", "ttStrConstant", "ttIntConstant", "ttVariable", "ttFunction", "ttDevider", "ttUnknown"}; for( unsigned i=0;i<_TokensBuffer.size( );++i) os<<types[_TokensBuffer[i].Type( )]<< ": '"<<_TokensBuffer[i].Text( )<<"'"<<endl; }
Тут все просто: последовательно выводим в поток строки вида <Тип токена>:<Текст токена>.
Не многим сложнее функция Lex:
bool CLexer::Lex(const string& text) { _OffSet = 0; _TokensBuffer.clear( ); //если текст text пуст - выход if ( text.empty( )) MACRO_ERROR_RET( "CLexer::Lex tryng to lex empty text", false); unsigned prev_offset=-1;//предидующея позиция; для отслеживания смещения CToken token;//очередной токен //сканиурем токены, пока не дойдем до конца скрипта do { //если смещения на следующую лексему по какой-либо причине не произошло if( prev_offset==_OffSet) MACRO_ERROR_RET( "CLexer::Lex error. Possibly end missed",false); prev_offset = _OffSet; token = SkanToken( text); if( token==ErrorToken)return false;//ошбика при сканировании токена _TokensBuffer.push_back( token); } while( token.Text( )!="end"); return true; }
Здесь ErrorToken – это токен, сигнализирующий об ошибке. SkanToken возвращает его, если что-то пошло не так. Вставить его описание можно куда-нибудь в начало Lexer.cpp после инклудов:
#include <ctype.h> #include <algorithm> #pragma hdrstop #include "Lexer.h" #include "Utils.h" CToken ErrorToken(ttUnknown, "ErrorToken");
Также для того, чтобы вышеприведенный код нормально скомпилировался, нужно добавить в класс токена два оператора: operator= и operator==:
CToken& CToken::operator=(const CToken& other) { _Type = other._Type; _Text = other._Text; return *this; } bool CToken::operator==( const CToken& other)const { return _Type==other._Type && _Text==other._Text; }
14 декабря 2003 (Обновление: 18 ноя 2009)