Собираем парсер математических выражений

 Согласно формальной грамматике у нас должно получится следующие файлы:

• Нетерминалы
  
  • SummaValue.java — сложение / вычитание, будет в дальнейшем использоваться как начальный нетерминал
  • MultipleValue.java — умножение / деление
  • CValue.java — число / скобки / унарный минус
• Лексемы
  
  • SummaOperatorToken.java — плюс / минус
  • MultipleOperatorToken.java — множить / делить
  • OpenBraceToken.java — открытая скобка
  • CloseBraceToken.java — закрытая скобка
  • NumberToken.java — число
  • WhiteSpaceToken.java — пробел
• TokensParser.java — Лексический анализатор
• SyntaxParser.java — Базовый класс для нетерминалов
• TokenParser.java — Интерфейс лексического анализатора
• Operator.java — Перечисление математический операторов
• Token.java — Базовый класс лексемы
• Value.java — Интерфейс математического выражения

Математическое выражение будет предоставляться через интерфейс Value.

Главный файл будет у нас примерно следующего вида:


public class Main
{
public static void main(String[] args)
{
// Инициализируем лексический анализатор
TokensParser tokParser = new TokensParser();
tokParser.getParsers().add(new WhiteSpaceToken.Parser());
tokParser.getParsers().add(new OpenBraceToken.Parser());
tokParser.getParsers().add(new CloseBraceToken.Parser());
tokParser.getParsers().add(new SummaOperatorToken.Parser());
tokParser.getParsers().add(new MultipleOperatorToken.Parser());
tokParser.getParsers().add(new NumberToken.Parser());

// Это исходное выражение которое нужно вычислить
String source = " 2+3*4*(1+9)";

// Вычисляем лексемы
List<Token> tokens = tokParser.parse(source);
if( tokens==null )
{
System.out.println("no tokens");
return;
}

// Удаляем пробелы
tokens = TokensParser.filterWhiteSpace(tokens);

// Создаем дерево математического выражения используя синтаксический анализатор
SyntaxParser.Result res = SummaValue.instance.parse(0, tokens);
if( res==null ){
System.out.println("not parsed");
return;
}

Object r = res.getResult();
if( r==null || !(r instanceof Value) ){
System.out.println("no value parsed");
return;
}

// Вычисляем значение используя построенное дерево
System.out.println("result = "+((Value)r).eval());
}
}

В результате работы у нас должно быть создано следующее дерево выражения «2+3*4*(1+9)»:

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

Заключение

Рассмотрено принцип создания синтаксического анализатора, работающего методом рекурсивного спуска.

В данной части не рассмотрено теория связанная с формальной грамматикой, соответствующую теорию можно почитать в разделе литература.

Литература

1. Н.Н. Вояковская, А.Е. Москаль, Д.Ю. Булычев, А.А. Терехов «Разработка компиляторов» http://www.intuit.ru/department/sa/compilersdev/
2. Терехов Ан.А., Вояковская Н., Булычев Д., Москаль А. Разработка компиляторов на платформе .NET: Курс лекций. - СПб.: СПбГУ, Кафедра системного программирования, 2001. - 357 с. http://window.edu.ru/window/library?p_rid=41679