使用Menhir解析含变量算术表达式的优先级与返回值问题

一、运算符优先级问题解析与修正 #

问题现象 #

最初设置优先级：

%left SUB 
%right EQUAL

执行时a=1-3解析错误，得到结果-3，实际期望a被赋值为-2；调整为：

%left EQUAL
%right SUB

后a=1-3正确，但a-b-5结果错误（得到4，正确应为-6）。

Menhir优先级规则说明 #

Menhir中运算符的优先级由声明顺序决定：越晚声明的运算符优先级越高；%left表示左结合（相同优先级运算符从左到右计算），%right表示右结合（从右到左计算）。

• 原设置中EQUAL晚于SUB声明，优先级更高，导致a=1-3被解析为(a=1)-3，先执行赋值得到0，再减3返回-3。
• 调整后SUB优先级更高，且为右结合，导致a-b-5被解析为a-(b-5)，计算得1-(2-5)=4，不符合左结合的减法预期。

正确优先级设置 #

赋值运算符（EQUAL）优先级应低于减法（SUB），且赋值为右结合、减法为左结合。正确声明：

%right EQUAL  // 优先级低，右结合
%left SUB     // 优先级高，左结合

此时：

• a=1-3会解析为a=(1-3)，先计算减法得到-2，再赋值给a；
• a-b-5解析为(a-b)-5，按左结合计算得到(1-2)-5=-6，符合预期。

二、赋值语句冗余返回值问题解决 #

问题原因 #

main类型定义为<int>，而Hashtbl.add返回unit类型，因此必须添加;0强制返回int值，导致冗余输出。

两种解决方法 #

方法1：返回被赋值的值（推荐）

修改赋值语句的动作代码，让其返回被赋的值，既符合int类型要求，又避免冗余的0：

| var EQUAL expr { let value = $3 in Hashtbl.add env $1 value; value }

此时执行a=1-3会直接返回-2，输入a也返回-2，输出更符合直觉。

方法2：区分表达式与语句类型

1. 在syntax.ml中定义联合类型：

type result = Int of int | Unit

2. 修改parser.mly的类型声明与规则：

%type<result> main
%%
main:
  expr EOL { $1 }
;

expr:
   INT                     { Int $1 }
  | expr SUB expr           { let Int a = $1 and Int b = $3 in Int (a - b) }
  | var EQUAL expr { let Int v = $3 in Hashtbl.add env $1 v; Unit }
  | var { Int (Hashtbl.find env $1) }

3. 修改calc.ml的打印逻辑：

open Syntax

let _ =
  try
    let lexbuf = Lexing.from_channel stdin in
    while true do
      match Parser.main Lexer.token lexbuf with
      | Int n -> print_int n; print_newline ()
      | Unit -> ()  // 赋值语句不输出内容
    done
  with Lexer.Eof -> exit 0

此方法彻底区分表达式（返回int）与赋值语句（返回unit），赋值语句执行后无输出。

修正后的完整代码 #

parser.mly #

%{
  let env = Hashtbl.create 10
%}
%token <int> INT
%token SUB
%token EOL
%token EQUAL
%token <string> NAME

%right EQUAL
%left SUB

%start main
%type<int> main
%%
main:
  expr EOL { $1 }
;

expr:
   INT                     { $1 }
  | expr SUB expr           { $1 - $3 }
  | var EQUAL expr { let value = $3 in Hashtbl.add env $1 value; value }
  | var { Hashtbl.find env $1 }
;

var: NAME { $1 }

lexer.mll #

{
open Parser
exception Eof
}
rule token = parse
  [' ' '\t']     { token lexbuf }
| ['\n' ]        { EOL }
| ['0'-'9']+ as lxm { INT(int_of_string lxm) }
| '-'            { SUB }
| ['a'-'z']+ as name { NAME name }
| '='            { EQUAL }
| eof            { raise Eof }

calc.ml（方法1使用） #

open Syntax

let _ =
  try
    let lexbuf = Lexing.from_channel stdin in
    while true do
      let result = Parser.main Lexer.token lexbuf in
      print_int result;
      print_newline ();
      flush stdout
    done
  with Lexer.Eof -> exit 0

内容的提问来源于stack exchange，提问作者wang kai