Анализ выражений в JavaScript

Подробный анализ утверждений и выражений (и различий между ними)

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

• Нить
• Число
• Логическое значение (истина или ложь)
• Объект

Оператор - это инструкция, которую может выполнить интерпретатор. У нас есть:

• while заявления
• Операторы for loop
• операторы присваивания
• операторы объявления переменных
• Операторы if
• так далее

Небольшой совет, прежде чем мы продолжим: используйте Bit, чтобы легко делиться, повторно использовать и совместно работать над компонентами кода.
Bit дает вам возможность кодировать быстрее и лучше как в одиночку, так и в команде.

Выражения необходимо оценивать, чтобы получить значение.

1 + 4

Вышеупомянутое выражение, которое при вычислении даст 5

2 < 4

Вышеупомянутое также является выражением, которое при вычислении даст:

true

Итак, выражение - это комбинация значений. переменные, операторы и вызовы функций.

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

См. Общую структуру оператора if:

if(cond expression) {
    // ...
    // body
}

Тело оператора if будет выполнено, если cond expression в квадратных скобках оценивается как true.

Автономное значение - это выражение:

1
23
445
'nnamdi'
true

Они называются первичными выражениями. При оценке они вернут свое значение, которое есть само. Выражения появляются в правой части оператора присваивания.

b = 78 * 56
a = 98 * 67 + 454 - 909

Вышеупомянутые операторы присваивания. Присваивания - это утверждения, потому что они не производят ценности. Выполнение вышеуказанного в интерпретаторе приведет к следующему:

>> b = 78 * 56
>> a = 98 * 67 + 454 - 909

Значение не печатается, но когда мы запускаем переменные a и b:

>> b = 78 * 56
>> a = 98 * 67 + 454 - 909
>> b
4368
>> a
6111

Их значения печатаются, потому что есть первичные выражения. Оператор присваивания не напечатал никакого значения, потому что это оператор, и только его выполнение не оценивается.

Что-то выполняется для выполнения действия, но что-то оценивается для получения ответа. Вот почему в нашей школе на уроках математики говорят, что нужно вычислять это квадратное уравнение.

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

Как будто мы собираемся создать экземпляр нашего оценщика следующим образом:

const str = `
    5+9
    3 + 3
    2 + 2 + 2;
    22*9 - 2*90
    66>=90
    90>1
    88==7
    3*250*360
    (45*89)+90
    4-5+6
    4-(5+6)
`
const asts = Parser.getInst().parse(str)
new Evaluator(asts).evaluate()

И ответы будут напечатаны на нашем терминале:

$ node .
======================== RESULTS ========================
14
6
6
-3762
false
true
false
270000
4095
-7
-7

Запуск…

Во-первых, нам нужно создать наш проект, потому что вы будете печатать вместе со мной.

mkdir expr_parser
cd expr_parser

Инициализируйте среду узла:

npm init -y

Сканирование и токенизация

Прежде всего, нам нужно разметить наше выражение. Токенизация означает разбиение нашего выражения на отдельные части.

Пример:

2 + 45 - 90

Вышеупомянутое выражение можно разбить на токены

[
    {
        value: '2',
        type: Number
    },
    {
        value: '+',
        type: AddOp
    },
    {
        value: '45',
        type: Number
    },
    {
        value: '-',
        type: SubOp
    },
    {
        value: '90',
        type: Number
    }
]

Токенизация означает разбиение, чтобы сообщить парсеру, что представляет собой каждая единица. В нашем 2 + 45 - 90 выражении у нас есть 5 единиц или жетонов:

+---+ +---+ +----+ +---+ +----+
| 2 | | + | | 45 | | - | | 90 |
+---+ +---+ +----+ +---+ +----+

У нас есть это в массиве выше, каждый из токенов имеет свойство, свое значение и тип данных, которые они представляют или представляют. Первый - это число, затем второй - + оператор AddOp, третий токен - это Number, четвертый токен - это оператор вычитания, ему назначается SubOp, а последний токен - это Number.

Если у нас есть такое выражение:

90 * (78 - 65) / 90

Токенизация даст нам:

+----+ +---+ +---+ +----+ +---+ +----+ +---+ +---+ +----+
| 90 | | * | | ( | | 78 | | - | | 65 | | ) | | / | | 90 |
+----+ +---+ +---+ +----+ +---+ +----+ +---+ +---+ +----+

Представление вышеперечисленного в объекте будет выглядеть так:

[
    {
        value: '90',
        type: Number
    },
    {
        value: '*',
        type: MulOp
    },
    {
        value: '(',
        type: LParen
    },
    {
        value: '78',
        type: Number
    },
    {
        value: '-',
        type: SubOp
    },
    {
        value: '65',
        type: Number
    },
    {
        value: ')',
        type: RParen
    },
    {
        value: '/',
        type: DivOp
    },
    {
        value: '90',
        type: Number
    }
]

Эти токены сообщают нам, что представляет каждая единица выражения, будь то число, оператор деления, оператор вычитания и т. Д.

Теперь давайте создадим класс Token. Класс Token будет иметь конструктор, который будет принимать строку, которую мы хотим токенизировать, также класс Token будет иметь метод tokenize при вызове, который будет анализировать строку и создавать токены из строки.

При синтаксическом анализе строки токенизатор должен определить, когда он попадает в разумный токен. Например, у нас есть такое выражение 34+4.

3 вне выражения имеет смысл 34 имеет смысл 34+ не имеет смысла, указанные выше токены являются числами, но у нас нет ничего для этого. Таким образом, мы должны знать, когда попадаем в разумный жетон, и отбрасывать остальные.

Token.js

// token.js
const { isNum, isOp } = require('./util')
class Token {
    constructor() {
        this.inst = null
        this.tokens = []
    }
    static getInst() {
        if (!this.inst)
            this.inst = new Token()
        return this.inst
    }
    tokenize(str) {
        str = str.trim()
        var s = ''
        for (var index = 0; index < str.length; index++) {
            s += str[index];
            const peek = str[index + 1]
            if (isNum(s.trim()) && !isNum(peek)) {
                this.tokens.push({ type: 'NUM', value: s.trim() })
                s = ''
            }
            if (s.trim() == '(' || s.trim() == ')') {
                s.trim() == '(' ? this.tokens.push({ type: 'LPAREN' }) : this.tokens.push({ type: 'RPAREN' })
                s = ''
            }
            if (isOp(s.trim()) && !isOp(peek)) {
                this.tokens.push({ type: 'OP', value: s.trim() })
                s = ''
            }
            if (s == ';' || s == '\n') {
                this.tokens.push({ type: 'EOL' })
                s = ''
            }
            if (index == (str.length - 1)) {
                this.tokens.push({ type: 'EOF' })
                s = ''
            }
        }
        return this.tokens
    }
}
exports.Token = Token

Посмотрите, как в методе tokenize мы сначала обрезаем строку, чтобы удалить лишние пробелы. затем мы перебираем строку, используя оператор for.

У нас есть это правило, чтобы знать, что мы ищем, сначала мы встретим только

• Числа.
• Операторы.
• и Левый Парен ( и Правый Парен ).

Мы объединяем каждое значение текущего индекса с переменной s, поэтому для каждого цикла мы заглядываем в будущее и сохраняем значение в переменной peek, затем мы проверяем, является ли агрегированная строка в s числом, а следующее значение в массиве - не число, если проверка прошла, значит, мы собрали целое число.

На примере:

345+90

В первом цикле будет 3 в переменной s, число не будет выполнено, потому что peek будет 4, поэтому во втором цикле s будет 34, проверка числа не будет выполнена, потому что значение peek является числом 5. В третьем цикле s будет b 345, и число будет передано, потому что значение peek не является числом +. Теперь мы собрали число 345, теперь мы помещаем его в массив tokens с типом NUM:

[
    {
        type: 'NUM',
        value: '345'
    }
]

Посмотрите, что в методе tokenize у нас есть проверки для Number, LParen и RParen, и проверки операторов, они позволяют нам узнать, когда мы объединили Number, operator или L / RParen.

Поскольку мы нажимаем Number, объединенная строка на s будет удалена в пустую строку, чтобы начать заново.

Затем в четвертом цикле s будет +, переменная peek будет 9. Проверка числа завершится ошибкой, L / RParen завершится ошибкой, проверка оператора пройдет, потому что текущее значение + является оператором, а значение peek 9 является числом, а не оператором, поэтому объект будет помещен в массив tokens.

[
    {
        type: 'NUM',
        value: '345'
    },
    {
        type: 'OP',
        value: '+'
    }
]

Удаляем значение s и даем пустую строку. В пятом цикле s будет 9, а значение peek будет 0. s - это число, а следующая величина peek также является числом, поэтому никакая проверка не проходит, особенно проверка числа. Шестой цикл будет иметь s = 90, а значение peek будет иметь null. Проверка числа будет пройдена, потому что s ('90') - это число, а значение peek не является числом, поэтому у него есть полный и разумный токен, он помещает его в массив tokens:

[
    {
        type: 'NUM',
        value: '345'
    },
    {
        type: 'OP',
        value: '+'
    },
    {
        type: 'NUM',
        value: '90'
    }
]

Теперь наш цикл for завершается. Теперь у нас есть вышеуказанные жетоны. Из переданной строки наш класс Token смог проанализировать строку и распознать числа и операторы, выдернуть их из строки и сгруппировать в последовательности, которые что-то представляют.

Для меня возможность создавать токенизаторы - это половина работы при создании интерпретаторов, компиляторов или оценщиков. Отсюда мы можем делать с ними все, что захотим.

Давайте протестируем наш Token класс:

// i.js
const tokenizer = Token.getInst()
const tokens = tokenizer.tokenize('234+90')
console.log(tokens)

Выход:

$ node token
[ { type: 'NUM', value: '234' },
  { type: 'OP', value: '+' },
  { type: 'NUM', value: '90' },
  { type: 'EOF' } ]

Две вещи, которые мы не затронули, - это вызовы функций isNum и isOp. isNum ожидает, что значение определяет, является ли параметр числом:

// util.js
function isNum(v) {
    return !isNaN(parseFloat(v)) && isFinite(v)
}

isOp проверяет, является ли переданный аргумент оператором. У нас есть разные операторы '+ = - * /', поэтому функция проверяет, является ли аргумент одним из них:

// util.js
const operators = ['=', '+', '-', '*', '/', '>', '<', '>=', '<=', '==', '!=']
function isOp(v) {
    for (var i = 0; i < operators.length; i++) {
        if (operators[i] == v) return true
    }
    return false
}

Грамматика

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

Мы преобразовали строку в серию токенов, мы можем посмотреть на выражение:

345+90

и решаем это с помощью нашего мозга, сначала мы берем +, мы знаем, что это операция сложения, берем левое значение 345, а затем правое значение 90, затем складываем их вместе.

Решение более сложной арифметики:

345+90-88

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

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

345+90
    [+]
    /\
   /  \
  /    \
[345] [90]
345+90-88

становится

            [+]
            /\
           /  \
         [-]  [90]
         / \
        /   \
       /     \
      [345] [90]

Чтобы сгенерировать вышеуказанный

Чтобы интерпретировать выражение и построить дерево выражений из токенов, нам понадобится набор правил. Как будто нам нужно знать, какую операцию выполнить перед другой: приоритет и ассоциативность. Такие языки, как английский, следуют правилу грамматики. Грамматика выводит или дает правило, которому нужно следовать при построении предложения. Если предложение следует правилу грамматики, оно называется хорошим предложением, если нет - плохим предложением, а при разговоре становится плохим английским.

Предложение на английском языке состоит из подлежащего и сказуемого.

Nkechi has a ball

разбивая это, мы имеем:

Nkechi           has a ball
|__Subject____| |_Predicate____|

Подлежащее может быть существительным. Предикат - это комбинация Глагола и Объекта.

Nkechi           has a ball
    |__Subject____| |_Predicate____|
                /       \
               /         \
              /           \
          [Noun]      [Verb] [Object]
           /            /      \
          /            /        \
     Nkechi          has a     ball

Посмотри на дерево. Мы можем

sentence → Subject Predicate
Subject → Noun
Predicate → Verb Object
Object → Noun Opt_Participle
Opt_Participle → participle
Noun → Nkechi Ball
Participle → Run
Verb → Has a

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

expression → literal
                | binary
                | grouping ;
literal → NUMBER;
grouping → "(" expression ")" ;
binary → expression operator expression ;
operator → "==" | "!=" | "<" | "<=" | ">" | ">="
| "+" | "-" | "*" | "/" ;

AST

AST - это аббревиатура от Abstract Syntax Tree, это структурное представление анализируемого предложения или выражения. AST представляет предложение или выражение в иерархическом порядке.

Дерево синтаксического анализа для A + B * C - D

       [ * ]
        / \
       /   \
     [ + ]   [ - ]
      /\       /\
     /  \     /  \
   [A]  [B]  [C] [D]

Оценка начинается снизу вверх. Например

345+90-88

становится

           [ - ]
            /\
           /  \
         [+]  [88]
         / \
        /   \
       /     \
      [345] [90]

[-] лист оценивается, у нас есть дерево:

           [ - ]
            /\
           /  \
         [255]  [88]

[+] Оценивается:

[343]

У нас есть ответ !!.

Но мы не получили ответа. При оценке математического выражения мы следуем правилу приоритета и ассоциативности. В моей школе правила давались в простой форме:

BODMAS

B → Кронштейн

O → Of

D → Дивизия

M → Умножение

A → Дополнение

S → Вычитание

Это означает, что всякий раз, когда мы видим комбинацию любого из них, оценивается первое в BODMAS, затем второе, третье,… и последнее.

Итак, в этом выражении:

345-90+88
        [ + ]
          /\
         /  \
        /    \
      [ - ] [ 88 ]
       /\       
      /  \        
     /    \        
 [ 345 ] [ 90 ]

Мы могли бы начать с RHS и оценить до LHS.

         [ + ]
          /\
         /  \
        /    \
      [ - ] [ 88 ]
       /\       
      /  \        
     /    \        
 [ 345 ] [ 90 ]
          |
          |
          v
        [ + ]
          /\
         /  \
        /    \
    [ 255 ] [ 88 ]
            |
            |
            v
        [ 343 ]
345-90+88 = 255+88 = 343

Это неправильный ответ, потому что + имеет приоритет над -. Проверьте BODMAS, сложение предшествует вычитанию. Итак, мы должны сначала оценить 345-90+88.

345-90+88 = 345-178 = 167 

Там!! у нас есть правильный ответ.

Итак, представление дерева должно измениться на это:

        [ - ]
          /\
         /  \
        /    \
    [ 345 ]  [ + ] 
              /\       
             /  \        
            /    \        
        [ 88 ] [ 90 ]
            |
            |
            v
        [ - ]
          /\
         /  \
        /    \
    [ 345 ] [ 178 ] 
            |
            |
            v
        [ 167 ]

Рекурсивный спуск

Это один из наиболее широко используемых методов синтаксического анализа, он начинается с верхнего или самого внешнего правила грамматики (здесь выражение) и продвигается вниз во вложенные подвыражения, прежде чем, наконец, достигнет листьев синтаксического дерева.

Используя синтаксический анализ с рекурсивным спуском, правила грамматики превращаются в функции. Следуя правилу BODMAS, мы видим, что операция с высоким приоритетом находится внизу AST. Таким образом, при рекурсивном синтаксическом анализе наших токенов мы спустимся в глубину в порядке старшинства.

Наш синтаксический анализатор будет реализован с использованием алгоритма синтаксического анализа RD, чтобы он мог перемещаться по токенам и генерировать AST в соответствии с порядком приоритета.

Давайте представим наши правила в классах:

// ast.js
class Binary {
    constructor(left, operator, right) {
        this.left = left
        this.right = right
        this.operator = operator
    }
}
class Literal {
    constructor(value) {
        this.value = value
    }
}
class Grouping {
    constructor(expr) {
        this.expr = expr
    }
}

Давайте посмотрим на наше правило выражения:

expression → addition;
addition → subtraction(("+") subtraction)*;
subtraction → multiplication(("-") multiplication)*;
multiplication → "*" | primary;
primary → NUMBER | STRING | "false" | "true";

Смотрите, что операции основаны на приоритете.

Следуя нашему правилу приоритета грамматики, мы реализуем наш Parser:

// parser.js
/**
 * Using Recursive Descent algorithm
 * 
 */
class Parser {
    constructor() {
        this.inst
        this.index = 0
        this.tokens = null
        this.expr = []
    }
    static getInst() {
        if (!this.inst)
            this.inst = new Parser()
        return this.inst
    }
    advance() {
        this.index++
    }
    peep() { return this.tokens(this.index + 1) }
    current() { return this.tokens[this.index] }
    parse(str) {
        const tokenizer = Token.getInst()
        const tokens = tokenizer.tokenize(str)
        this.tokens = tokens
        while (this.current().type != 'EOF') {
            const expr = this.add()
            if (expr)
                this.expr.push(expr)
        }
        return this.expr
    }
    add() {
        const left = this.sub()
        if (this.current().value == '+') {
            this.advance()
            return new Binary(left, 'ADD', this.sub())
        }
        return left
    }
    sub() {
        const left = this.mul()
        if (this.current().value == '-') {
            this.advance()
            return new Binary(left, 'SUB', this.mul())
        }
        return left
    }
    mul() {
        const left = this.primary()
        if (this.current().value == '*') {
            this.advance()
            return new Binary(left, 'MUL', this.all())
        }
        return left
    }
    primary() {
        const curr = this.current()
        this.advance()
        if (curr.type == 'NUM')
            return new Literal(curr.value)
        if (curr.type == 'LPAREN') {
            const expr = this.add()
            this.advance()
            return new Grouping(expr)
        }
    }
}

Смотрите, они следуют правилу приоритета, вызывается метод добавления, внутри метода добавления операция с более низким приоритетом называется sub(...), то, что возвращается, сохраняется в переменной left, если текущее значение является оператором +, создается новый двоичный объект . То же самое происходит и по цепочке приоритетов.

Итак, для этого:

56 - 89 * 78
        [-]
        /\
       /  \
    [*]   [56]
    /\
   /  \
[89] [78]

Ниже генерируется:

Binary {
    type: '-',
    left: 56,
    right: Binary {
        type: '*',
        left: 89,
        right: 78
    }
}
78 * 89 - 56
Binary {
    type: '-',
    left: 78,
    right: Binary {
        type: '*',
        left: 89,
        right: 56
    }
}

Оценка

Мы сгенерировали AST в предыдущем разделе, теперь нам нужно оценить AST. Чтобы оценить AST, мы будем использовать шаблон Visitor.

Шаблон посетителя помогает нам отделить алгоритм от группы объектов, реализующих алгоритм в классе.

Для каждого класса AST нам нужно предоставить им единственный метод visit, метод примет экземпляр класса посетителя в качестве параметра, в теле метода visit мы вызовем соответствующий алгоритм для AST:

// ast.js
class Binary {
    constructor(left, operator, right) {
        this.left = left
        this.right = right
        this.operator = operator
    }
    visit(visitor) {
        return visitor.visitBinary(this)
    }
}
class Literal {
    constructor(value) {
        this.value = value
    }
    visit(visitor) {
        return visitor.visitLiteral(this)
    }
}
class Grouping {
    constructor(expr) {
        this.expr = expr
    }
    visit(visitor) {
        return visitor.visitGrouping(this)
    }
}

Мы видели классы раньше, но теперь с методом visit. Посмотрите, что класс Literal в своем visit методе вызывает visiLiteral метод visitor, передавая себя ему, это называется двойной отправкой. visitLiteral реализован в классе visitor, именно здесь написан алгоритм оценки Literals. То же самое с Binary, Grouping.

Затем мы создаем класс Visitor и добавляем его реализации:

// visitor.js
/**
 *  Binary Expressions
 *  *,/,-,+
 */

class Visitor {
    visitBinary(ctx) {
        const type = ctx.operator
        switch (type) {
            case 'ADD':
                return ctx.left.visit(this) + ctx.right.visit(this)
            case 'SUB':
                return ctx.left.visit(this) - ctx.right.visit(this)
            case 'MUL':
                return ctx.left.visit(this) * ctx.right.visit(this)
        }
    }
    visitLiteral(ctx) {
        return Number(ctx.value)
    }
    visitGrouping(expr) {
        const e = expr.expr
        return e.visit(this)
    }
    visitExpressions(expressions) {
        for (const expr of expressions) {
            log(expr.visit(this))
        }
    }
}

Давайте создадим класс Evaluator:

// evaluator.js
class Evaluator {
    constructor(asts) {
        this.asts = asts
        this.visitor = new Visitor()
    }
    evaluate() {
        log('======================== RESULTS ========================')
        this.visitor.visitExpressions(this.asts)
    }
}

Требуется массив AST, сгенерированный парсером. Создает экземпляр класса Visitor. Метод evaluate вызывает метод visitExpressions класса посетителя, передавая массив AST. visitExpresssions, как мы видели в классе Visitor, перебирает выражения в массиве и оценивает их.

Заключение

Чтобы создать простейший синтаксический анализатор выражения, требуется много кода. В процессе создания простого синтаксического анализатора выражений, который оценивает только +, - и *, мы многому научились. Отметим их галочкой:

• Токенизация
• Грамматика
• Ассоциативность и приоритет
• AST
• Шаблон посетителя

Чтобы узнать больше, я призываю вас расширить это, ссылка на GitHub этого проекта находится в разделе ниже, не стесняйтесь присылать свой PR.

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

Если у вас есть какие-либо вопросы относительно этого или чего-либо, что я должен добавить, исправить или удалить, не стесняйтесь комментировать, напишите мне или напишите мне

Спасибо !!!

Полный код

Учить больше