ЯЗЫКИ ПРОГРАММИРОВАНИЯ И МЕТОДЫ ТРАНСЛЯЦИИ Рейн Т. С. Пример лексического анализатора

Задача лексического анализатора Задача лексического анализа – разбиение исходной программы на лексемы Типичные лексические классы : Ключевые слова (if, switch, for…) Идентификаторы Строковые литералы Числовые константы Каждому подмножеству сопоставляется некоторое число, называемое идентификатором лексического класса (token) или, короче, лексическим классом ( лексхема с типом ).

Класс токена (lexer.h и lexer.cpp) lexer.h #include 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&); };

Тип Примеры Тип Примеры Зарезервиров анные слова 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::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) {};

Работа лексического анализатора вход -> пока не обработаны все данные : формировать очередной токен -> помещать его в буфер токенов формирование очередного токена : выделение очередной лексемы из входных данных -> определение ее типа -> помещение типа и текста лексемы в объект токена

« выделение очередной лексемы из входных данных » достаточно знать все символы, которые могут разделять слова, а также операторы ( которые тоже являются разделяющими символами ). удобнее всего хранить эти символы в двух строках (std::string) зная разделители, достаточно последовательно пробежать по входным данным, выделяя фрагменты, заключенные между двумя соседними разделителями.

Интерфейс ЛА typedef vector 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; // Функция SaveTokens предназначена для контроля состояния _TokensBuffer. Она выводит каждый // токен в указанный поток. bool Lex(const string&); //разбивает передаваемый текст на массив токенов };

Последовательно выводим в поток строки вида : 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

Функция 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;//очередной токен

Функция Lex //сканиурем токены, пока не дойдем до конца скрипта 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 возвращает его, если что - то пошло не так.

ErrorToken- добавить в начало Lexer.cpp ( после include) #include #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; }

Задача ЛА Задан текст, позиция в этом тексте (_OffSet), массивы операторов и разделителей ; Используя эти данные надо выделить из текста очередной токен ( тип его не определен ) и переместить позицию за этот токен. Дополнительно необходимо учитывать, что сами разделители и операторы, встречающиеся в тексте, также являются лексемами и их наряду с остальными элементами текста придется выделять и идентифицировать.

Решение 1 Простое решение - последовательно перебирать символы текста с текущей позиции, занося их в строковую переменную, до тех пор, пока не будет встречен символ из массива разделителей или операторов. В итоге в строковой переменной будет хранится очередная лексема. На первый взгляд довольно просто. Но если в тексте в позиции _OffSet находится разделитель или оператор, то лексема не будет выделена корректно. Отсюда возникает необходимость дополнительных проверок

Решение 2 Объединить разделители и операторы в статическую константную строку для разделяющих символов. Таким образом, количество проверок сокращается до минимума. Можно также воспользоваться стандартным поиском string а.

CToken CLexer::SkanToken(const string& text) { CToken ret; //строка, содержащая разделяющие символы static const string delim = _Deviders + _Operators; //позиция ближайшего разделяющего символа const unsigned delimpos = text.find_first_of(delim, _OffSet); //если это //последняя лексема в text то выделяем фрагмент текста между позицией и //концом файла if(delimpos==text.npos) ret.Text = text.substr(_OffSet); //позиция не последняя, то есть выделяем текст, заключенный между //текушей позицией и ближайшим разделяющим символом else { //либо, если находимся на разделителе (delimpos-_OffSet=0) выделяем его ret._Text = text.substr(_OffSet,max(delimpos-_OffSet,unsigned(1))); //перемещение на следующую лексему _ OffSet = max(delimpos,_OffSet+1); } return ret;} Здесь осуществляется прямой доступ из функции класса CLexer к закрытым данным класса CToken. Для этого CLexer должен быть объявлен другом CTokenа.

Инициализация ЛА Для занесения данных в _Operators и _Deviders, создадим функцию Init. class Clexer{ private: //распознаваемые лексическим анализатором... StringsArray _ResWordsArray, //зарезервированные слова FunctionsArray; //функции string _Operators, //операторы _Deviders; //разделители //...

Инициализация ЛА public: //... //инициализирует лексический анализатор. // Эта функция должны быть вызвана //до первого "лексирования" void Init (const string*, unsigned, unsigned, unsigned, unsigned); //добавляет дополнительные функции в _FunctionsArray void AddFunctions(const string*, unsigned); };

Реализация функции инициализации void CLexer::Init( //указатель на первый элемент массива строк-данных const string* data, unsigned rwc, //число зарезервироавнных слов unsigned opc, //число операторов unsigned fnc, //число функций unsigned dvc //число разделителей )

{ //копирование зарезервированных слов _ResWordsArray.resize(rwc); const string* rwend = data + rwc; copy(data,rwend,_ResWordsArray.begin()); //копирование операторов const string* opend = rwend + opc; for(unsigned i=0;i

Запуск программы Для запуска можно создать файл test.txt и поместите туда следующую строку : int a = Random(1, 100); end; Функция main #include #pragma hdrstop #include "Lexer.h« #include "Utils.h«

int main(int argc, char* argv[]) { CLexer Lexer; string data[ ] = {"int","end", "+,"Random", " ", ";", "(", ")", ",", "\n"}; Lexer.Init(data,2,1,1,6); FILE *f = fopen("test.txt","rt"); fseek(f, 0, SEEK_END); long len = ftell(f); fseek(f, 0, SEEK_SET); string str; str.resize(len); fread(&str[0],1,len,f); Lexer.Lex(str); Lexer.SaveTokens(cout); fclose(f); getch(); return 0; } При изменении содержимого test.txt, необходимо внести соответствующие дополнения синтаксиса в data[].

После запуска программы в консоль выводится последовательность неидентифицированных токенов: ttUnknown: 'int ttUnknown: ' ttUnknown: '= ttUnknown: ' ttUnknown: Random ttUnknown: '( ttUnknown: '1 ttUnknown: ', ttUnknown: ' ttUnknown: '100 ttUnknown: ') ttUnknown: ' ttUnknown: '+ ttUnknown: ' ttUnknown: '10 ttUnknown: '; ttUnknown: ' ttUnknown: 'end'

Распознавание токенов Необходимо добавить в CLexer ( в private- раздел ) функцию void DefineTokenType(CToken&)const;

void Clexer :: DefineTokenType(CToken& token) const { //поиск в массиве разделителей if (_Deviders.find(token.Text())!=_Deviders.npos) token.Type = ttDevider; //поиск в массиве операторов else if (_Operators.find(token.Text())!=_Operators.npos) token.Type = ttOperator; //поиск в массиве зарезервированных слов else if (find(_ResWordsArray.begin(), _ResWordsArray.end(), token.Text())!= _ResWordsArray.end()) token.Type = ttResWord;

//поиск в массиве функций else if (find(_FunctionsArray.begin(), _FunctionsArray.end(), token.Text())!= _FunctionsArray.end()) token.Type = ttFunction; //проверка: является ли токен целым числом else {unsigned i; for(i=0; i< token.Text.length(); ++i) if( !isdigit (token.Text()[i])) break; if(i==token.Text().length()) //если все символы текста токена - цифры token._Type = ttIntConstant;

/*никаких соответствий не найдено, значит токен - название какой-либо переменной. Если это не так (т.е. текст токена некорректен - например опечатка или название несуществующей переменной), то ошибка будет выявлена на стадии выполнения опкода виртуальной машиной*/ else token._Type = ttVariable; }

После добавления вызова этой функции в конец SkanToken CToken CLexer::SkanToken (const string& text) {... DefineTokenType(ret); //определение типа токена, по тексту в нем return ret;}

Запуск программы - новый результат ttResWord: 'int ttDevider: ' ttOperator: '= ttDevider: ' ttFunction: 'Random ttDevider: '( ttIntConstant: '1 ttDevider: ', ttDevider: ' ttIntConstant: '100 ttDevider: ') ttDevider: ' ttOperator: '+ ttDevider: ' ttIntConstant: '10 ttDevider: '; ttDevider: ' ttResWord: 'end'

Полная инициализация ЛА... string data[]= {"bool", "int","string","end","if","else","while", "for","break", "+", "-", "=", "/", "*", ">", "

Внесение в в test.txt строковой константы string s = This is string!; end; Вместо одного токена типа ttStrConstant, содержащего строку, в консоль выводится несколько токенов ошибочного типа. Это связано с тем, что в настоящий момент, текст, заключенный в кавычки, не рассматривается как единое целое, а лексируется по обычным правилам. Нам же надо добиться того, чтобы ни разделители, ни операторы в закавыченном тексте не воспринимались как таковые.

Если внимательно проанализировать процесс сканирования текста, заключенного в кавычки, то можно заметить, что в какой - то момент времени _OffSet находится в позиции первой кавычки ( даже если та не является разделителем ). Такой эффект получается вследствие того, что по правилам языка этой кавычке всегда предшествует оператор, либо разделитель. Таким образом, логично написать отдельную функцию для сканирования строковой константы и вызывать ее из функции SkanToken, когда в позиции _OffSet лексируемого теста находится кавычка. Внесение в в test.txt строковой константы

Реализация функции SkanStringConstant ( она также является private- членом класса CLexer) CToken CLexer::SkanStringConstant(const string& text) { //_OffSet сейчас находится в позиции первой кавычки //поиск второй закрывающей кавычки const unsigned pos = text.find_first_of('"',++_OffSet); if(pos==text.npos) //если зыкрывающая кавычка не найдена MACRO_ERROR_RET("CLexer::SkanStringConstant: '' expected",ErrorToken); //все в порядке, кавычка найдена const unsigned begin = _OffSet; _ OffSet = pos+1; //перемещение позиции за кавычку return CToken(ttStrConstant, string(text, begin, pos-begin));}

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

Дополнение функции SkanToken CToken CLexer::SkanToken (const string& text) { //если в текущей позиции кавычка, // значит далее следует строковая константа if(text[_OffSet]=='"') return SkanStringConstant(text);... }

Кавычки в тексте Важно : Символ никогда не должен использоваться внутри строковой константы ; это неизбежно вызовет ее неправильный анализ.

Пропуск коментариев Пусть test.txt, содержит текст : При выполнении программы комментарии воспринимаются как переменные. string s = "This is string!"; %comment % this is comment end;

добавление еще одной функции в SkanToken: CToken CLexer::SkanToken (const string& text) { //если в текущей позиции кавычка, значит далее следует строковая константа if(text[_OffSet]=='"') return SkanStringConstant(text); //пропуск комментария если надо if(text[_OffSet]=='%') SkipComment(text);... }

Реализация private- функции CLexera SkipComment void CLexer::SkipComment(const string& text) { while(text[_OffSet]=='%') _OffSet = text.find_first_of("\n", _OffSet) + 1; }