functional-programming - 在计算器语法中为括号添加优先级

Question

我正在用 SML 编写一个简单的计算器，我的代码需要支持 3 种括号:

( ) 

[ ] 

{ } 

在{ } 里面，可以出现{ } , [ ] , ( ) 表达式,

在[ ] 中，可以出现[ ] , ( ) 表达式,

而在( ) 中，只能出现( ) 表达式。

意思是，{ } 具有最高优先级，[ ] - 中间优先级，而 ( ) 具有最低优先级.

实现该目标的最佳方法是什么？

我写了一个包含太多循环和递归的大方法，它在不同的情况下运行，但是我认为这不是最好的方法。

如有任何建议，我们将不胜感激

问候

编辑:

相关代码:

signature CalculatorOperation = sig
  datatype token = 
                    (* paranthesis *)

                   Lpar3             (* { *)
                 | Rpar3             (* } *)
                 | Lpar2             (* [ *)
                 | Rpar2             (* ] *)  
                 | Lpar              (* ( *)
                 | Rpar              (* ) *)

结构:

structure CalculatorOperation : CalculatorOperation = struct 
  datatype token =
                    (* paranthesis *)

                   Lpar3             (* { *)
                 | Rpar3             (* } *)
                 | Lpar2             (* [ *)
                 | Rpar2             (* ] *)  
                 | Lpar              (* ( *)
                 | Rpar              (* ) *)

扫描仪:

 fun stringScanner s [] = (toToken s,[])
    | stringScanner s (c::l)
      = case c::l of
          #" "::r => if s = "" then (stringScanner "" l) else (toToken s,l)
        (* paranthesis *)

        | #"{"::r => if s = "" then (Lpar3,r) else (toToken s,c::l)
        | #"}"::r => if s = "" then (Rpar3,r) else (toToken s,c::l)     
        | #"["::r => if s = "" then (Lpar2,r) else (toToken s,c::l)
        | #"]"::r => if s = "" then (Rpar2,r) else (toToken s,c::l)
        | #"("::r => if s = "" then (Lpar,r) else (toToken s,c::l)
        | #")"::r => if s = "" then (Rpar,r) else (toToken s,c::l)

解析器:

structure CalculatorParser : CalculatorParser = struct
  open CalculatorOperation

  exception CalculatorParser

  datatype expr = NumNode of int
               | UminusNode of expr
               | MultiplyNode of expr * expr
               | DivNode of expr * expr
               | PlusNode of expr * expr
               | MinusNode of expr * expr
               | ModuloNode of expr * expr
               | PowerNode of expr * expr                          





  fun parserBrackets l = parserHelper2 l
  and parserHelper l
      = case l of 
          (Num n)::l1 => (NumNode n,l1)
        | Lpar3::l1 => let val (en,l2) = parserBrackets l1  in case l2 of Rpar3::l3 => (en,l3)
        | _ => raise CalculatorParser end

        | Lpar2::l1 => let val (en,l2) = parserBrackets l1 in case l2 of Rpar2::l3 => (en,l3)
        | _ => raise CalculatorParser end   

        | Lpar::l1 => let val (en,l2) = parserBrackets l1 in case l2 of Rpar::l3 => (en,l3)
        | _ => raise CalculatorParser end   

Answer 1

我不是 SML 专家，但根据您的描述，我了解到您正在寻找的语法规则可以用 BNF 表示如下:

<expr1> ::= '{' ( <expr1> | <expr2> ) '}'

<expr2> ::= '[' ( <expr2> | <expr3> ) ']'

<expr3> ::= '(' ( <expr3> | <expr> ) ')' 

当我查看您对数据类型 expr 的定义时，在我看来您可以为 expr1、expr2 和 expr3 定义类似的类型，如下所示:

datatype expr3 = E3Node of expr3
              | ENode of expr

datatype expr2 = E2Node of expr2
              | E3Node of expr3

datatype expr1 = E1Node of expr1
              | E2Node of expr2

老实说，我什至不知道这是否是有效的 SML，但我相信您能够修复它……并填补空白。