Интерпретатор выражений за 15 минут

Насколько сложно написать свой интерпретатор языка? Как оказалось это довольно простая задача, особенно, если описание языка уже составлено. И сейчас вы в этом убедитесь. Интерпретатор для Just Do It! я написал, примерно, за два часа, причем час этого времени я потратил на то, чтобы вспомнить, как реализуется метод рекурсивного спуска.

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

Минимально из чего может состоять выражение — это число или переменная. Назовём этот символ VALUE.

VALUE => NUMBER | VARIABLE
NUMBER => DIGIT +
VARIABLE => ( ALPHA | '_' ) ( ALPHA | DIGIT | '_' ) *
ALPHA => 'a' - 'z'
DIGIT => '0' - '9'

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

На javascript это будет выглядеть примерно так (некоторые функции я не определяю, их название отражает функционал):

function value() {
    skipSpaces(); // пропускаем пробельные символы, функцию 
                  // можно и не использовать, если в нашем языке 
                  // не предусмотрены пробелы между символами
    var char = currentChar(); // получаем текущий символ потока
    if (isNumber(char)) { // проверяем является ли символ числом
        return ['number', getNumber()];
    }
    if (isAlpha(char)) { // проверяем является ли символ буквой или символом подчеркивания
        return ['variable', this.getVariable()];
    }
    throw 'value expected';
}
function isNumber(s) {
    var c = s.charCodeAt(0);
    return c >= 48 && c <= 57; // коды символов '0' - '9'
}
function isAlpha(s) {
    var c = s.charCodeAt(0);
    return c >= 97 && c <= 122 || s == '_'; // коды символов 'a'-'z' и символ подчеркивания
}
function getNumber() {	
    var num = '';
    var char = currentChar();
    while (isNumber(char)) {
        num += char;
        char = nextChar(); // следующий символ из потока
    }
    return parseInt(num);
}
function getVariable() {	
    var variable = '';
    var char = currentChar();
    if (isAlpha(char)) {
        variable += char;
        char = nextChar();
        while (isAlpha(char) || isNumber(char))) {
            variable += char;
            char = nextChar();
        }
    }
    return variable;
}

Мы научили интерпретатор считывать значения из потока (исходной строки). Теперь приступим к операндам.

EXPR1 => EXPR2 [ OPERAND2 EXPR1 ]
EXPR2 => EXPR3 [ OPERAND1 EXPR2 ]
EXPR3 => BRACKETS | VALUE | OPERAND1 EXPR3
OPERAND1 => '-'
OPERAND2 => '*' | '/'
OPERAND3 => '+' | '-'
BRACKETS => '(' EXPR1 ')'

Здесь немного поясню:

  • EXPR1 — выражение 1-го уровня (операция сложения или вычитания);
  • EXPR2 — выражение 2-го уровня (операция умножения или деления);
  • EXPR3 — выражение 3-го уровня (выражение в скобках, значение или отрицание);
  • BRACKETS — выражение в скобках;
  • OPERAND1 — операнд 1-го приоритета (знак отрицания);
  • OPERAND2 — операнд 2-го приоритета (умножение и деление);
  • OPERAND3 — операнд 3-го приоритета (сложение и вычитание);

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

function expr1() {
    skipSpaces();
    var left_operand = expr2();
    skipSpaces();
    if (endOfStream()) {  // конец выражения
        return left_operand;
    }
    var char = currentChar();
    nextChar();
    if ('+' == char) {
        return ['+', left_operand, expr1()];
    }
    if ('-' == char) {
        return ['-', left_operand, expr1()];
    }
    throw 'unexpected symbol `' + char + '`, `+` or `-` expected';
}
function expr2() {
    skipSpaces();
    var left_operand = expr3();
    skipSpaces();
    if (endOfStream()) {  // конец выражения
        return left_operand;
    }
    var char = currentChar();
    nextChar();
    if ('*' == char) {
        return ['*', left_operand, expr2()];
    }
    if ('/' == char) {
        return ['/', left_operand, expr2()];
    }
    throw 'unexpected symbol `' + char + '`, `*` or `/` expected';
}
function expr3() {
    skipSpaces();
    var char = currentChar();
    if ('(' == char) {
        nextChar();
        var expr = ['()', expr1()];
        expect(')'); // ожидаем, что следующий символ будет ')', 
                     // иначе бросаем исключение
        return expr;
    }
    if ('-' == char) {
        nextChar();
        return ['neg', expr3()];
    }
    return value();
}

Что-то в этом вроде...

Это конечно же нерабочий код (по крайней мере, в таком виде), но он демонстрирует подход к реализации метода рекурсивного спуска. Обработка начинается с вызова функции expr1(), которая вернет выражение, представленное в виде дерева. Вычислить выражение можно с помощью такой функции:

function evaluate(expr) {
    switch (expr[0]) {
        case 'number': return expr[1];
        case 'variable': return variables[expr[1]] || 0;
        case 'neg': return -evaluate(expr[1]);
        case '*': return evaluate(expr[1]) * evaluate(expr[2]);
        case '/': return evaluate(expr[1]) / evaluate(expr[2]);
        case '+': return evaluate(expr[1]) + evaluate(expr[2]);
        case '-': return evaluate(expr[1]) - evaluate(expr[2]);
        case '()': return evaluate(expr[1]);
    }
    throw 'unknow operand `' + expr[0] + '`';
}

Таким же способом можно создать компилятор для любого языка. Например, впервые я использовал этот метод для написания интерпретатора языка «T-Script» для дипломной работы несколько лет назад. Язык состоял из кириллических управляющих конструкций, поддерживал классы, исключения, определение типов, перегрузку функций (как вспомню, аж страшно), подключение кода из DLL (да, тогда я сидел на винде) и много других вещей. Так что если вы хотите встроить куда-нибудь простенький интерпретатор сценариев — вперед, в этом нет ничего сложного.