Написание парсера в JavaScript для матричной арифметики

Question

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

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

[[0, 0],[4, 5]] + [[4, 8], [12, 6]]

будет сохранено следующим образом:

variables = ["$", "+", "$"]
matrices = [[[0, 0],[4, 5]], [[4, 8], [12, 6]]

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

det([[0, 0],[4, 5]]) + inv([[0, 0],[4, 5]] + [[4, 8], [12, 6]])

Где det и inv соответствуют определителю и обратному.

, которые в моем коде будут сохранены as:

variables = ["d", "e", "t", "(", "$", ")", "+", "i", "n", "v", "(", "$", "+", "$", ")"]
matrices = [ [[0, 0],[4, 5]], [[0, 0],[4, 5]],  [[4, 8], [12, 6]] ]

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

Answer 1

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

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

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

В случае простого числового калькулятора c буквальные объекты (то есть числа) обычно просто выпадают из лексера, поскольку они не имеют внутренней структуры. Но очевидно, что матрицы имеют внутреннюю структуру, и лексеры на основе регулярных выражений не идеальны для анализа структурированного текста. Лучшее решение состоит в том, чтобы рассматривать матричный литерал как последовательность токенов (как минимум, чисел и символов [, ] и ,), а также включать в свои контекстно-свободные грамматические произведения, которые можно использовать для анализа матрицы.

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

Базовая c форма неконтекстной грамматики для список с разделителями следующий, где вы должны заменить X типом элемента в списке:

/* Only parses lists with at least one element */
list_of_X: X
         | list_of_X ',' X

Если разрешены пустые списки (вероятно, не в случае матриц, но часто встречается в вызовах функций), Вы комбинируете вышеизложенное с другим шаблоном:

optional_list_of_X: %empty
                  | list_of_X

Ваша грамматика будет включать такие произведения, как:

expression: matrix
          | /* ... all the other forms of an expression */

matrix: '[' list_of_vector ']'
vector: '[' list_of_number ']'

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