Лексический анализатор

Лексический анализ заключается в анализе символов и выделение из них осмысленных единиц — лексем.
Например лексемой может являться число, математические оператор (плюс, минус, …), скобки, идентификатор переменной, комментарий и т. д.

Для реализации лексического анализа будем использовать часть своих классов и регулярных выражений.
Так в коде лексема числа будет представлена подклассом NumberToken класса Token.

public abstract class Token
{
…
/**
* Возвращает индекс начала лексемы
* @return Индекс начала лексемы
*/
public int getBegin()

/**
* Возвращает конца лексемы (исключительно)
* @return Индекс конца лексемы (исключительно)
*/
public int getEnd()

/**
* Возвращает исходный текст
* @return Исходная строка
*/
public String getSource()

/**
* Возвращает текст лексемы
* @return текст лексемы
*/
public String getText()
…
}

public class NumberToken extends Token
{
…
/**
* Возвращает вычисленное число
* @return Число
*/
public double getNumber()
…
}

Сам лексический анализатор в коде представлен классом TokensParser, который содержит список анализаторов для конкретных лексем.

public class TokensParser
{
…
/**
* Указывает список лексических анализаторов (анализаторов лексем)
* @return Список лексических анализаторов
*/
public List<TokenParser> getParsers()

/**
* Анализирует текст и возвращает распознанные лексемы
* @param source Исходный текст
* @return Список распознаны лексем
*/
public List<Token> parse(String source)
…
}

public interface TokenParser
{
/**
* Анализирует строку символов и возвращает соответствующую лексему
* @param source Исходная строка символов
* @param fromIndex Индекс символа с которого начать анализ
* @return Лексема или null, если лексема не распознана
*/
public Token parseToken(String source,int fromIndex);
}


Работа лексического анализатора

Работа с анализатора в данном случае проста.

1. Лексический анализатор в начале работы устанавливает указатель (pos) на начало строки исходной строки.
2. Используя список распознаваемых лексем последовательно распознает
3. Если распознана лексема, то он перемещает указатель на следующую часть строки и снова производит распознавание согласно списку лексем.
4. Если очередная часть текста не была распознана, как ни одна лексема, то это свидетельствует о ошибке входных данных
5. Распознавание видеться до конца текста или до ошибки.

Пример:

// Индекс символа с которого начать анализ
int pos = 0;

// Здесь будет храниться резуьтат
List<Token> result = new ArrayList<Token>();

while(true){
Token tok = null;

// Последовательно перебираем анализаторы
for(TokenParser parser : getParsers()){
if( parser==null )continue;

// Анализируем лексему
tok = parser.parseToken(source, pos);

// Лексема распознана? если да то добавляем как результат
// и переходим к след. символам
if( tok!=null ){
pos = tok.getEnd();
break;
}
}

// Ниодин анализатор не сработал, завершаем работу
if( tok==null )break;

// Добавляем как результат
result.add(tok);
}

Анализатор конкретной лексемы может быть реализован как в ручную, так и при помощи регулярных выражений. Смысл останется тем же.
В нашем примере калькулятора будут выделены следующие лексемы и в указанной последовательности:

1. WhiteSpaceToken — Пробельные символы
2. OpenBraceToken — Открытая скобка
3. CloseBraceToken — Закрытая скобка
4. SummaOperatorToken — Оператор + -
5. MultipleOperatorToken — Оператор * /
6. NumberToken — Число

А так же функция List<Token> filterWhiteSpace(List<Token> sourceTokens) для удаления пробелов (WhiteSpaceToken).

Для распознавания чисел в коде калькулятора напишем следующий лексический анализатор:


public static class Parser implements TokenParser
{
@Override
public Token parseToken(String source, int fromIndex)
{
if (source == null) {
throw new IllegalArgumentException("source == null");
}

if( fromIndex>=source.length() )return null;

Pattern p = Pattern.compile("(?s)^.{"+fromIndex+"}(\\s*\\d{1,}(\\.\\d{1,})?).*");
Matcher m = p.matcher(source);
if( !m.matches() )return null;

String mText = m.group(1);
Double number = Double.parseDouble(mText);

Token tok = new NumberToken(source, fromIndex, fromIndex+mText.length(), number);

return tok;
}
}


Так для анализа что заданная последователь является числом используется следующие регулярное выражение:


"(?s)^.{"+fromIndex+"}(\\s*\\d{1,}(\\.\\d{1,})?).*"


• (?s) — для ислючения символом перевода строк
• ^.{"+fromIndex+"} — Пропускаем символы согласно указанному количеству fromIndex
• \\s* — Допускаем возможное наличие пробелов
• \\d{1,}(\\.\\d{1,})? — Должны следовать цифры минимум 1 раз и возможно после них точка и снова цифры
• .* — Допускаем что после числа будет еще какие-то символы.

Остальные лексемы таким же образом будут распозноваться.