parsing - 为算术表达式定义从左到右的解析器
问题描述
我很难在 Haskell 中定义从左到右的算术表达式解析器。到目前为止,我所做的是定义一个从右到左的解析器,遵循“G. Hutton, Programming in Haskell”一书。
-- the aexpr integer parser
aexpr_int :: Parser Int
aexpr_int = do
a1 <- aterm_int
s <- sign -- return 1 for "+" and -1 for "-"
a2 <- aexpr_int
return (a1 + (s * a2))
<|>
aterm_int
-- the aterm integer parser
aterm_int :: Parser Int
aterm_int = do
a1 <- aterm_int
char '*'
a2 <- afactor_int
return (a1 * a2);
<|>
do
a1 <- afactor_int
char '/'
a2 <- aterm_int
return (div a1 a2)
<|>
afactor_int
-- afactor_int
afactor_int :: Parser Int
afactor_int = do
token (char '(')
e <- aexpr_int
token (char ')')
return e
<|>
do
s <- sign
ic <- aexpr_int
return (s * ic)
<|>
token int_const
所以这解析1 - 2 - 3 - 4
为1 - (2 - (3 - 4))
,但我希望它解析为((1 - 2) - 3) - 4
。我怎样才能达到这个结果?
解决方案
这里的技巧是定义一个aexpr_int
解析器,它首先解析一个aterm_int
,然后递归地,在一个累加表达式上使用一个辅助函数,检查多个额外出现的sign >> aterm_int
,将额外的项添加到累加器中。它可能看起来像这样:
-- the aexpr integer parser
aexpr_int :: Parser Int
aexpr_int = do
a1 <- aterm_int
go a1
where go expr =
do
s <- sign
a2 <- aterm_int
go (expr + (s * a2))
<|> return expr
连同以下内容:
-- the aterm integer parser
aterm_int :: Parser Int
aterm_int = do
a1 <- afactor_int
go a1
where go expr =
do
char '*'
a2 <- afactor_int
go (expr * a2)
<|>
do
char '/'
a2 <- afactor_int
go (div expr a2)
<|> return expr
-- afactor_int
afactor_int :: Parser Int
afactor_int = do
token (char '(')
e <- aexpr_int
token (char ')')
return e
<|>
do
s <- sign
ic <- afactor_int
return (s * ic)
<|>
token int_const
这似乎工作正常:
> parseTest aexpr_int "1-2-3-4"
-8
请注意,如果您使用真正的解析器库而不是尝试编写自己的解析器代码以用于学习目的,您将需要使用库的内置表达式解析器或名称为 或 的组合chainl
器sepBy
来完成此操作。
推荐阅读
- matlab - 在 MATLAB 中将坐标显示为 surf
- javascript - Rails x JQuery 不显示图像
- spring-mvc - Hibernate JPA 返回重复记录
- android - 将改造错误作为 gson 模型处理
- laravel - 由于 dompdf,无法在 docker 上安装 laravel/cashier
- spring - Thymeleaf switch block returns incorrect value
- python - 每次加载时的 Python 屏幕截图特定选项卡
- f# - F#使用递归一一打印列表中的所有元素
- javascript - Vue、firebase 数据库返回空数组
- php - 将点的坐标(纬度/经度)转换为“半径矩形”的坐标