使用 Parsec 在 Haskell 中编写小型解析器时出现问题

2024-01-16

我正在尝试使用以下代码为小语言编写解析器

import Text.ParserCombinators.Parsec
import Text.Parsec.Token

data Exp = Atom String | Op String Exp

instance Show Exp where
  show (Atom x) = x
  show (Op f x) = f ++ "(" ++ (show x) ++ ")"

parse_exp :: Parser Exp
parse_exp = (try parse_atom) <|> parse_op

parse_atom :: Parser Exp
parse_atom = do
  x <- many1 letter
  return (Atom x)

parse_op :: Parser Exp
parse_op = do
  x <- many1 letter
  char '(' 
  y <- parse_exp
  char ')'
  return (Op x y)

但是当我输入 ghci 时

>>> parse (parse_exp <* eof) "<error>" "s(t)"

我得到输出

Left "<error>" (line 1, column 2):
unexpected '('
expecting letter or end of input

如果我重新定义parse_exp as

parse_exp = (try parse_op) <|> parse_atom

然后我得到正确的结果

>>> parse (parse_exp <* eof) "<error>" "s(t)"
Right s(t)

但我很困惑为什么第一个不起作用。解析中此类问题是否有通用的解决方案?


当 Parsec 解析器时,比如parse_atom,在特定字符串上运行,有四种可能的结果:

  1. 它成功了,消耗了一些输入。
  2. 它失败了,消耗了一些输入。
  3. 它成功了,不消耗任何输入。
  4. 它失败了,不消耗任何输入。

在 Parsec 源代码中,这些被称为“consumed ok”、“consumed err”、“empty ok”和“empty err”(有时缩写为 cok、cerr、eok、eerr)。

当两个 Parsec 解析器用于替代方案时,例如p <|> q,这是它的解析方式。首先,Parsec 尝试解析p. Then:

  • 如果结果是“consumed ok”或“empty ok”,则解析成功,这将成为整个解析器的结果p <|> q.
  • 如果这导致“空错误”,Parsec 会尝试替代方案q,这成为整个的结果p <|> q parser.
  • 如果这导致“consumed err”,则整个解析器p <|> q失败并显示“consumed err”(cerr)。

请注意之间的关键区别p返回 cerr (这会导致整个解析器失败)与返回 eerr (这会导致替代解析器q有待尝试)。

The try函数通过将“cerr”结果转换为“eerr”结果来更改解析器的行为。

这意味着如果您尝试解析文本"s(t)"使用不同的解析器:

  • 与解析器parse_atom <|> parse_op, 解析器parse_atom返回“cok”消耗"s"并留下无法解析的文本"(t)"这会导致错误
  • 与解析器try parse_atom <|> parse_op, 解析器parse_atom still返回“cok”消耗"s", 所以try(仅将 cerr 更改为 eerr)没有任何效果,并且无法解析的文本"(t)"导致同样的错误
  • 与解析器parse_op <|> parse_atom, 解析器parse_op成功解析字符串(实际上,它没有因为递归调用parse_exp无法解析"t",但我们忽略这一点);但是,如果对文本使用相同的解析器"s", then parse_op会消耗"s"在失败之前(即 cerr),导致整个解析失败而不是尝试替代方案parse_atom
  • 与解析器try parse_op <|> parse_atom,这将解析"s(t)",与前面的示例完全相同,并且try不会有任何影响;然而,它会also处理文本"s", 因为parse_op会消耗"s"在 cerr 失败之前,然后try将通过将 cerr 转换为 eerr 来“拯救”解析,而替代方案parse_atom将被检查,成功解析(cok)原子"s".

这就是为什么您的问题的“正确”解析器是try parse_op <|> parse_atom.

请注意,这种行为不是单子解析器的基本方面。这是 Parsec(以及像 Megaparsec 这样的兼容解析器)做出的设计选择。其他一元解析器可以有不同的规则来决定如何使用<|> work.

此类 Parsec 解析问题的“一般解决方案”是要了解表达式中的事实p <|> q:

  • p首先尝试,如果成功,q会被忽略,即使q将提供“更长”或“更好”或“更合理”的解析或避免进一步的额外解析错误。在parse_atom <|> parse_op, 因为parse_atom可以在字符串上取得成功parse_op,此命令将无法正常工作。
  • q仅在以下情况下尝试p fails 不消耗输入。您必须安排p失败时不消耗任何东西,可能通过使用try,如果您期望替代方案q被检查。所以,parse_op <|> parse_atom如果parse_op在意识到无法继续并返回 cerr 之前开始消耗某些内容(例如标识符)。

作为使用的替代方案try,您还可以更仔细地考虑解析器的结构。另一种写作方式parse_exp例如,将是:

parse_exp :: Parser Exp
parse_exp = do
  -- there's always an identifier
  x <- many1 letter
  -- there *might* be an expression in parentheses
  y <- optionMaybe (parens parse_exp)
  case y of
    Nothing -> return (Atom x)
    Just y' -> return (Op x y')

  where parens = between (char '(') (char ')')

这可以写得更简洁一些,但即便如此,它也不像这样“优雅”try parse_op <|> parse_atom。 (不过,它的性能更好,因此在某些应用程序中可能需要考虑这一点。)

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

使用 Parsec 在 Haskell 中编写小型解析器时出现问题 的相关文章

  • 为什么 Haskell 中有协函子和逆变函子的区别,而范畴论却没有区别?

    这个答案是从范畴论的角度来看的 https math stackexchange com a 661989 72174包括以下语句 事实是 协函子和逆变函子之间没有真正的区别 因为每个函子只是一个协变函子 More in details a
  • 从 csv 中读取 pandas 数据帧,以非固定标头开始

    我有许多数据文件是由我的实验室中使用的一些相当黑客的脚本生成的 该脚本非常有趣 因为它在标头之前附加的行数因文件而异 尽管它们具有相同的格式并具有相同的标头 我正在编写一个批处理来将所有这些文件处理为数据帧 如果我不知道位置 如何让 pan
  • Haskell 类型系统的细微差别

    我一直在深入了解 haskell 类型系统的本质 并试图了解类型类的要点 我已经学到了很多东西 但我在下面的代码片段上遇到了困难 使用这些类和实例定义 class Show a gt C a where f Int gt a instanc
  • 将数据类型设置为 Kind * -> * 这不是函子

    布伦特 约尔吉类型分类百科全书 https www haskell org haskellwiki Typeclassopedia给出以下练习 举一个类型的例子 gt 不能将其制成 的实例Functor 不使用undefined 请告诉我什
  • 无点镜头创建不进行类型检查

    在函数中test 我遍历一个列表 从它的成员生成镜头 然后打印一些数据 当我使用有针对性的呼叫风格时 这会起作用 当我使其成为无点时 它无法进行类型检查 为什么会出现这种情况 我该如何解决这个问题 在我看来 GHC 并没有保留排名较高的信息
  • Haskell scala 互操作性

    我是 Scala 初学者 来自面向对象范式 在了解 Scala 的函数式编程部分时 我被引导到 Haskell 纯函数式编程语言 探索 SO 问题答案 我发现 Java Haskell 具有互操作性 我很想知道 Scala Haskell
  • 如何使用 SAX Java 解析器读取注释文本

    我只想使用 Java 中的 SAX 解析器读取 XML 文件中对象标记的注释 这是我的文件的摘要
  • “单词的正则表达式”(语义替换)-任何示例语法和库吗?

    我正在寻找在给定过程语言的情况下对单词而不是字符进行正则表达式样式转换的常用技术的语法示例 例如 为了追踪复制 人们可能想要创建一份具有相似含义但具有不同单词选择的文档 我希望能够简洁地定义这些可以应用于文本流的可能的转换 例如 快速地no
  • 搜索重写规则

    有什么办法可以浏览或搜索重写规则吗 当我使用像这样的标志时 ddump rule firings or ddump rule rewrites我只是得到了触发的规则的名称以及它引起的重写 但没有得到实际的规则本身 理想情况下 我想通过 GH
  • Haskell,堆栈:找到可执行文件

    我正在寻找类似的东西 stack whereis hasktags where whereis行为或多或少类似于 UNIXwhereis命令 hasktags是这样运行的 stack exec hasktags stack exec whe
  • 使用 R 读取和转换二进制原始数据

    我有一个file https drive google com file d 0BxMpk0nhnJy6SFhxd2xuMzJYYlk edit usp sharing其中包含原始 二进制数据和 ascii 它包含一个时间戳和一个代表速度的
  • 预处理后解析 C++ 源文件

    我正在尝试分析c 使用我定制的解析器的文件 写在c 在开始解析之前 我想摆脱所有 define 我希望源文件在预处理后可以编译 所以最好的方法是运行C Preprocessor在文件上 cpp myfile cpp temp cpp or
  • 在Python中连续解析文件

    我正在编写一个脚本 该脚本使用 HTTP 流量行解析文件 并取出域 目前仅将它们打印到屏幕上 我正在使用 httpry 将流量连续写入文件 这是我用来删除域名的脚本 usr bin python import re input open r
  • 如何在 Haskell 中制作打勾游戏的图案?

    实现有 2 个参数的函数 ticktick 第一个参数是自然数元组 定义游戏场地的行数和列数 第二个列表包含由玩家 x 和玩家 o 轮流玩的坐标给出的井字游戏比赛的记录 打印游戏的实际状态 其中游戏区域将由字符 和 界定 空方块 以及字符
  • Haskell / GHC - 是否有“警告不完整模式”的中缀标签/编译指示

    我正在寻找一个可以对特定的不完整模式发出警告的编译指示 它会使编译器失败并显示以下 假设的 代码 FAILIF incomplete patterns f Int gt Int f 0 0 我正在尝试使用 Arrows 编写一个 编译器 并
  • 如何在 Azure 逻辑应用中解析 Excel 电子表格

    我需要使用 Azure 逻辑应用从 Excel 电子表格中解析和提取列信息 我已经为我的逻辑应用程序设置了从 Outlook 检索最新未读电子邮件的功能 此外 我的逻辑应用程序执行 FOR EACH 来读取所有附件 来自未读电子邮件 并确保
  • 无论如何要抓取重定向的链接吗?

    无论如何 我可以让 python 单击一个链接 例如 bit ly 链接 然后抓取生成的链接吗 当我抓取某个页面时 我唯一可以抓取的链接是重定向的链接 它重定向到的位置就是我需要的信息所在的位置 重定向有 3 种类型 HTTP 作为响应标头
  • Traversable 类型类的用途

    有人可以向我解释一下类型类的目的是什么吗Traversable 类型类定义是 class Functor t Foldable t gt Traversable t gt where So Traversable is a Functor
  • QuickCheck是否可以生成任意函数

    我试图为身份编写一个 QuickCheck 测试 f y f y 我最初的计划是编写一个返回函数和整数的任意生成器 具有签名Gen Int gt Int Int 并在prop DollerDoesNothing使用 不使用测试该功能应用程序
  • 为正则表达式编写解析器

    即使经过多年的编程 我很羞愧地说我从未真正完全掌握正则表达式 一般来说 当问题需要正则表达式时 我通常可以 在一堆引用语法之后 想出一个合适的正则表达式 但我发现自己越来越频繁地使用这种技术 所以 自学并理解正则表达式properly 我决

随机推荐

  • 使用 RegEx 可靠地解析 HTML 元素 [重复]

    这个问题在这里已经有答案了 可能的重复 使用 PHP 解析 HTML 的最佳方法 https stackoverflow com questions 3577641 best methods to parse html with php 我
  • va_list的重用

    我需要对一个进行两次 或更多 次传递va list 我有一个一定大小的缓冲区 我想用 sprintf 向其中写入一个格式化字符串 如果格式化的字符串不适合分配的空间 我想将分配的空间加倍并重复直到适合为止 作为旁注 我希望能够首先计算格式化
  • 显示享受sql的日子[重复]

    这个问题在这里已经有答案了 我的查询是我有两个表 一个称为sec users包含以下字段 pk user name days available 另一个电话solicitud包含以下字段 pk solicitud fk empleado n
  • .arff 文件与 scikit-learn 一起使用吗?

    我想用一个属性关系文件格式 http www cs waikato ac nz ml weka arff html用 scikit learn 来做一些 NLP 任务 这可能吗 如何使用 arff文件与scikit learn 我真的推荐利
  • Zeppelin 上的皮肤可以自定义吗?

    Zeppelin 上的皮肤可以自定义吗 换句话说 把齐柏林飞艇的标志换成别的东西 是的 很有可能 如您所知 Apache Zeppelin 正在孵化 是一个开源项目 因此只需 克隆它来自github com apache incubator
  • 如何检查 Android 4.0+ 中自动旋转屏幕设置是否打开/关闭

    我认为每个 Android 设备都有能力打开 关闭自动旋转功能 通常你可以在以下位置找到它settings gt display gt auto rotate on off 如何从我的应用程序中读取此设置状态 我怎样才能访问这个设置值 如果
  • 根据 Winforms/C# 中的文本量和字体大小确定标签大小

    我想知道是否有更好的方法来解决这个问题 我想调整标签的大小 垂直 以容纳一定数量的文本 我的标签具有固定宽度 在必须换行之前大约 60 个字符宽 大约 495 像素 字体也是固定大小 据我所知是 12 点 但文本不是 我想要做的是当有 换行
  • 批处理脚本 - 以编程方式在 Windows XP 中创建用户

    有没有办法通过批处理脚本在 Windows XP 中创建用户 甚至为其分配管理员 有限用户值 假设用户名是 rased 密码是 passS net user rased pAsS add net localgroup administrat
  • fork()如何知道自己是在子进程还是在父进程? [关闭]

    Closed 这个问题需要多问focused help closed questions 目前不接受答案 当执行 fork 系统调用时 处理器转入内核模式 因此 在 fork 调用结束时 会生成一个新进程 其中包含调用进程的几乎所有结构的副
  • 了解 aiohttp.TCPConnector 池和连接限制

    我正在尝试limit and limit per host参数为aiohttp connector TCPConnector 在下面的脚本中 我通过connector aiohttp connector TCPConnector limit
  • 从 EPS 中提取图像数据

    我有一个封装的 PostScript http en wikipedia org wiki Encapsulated PostScript文件似乎只包装了一个图像文件 有没有工具可以从中提取图像数据 convert 将使用ghostscri
  • 发送标头后重定向用户

    据我所知 只要数据已发送到浏览器 那么标头就无法修改 有什么方法 使用 PHP 可以执行重定向以将用户带到另一个页面 显然不使用标头 如果是这样 您能给我指出一些文档吗 决定编写我自己的 php 函数来实现 javascript 重定向 请
  • 是否可以在 WPF 中使用 ReactiveUI 绑定仅通过 INotifyDataErrorInfo 验证用户输入?

    我们在 Net Core WPF 应用程序中使用 ReactiveUI WPF 11 0 1 我们正在考虑将所有基于 XAML 的绑定替换为基于 ReactiveUI 的绑定 域类型有一个 ViewModel 实现了 INotifyProp
  • Ruby on Rails 的隐藏功能 [关闭]

    就目前情况而言 这个问题不太适合我们的问答形式 我们希望答案得到事实 参考资料或专业知识的支持 但这个问题可能会引发辩论 争论 民意调查或扩展讨论 如果您觉得这个问题可以改进并可能重新开放 访问帮助中心 help reopen questi
  • UIImageWriteToSavedPhotosAlbum() 不保存裁剪后的图像

    我正在尝试将裁剪后的图像保存到相机胶卷中 我需要以编程方式完成 我不能让用户编辑它 这是我的 仍然很基本 剪切和保存代码 void cutAndSaveImage UIImage rawImage CIImage workingImage
  • JavaFX 中的磨砂玻璃效果?

    我正在制作一个 iOS 7 主题的 JavaFX 2 FXML 项目 我想知道如何使 Rectangle 对象具有类似 iOS7 的磨砂玻璃效果 我还希望它有一个小阴影 这很棘手 因为您可能能够看到半透明物体后面的阴影 我只是希望它出现在边
  • Centos 7 - openjdk8 的 jfx 库在哪里?

    我有centos 7 1 我安装了openjdk8和openjdk devel8 但是 当我尝试在 netbeans 中编译我的 jfx 应用程序时 我得到包 javafx 不存在 经过一番调查 我发现jdk中没有jfxrt jar 除了
  • 在 Archlinux 上设置 Haskell 的建议方法是什么?

    我想要一些关于让 Haskell 在 Archlinux 上工作的 最佳 方法的指导 By work我的意思是所有 就ghci命令行工具 安装我没有的软件包 例如vector space http hackage haskell org p
  • 我到底如何在rails 3中安装restful身份验证插件?

    我对 Rails 3 上的这个 Restful 身份验证插件感到非常困惑 我尝试使用以下命令安装该插件 它告诉我它已经安装了 然后我尝试使用 force重新安装这个插件它告诉我找不到该插件 所以如果插件已经安装为什么我会收到错误Could
  • 使用 Parsec 在 Haskell 中编写小型解析器时出现问题

    我正在尝试使用以下代码为小语言编写解析器 import Text ParserCombinators Parsec import Text Parsec Token data Exp Atom String Op String Exp in