Разбор полных математических выражений с помощью PEG.js

Я пытаюсь расширить пример грамматики PEG.js для разбора математических выражений всеми 4 операторами для моего эксперимента с интерпретатором BASIC:

http://www.dantonag.it/basicjs/basicjs.html

но не все выражения анализируются правильно.

Это моя грамматика PEG:

expression = additive

additive = left:multiplicative atag:("+" / "-") right:additive { return {tag: atag, left:left, right:right}; } / multiplicative

multiplicative = left:primary atag:("*" / "/") right:multiplicative { return {tag: atag, left:left, right:right}; } / primary

primary = number / "(" additive:additive ")" { return additive; }

number = digits:[0-9]+ { return parseInt(digits.join(""), 10); }

Он правильно анализирует выражения, такие как 2*3+1 (давая 7), но не выражение как 2-1-1, которое дает 2 вместо 0.

Можете ли вы помочь мне улучшить и отладить это?

Заранее спасибо.

Изменить: я добавил правило "число" в грамматику. И да, моя грамматика дает на выходе рекурсивную структуру, которая является аналогом дерева разбора.

Источник

2 ответа

Решение

Во-первых: в вашей грамматике отсутствует number править. Кроме того, как я уверен, вы знаете, запустив свою грамматику (после добавления number) на вашем примере не дает 2, а скорее что-то вроде дерева разбора. Не могли бы вы обновить вопрос, чтобы исправить эти две проблемы?

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

Я предполагаю что 2*3+1 анализируется правильно, потому что два оператора имеют разные приоритеты, это означает, что ассоциативность не вступает в игру, и что ваша грамматика правильно реализует приоритет (хотя вы должны заметить, что 2+3*1 более стандартный пример, показывающий, что умножение имеет более высокий приоритет, чем сложение, так как простой разбор слева направо 2*3+1 дает тот же результат, что и ваш парсер).

Я полагаю, вы хотите - быть левоассоциативным, но в вашей грамматике это выглядит как ассоциативно справа, основываясь на следующем примере:

  • вход:

    1-2-3

  • выход (анализируется как 1-(2-3)):

    {
   "tag": "-",
   "left": "1",
   "right": {
      "tag": "-",
      "left": "2",
      "right": "3"
   }
}

Левое ассоциативное дерево будет выглядеть так (из (1-2)-3):

{
   "tag": "-",
   "left": {
      "tag": "-",
      "left": "1",
      "right": "2"
   },
   "right": "3"
}

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

Решение: я действительно не знаю, как работает peg.js, но быстрое прибегание к поиску показало это.

Основанные на грамматике решения приоритета операторов и ассоциативности часто бывают довольно неприятными (см. Грамматику для Python для доказательства), поэтому вы можете захотеть проверить синтаксический анализ приоритета оператора [сверху вниз] для более гибкой и выразительной альтернативы. Дуглас Крокфорд, Вон Пратт и Анника Ааса подготовили несколько хороших статей на эту тему.

Источник

Ответ Мэтта правильный, но о том, как реализовать левую ассоциативность в pegjs:

expression = additive

additive
  = first:multiplicative rest:(("+" / "-") multiplicative)+ {
    return rest.reduce(function(memo, curr) {
      return {atag: curr[0], left: memo, right: curr[1]};
    }, first);
  }
  / multiplicative

multiplicative
  = first:primary rest:(("*" / "/") primary)+ {
    return rest.reduce(function(memo, curr) {
      return {atag: curr[0], left: memo, right: curr[1]};
    }, first);
  }
  / primary

primary
  = number
  / "(" additive:additive ")" { return additive; }

number
  = digits:[0-9]+ { return parseInt(digits.join(""), 10); }

Пример javascript.pegjs, на который ссылается Мэтт, использует похожий метод. Ключ заключается в обработке строк операций с тем же приоритетом, что и в списке, что позволяет вам построить дерево с правильной ассоциативностью.

Источник
Другие вопросы по тегам