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

«Синтаксический анализ (парсинг) — это процесс сопоставления линейной последовательности лексем языка с его формальной грамматикой. Результатом обычно является дерево разбора (синтаксическое дерево)»

http://ru.wikipedia.org/wiki/Синтаксический анализ

Формальная грамматика состоит из таких компонентов как:

• Лексем, научно называется терминал.
• Нетерминал - объект, обозначающий какую-либо сущность языка. В нашем случае это сложение, вычитание, … (не путать с соответ. лексемой).
• Правил — это объект из двух частей, левой и правой. В частях могут содержаться терминалы и нетерминалы.
• Начальное правило.

Так в нашем случае будут следующие нетерминалы:

• CValue — Число либо скобочное выражение
• SummaValue — Сложение чисел
• MultipleValue — Умножение чисел.

По формальной грамматике строиться в дальнейшем код программы.
Формальная грамматика может быть представлена нескольких формах:

Текстовая форма грамматики

1. SummaValue → MultipleValue SummaOperatorToken SummaValue
2. SummaValue → MultipleValue
3. MultipleValue → CValue MultipleOperatorToken SummaValue
4. MultipleValue → CValue
5. CValue → NumberToken
6. CValue → OpenBraceToken SummaValue CloseBraceToken
7. CValue → SummaOperatorToken NumberToken

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

Нотация Бэкуса — Наура


<SummaValue> ::= <MultipleValue> { SummaOperatorToken <SummaValue> }
<MultipleValue> ::= <CValue> { MultipleOperatorToken <SummaValue> }
<CValue> ::= NumberToken
| OpenBraceToken <SummaValue> CloseBraceToken
| SummaOperatorToken NumberToken


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

Графическая форма грамматики

Код синтаксического анализатора

Будем использовать формальную грамматику как средство для написание кода синтаксического анализатора.
Повторюсь что задача синтаксического анализа — «процесс сопоставления линейной последовательности лексем языка с его формальной грамматикой». Описание грамматики мы рассмотрели.
Синтаксический анализатор представим как такую функцию:


/**
* Анализирует список лексем начиная с указанного индекса (0 - начало),
* и если входная последовательность лексем совпадает, то возвращает результат
* @param beginIndex Индекс лексемы с которой начать анализ
* @param tokens Список лексем
* @return Результат анализа либо null, если входная последовательность лексем не удовлетворяет правилу.
*/
public abstract Result parse(int beginIndex, List<Token> tokens);


Так рассмотрим правило CValue


<CValue> ::= NumberToken
| OpenBraceToken <SummaValue> CloseBraceToken
| SummaOperatorToken NumberToken


Оно состоит из трех вариантов, каждый из которых начинается с терминала и второе правило содержит один нетерминал.
Код в данном случае этого анализатора будет такой (псевдокод):

CValue( beginIndex, tokens ){
// Сопоставление лексем согласно первому варианту
if ( matched( beginIndex, tokens, NumberToken ) ){
…
// Вычисления
return результат
} else
// Сопоставление лексем согласно второму варианту
if ( matched( beginIndex, tokens, OpenBraceToken, SummaValue, CloseBraceToken ) ){
…
// Вычисления
return результат
} else
// Сопоставление лексем согласно третьему варианту
if ( matched( beginIndex, tokens, SummaOperatorToken, NumberToken ) ){
…
// Вычисления
return результат
}
return Ошибка
}


В данном коде присутствует функция matched, ее задача сопоставить лексемы согласно переданным параметрам, где параметры могут быть двух типов: терминал (лексема) и нетерминал (функция Result parse(int beginIndex, List<Token> tokens) — функция синтаксического анализатора). А результат — это массив распознанных терминалы/нетерминалы.

Код функции matched таков:


/**
* Сравнивает последовательность лексем с шаблоном.<br/>
* Шаблоном состоит из массива экземпляров SyntaxParser, либо классов лексем (NumberToken.class, и др.).
* Результатом анализа является:
* <ul>
* <li>Для классы лексемы - ее объект</li>
* <li>Для SyntaxParser - результат вызова метода parse соответствующего объекта</li>
* </ul>
* Кол-во объектов и их последовательность в массиве результата, соответствует шаблону
* @param beginIndex Индекс лексемы с которой начать анализ
* @param tokens Список лексем
* @param pattern Шаблон
* @return Результат анализа либо null, если входная последовательность лексем не удовлетворяет шаблону.
*/
public Result[] match(int beginIndex, List<Token> tokens, Object ... pattern )
{
if( beginIndex<0 )return null;
if( tokens==null )return null;
if( beginIndex>=tokens.size() )return null;

int tokIdx = beginIndex;

// Результат будет здесь
Result[] result = new Result[pattern.length];
int resIdx = 0;

// Последовательно берем элементы шаблона
for( Object p : pattern ){
// Это терминал (лексема) ?
if( p instanceof Class ){
if( tokIdx>=tokens.size() )return null;
Token tok = tokens.get(tokIdx);

// Лексема соответствует ожидаемой ?
if( ((Class)p).isAssignableFrom(tok.getClass()) ){
result[resIdx] = new Result(tok, tokIdx+1);
resIdx++;
tokIdx++; // переходим к следующей лексеме
}else{
return null;
}
// Это нетерминал ?
}else if( p instanceof SyntaxParser ){
// Анализируем последовательность согласно нетерминалу
Result r = ((SyntaxParser)p).parse(tokIdx, tokens);

// Последовательность лексем соответствует нетерминалу ?
if( r!=null ){
tokIdx = r.getNext(); // переходим к концу где остановился нетерминал
result[resIdx] = r;
resIdx++;
}else{
return null;
}
}else{
return null;
}
}
return result;
}

Так будет выглядеть фрагмент кода анализа CValue для выражения OpenBraceToken <SummaValue> CloseBraceToken.


...
Result[] r2 = match(
beginIndex, tokens,
OpenBraceToken.class, SummaValue.instance, CloseBraceToken.class );

if( r2!=null ){
CValue cv = new CValue();
cv.inBraceValue = (Value)r2[1].getResult();
return new Result(cv, r2[2].getNext());
}
...


Все нетерминалы будут дочерними классами класса SyntaxParser. Код класса SyntaxParser будет примерно следующим:


/**
* Синтаксический анализатор (Синтаксический парсер)
*/
public abstract class SyntaxParser
{
/**
* Результат синтаксического анализа
*/
public static class Result
{
private int next = -1;
private Object result = null;

/**
* Конструктор
* @param result Результат анализа - вычисленное значение
* @param next Индекс следующей лексемы, после результата
*/
public Result(Object result,int next)
{
this.result = result;
this.next = next;
}

/**
* Возвращает индекс следующей лексемы, после результата
* @return Индекс следующей лексемы
*/
public int getNext()
{
return next;
}

/**
* Возвращает результат анализа - вычисленное значение
* @return Результат анализа - вычисленное значение
*/
public Object getResult()
{
return result;
}
}

/**
* Анализирует список лексем начиная с указанного индекса (0 - начало),
* и если входная последовательность лексем совпадает, то возвращает результат
* @param beginIndex Индекс лексемы с которой началь анализ
* @param tokens Список лексем
* @return Результат анализа либо null, если входная последовательность лексем не удолетворяет правилу.
*/
public abstract Result parse(int beginIndex, List<Token> tokens);

/**
* Сравнивает последовательность лексем с шаблоном.<br/>
* Шаблоном состоит из массива экземпляров SyntaxParser, либо классов лексем (NumberToken.class, и др.).
* Результатом анализа является:
* <ul>
* <li>Для классы лексемы - ее объект</li>
* <li>Для SyntaxParser - результат вызова метода parse соответствующего объекта</li>
* </ul>
* Кол-во объектов и их последовательность в массиве результата, соответствует шаблону
* @param beginIndex Индекс лексемы с которой началь анализ
* @param tokens Список лексем
* @param pattern Шаблон
* @return Результат анализа либо null, если входная последовательность лексем не удолетворяет шаблону.
*/
public Result[] match(int beginIndex, List<Token> tokens, Object ... pattern )
...
}