Как реализовать лексический анализ в Javascript - PullRequest
Новая
       4

Как реализовать лексический анализ в Javascript

14 голосов
/ 18 января 2011

Привет, ребята, спасибо, что прочитали

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

Я начал медленно с основ: + - / * и обработки скобок.

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

Этот вид работы легко применим с такими языками, как Lex и Yacc, кроме IЯ разрабатываю приложение только для Javascript.

Я пытался перевести эту идею в Javascript, но не могу понять, как обращаться со всем чистым и красивым способом, особенно с вложенными скобками.

Анализ

Давайте определим, что такое запрос калькулятора: 

// NON TERMINAL EXPRESSIONS //
query     -> statement
query     -> ε // means end of query

statement -> statement operator statement
statement -> ( statement )
statement -> prefix statement
statement -> number

number    -> integer
number    -> float

// TERMINAL EXPRESSIONS //
operator  -> [+*/%^-]

prefix    -> -

integer   -> [0-9]+

float     -> [0-9]+[.,][0-9]+

Javascript

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

(я добавил пробелы, чтобы сделать его более читабельным) 

var calcPat = 
/^ (\s*
    ( ([+/*%^-]) | ([0-9]+) | ([0-9]+[.,][0-9]+) | (\() | (\)) )
)+ \s* $/;

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

Я не собираюсь вставлять код, потому что он не чистый и не понятный, но я собираюсь объяснить процесс, которому я следовал, и почему я застрял:

Я создал метод с именем isStatement(string), который должен вызывать себя рекурсивно.Основная идея состоит в том, чтобы разбить строку на «потенциальные» операторы и проверить, действительно ли они являются операторами и образуют их вместе.
Процесс выглядит следующим образом:

-Если первые два токена являются числом, за которым следуетоператор:

-Then,
- Если оставшийся - только один токен и это число:
--- Тогда это утверждение.
--- Иначе,проверить, образуют ли остальные токены оператор (рекурсивный вызов)

-Ельсе, если первый токен является круглой скобкой
-Then, Найти соответствующие закрывающие скобки и проверить, является ли внутри оператор (рекурсия)
- также проверьте, есть ли что-то после закрывающей скобки и формирует ли он оператор, связанный со структурой скобок.

В чем проблема?

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

Большое вам спасибо за то, что нашли время, чтобы прочитать все.Gael

(PS: Как вы, наверное, заметили, я не являюсь носителем английского языка! Извините за ошибки и все!)

1 Ответ

10 голосов
/ 18 января 2011

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

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

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

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

Теперь, поскольку у вас есть регулярные выражения Javascript для работы, вы могли бы придумать регулярное выражениеразработан, чтобы соответствовать строке токенов.Хитрость в этом заключается в том, чтобы найти способ определить, какой токен был найден в списке возможностей.Движок регулярных выражений Javascript может возвращать вам массивы групп, поэтому, возможно, вы могли бы что-то построить поверх этого.

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

...