示例工程【免费下载链接】fpinscalaCode, exercises, answers, and hints to go along with the book Functional Programming in Scala项目地址https://gitcode.com/gh_mirrors/fp/fpinscala点击查看免费下载导读《Functional Programming in Scala》第二版第 9 章围绕用组合子构造解析器展开其中习题 9.9 的提示answerkey/parsing/09.hint.md给出了一条极其重要的工程经验为文法中的每个 token 跳过尾部空白并用*、*忽略序列中不需要的结果。本文以该提示为核心结合仓库中Parsers.scala的完整组合子定义与JSON.scala的参考答案实现系统讲解 token 化、空白处理、结果忽略三个技法并展示它们如何让 JSON 解析器从到处处理空白的泥潭中解脱出来。读完本文你将能独立设计出可读性强、健壮性好、可复用的组合子文法。一、问题背景为什么要在文法里到处处理空白手工编写解析器时最恼人的问题之一就是空白字符空格、换行、制表符无处不在。以 JSON 为例{ Company name : Microsoft Corporation, Ticker : MSFT }{与字符串之间、:两侧、数组元素之间都可能出现任意数量的空白。如果每个文法规则都显式地写whitespace * ... * whitespace文法会迅速被whitespace淹没每个终结符后面都要跟一个可选空白解析器规则重复、难以阅读很容易漏掉某个位置的处理导致解析器对带空白的合法输入报错规则的层级关系被空白细节掩盖无法一眼看出文法结构。习题 9.9 的提示正是针对这一痛点提出的两条建议为文法中的每个 token 跳过尾部空白——引入一个组合子封装解析一个 token 并吞掉其后空白用*与*忽略序列中不需要的解析结果——例如{、}、,、:这类分隔符/定界符的结果本身毫无价值应当被忽略只保留有意义的值。这两条建议合在一起构成了本仓库解析器库中token、*、*三个组合子的设计动机。二、核心组合子定义whitespace、token、*、*仓库中组合子的权威定义位于 src/main/scala/fpinscala/answers/parsing/Parsers.scala。先看与本题直接相关的三个部分。1. 空白解析器whitespace/** Parser which consumes zero or more whitespace characters. */ def whitespace: Parser[String] regex(\\s*.r)whitespace直接由正则\s*定义匹配零个或多个空白字符。注意它匹配零个——这意味着在无空白处它也能成功消费 0 个字符这是它可以在 token 尾部安全拼接的前提。2. token 组合子解析一个 token 并吞掉尾部空白/** Attempts p and strips trailing whitespace, usually used for the tokens of a grammar. */ def token: Parser[A] p.attempt * whitespacetoken的实现只有一行却融合了两个关键动作p.attempt对p做回溯uncommit处理。attempt会把失败标记为未提交从而允许外层or/|在p失败时继续尝试其他分支避免解析true失败后把错误锁死。其底层实现在 Reference.scala 中def attempt: Parser[A] l p(l).uncommituncommit将Failure(e, true)改写为Failure(e, false)* whitespace在p成功后消费掉其后所有空白。token的效果是该 token 本身 紧随其后的所有空白被当作一个整体消费。于是文法的其余部分再也不必关心空白——下一个 token 解析时当前位置已经站在空白之后。补充说明Reference实现中regex的失败是天然未提交的见regex定义中Failure(l.toError(sregex $r), false)而string的部分匹配会提交失败i ! 0因此对字符串 token 使用attempt尤为重要它保证了lit中null | double | escapedQuoted | true | false这类分支选择能正确回溯。3. 序列组合子*与*忽略不需要的结果/** Sequences two parsers, ignoring the result of the first. * We wrap the ignored half in slice, since we dont care about its result. */ def *B p.slice.map2(p2)((_, b) b) /** Sequences two parsers, ignoring the result of the second. * We wrap the ignored half in slice, since we dont care about its result. */ def *(p2: Parser[Any]) p.map2(p2.slice)((a, b) a)p * p2依次运行p和p2丢弃p的结果返回p2的结果p * p2依次运行p和p2丢弃p2的结果返回p的结果。两个实现都把被忽略的一侧用slice包起来。slice在 Sliceable.scala 中有专门优化通过ParseState上的isSliced标志被忽略的部分只记录消费长度、不构建无用的中间值Result.Slice(length)从而避免为丢弃的结果分配对象。这正是忽略结果不只是一种写法糖、而是一种真实性能优化的体现。此外提示提到的**是product的别名def **B: Parser[(A,B)] product(p2)当我们需要同时保留两个解析结果如键值对escapedQuoted ** (token(:) * value)时使用**当只需其中一个结果时则用*/*显式表达意图。三、实战把技巧应用到 JSON 文法习题 9.9 要求用这些组合子实现一个 JSON 解析器。参考答案位于 src/main/scala/fpinscala/answers/parsing/JSON.scala其中token、*、*被大量使用。1. 定义局部 token 辅助函数def token(s: String) string(s).token先用一个局部函数把字符串字面量 token 语义绑定在一起之后写token([)、token(:)、token(null)即可简洁且意图明确。2. 数组定界符全部忽略只保留元素def array: Parser[JSON] ( token([) * value.sep(token(,)).map(vs JArray(vs.toIndexedSeq)) * token(]) ).scope(array)逐层拆解token([) *消费[及其后空白丢弃结果value.sep(token(,))解析用逗号分隔的 value 列表。sep的定义是p.sep1(separator) | succeed(Nil)其中separator类型为Parser[Any]——因为分隔符结果无关紧要token(,)恰好满足这一要求* token(])消费]及尾部空白丢弃结果外层.scope(array)为该分支失败时压入上下文错误信息scope调用mapError(_.push(l, msg))错误报告中会显示1.1 array之类的定位。由于token已吞掉空白[ HPQ , IBM ]这类逗号前后带空格的写法无需任何额外规则即可通过。3. 对象与键值对def obj: Parser[JSON] ( token({) * keyval.sep(token(,)).map(kvs JObject(kvs.toMap)) * token(}) ).scope(object) def keyval: Parser[(String, JSON)] escapedQuoted ** (token(:) * value)对象主体与数组同构{、,、}的结果全部被*/*忽略keyval.sep(...)只关心键值对列表键值对keyval用**组合键和值键escapedQuoted的结果保留冒号token(:) *的结果丢弃值value的结果保留最终得到(String, JSON)二元组再toMap组装成JObject。这里恰好体现了提示中什么时候用**、什么时候用*的分工需要的结果用**保留定界符/分隔符用*或*丢弃。4. 字面量多个候选分支的 token 化def lit: Parser[JSON] ( token(null).as(JNull) | double.map(JNumber(_)) | escapedQuoted.map(JString(_)) | token(true).as(JBool(true)) | token(false).as(JBool(false)) ).scope(literal)token(null).as(JNull)as的定义是p.slice.map(_ b)把null映射为JNulldouble本身是数字 tokendoubleString定义regex([-]?([0-9]*\\.)?[0-9]([eE][-]?[0-9])?.r).token其内部已经带.token因此double能直接处理30.66、8.38e9等数字后紧跟空白的情况escapedQuoted定义为quoted.label(string literal).token同样内建 token 语义多分支靠|即or连接token内的attempt保证了失败分支可回溯、不会误报。value与根解析def value: Parser[JSON] lit | obj | array (whitespace * (obj | array)).root根规则先whitespace *吞掉输入最前面的空白再解析对象或数组最后.root定义为p * eof要求输入在结束后不能有多余字符否则报unexpected trailing characters。5. 完整 JSON 数据类型解析的目标类型定义在 src/main/scala/fpinscala/answers/parsing/JSON.scala 顶部enum JSON: case JNull case JNumber(get: Double) case JString(get: String) case JBool(get: Boolean) case JArray(get: IndexedSeq[JSON]) case JObject(get: Map[String, JSON])所有文法规则最终都折叠到这个代数数据类型上JArray的IndexedSeq由vs.toIndexedSeq转换JObject的Map由kvs.toMap构建。四、在 Reference 底层实现中验证组合子语义为了理解token、*、*为什么能各司其职值得回到它们展开后的底层原语上看一眼。Reference.scala 中string用firstNonmatchingIndex比较输入与目标串完全匹配返回Success(w, w.length)不匹配则Failure(l.advanceBy(i).toError(s$w), i ! 0)——第二个参数i ! 0正是是否提交的标志只要在目标串中间失败就提交阻止or继续尝试attemptl p(l).uncommit把已提交失败降级为未提交允许分支回溯orcase Failure(e, false) p2(l); case r r只对未提交失败尝试第二个分支flatMap成功时f(a)(l.advanceBy(n)).addCommit(n ! 0).advanceSuccess(n)只要第一个解析器消费了字符n ! 0后续失败即被提交。由此可以看出token p.attempt * whitespace的妙处attempt让 token 在自身失败时可回溯* whitespace在成功时多消费空白——失败时不吞空白便于回退成功时才吞空白便于后续解析这一成功才消费的行为是文法保持回溯正确性的关键。五、测试验证从正确输入到畸形输入仓库在 src/test/scala/fpinscala/exercises/parsing/JSONSuite.scala 中为 JSON 解析器提供了系统的属性测试基于PropSuite可作为验证token/*/*组合子正确性的直接证据各类型覆盖JNull、JNumber用Gen.double生成随机浮点数、JString、JBool、JArray含嵌套数组、JObject含多层嵌套对象与数组所有测试输入都带有空白缩进例如jObjectJson1直接使用与jsonExample相同的多行 JSON 文本malformed JSONs测试专门枚举了一组畸形输入缺少闭合括号、;代替:、数组元素缺少逗号、等断言parser.run(json).isLeft——这组用例正好验证了定界符结果被忽略、但定界符本身必须严格匹配的文法语义。运行时入口在JSON.scala的main def jsonExample它对合法 JSON 与两个畸形 JSON 分别调用JSON.jsonParser(Reference).run(...)打印结果可直观看到成功解析出的JObject/JArray结构与错误报告ParseError.toString会输出行.列定位、错误栈折叠及^光标指向。六、总结与延伸回到习题 9.9 的提示两条建议可以概括为一句话token 负责把空白从文法中抹掉*/*负责把噪声从结果中抹掉。二者叠加使文法得以用最少的符号表达真正的结构token([) * value.sep(token(,)) * token(]) // 数组 token({) * keyval.sep(token(,)) * token(}) // 对象 escapedQuoted ** (token(:) * value) // 键值对token是终结符 尾部空白的封装配合attempt保证失败可回溯*/*让定界符、分隔符的存在感降到最低只留下value、keyval等有意义的解析结果sep接受Parser[Any]分隔符与token天然搭配。这些组合子在习题 9.10 之后的实现中继续演进例如 Sliceable.scala 引入isSliced状态与Result.Slice构造子让被slice包裹的部分免于构造无用值但token 化 结果忽略的设计思想始终贯穿整个解析器库。读者可以继续阅读 Parsers.scala 中sep、sep1、opL、root等组合子的实现以及 UnitTestParser.scala 中供测试用的完整解析器实例从而在习题与答案之间建立起完整的理解闭环。赞分享示例工程【免费下载链接】fpinscalaCode, exercises, answers, and hints to go along with the book Functional Programming in Scala项目地址https://gitcode.com/gh_mirrors/fp/fpinscala点击查看免费下载相关推荐用 flatMap 与 map 组合实现 Option.map2fpinscala 错误处理章节组合子设计精讲用 flatMap 与 map 组合实现 Option.map2fpinscala 错误处理章节组合子设计精讲 导读 本文围绕《Functional Prog示例工程fpinscala 习题 24 精解用 startsWith 组合出尾递归的 hasSubsequence 子序列判定fpinscala 习题 24 精解用 startsWith 组合出尾递归的 hasSubsequence 子序列判定 本篇围绕《Functional Pro示例工程fpinscala 习题 08 精解用 Follow the types 推导 Applicative 的 product 组合子fpinscala 习题 08 精解用 Follow the types 推导 Applicative 的 product 组合子 导读 本文围绕《Fun示例工程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考