предисловие
При создании системы мониторинга Node нам нужно сделать оповещение по электронной почте. В настоящее время нам нужно настроить набор правил, чтобы написать выражение, которое вызывает оповещение. В этой статье будет рассказано, как написать простой анализатор выражений. Прилагается скриншот интерфейса, который является примером выражения.
Справочник: "Шаблоны реализации языков программирования"
Определите некоторые основные правила
Прежде чем вы начнете писать, вам нужно определить, какими возможностями должно обладать ваше выражение. Выражение в этой статье является условием для определения того, сработала ли тревога, и правила выражения не должны быть слишком сложными. В то же время, поскольку пользователи, которые пишут выражения, являются фронтенд-разработчиками или разработчиками узлов, наиболее подходящим является синтаксис, близкий к синтаксису js-выражений:
- Поддержка переменных, здесь указано, что переменные начинаются с @ и состоят из букв и цифр, например: @load15
- Константы поддержки: логические, числовые, строковые
- Поддержка операций сложения (+), вычитания (-), умножения (*), деления (/), остатка (%)
- Поддерживает операции сравнения, такие как равно (===), неравенство (!==), больше (>), меньше (=), меньше или равно (
- Поддерживает логические операции, такие как И (&&), ИЛИ (||), НЕ (!)
- Расширенная строка содержит операцию включения
- Опорные кронштейны ()
Построение абстрактного синтаксического дерева (AST)
Целью построения абстрактного синтаксического дерева является разработка структуры данных для описания значения выражения. Например@var > 5, в коде используется как строка, и не указано, как выполнять операцию.
Если разобрать в следующее абстрактное синтаксическое дерево:
Корневой узел — это оператор, а дочерние узлы — это операнды, поэтому мы абстрагируем операцию с помощью бинарного дерева.
Конечно, приведенный выше пример представляет собой относительно простое выражение операции. Как только выражение становится сложным, невозможно избежать приоритета операции. Как двоичное дерево представляет приоритет операции?
Проиллюстрируем двумя выражениями:
Как видно из рисунка, добавление круглых скобок ко второму выражению изменяет исходный порядок операций, а также меняется соответствующее абстрактное синтаксическое дерево.Нетрудно заметить, что:Чем выше приоритет операции, тем ниже позиция в синтаксическом дереве.
Например, структура данных AST, такая как следующее выражение
@load > 1 + 5
Анализируемый токен:
{
"type": "LOGICAL_EXP",
"operator": ">",
"left": {
"type": "VARIABLE",
"value": "load",
"raw": "@load"
},
"right": {
"type": "BINARY_EXP",
"operator": "+",
"left": {
"type": "NUMBER",
"value": 1,
"raw": "1"
},
"right": {
"type": "NUMBER",
"value": 5,
"raw": "5"
}
}
}
Определив структуру абстрактного синтаксического дерева, мы можем начать думать о том, как разобрать строку выражения.
Использование лексического анализатора рекурсивного спуска LL(1)
Токенизация относится к грамматике символов, аналогично тому, как мы используем буквы для написания слова с определенной грамматикой.
Лексический синтаксический анализатор LL(1) с рекурсивным спуском — это нисходящий синтаксический анализатор, который просматривает одну лексическую единицу вперед. анализируется в порядке «вправо», а второй L указывает, что нисходящий анализ также проходит по дочерним узлам слева направо.
Это самый простой парсер, и его легче понять, используя этот режим, если он может удовлетворить ваши потребности.
список лексических единиц
Так как мы хотим ожидать лексическую единицу, мы должны сначала перечислить лексические единицы, которые может иметь это выражение.Выражение в этой статье может иметь следующие лексические единицы:
- Переменная лексическая единица, флаги: начинаются с "@"
- Числовая лексическая единица, флаг: начинаться с 0-9 или "."
- Строковая лексическая единица, флаги: начинаться с одинарных или двойных кавычек
- Жетон скобки, флаг: начните с открывающей скобки
- Токен унарного оператора, флаги: начинать с "!", "+", "-"
Теперь мы можем официально начать писать код.
найти точку рекурсии
Выражение можно разложить на несколько выражений без круглых скобок, например следующие выражения:
5 * (3 + 2 * (5 + 6))
Мы можем разложить его на следующие выражения:
5 * expression_a
3 + 2 * expression_b // expression_a
5 + 6 // expression_b
Вся строка представляет собой выражение, которое является точкой рекурсии, которую мы ищем.Определите функцию eatExpression для разбора выражения и рекурсивное действие eatExpression при встрече со скобками до тех пор, пока не будет найдена ни одна лексическая единица.
Давайте начнем кодировать.
class ExpressionParser
class ExpressionParser {
constructor(expr) {
if (typeof expr !== 'string') {
throw new Error(`[expression-parser] constructor need a string parameter, but get [${typeof expr}]`);
}
this.expr = expr;
this.parse();
}
parse() {
this.index = 0;
this.tokens = this.eatExpression();
if (this.index < this.expr.length) {
this.throwError(`非法字符"${this.charAt()}"`);
}
}
}
const expression
const parser = new ExpressionParser(expression)
Это класс синтаксического анализатора. Первоначальная работа состоит в том, чтобы сохранить выражение, а затем использовать его выражение eatExpression для его анализа. Когда мы начинаем синтаксический анализ, мы смотрим на него посимвольно. Мы используем «есть» для представления действия обхода, поэтому нам нужно to Есть несколько вспомогательных параметров и вспомогательных функций:
this.index // 标记当前遍历的字符的下标
// 获取当前遍历字符
charAt(index = this.index) {
return this.expr.charAt(index);
}
// 获取当前字符的 Unicode 编码
charCodeAt(index = this.index) {
return this.expr.charCodeAt(index);
}
ExpressionParser.prototype.eatExpression
Эта функция является точкой входа всего парсера, и идея этой функции очень важна. Выражение можно разделить на два типа:
- выражения с бинарными операторами
- выражения без бинарных операторов
Выражение без бинарного оператора очень простое, пока оно разложено на множество вышеперечисленных лексических единиц, а если есть бинарный оператор и больше 1, то оно на данный момент сложнее, потому что порядок нашего разбора Слева направо, и порядок операторов не определен.
Итак, как решить эту проблему? Ниже приведен пример потока обработки, объясняющий основную идею расчета приоритета:
Основная идея состоит в том, чтобы использовать стек для хранения анализируемого токена на стеке. При расстановке оператора (разборки оператора unary в токен относится к бинарному оператору), сравните оператор, ближайший к вершине в стеке, если это Установлено, что недавно проанализированный оператор имеет более высокий приоритет и напрямую проталкивается в стек. Следовательно, в стеке приоритет операторов гарантирован от низкого до высокого. После того, как вновь анализируемый оператор имеет более низкий приоритет, это означает, что токены в стеке могут быть синтезированы в узле, пока все приоритеты оператора в стеке не имеют От низкого до высокого. Наконец, узлы синтезируются справа налево, чтобы получить полное двоичное дерево выражений.
Основная идея состоит в том, чтобы убедиться, что приоритет в стеке находится от низкого до высокого. Следующий код размещен для всех для консолидации и понимать:
eatExpression() {
let left = this.eatToken();
let operator = this.eatBinaryOperator();
// 说明这个运算树只有左侧
if (!operator) {
return left;
}
let operatorInfo = {
precedence: this.getOperatorPrecedence(operator), // 获取运算符优先级
value: operator,
};
let right = this.eatToken();
if (!right) {
this.throwError(`"${operator}"运算符后应该为表达式`);
}
const stack = [left, operatorInfo, right];
// 获取下一个运算符
while (operator = this.eatBinaryOperator()) {
const precedence = this.getOperatorPrecedence(operator);
// 如果遇到了非法的yuan fa
if (precedence === 0) {
break;
}
operatorInfo = {
precedence,
value: operator,
};
while (stack.length > 2 && precedence < stack[stack.length - 2].precedence) {
right = stack.pop();
operator = stack.pop().value;
left = stack.pop();
const node = this.createNode(operator, left, right);
stack.push(node);
}
const node = this.eatToken();
if (!node) {
this.throwError(`"${operator}"运算符后应该为表达式`);
}
stack.push(operatorInfo, node);
}
let i = stack.length - 1;
let node = stack[i];
while (i > 1) {
node = this.createNode(stack[i - 1].value, stack[i - 2], node);
i -= 2;
}
return node;
}
createNode:
const LOGICAL_OPERATORS = ['||', '&&', '===', '!==', '>', '<', '>=', '<=', 'include'];
...
createNode(operator, left, right) {
const type = LOGICAL_OPERATORS.indexOf(operator) !== -1 ? 'LOGICAL_EXP' : 'BINARY_EXP';
return {
type,
operator,
left,
right,
};
}
getOperatorPrecedence:
const BINARY_OPERATORS = {
'||': 1,
'&&': 2,
'===': 6, '!==': 6,
'<': 7, '>': 7, '<=': 7, '>=': 7,
'+': 9, '-': 9,
'*': 10, '/': 10, '%': 10,
include: 11,
};
...
getOperatorPrecedence(operator) {
return BINARY_OPERATORS[operator] || 0;
}
Я считаю, что теперь у вас есть очень четкое представление об общей идее.Далее есть еще один важный момент, о котором стоит поговорить – это анализ токена.
Анализ токенов
Процесс синтаксического анализа токена можно представить как движение слева направо с нижним индексом символ за символом.Когда встречается распознаваемый знак начала токена, токен анализируется, а затем нижний индекс продолжает двигаться до тех пор, пока вся строка не закончится или не может быть Знакомый логотип.
Чтобы узнать, как сопоставить каждый тип токена, вы можете просмотреть полный код.
Рассчитать значение результата
После того, как токен проанализирован, нам нужно вычислить значение выражения.Из-за существования переменных нам нужно предоставить контекст для переменной, чтобы получить значение, например:
const expr = new ExpressionParser('@load > 5');
console.log(expr.valueOf({ load: 8 })); // true
Поскольку мы уже создали двоичное дерево из выражения, нам нужно только рекурсивно пройти и вычислить значение каждого двоичного дерева.Поскольку это рекурсивный расчет, чем ниже дерево, тем раньше вычисление, что согласуется с идея начала проектирования приоритетов.
Полный код:
const OPEN_PAREN_CODE = 40; // (
const CLOSE_PAREN_CODE = 41; // )
const VARIABLE_BEGIN_CODE = 64; // @，变量开头
const PERIOD_CODE = 46; // '.'
const SINGLE_QUOTE_CODE = 39; // single quote
const DOUBLE_QUOTE_CODE = 34; // double quotes
const SPACE_CODES = [32, 9, 10, 13]; // space
// 一元运算符
const UNARY_OPERATORS = { '-': true, '!': true, '+': true };
// 二元运算符
const LOGICAL_OPERATORS = ['||', '&&', '===', '!==', '>', '<', '>=', '<=', 'include'];
const BINARY_OPERATORS = {
'||': 1,
'&&': 2,
'===': 6, '!==': 6,
'<': 7, '>': 7, '<=': 7, '>=': 7,
'+': 9, '-': 9,
'*': 10, '/': 10, '%': 10,
include: 11,
};
// 获取对象键的最大长度
const getMaxKeyLen = function getMaxKeyLen(obj) {
let max = 0;
Object.keys(obj).forEach((key) => {
if (key.length > max && obj.hasOwnProperty(key)) {
max = key.length;
}
});
return max;
};
const maxBinaryOperatorLength = getMaxKeyLen(BINARY_OPERATORS);
const maxUnaryOperatorLength = getMaxKeyLen(UNARY_OPERATORS);
class ExpressionParser {
constructor(expr) {
if (typeof expr !== 'string') {
throw new Error(`[expression-parser] constructor need a string parameter, but get [${typeof expr}]`);
}
this.expr = expr;
}
parse() {
this.index = 0;
try {
this.tokens = this.eatExpression();
if (this.index < this.expr.length) {
throw new Error(`非法字符"${this.charAt()}"`);
}
} catch (error) {
this.tokens = undefined;
if (typeof this.onErrorCallback === 'function') {
this.onErrorCallback(error.message, this.index, this.charAt());
} else {
throw new Error(error.message);
}
}
return this;
}
eatExpression() {
let left = this.eatToken();
let operator = this.eatBinaryOperator();
// 说明这个运算树只有左侧
if (!operator) {
return left;
}
let operatorInfo = {
precedence: this.getOperatorPrecedence(operator), // 获取运算符优先级
value: operator,
};
let right = this.eatToken();
if (!right) {
throw new Error(`"${operator}"运算符后应该为表达式`);
}
const stack = [left, operatorInfo, right];
// 获取下一个运算符
while (operator = this.eatBinaryOperator()) {
const precedence = this.getOperatorPrecedence(operator);
// 如果遇到了非法的yuan fa
if (precedence === 0) {
break;
}
operatorInfo = {
precedence,
value: operator,
};
while (stack.length > 2 && precedence < stack[stack.length - 2].precedence) {
right = stack.pop();
operator = stack.pop().value;
left = stack.pop();
const node = this.createNode(operator, left, right);
stack.push(node);
}
const node = this.eatToken();
if (!node) {
throw new Error(`"${operator}"运算符后应该为表达式`);
}
stack.push(operatorInfo, node);
}
let i = stack.length - 1;
let node = stack[i];
while (i > 1) {
node = this.createNode(stack[i - 1].value, stack[i - 2], node);
i -= 2;
}
return node;
}
eatToken() {
this.eatSpaces();
const ch = this.charCodeAt();
if (ch === VARIABLE_BEGIN_CODE) {
// 变量
return this.eatVariable();
} else if (this.isDigit(ch) || ch === PERIOD_CODE) {
// 数字
return this.eatNumber();
} else if (ch === SINGLE_QUOTE_CODE || ch === DOUBLE_QUOTE_CODE) {
// 字符串
return this.eatString();
} else if (ch === OPEN_PAREN_CODE) {
// 括号
return this.eatGroup();
} else {
// 检查单操作符 ！+ -
let toCheck = this.expr.substr(this.index, maxUnaryOperatorLength);
let toCheckLength;
while (toCheckLength = toCheck.length) {
if (
UNARY_OPERATORS.hasOwnProperty(toCheck) &&
this.index + toCheckLength <= this.expr.length
) {
this.index += toCheckLength;
return {
type: 'UNARY_EXP',
operator: toCheck,
argument: this.eatToken(),
};
}
toCheck = toCheck.substr(0, --toCheckLength);
}
}
}
eatGroup() {
this.index++; // eat "("
const node = this.eatExpression();
this.eatSpaces();
const ch = this.charCodeAt();
if (ch !== CLOSE_PAREN_CODE) {
throw new Error('括号没有闭合');
} else {
this.index++; // eat ")"
return node;
}
}
eatVariable() {
const ch = this.charAt();
this.index++; // eat "@"
const start = this.index;
while (this.index < this.expr.length) {
const ch = this.charCodeAt();
if (this.isVariablePart(ch)) {
this.index++;
} else {
break;
}
}
const identifier = this.expr.slice(start, this.index);
return {
type: 'VARIABLE',
value: identifier,
raw: ch + identifier,
};
}
eatNumber() {
let number = '';
// 数字开头
while (this.isDigit(this.charCodeAt())) {
number += this.charAt(this.index++);
}
// '.'开头
if (this.charCodeAt() === PERIOD_CODE) {
number += this.charAt(this.index++);
while (this.isDigit(this.charCodeAt())) {
number += this.charAt(this.index++);
}
}
// 科学计数法
let ch = this.charAt();
if (ch === 'e' || ch === 'E') {
number += this.charAt(this.index++);
ch = this.charAt();
if (ch === '+' || ch === '-') {
number += this.charAt(this.index++);
}
while (this.isDigit(this.charCodeAt())) {
number += this.charAt(this.index++);
}
// 如果e + - 后无数字，报错
if (!this.isDigit(this.charCodeAt(this.index - 1))) {
throw new Error(`非法数字(${number}${this.charAt()})，缺少指数`);
}
}
return {
type: 'NUMBER',
value: parseFloat(number),
raw: number,
};
}
eatString() {
let str = '';
const quote = this.charAt(this.index++);
let closed = false;
while (this.index < this.expr.length) {
let ch = this.charAt(this.index++);
if (ch === quote) {
closed = true;
break;
} else if (ch === '\\') {
// Check for all of the common escape codes
ch = this.charAt(this.index++);
switch (ch) {
case 'n':
str += '\n';
break;
case 'r':
str += '\r';
break;
case 't':
str += '\t';
break;
case 'b':
str += '\b';
break;
case 'f':
str += '\f';
break;
case 'v':
str += '\x0B';
break;
default:
str += ch;
}
} else {
str += ch;
}
}
if (!closed) {
throw new Error(`字符"${str}"缺少闭合括号`);
}
return {
type: 'STRING',
value: str,
raw: quote + str + quote,
};
}
eatBinaryOperator() {
this.eatSpaces();
let toCheck = this.expr.substr(this.index, maxBinaryOperatorLength);
let toCheckLength = toCheck.length;
while (toCheckLength) {
if (
BINARY_OPERATORS.hasOwnProperty(toCheck) &&
this.index + toCheckLength <= this.expr.length
) {
this.index += toCheckLength;
return toCheck;
}
toCheck = toCheck.substr(0, --toCheckLength);
}
return false;
}
getOperatorPrecedence(operator) {
return BINARY_OPERATORS[operator] || 0;
}
createNode(operator, left, right) {
const type = LOGICAL_OPERATORS.indexOf(operator) !== -1
? 'LOGICAL_EXP'
: 'BINARY_EXP';
return {
type,
operator,
left,
right,
};
}
isVariablePart(ch) {
return (ch >= 65 && ch <= 90) || // A...Z
(ch >= 97 && ch <= 122) || // a...z
(ch >= 48 && ch <= 57); // 0...9
}
isDigit(ch) {
return ch >= 48 && ch <= 57; // 0...9
}
eatSpaces() {
let ch = this.charCodeAt();
while (SPACE_CODES.indexOf(ch) !== -1) {
ch = this.charCodeAt(++this.index);
}
}
onError(callback) {
this.onErrorCallback = callback;
return this;
}
charAt(index = this.index) {
return this.expr.charAt(index);
}
charCodeAt(index = this.index) {
return this.expr.charCodeAt(index);
}
valueOf(scope = {}) {
if (this.tokens == null) {
return undefined;
}
const value = this.getNodeValue(this.tokens, scope);
return !!value;
}
getNodeValue(node, scope = {}) {
const { type, value, left, right, operator } = node;
if (type === 'VARIABLE') {
return scope[value];
} else if (type === 'NUMBER' || type === 'STRING') {
return value;
} else if (type === 'LOGICAL_EXP') {
const leftValue = this.getNodeValue(left, scope);
// 如果是逻辑运算的&&和||，那么可能不需要解析右边的值
if (operator === '&&' && !leftValue) {
return false;
}
if (operator === '||' && !!leftValue) {
return true;
}
const rightValue = this.getNodeValue(right, scope);
switch (node.operator) {
case '&&': return leftValue && rightValue;
case '||': return leftValue || rightValue;
case '>': return leftValue > rightValue;
case '>=': return leftValue >= rightValue;
case '<': return leftValue < rightValue;
case '<=': return leftValue <= rightValue;
case '===': return leftValue === rightValue;
case '!==': return leftValue !== rightValue;
case 'include': return leftValue.toString &&
rightValue.toString &&
leftValue.toString().indexOf(rightValue.toString()) !== -1;
// skip default case
}
} else if (type === 'BINARY_EXP') {
const leftValue = this.getNodeValue(left, scope);
const rightValue = this.getNodeValue(right, scope);
switch (node.operator) {
case '+': return leftValue + rightValue;
case '-': return leftValue - rightValue;
case '*': return leftValue * rightValue;
case '/': return leftValue - rightValue;
case '%': return leftValue % rightValue;
// skip default case
}
} else if (type === 'UNARY_EXP') {
switch (node.operator) {
case '!': return !this.getNodeValue(node.argument, scope);
case '+': return +this.getNodeValue(node.argument, scope);
case '-': return -this.getNodeValue(node.argument, scope);
// skip default case
}
}
}
}
const expression = new ExpressionParser('@load + 3');
expression.onError((message, index, ch) => {
console.log(message, index, ch);
}).parse();
console.log(expression.valueOf({ load: 5 }));