Пишем интерпретатор на PascalABC.NET. Лексический анализатор. Часть 3
Данный текст - продолжение https://teletype.in/@pascalabcnet/Lex2
Построим лексический анализатор для языка, содержащего следующие лексемы: ключевые слова (if, then, else, while, do), идентификаторы, целые и вещественные константы, строковые константы, заключенные в "", операции присваивания, операции сравнения и логические операции в стиле C, арифметические операции, лексемы { } для выделения блока кода, комментарии // до конца строки.
Напомним, что лексема (токен) - это неделимая конструкция в тексте программы.
Базовые типы
Определим вначале все типы токенов в виде перечислимого типа TokenType:
type
TokenType = (Int, DoubleLiteral, StringLiteral,
Id,
Plus, Minus, Multiply, Divide, Dot,
Semicolon, LPar, RPar, LBrace, RBrace, Comma, Colon,
Assign, AssignPlus, AssignMinus, AssignMult, AssignDiv,
Equal, Less, LessEqual, Greater, GreaterEqual, NotEqual,
tkAnd, tkOr, tkNot,
Eof,
tkTrue, tkFalse, tkIf, tkThen, tkElse, tkWhile, tkDo
);Далее определим класс Token, производный от TokenBase и включающий в себя тип токена как поле:
type
Token = class(TokenBase)
public
Typ: TokenType;
constructor (Typ: TokenType; Pos: Position; Value: Object := nil);
begin
(Self.Typ, Self.Pos, Self.Value) := (Typ, Pos, Value);
end;
end;Словарь ключевых слов
Кроме того, определим словарь, ставящий в соответствие ключевым словам типы их токенов:
var Keywords := Dict(
('True', TokenType.tkTrue),
('False', TokenType.tkFalse),
('if', TokenType.tkIf),
('then', TokenType.tkThen),
('else', TokenType.tkElse),
('while', TokenType.tkWhile),
('do', TokenType.tkDo)
);Класс Lexer
Теперь всё готово для создания конкретного лексического анализатора, который определим в виде класса, производного от LexerBase:
type Lexer = class(LexerBase) ... end;
Метод NextToken
Приведем полный код главного метода этого класса - NextToken - возвращающего следующий токен:
function NextToken: Token;
begin
var c := NextChar;
while c in |#13,#7,' ',#10| do
c := NextChar;
var pos := CurrentPosition;
start := cur-1;
case c of
#0 : Result := new Token(TokenType.Eof,pos,'Eof');
',': Result := new Token(TokenType.Comma,pos);
')': Result := new Token(TokenType.RPar,pos);
'(': Result := new Token(TokenType.LPar,pos);
'}': Result := new Token(TokenType.RBrace,pos);
'{': Result := new Token(TokenType.LBrace,pos);
'+': Result := new Token(IsMatch('=') ?
TokenType.AssignPlus : TokenType.Plus,pos);
'-': Result := new Token(IsMatch('=') ?
TokenType.AssignMinus : TokenType.Minus,pos);
'*': Result := new Token(IsMatch('=') ?
TokenType.AssignMult : TokenType.Multiply,pos);
'/': if IsMatch('/') then
while (PeekChar <> #10) and not IsAtEnd do
NextChar
else Result := new Token(IsMatch('=') ?
TokenType.AssignDiv : TokenType.Divide,pos);
';': Result := new Token(TokenType.Semicolon,pos);
'!': Result := new Token(IsMatch('=') ?
TokenType.NotEqual : TokenType.tkNot,pos);
'=': Result := new Token(IsMatch('=') ?
TokenType.Equal : TokenType.Assign,pos);
'>': Result := new Token(IsMatch('=') ?
TokenType.GreaterEqual : TokenType.Greater,pos);
'<': Result := new Token(IsMatch('=') ?
TokenType.LessEqual : TokenType.Less,pos);
'&': if IsMatch('&') then
Result := new Token(TokenType.tkAnd,pos)
else raise new LexerException(#39;Неверный символ {c.Code} после &',CurrentPosition);
'|': if IsMatch('|') then
Result := new Token(TokenType.tkOr,pos)
else raise new LexerException(#39;Неверный символ {c.Code} после |',CurrentPosition);
'"': Result := GetString(pos)
else
if c.IsDigit then
Result := GetNumber(pos)
else if IsAlpha(c) then
Result := GetIdentifier(pos)
else raise new LexerException(#39;Неизвестный символ {c} в позиции {pos.line},{pos.col}',pos);
end;
if Result.Value = nil then
Result.Value := code[start:cur];
end;В начале этого метода мы пропускаем пробельные символы и считываем первый не пробельный. После этого запоминаем текущую позицию этого символа (это будет позиция начала токена) и в переменной start - индекс начала токена в строке code.
Далее в коде метода следует большой оператор case, который по текущему считанному символу c пытается определить лексему и вернуть её в качестве значения этого метода.
Рассмотрим несколько примеров.
#0 : Result := new Token(TokenType.Eof,pos,'Eof');
обрабатывает ситуацию, когда достигнут конец строки (). В этом случае возвращается токен с типом TokenType.Eof и строковым представлением Eof.
',': Result := new Token(TokenType.Comma,pos);
')': Result := new Token(TokenType.RPar,pos);
'(': Result := new Token(TokenType.LPar,pos);
'}': Result := new Token(TokenType.RBrace,pos);
'{': Result := new Token(TokenType.LBrace,pos);обрабатывают односимвольные токены, с которых не могут начинаться многосимвольные токены. Обратим внимание, что каждый токен сохраняет позицию своего начала.
Далее рассмотрим ситуацию определения одного из токенов + или +=. Заметим, что оба токена имеют префикс + и более не существует токенов с этим префиксом. Обрабатывается подобная ситуация так: если после символа + мы встречаем символ =, то это токен с типом TokenType.AssignPlus, в противном случае это токен TokenType.Plus и следующий символ не считывается:
'+': Result := new Token(IsMatch('=') ?
TokenType.AssignPlus : TokenType.Plus,pos);Далее рассмотрим случай обработки двухсимвольного токена на примере &&. После считывания первого символа мы анализируем второй - он также должен быть & - если это не так, то кидаем исключение:
'&': if IsMatch('&') then
Result := new Token(TokenType.tkAnd,pos)
else raise new LexerException(#39;Неверный символ {c.Code} после &',CurrentPosition);Нам осталось выделить такие составные лексемы как литеральные строки, числа и идентификаторы.
Метод GetString
Наконец, если встретился символ ", то перед нами - начало литеральной строки вида "Hello" - соответствующий токен возвращается вызовом метода Result := GetString(pos), где метод GetString описывается так:
function GetString(startPos: Position): Token;
begin
while (PeekChar <> '"') and not IsAtEnd do
NextChar;
NextChar; // пропустить "
var value := code[start + 1: cur - 1];
Result := new Token(TokenType.StringLiteral, startPos, value);
end;Нетрудно видеть, что здесь пропускаются все символы до второго " и затем также пропускается сам символ ". После этого возвращается токен TokenType.StringLiteral, значение которого - это литеральная строка без кавычек, расположенная в срезе строки code[start + 1: cur - 1].
В ветви else оператора case обработаем все остальные случаи, включающие не отдельные символы, а классы символов.
Выделение чисел и идентификаторов
Если далее встречается символ из класса цифр, то возвращается токен Число (целое или вещественное), а если - символ из класса букв, то токен Идентификатор. В любом из оставшихся случаев генерируется исключение:
if c.IsDigit then
Result := GetNumber(pos)
else if IsAlpha(c) then
Result := GetIdentifier(pos)
else raise new LexerException(#39;Неизвестный символ {c} в позиции {pos.line},{pos.col}',pos);В заключительной части метода NextToken мы заполняем поле Value у токена текстовым представлением токена - если это значение отсутствует:
if Result.Value = nil then Result.Value := code[start:cur];
Исключение LexerException
Отдельно поясним класс исключения LexerException. Он вводится следующим кодом:
type
BaseCompilerException = class(Exception)
public
Pos: Position;
constructor(msg: string; p: Position);
begin
inherited Create(msg);
Pos := p;
end;
end;
LexerException = class(BaseCompilerException) end;Нетрудно видеть, что этот класс наследуется от базового класса BaseCompilerException ,Нетрудно видеть, что этот класс наследуется от базового класса BaseCompilerException, хранящего помимо сообщения ошибки её позицию. Обработке этого исключения будет посвящен отдельный пункт.
Методы GetNumber и GetIdentifier
Теперь разберем оставшиеся методы - GetNumber и GetIdentifier.
Если мы считали букву, то это - идентификатор, и считываем далее буквы или цифры:
function GetIdentifier(startPos: Position): Token;
begin
while IsAlphaNumeric(PeekChar) do
NextChar;
var value := code[start:cur];
var typ := TokenType.Id;
if value in Keywords then
typ := Keywords[value];
Result := new Token(typ, startPos, value);
end;Текст идентификатора находится как обычно в code[start:cur].
Есть только небольшое исключение, которое обрабатывается аналогичным образом во всех языках, имеющих ключевые слова: если данный идентификатор является ключевым словом, то мы находим соответствующий ему тип токена в словаре Keywords:
if value in Keywords then typ := Keywords[value];
Наиболее сложно обрабатывается число - вот код метода GetNumber:
function GetNumber(startPos: Position): Token;
begin
while PeekChar.IsDigit do
NextChar;
if (PeekChar = '.') and PeekNextChar.IsDigit then
begin
NextChar;
while PeekChar.IsDigit do
NextChar;
var value := code[start : cur];
var re: real := value.ToReal;
Result := new Token(TokenType.DoubleLiteral, startPos, value.ToReal);
exit;
end;
var val := code[start : cur];
Result := new Token(TokenType.Int,startPos,val.ToInteger);
end;Основная сложность здесь - в том, что число может быть либо целым, либо вещественным (содержать точку).
Вначале мы пропускаем все цифры:
while PeekChar.IsDigit do NextChar;
Затем если текущий символ - точка и следующий символ - цифра, то мы пропускаем точку и вновь пропускаем все цифры:
if (PeekChar = '.') and PeekNextChar.IsDigit then
begin
NextChar;
while PeekChar.IsDigit do
NextChar;Затем получаем строковое представление числа, преобразуем его в вещественное и именно этим значением инициализируем возвращаемый токен:
var value := code[start : cur]; var re: real := value.ToReal; Result := new Token(TokenType.DoubleLiteral, startPos, value.ToReal); exit; end;
Наконец, если мы не встретили точку, то это - целое число:
var val := code[start : cur]; Result := new Token(TokenType.Int,startPos,val.ToInteger);
Итоговый класс Lexer
Итак, мы написали класс Lexer нашего будущего языка. Вот его полный код:
Lexer = class(LexerBase)
private
function GetIdentifier(startPos: Position): Token;
begin
while IsAlphaNumeric(PeekChar) do
NextChar;
var value := code[start:cur];
var typ := TokenType.Id;
if value in Keywords then
typ := Keywords[value];
Result := new Token(typ, startPos, value);
end;
function GetString(startPos: Position): Token;
begin
while (PeekChar <> '"') and not IsAtEnd do
NextChar;
NextChar; // пропустить "
var value := code[start + 1: cur - 1];
Result := new Token(TokenType.StringLiteral, startPos, value);
end;
function GetNumber(startPos: Position): Token;
begin
while PeekChar.IsDigit do
NextChar;
if (PeekChar = '.') and PeekNextChar.IsDigit then
begin
NextChar;
while PeekChar.IsDigit do
NextChar;
var value := code[start : cur];
var re: real := value.ToReal;
Result := new Token(TokenType.DoubleLiteral, startPos, value.ToReal);
exit;
end;
var val := code[start : cur];
Result := new Token(TokenType.Int,startPos,val.ToInteger);
end;
public
function NextToken: Token;
begin
var c := NextChar;
while c in |#13,#7,' ',#10| do
c := NextChar;
var pos := CurrentPosition;
start := cur-1;
case c of
#0 : Result := new Token(TokenType.Eof,pos,'Eof');
',': Result := new Token(TokenType.Comma,pos);
')': Result := new Token(TokenType.RPar,pos);
'(': Result := new Token(TokenType.LPar,pos);
'}': Result := new Token(TokenType.RBrace,pos);
'{': Result := new Token(TokenType.LBrace,pos);
'+': Result := new Token(IsMatch('=') ? TokenType.AssignPlus : TokenType.Plus,pos);
'-': Result := new Token(IsMatch('=') ? TokenType.AssignMinus : TokenType.Minus,pos);
'*': Result := new Token(IsMatch('=') ? TokenType.AssignMult : TokenType.Multiply,pos);
'/': if IsMatch('/') then
while (PeekChar <> #10) and not IsAtEnd do
NextChar
else Result := new Token(IsMatch('=') ? TokenType.AssignDiv : TokenType.Divide,pos);
';': Result := new Token(TokenType.Semicolon,pos);
'!': Result := new Token(IsMatch('=') ? TokenType.NotEqual : TokenType.tkNot,pos);
'=': Result := new Token(IsMatch('=') ? TokenType.Equal : TokenType.Assign,pos);
'>': Result := new Token(IsMatch('=') ? TokenType.GreaterEqual : TokenType.Greater,pos);
'<': Result := new Token(IsMatch('=') ? TokenType.LessEqual : TokenType.Less,pos);
'&': if IsMatch('&') then
Result := new Token(TokenType.tkAnd,pos)
else raise new LexerException(#39;Неверный символ {c.Code} после &',CurrentPosition);
'|': if IsMatch('|') then
Result := new Token(TokenType.tkOr,pos)
else raise new LexerException(#39;Неверный символ {c.Code} после |',CurrentPosition);
'"': Result := GetString(pos)
else
if c.IsDigit then
Result := GetNumber(pos)
else if IsAlpha(c) then
Result := GetIdentifier(pos)
else raise new LexerException(#39;Неизвестный символ {c} в позиции {pos.line},{pos.col}',pos);
end;
if Result.Value = nil then
Result.Value := code[start:cur];
end;
end; Тестирующая программа
Простая тестирующая программа:
uses LexUnit;
begin
var lex := new Lexer('a = 35; if a > 40 then a = 40 else { a = 0; print(a * 223 + 10) }');
var t: Token;
repeat
t := lex.NextToken;
Print(t.Value);
until t.Typ = TokenType.Eof;
end.a = 35 ; if a > 40 then a = 40 else { a = 0 ; print ( a * 223 + 10 ) } Eof Немного модифицированная тестирующая программа:
uses LexUnit;
begin
var lex := new Lexer('a = 35; if'#10'a > 40 && True'#10#10'then a = 40 else '#10'{ a = 0; print(a * 223 + 10) }');
var t: Token;
repeat
t := lex.NextToken;
Println(t);
until t.Typ = TokenType.Eof;
end.((1,1),a,Id)
((1,3),=,Assign)
((1,5),35,Int)
((1,7),;,Semicolon)
((1,9),if,tkIf)
((2,1),a,Id)
((2,3),>,Greater)
((2,5),40,Int)
((2,8),&&,tkAnd)
((2,11),True,tkTrue)
((4,1),then,tkThen)
((4,6),a,Id)
((4,8),=,Assign)
((4,10),40,Int)
((4,13),else,tkElse)
((5,1),{,LBrace)
((5,3),a,Id)
((5,5),=,Assign)
((5,7),0,Int)
((5,8),;,Semicolon)
((5,10),print,Id)
((5,15),(,LPar)
((5,16),a,Id)
((5,18),*,Multiply)
((5,20),223,Int)
((5,24),+,Plus)
((5,26),10,Int)
((5,28),),RPar)
((5,30),},RBrace)
((5,30),Eof,Eof) Здесь следует обратить внимание, что для каждого токена выводится позиция его начала, его значение и тип.
Поздравляем! Мы создали лексический анализатор простого языка. Он занимает около 250 строк кода вместе со всеми модулями.