Войти
ПрограммированиеСтатьиОбщее

Написание интерпретатора скриптов на С++. Часть 2: Лексический Анализатор.

Автор:

Часть 1
Часть 2

Часть 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;
}

Страницы: 1 2 Следующая »

#скрипты

14 декабря 2003 (Обновление: 18 ноя. 2009)

Комментарии [18]