Разбор выражений: как токенизировать

Question

Я пытаюсь токенизировать Java / Javascript-подобные выражения в коде Javascript. Мой ввод будет строкой, содержащей выражение, а вывод должен быть массивом токенов.

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

Мне нужно это, чтобы иметь возможность поддерживать:

• Числа и строковые литералы (одинарные и двойные кавычки, с экранированием кавычек)
• Основные математические и логические операторы и компараторы (+, -, *, /,!, А не, <,> и т. Д.)
• Точечные и скобочные обозначения для доступа к объекту с помощью рекурсии (foo.bar, foo ['bar'], foo [2] [prop])
• Скобки со вложением
• Тернарный оператор (foo? Bar: 'baz')
• вызовы функций (foo (bar))

Я специально хочу по соображениям безопасности избегать использования eval() или чего-либо подобного. Кроме того, eval() в любом случае не будет означать для меня выражение.

Answer 1

Научитесь писать парсер рекурсивного спуска. Как только вы поймете концепции, вы сможете сделать это на любом языке: Java, C ++, JavaScript, SystemVerilog, ... что угодно. Если вы можете обрабатывать строки, то можете анализировать.

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

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

Простой пример: выражения, включающие числа, сложение и умножение (это иллюстрирует приоритет оператора). Во-первых, грамматика:

expr ::= term
         | expr "+" term

term ::= factor
         | term "*" factor

factor ::= /[0-9/+ (I'm using a regexp here)

Теперь, чтобы написать синтаксический анализатор (который включает лексер; с рекурсивным спуском вы можете соединить их вместе). Я никогда не использовал JavaScript, поэтому давайте попробуем это в (мой ржавый) Java:

class Parser {
  string str;
  int idx; // index into string

  Node parseExpr() throws ParseException
  {
    Node op1 = parseTerm();
    Node op2;

    while (idx < str.size() && str.charAt(idx) == '+') {
      idx++;
      op2 = parseTerm();
      op1 = new AddNode(op1, op2);
    }
    return op1;
  }

  Node parseTerm() throws ParseException
  {
    Node op1 = parseFactor();
    Node op2;

    while (idx < str.size() && str.charAt(idx) == '*') {
      idx++;
      op2 = parseFactor();
      op1 = new MultNode(op1, op2);
    }
    return op1;
  }

  Node parseFactor() throws ParseException
  {
    StringBuffer sb = new StringBuffer();
    int old_idx = idx;

    while (idx < str.size() && str.charAt(idx) >= '0' && str.charAt(idx) <= '9') {
      sb.append(str.charAt(idx));
      idx++;
    }
    if (idx == old_idx) {
      throw new ParseException();
    }
    return new NumberNode(sb.toString());
  }
}

Вы можете видеть, как каждое правило грамматики переводится в процедуру. Я не проверял это; это упражнение для читателя.

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

Для получения дополнительной информации посмотрите "Парсер LL" и "Парсер рекурсивного спуска" в Википедии. Как я сказал в начале, если вы можете понять концепции (и они просты по сравнению с концепциями, лежащими в основе замыканий конфигурации конечного автомата LALR (1)), то вы можете написать анализатор для небольших задач на любом языке, если как у вас есть некоторые элементарные возможности строки. Наслаждайтесь силой.

Answer 2

Вам необходимо внедрить лексический анализатор. Вы можете использовать js / cc , чтобы сделать это, или вы можете реализовать конечные автоматы самостоятельно.

Поскольку формально язык, которым вы будете манипулировать, является регулярным, вы можете использовать регулярное выражение. Но я вам его не рекомендую.

Хотя я никогда не использовал js / cc, я сначала попробовал бы с ним, и если он не работает, я бы попытался построить лексический анализатор самостоятельно.

Answer 3

Для простых лексеров, где скорость не критична, я обычно пишу регулярное выражение для каждого типа токена и неоднократно пытаюсь сопоставить каждый из них по очереди с началом ввода. (Убедитесь, что у вас нет алгоритма O (n ^ 2)!) Такой инструмент, как lex, даст более эффективный лексер, потому что он объединяет регулярные выражения в один конечный автомат.