使用menhir解析带有变量的算术表达式满足优先级问题

Question

解析器.mly

%{
  让 env=Hashtbl.create 10
%}
%代币 INT
%代币SUB
%代币停产
%令牌等于
%代币名称
%左SUB
%右等于

%start main /* 入口点 */
%类型主要
%%
 主要的：
  表达式 EOL { $1 }
;

表达式：
   智力 { $1}
  | expr SUB expr { $1 - $3}
  | var EQUAL expr {Hashtbl.add env $1 $3;0}
  | var {Hashtbl.find env $1}
;

变量：名称{$1}

运行程序：

a=1
0
b=2
0
a-b-5
-6
a=1-3
-3
A
1

这意味着a=1,b=2,a-b-5可以得到正确答案，但a=1-3不能

如果更改优先级：

%左等于
%右子

比：

a=1-3
0
A
-2
a=1
0
b=2
0
a-b-5
4

看来我不明白menhir的优先级，如何解决它？谢谢！

和线路

| var EQUAL expr {Hashtbl.add env $1 $3;0}

我真正需要的是

Hashtbl.add 环境 $1 $3

但是好像必须定义main的类型，而且我无法定义

％类型主要

所以我必须写丑陋的“0”，如何修复它？

其他文件： 词法分析器.mll:

{
打开解析器
异常Eof
}
规则标记=解析
  [' ' ' '] { token lexbuf } (* 跳过空格 *)
| ['
'] { 停产 }
 | ['0'-'9']+ as lxm { INT(int_of_string lxm) }
| '-' { 子 }
|['a'-'z']+ {NAME}
|'='{等于}
| eof { 提高 Eof }

计算.ml

开放语法

让_=
  尝试
    让 lexbuf = Lexing.from_channel stdin 中
    虽然是真的
      让结果 = Parser.main Lexer.token lexbuf in
      print_int 结果；
      print_newline();
      刷新标准输出
    完毕
  使用 Lexer.Eof -> exit 0

生成文件：

calc:lexer.cmo 解析器.cmo 语法.cmo calc.cmo
    ocamlc -o calc lexer.cmo 解析器.cmo 语法.cmo calc.cmo

词法分析器.cmo:词法分析器.mll
    ocamllex 词法分析器.mll
    
解析器.cmo:解析器.mly
    门希尔解析器.mly

语法.cmo:语法.ml
    ocamlc -c 语法.ml

计算.cmo:计算.ml
    ocamlc -c 词法分析器.ml
    ocamlc -c 解析器.mli
    ocamlc -c 解析器.ml
    ocamlc -c calc.ml

Answer 1

您混淆了运算符的优先级和关联性。 Menhir 标记声明设置了这两者：使用

%left SUB

，您声明

a-b-c

形式的某些内容应被解析为

(a-b)-c

而不是

a-(b-c)

。类似地，对于

%right EQUAL

，您说

a=b=c

应该被解析为

a=(b=c)

，这可能是正确的，因为这是流行编程语言（即 C）中这些运算符的通常关联性。

但是，这些声明的 order 也很重要：它指示

a=b-c

是否应该被解析为

a=(b-c)

或

(a=b)-c

。通过在

SUB

之前声明

EQUAL

，

EQUAL

将具有更高的优先级，因此将发生后者的解析（这不是您想要的）。因此，您想要的可能是以下内容：

%right EQUAL
%left SUB