时间戳

首页 > 解决方案 > 有没有办法在解析后使用关联性和优先级表来修复带有运算符的表达式？

parsing - 有没有办法在解析后使用关联性和优先级表来修复带有运算符的表达式？

问题描述

我目前正在研究一种用 Haskell 编写的简单编程语言的解析器。当我尝试允许具有不同关联性和优先级的二元运算符时遇到了问题。通常这不是问题，但由于我的语言允许用户定义自己的运算符，因此编译器在程序已经被解析之前不知道运算符的优先级。

以下是我迄今为止定义的一些数据类型：

data Expr
  = Var String 
  | Op String Expr Expr
  | ..

data Assoc 
  = LeftAssoc 
  | RightAssoc 
  | NonAssoc

type OpTable = 
  Map.Map String (Assoc, Int)

目前，编译器解析所有运算符，就好像它们是具有相同优先级的右结合。因此，如果我给它一个表达式a + b * c < d，结果将是Op "+" (Var "a") (Op "*" (Var "b") (Op "<" (Var "c") (Var "d"))).

我正在尝试编写一个名为的函数，该函数fixExpr接受一个OpTable和一个Expr并Expr根据OpTable. 例如：

operators :: OpTable
operators =
  Map.fromList
    [ ("<", (NonAssoc, 4))
    , ("+", (LeftAssoc, 6))
    , ("*", (LeftAssoc, 7))
    ]

expr :: Expr
expr = Op "+" (Var "a") (Op "*" (Var "b") (Op "<" (Var "c") (Var "d")))

fixExpr operators expr应评估为Op "<" (Op "+" (Var "a") (Op "*" (Var "b") (Var "c"))) (Var "d")。

如何定义fixExpr函数？我尝试了多种解决方案，但都没有奏效。

标签： parsinghaskelloperatorsabstract-syntax-tree

解决方案

推荐阅读