四则运算的句法分析器

hbghlyj

PEG.js demonstation有一个四则运算的句法分析器

1. Expression
2.   = head:Term tail:(_ ("+" / "-") _ Term)* {
3.       return tail.reduce(function(result, element) {
4.         if (element[1] === "+") { return result + element[3]; }
5.         if (element[1] === "-") { return result - element[3]; }
6.       }, head);
7.     }
9. Term
10.   = head:Factor tail:(_ ("*" / "/") _ Factor)* {
11.       return tail.reduce(function(result, element) {
12.         if (element[1] === "*") { return result * element[3]; }
13.         if (element[1] === "/") { return result / element[3]; }
14.       }, head);
15.     }
17. Factor
18.   = "(" _ expr:Expression _ ")" { return expr; }
19.   / Integer
21. Integer "integer"
22.   = [0-9]+ { return parseInt(text(), 10); }
24. _ "whitespace"
25.   = [ \t\n\r]*

复制代码

例子
2 * (3 + 16/2/2)输出14

解释

• Expression拆分成head和tail.
  head是一个Term.
  tail是几个前面带着+或-的Term(这里*表示0个或更多),每个+或-两边可以带空白(见最后一条).
• Term拆分成head和tail.
  head是一个Factor.
  tail是几个前面带着*或/的Factor,每个*或/两边可以带空白.
• Factor是一个用()括住的Expression(两边可以带空白),或一个Integer.
• Integer是几个0-9字符(这里+表示1个或更多).
• _是几个连续空白(0个或更多).
  

问题
如何给这个分析器加上乘方^呢? 像2^2=4、2^2^2=16这些.
注意, 乘方^是右结合的, 而*和/是左结合的.

相关
latex.js is written in JavaScript using PEG.js.
Wikipedia–Abstract syntax tree
Context-Free Grammars
$\LaTeX$ Calculator$^2$
Interpreted math equation language 🧮

hbghlyj

按照这里所说
  E -> E+T | E-T | T
  T -> T*X | T/X | X
  X -> F^X | F //Note: it's F^X not X^F
  F -> i | (E)
写成PEG.js我想应该是(不含空白的话)

1. E
2.   = head:("-"?T) tail:(("+"/"-")T)* {
3.       if(head[0]){ head[1] = - head[1]; };
4.       return tail.reduce(function(result, element) {
5.         if (element[0] === "+") { return result + element[1]; }
6.         if (element[0] === "-") { return result - element[1]; }
7.       }, head[1]);
8.     }/T
10. T
11.   = head:X tail:(("*"/"/")X)* {
12.       return tail.reduce(function(result, element) {
13.         if (element[0] === "*") { return result * element[1]; }
14.         if (element[0] === "/") { return result / element[1]; }
15.       }, head);
16.     }/X
18. X
19.   = head:F "^" tail:X { return head**tail; }/F
21. F
22.   = "("expr:E")"{return expr;}/Integer
24. Integer "integer"
25.   = [0-9]+ { return parseInt(text(), 10); }

复制代码

uk702

hbghlyj 发表于 2022-12-26 03:34
按照这里所说
  E -> E+T | E-T | T
  T -> T*X | T/X | X

不好意思，上面的评论是错的。

我想这个分析器大概是无穷递降法：
E -> E+T | E-T | T
T -> T*X | T/X | X
F -> i | (E)

对每一个表达式，识别有没有关键符号，如 E->E+T | E-T | T，如果能找到+或-，则抽取左边部分为 E，右边部分为 T，如果没有关键符号，则整个表达式整体下降一级作为 T 继续解析。

@@当碰到 X -> F^X | F 时，如果找到 ^ 符号，则左边分解成 F ，右边分解成 X，但 X 无法下降，只能继续到当成 X -> F^X | F 来解析，这样就可能造成了无穷循环。@@
-- 好像也不对，当碰到 X -> F^X | F 时，如果找到 ^ 符号，则左边分解成 F ，右边分解成 X，然后继续到当成 X -> F^X | F，如果找到 ^，这时 X  分解成更小的 F^X，如果找不到 ^，那么跟其它规则一样，执行 x->F，将 X 整个下降一级，这么说这个语法应该也没问题呀。

如果换成 X -> F^P | F， F -> i | (E)， P -> i | (E) 不知可不可以，相信在语法上是可以的，但能不能达到运算的目的，就不好说了。

hbghlyj

uk702 发表于 2022-12-26 02:08
不好意思，上面的评论是错的。

我想这个分析器大概是无穷递降法：

把2#改好了. 仿照1#把tail写成数组, 就没有possible infinite loop了
测试:
-1+(1+2)^(2+2)输出80
-2^2+2^4输出12
2^2^2^2输出65536
-2^3+3^2输出1