/LALR(1) 解析器)
基于 iTerm2 仓库中 CoreParse 解析框架的实战指南Tokeniser、BNF 文法与 SLR/LR(1)/LALR(1) 解析器【免费下载链接】iTerm2iTerm2 is a terminal emulator for Mac OS X that does amazing things.项目地址: https://gitcode.com/gh_mirrors/it/iTerm2本指南以 ThirdParty/CoreParse/README.md 为核心结合仓库内 CoreParse 框架源码与 iTerm2 主程序sources/下的表达式解析器的真实用法讲解如何用 CoreParse 完成词法分析Tokenisation、BNF 文法定义与语法分析Parsing以及 SLR / LR(1) / LALR(1) 三类 shift/reduce 解析器的选型与性能策略。读完本文你可以在自己的 Objective-C / Swift 项目中从零搭建一个完整的词法分析器 语法分析器并了解 iTerm2 是如何用它解析表达式与函数调用的。CoreParse 是一个面向 Mac OS X 与 iOS 的解析库仓库内以完整可构建的 Xcode 工程形式随附于 ThirdParty/CoreParse含源码、测试与 LICENSE。它基于 shift/reduce 移进-归约解析机制支持 SLR、LR(1) 与 LALR(1) 三类解析器覆盖了大多数实用编程语言文法LR(1) 文法集合包含全部 LL(1) 文法且更多。本指南将复现 README 中的数值表达式求值完整示例并逐层剖析其背后的实现机制。一、为什么要使用 CoreParse与现有方案的对比README 从两个维度给出了选型理由这些判断与仓库中CPParser的实现结构相互印证。与 ParseKit 相比语言覆盖更广LR(1) 文法覆盖所有 LL(1) 文法且更多实践中 LALR(1) 文法即可覆盖大多数实用语言。ParseKit 主要基于 LL 文法。解析器更快CoreParse 生成的是查表驱动的 shift/reduce 解析器见CPShiftReduceParser家族运行期不含递归下降的开销。可归档CoreParse 的 parser 与 tokeniser 都遵循NSCoding协议CPTokeniser、CPGrammar、CPParser均声明NSCoding可用NSKeyedArchiver序列化到磁盘避免每次启动重复生成解析表。非递归算法解析算法不依赖调用栈递归理论上可处理非常深的语言层级结构而不会栈溢出。与 lex/yacc、flex/bison 相比README 坦承未经基准测试lex/yacc 生成的解析器预计更快。不强制预编译CoreParse 允许运行时才从文法构建解析器虽然推荐预生成并归档。文法内嵌于 Objective-C 源码BNF 直接用NSString写在源码里不需要引入第二种编译语言避免了 C/Obj-C 代码混杂。无全局状态多个 parser 实例可以并行运行同一个 parser 实例也可以并行解析多个 token 流。从源码看CPParser.h 的状态完全封装在实例内部CPTokeniser.h 甚至提供了tokenise:into:方法允许把预分配的 token 流同时交给 tokeniser 线程与 parser 线程——这正是为多线程解析设计的接口。已知实际使用案例README 列出了三个公开使用者CSS 选择器转换器Francis Chong、statec 状态机规格解析Matt Mower、OpenStreetPad 的 MapCSS 解析。而在本仓库内CoreParse 还有更重量级的落地场景iTerm2 自身的表达式与函数调用解析器见下文第四节。二、CoreParse 框架源码结构速览在动手编码前先了解框架的分层结构对应仓库目录CoreParse.h统一头文件导入全部公开接口。Tokenisation/词法分析。含 CPTokeniser.h、CPTokenStream以及两类子目录Token Recognisers/识别器包括CPKeywordRecogniser、CPNumberRecogniser、CPWhiteSpaceRecogniser、CPIdentifierRecogniser、CPQuotedRecogniser、CPRegexpRecogniser。Token Types/Token 类型包括CPToken基类及CPKeywordToken、CPNumberToken、CPWhiteSpaceToken、CPQuotedToken、CPIdentifierToken、CPErrorToken、CPEOFToken。Grammar/文法表示。CPGrammar.h 定义上下文无关文法CPRule、CPGrammarSymbol、CPRHSItem支撑 BNF/EBNF 描述的内部建模。Parsers/解析器。基类 CPParser.h具体实现位于CPShiftReduceParsers/CPSLRParser、CPLR1Parser、CPLALR1Parser以及动作表CPShiftReduceActionTable、goto 表、移进/归约状态CPShiftReduceStateError Recovery/提供CPRecoveryAction错误恢复。Syntax Tree/语法树节点 CPSyntaxTree.h。Built In Parsers/开箱即用的 CPJSONParser.h JSON 解析器README 提到的演示性内置解析器。CoreParseTests/完整测试套件其中 Expression.m 就是 README 数值表达式例子的可运行实现另有Expression2、Term、Term2、RuleBase等辅助类与各类 delegate 测试桩。三、从零构建词法分析器TokenisationCoreParse 的词法分析器类是CPTokeniser。其核心思想是按优先级顺序注册一组 token 识别器CPTokenRecognisertokeniser 在输入字符串的每个位置按优先级依次尝试匹配命中后回调 delegate 决定是否产出 token。3.1 注册识别器注意优先级以 README 的数值表达式语言为例——包含数字、空白、注释与若干符号CPTokeniser *tokeniser [[[CPTokeniser alloc] init] autorelease]; [tokeniser addTokenRecogniser:[CPNumberRecogniser numberRecogniser]]; [tokeniser addTokenRecogniser:[CPWhiteSpaceRecogniser whiteSpaceRecogniser]]; [tokeniser addTokenRecogniser:[CPQuotedRecogniser quotedRecogniserWithStartQuote:/* endQuote:*/ name:Comment]]; [tokeniser addTokenRecogniser:[CPKeywordRecogniser recogniserForKeyword:]]; [tokeniser addTokenRecogniser:[CPKeywordRecogniser recogniserForKeyword:-]]; [tokeniser addTokenRecogniser:[CPKeywordRecogniser recogniserForKeyword:*]]; [tokeniser addTokenRecogniser:[CPKeywordRecogniser recogniserForKeyword:/]]; [tokeniser addTokenRecogniser:[CPKeywordRecogniser recogniserForKeyword:(]]; [tokeniser addTokenRecogniser:[CPKeywordRecogniser recogniserForKeyword:)]];README 特别强调注释识别器必须注册在除号/关键字识别器之前。因为识别器按优先级顺序尝试若除号先注册遇到/* ... */注释时首字符/会被当作除法运算符吞掉把CPQuotedRecogniser前置注释的第一个斜杠才能被正确识别为注释开头。这是理解CPTokeniser优先级模型的关键点。从源码看CPTokeniser.h 提供了三档注册 APIaddTokenRecogniser:追加到优先级队列末尾insertTokenRecogniser:atPriority:插入到指定优先级该位置及以下的识别器整体下移priority 越界抛NSRangeExceptioninsertTokenRecogniser:beforeRecogniser:插入到某个识别器之前nil或不在队列中则抛NSInvalidArgumentException。在 iTerm2 的真实代码 iTermExpressionParser.m 中可以看到同一条规则的实践OptionalPath识别器必须先于标识符与?关键字注册否则name?会被拆成两个 token多字符运算符、!、、、、||必须先于单字符、注册否则会被拆成两个。这与 README 中按优先级添加识别器的原则完全一致。3.2 通过 delegate 过滤 token接下来把对象自身设为 tokeniser 的 delegate实现CPTokeniserDelegate协议定义见 CPTokeniser.h让空白与注释被消费但不进入输出流- (BOOL)tokeniser:(CPTokeniser *)tokeniser shouldConsumeToken:(CPToken *)token { return YES; } - (void)tokeniser:(CPTokeniser *)tokeniser requestsToken:(CPToken *)token pushedOntoStream:(CPTokenStream *)stream { if (![token isWhiteSpaceToken] ![[token name] isEqualToString:Comment]) { [stream pushToken:token]; } }两个回调的职责与CPTokeniserDelegate头文件注释一致tokeniser:shouldConsumeToken:必选决定 tokeniser 是否消费该 token 对应的输入文本。返回NO时tokeniser 会在同一位置继续尝试其余识别器返回YES才消费并进入产出阶段。tokeniser:requestsToken:pushedOntoStream:可选推荐在此将 token 推入输出流可换一个 token或完全不输出上例即利用该回调丢弃空白与注释。头文件中还有一个被标记废弃的tokeniser:willProduceToken:返回数组形式新代码应使用requestsToken:pushedOntoStream:。此外该协议还提供两个进阶回调tokeniser:didNotFindTokenOnInput:position:error:用于处理任何识别器都无法匹配当前位置的情况可返回新位置继续或返回NSNotFound终止并可写出错误信息到CPErrorTokentokeniserWillFinish:stream:允许在EOFtoken 推入前追加 token头文件注释中举的例子是 Python tokeniser 追加作用域闭合 token。3.3 调用 tokeniserCPTokenStream *tokenStream [tokeniser tokenise:5 (2.0 / 5.0 9) * 8];tokenise:会返回一个CPTokenStream如果整个输入被完整 tokenise流末尾会追加一个CPEOFToken表示输入结束若中途失败则无 EOF token。多线程场景可用tokenise:into:写入预分配的流把该流同时传给 tokeniser 线程与 parser 线程。四、用 BNF 文法构建解析器Parsing4.1 用 BNF 字符串描述文法CPGrammar支持用类 BNF 的 DSL 直接描述文法。README 示例NSString *expressionGrammar Expression :: termTerm | exprExpression opAddOp termTerm; Term :: factFactor | factFactor opMulOp termTerm; Factor :: numNumber | ( exprExpression ); AddOp :: | -; MulOp :: * | /;; NSError *err; CPGrammar *grammar [CPGrammar grammarWithStart:Expression backusNaurForm:expressionGrammar error:err]; if (nil grammar) { NSLog(Error creating grammar:); NSLog(%, err); } else { CPParser *parser [CPLALR1Parser parserWithGrammar:grammar]; [parser setDelegate:self]; ... }文法语法要点详见 CPGrammar.h 头文件注释中的 BNF 元文法定义规则形式nonTerminal :: 产生式;多个备选产生式用|分隔每条规则以;结束。非终结符用尖括号包裹如Term终结符用引号包裹如Number终结符名称对应 token 名称——这里Number正是CPNumberRecogniser产出的 token 名。标签tagtagNonTerminal或tagTerminal形式如exprExpression、opAddOp、numNumber。标签语义上等价于直接写NonTerminal但便于后续从语法树快速取回对应子节点的值。一个规则项可以打多个标签例如range :: minNumber - maxNumber | ... | minmaxNumber。EBNF 扩展规则项后可跟*0 次或多次、1 次或多次、?0 次或 1 次支持括号分组子规则。使用这些 EBNF 结构时parser 返回的结果是NSArray。错误处理推荐使用带error:参数的grammarWithStart:backusNaurForm:error:旧的grammarWithStart:backusNaurForm:已被标记废弃只打印错误。错误域为CPEBNFParserErrorDomain错误码包括CPErrorCodeCouldNotParseEBNFBNF 无法解析1、CPErrorCodeDuplicateTag标签重复2、CPErrorCodeUndefinedNonTerminal引用了未定义的非终结符3。4.2 让解析结果变成你的数据模型CoreParse 的两条产出路径机制见 CPParser.h结果类 CPParseResult协议当一条规则被归约时CoreParse 会尝试以规则左部非终结符命名的类如Expression、Term、Factor新建实例并调用其initWithSyntaxTree:方法。parser delegate 兜底若不存在对应类则调用 delegate 的parser:didProduceSyntaxTree:方法。README 中为Expression、Term、Factor各实现了一个类AddOp、MulOp交由 delegate 处理。Expression的initWithSyntaxTree:实现- (id)initWithSyntaxTree:(CPSyntaxTree *)syntaxTree { self [self init]; if (nil ! self) { Term *t [syntaxTree valueForTag:term]; Expression *e [syntaxTree valueForTag:expr]; if (nil e) { [self setValue:[t value]]; } else if ([[syntaxTree valueForTag:op] isEqualToString:]) { [self setValue:[e value] [t value]]; } else { [self setValue:[e value] - [t value]]; } } return self; }CPSyntaxTreeCPSyntaxTree.h是语法树节点携带归约所用的CPRule、子节点children与标签值tagValuesvalueForTag:按标签名取回子语法树/值——README 用它区分单产生式Expression - Term与二元运算产生式childAtIndex:按下标取子节点还有rule、children、tagValues三个只读属性可遍历整棵树。需要说明的是仓库测试套件中的 Expression.m 给出了该类的实际可运行版本其实现略有不同——它通过[syntaxTree children]的数量判断是单元素产生式还是二元运算产生式count 1时直接取Term的值否则取Expression Term做加法。这印证了两种风格皆可行标签方式更直观按下标/子节点数组方式更贴近规则结构两种方式 README 与测试均有覆盖。delegate 处理运算符非终结符- (id)parser:(CPParser *)parser didProduceSyntaxTree:(CPSyntaxTree *)syntaxTree { return [(CPKeywordToken *)[syntaxTree childAtIndex:0] keyword]; }即把AddOp/MulOp归约出的语法树直接替换为底层CPKeywordToken的关键字字符串、-、*、/供上层Expression/Term的判断逻辑使用。这正是 CPParser.h 中CPParserDelegate的用途用 delegate 把产生的语法树替换成你想要的任何数据结构。头文件注释还点明了一个优化思路数值表达式解析器的 delegate 可以边解析边求值把每个语法树直接替换为结果NSNumber一趟完成解析与计算。4.3 执行解析NSLog(%f, [(Expression *)[parser parse:tokenStream] value]);输出80.2CPParser的parse:方法CPParser.h接收CPTokenStream返回整条流对应的语法树或自定义对象解析失败返回nil并用NSLog记录错误。注意CPParser是抽象基类必须使用其子类CPSLRParser/CPLR1Parser/CPLALR1Parser构建实例。4.4 错误恢复进阶CPParserDelegate还提供错误处理入口parser:didEncounterErrorOnInput:expecting:旧签名parser:didEncounterErrorOnInput:已废弃当 parser 遇到既不能移进、也不能归约、也不能接受的 token 时被调用。参数acceptableTokens是当前状态下能让 parser 继续前进的 token 名集合。方法返回一个CPRecoveryAction定义于Parsers/Error Recovery/CPRecoveryAction.h执行恢复返回nil时若问题 token 是CPErrorToken解析栈会回退一层交给父规则处理。仓库的CoreParseTests/中提供了CPTestErrorHandlingDelegate、CPTestErrorEvaluatorDelegate等测试桩验证该机制。五、解析器选型与最佳实践Best Practices5.1 三类 shift/reduce 解析器的权衡README 给出的权威对比与三个具体子类的头文件注释完全一致见 CPSLRParser.h、CPLR1Parser.h、CPLALR1Parser.h解析器语言覆盖生成速度运行速度内存适用建议SLR最小最快最快低默认首选LR(1)最大慢慢高显著仅在极端情况下使用LALR(1)几乎与 LR(1) 相同比 SLR 慢与 SLR 相当与 SLR 相当文法在 SLR 下无法生成时的升级选择推荐路径先试 SLR 解析器除非你明确知道文法需要更强的能力当文法无法生成解析器时升级到 LALR(1)。LR(1) 虽然覆盖语言集合最大但内存占用大、速度慢README 明确不推荐仅限极端场景。5.2 用 NSKeyedArchiver 缓存解析器解析表生成尤其是 LALR(1)可能耗时。README 强烈建议对于需要 LALR(1) 的较大文法用NSKeyedArchiver把解析器归档到文件运行时直接反归档避免每次启动都重新生成。这一建议在框架设计上是有保证的CPTokeniser、CPGrammar、CPParser全家都实现了NSCoding。iTerm2 主程序把这一实践做成了完整的工程化方案——CPParserCache.m 中实现了基于NSKeyedArchiver的解析器磁盘缓存以App 版本号 parser 类名 BNF 内容哈希 起始符号组合成缓存 keyit_keyWithBNF:start:保证文法变化后缓存自动失效查找顺序进程内内存缓存 → 磁盘缓存文件位于 caches 目录parsers/下用NSKeyedArchiver以二进制属性列表格式写出→ 现场构建并写盘parser 释放时it_releaseParser会归还到内存缓存池供后续复用。这正是 README归档解析器避免重复生成建议的生产级落地同时也验证了 CoreParse parser 可被归档/反归档的能力。六、iTerm2 中的真实应用表达式与函数调用解析作为补充佐证本仓库中 CoreParse 的实际消费方是 iTerm2 自身的表达式解析器 iTermExpressionParser.m其使用模式与 README 示例一一对应tokeniser 组装newTokenizer方法同文件第 155 行起按严格优先级注册CPKeywordRecogniser运算符、括号、true/false、CPNumberRecogniser、CPWhiteSpaceRecogniser、CPIdentifierRecogniser并组合自定义识别器iTermOptionalPathRecognizer与iTermSwiftyStringRecognizer继承自 CoreParse 的CPQuotedRecogniser带转义序列处理见同文件addSwiftyStringRecognizers与setEscapeReplacerInStringRecognizer文法与解析器通过iTermGrammarProcessoriTermGrammarProcessor.h负责组装 BNF 规则并运行转换块产出backusNaurForm再调用CPLALR1Parser parserWithBNF:start:构建 LALR(1) 解析器——对应 README 中较大文法用 LALR(1)的建议结果转化parser 与 tokeniser 的 delegate 都是iTermExpressionParser自身把语法树转换为iTermParsedExpression等模型对象——即 README用 delegate 把语法树替换为数据模型的实践解析器实例以单例缓存expressionParser/callParser两个 dispatch_once 单例并配合上述CPParserCache做磁盘级归档复用。此外iTerm2 对 CoreParse 识别器还做了针对自身语法的扩展sources/Language/iTermQuotedRecognizer.h、sources/Language/iTermTruncatedQuotedRecognizer.h、sources/Language/iTermSwiftyStringRecognizer.h等均派生自 CoreParse 的识别器体系在iTerm2SharedARC-Bridging-Header.h中统一导入说明 CoreParse 的扩展点delegate 协议、识别器子类化在实际工程中是经得起考验的。七、内置解析器与测试资源若你只想快速验证 CoreParse 的能力仓库提供了开箱即用的 JSON 解析器 CPJSONParser.hparse:方法把 JSON 字符串解析为标准 Objective-C 数据结构数字与布尔 →NSNumber字符串 →NSStringnull→NSNull数组 →NSArray对象 →NSDictionary。注意其实现刻意不支持 Unicode 转义字符——头文件说明这仅用于演示 CoreParse 用法Unicode 处理与演示主题无关故略去。完整的测试套件位于 ThirdParty/CoreParse/CoreParseTests/覆盖表达式求值Expression.m、Expression2.m、Term.m、Term2.m、RuleBase.m正则识别器CPRegexpRecogniserTest.m各类 delegate 行为求值、错误处理、忽略空白、MapCSS tokenising 等测试桩结束回调CPWillFinishDelegateTest.m对应tokeniserWillFinish:stream:。这些测试文件是理解 README 示例在真实工程中如何组织类与 delegate 的最佳范本。八、结语一个示例三步套路回顾 README 的完整流程CoreParse 的使用可以凝练为三步词法分析创建CPTokeniser按优先级注册识别器长匹配/注释优先通过 delegate 过滤无意义 token产出CPTokenStream文法与解析用 BNF/EBNF 字符串构造CPGrammar可带标签与*//?扩展选择 SLR / LR(1) / LALR(1) 解析器结果映射为规则左部非终结符实现initWithSyntaxTree:类或用CPParserDelegate把语法树替换为自定义模型——甚至可以在这一阶段边解析边求值。在此基础上借鉴 iTerm2 的做法单例复用、NSKeyedArchiver 磁盘缓存、多字符运算符识别器优先级处理即可把 CoreParse 稳定地嵌入真实应用。深入实现细节可继续研读 ThirdParty/CoreParse/README.md、CPGrammar.h、CPTokeniser.h 与 CPParser.h 的完整文档注释。【免费下载链接】iTerm2iTerm2 is a terminal emulator for Mac OS X that does amazing things.项目地址: https://gitcode.com/gh_mirrors/it/iTerm2创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 基于 iTerm2 仓库中 CoreParse 解析框架的实战指南：Tokeniser、BNF 文法与 SLR/LR(1)/LALR(1) 解析器
基于 iTerm2 仓库中 CoreParse 解析框架的实战指南Tokeniser、BNF 文法与 SLR/LR(1)/LALR(1) 解析器【免费下载链接】iTerm2iTerm2 is a terminal emulator for Mac OS X that does amazing things.项目地址: https://gitcode.com/gh_mirrors/it/iTerm2本指南以 ThirdParty/CoreParse/README.md 为核心结合仓库内 CoreParse 框架源码与 iTerm2 主程序sources/下的表达式解析器的真实用法讲解如何用 CoreParse 完成词法分析Tokenisation、BNF 文法定义与语法分析Parsing以及 SLR / LR(1) / LALR(1) 三类 shift/reduce 解析器的选型与性能策略。读完本文你可以在自己的 Objective-C / Swift 项目中从零搭建一个完整的词法分析器 语法分析器并了解 iTerm2 是如何用它解析表达式与函数调用的。CoreParse 是一个面向 Mac OS X 与 iOS 的解析库仓库内以完整可构建的 Xcode 工程形式随附于 ThirdParty/CoreParse含源码、测试与 LICENSE。它基于 shift/reduce 移进-归约解析机制支持 SLR、LR(1) 与 LALR(1) 三类解析器覆盖了大多数实用编程语言文法LR(1) 文法集合包含全部 LL(1) 文法且更多。本指南将复现 README 中的数值表达式求值完整示例并逐层剖析其背后的实现机制。一、为什么要使用 CoreParse与现有方案的对比README 从两个维度给出了选型理由这些判断与仓库中CPParser的实现结构相互印证。与 ParseKit 相比语言覆盖更广LR(1) 文法覆盖所有 LL(1) 文法且更多实践中 LALR(1) 文法即可覆盖大多数实用语言。ParseKit 主要基于 LL 文法。解析器更快CoreParse 生成的是查表驱动的 shift/reduce 解析器见CPShiftReduceParser家族运行期不含递归下降的开销。可归档CoreParse 的 parser 与 tokeniser 都遵循NSCoding协议CPTokeniser、CPGrammar、CPParser均声明NSCoding可用NSKeyedArchiver序列化到磁盘避免每次启动重复生成解析表。非递归算法解析算法不依赖调用栈递归理论上可处理非常深的语言层级结构而不会栈溢出。与 lex/yacc、flex/bison 相比README 坦承未经基准测试lex/yacc 生成的解析器预计更快。不强制预编译CoreParse 允许运行时才从文法构建解析器虽然推荐预生成并归档。文法内嵌于 Objective-C 源码BNF 直接用NSString写在源码里不需要引入第二种编译语言避免了 C/Obj-C 代码混杂。无全局状态多个 parser 实例可以并行运行同一个 parser 实例也可以并行解析多个 token 流。从源码看CPParser.h 的状态完全封装在实例内部CPTokeniser.h 甚至提供了tokenise:into:方法允许把预分配的 token 流同时交给 tokeniser 线程与 parser 线程——这正是为多线程解析设计的接口。已知实际使用案例README 列出了三个公开使用者CSS 选择器转换器Francis Chong、statec 状态机规格解析Matt Mower、OpenStreetPad 的 MapCSS 解析。而在本仓库内CoreParse 还有更重量级的落地场景iTerm2 自身的表达式与函数调用解析器见下文第四节。二、CoreParse 框架源码结构速览在动手编码前先了解框架的分层结构对应仓库目录CoreParse.h统一头文件导入全部公开接口。Tokenisation/词法分析。含 CPTokeniser.h、CPTokenStream以及两类子目录Token Recognisers/识别器包括CPKeywordRecogniser、CPNumberRecogniser、CPWhiteSpaceRecogniser、CPIdentifierRecogniser、CPQuotedRecogniser、CPRegexpRecogniser。Token Types/Token 类型包括CPToken基类及CPKeywordToken、CPNumberToken、CPWhiteSpaceToken、CPQuotedToken、CPIdentifierToken、CPErrorToken、CPEOFToken。Grammar/文法表示。CPGrammar.h 定义上下文无关文法CPRule、CPGrammarSymbol、CPRHSItem支撑 BNF/EBNF 描述的内部建模。Parsers/解析器。基类 CPParser.h具体实现位于CPShiftReduceParsers/CPSLRParser、CPLR1Parser、CPLALR1Parser以及动作表CPShiftReduceActionTable、goto 表、移进/归约状态CPShiftReduceStateError Recovery/提供CPRecoveryAction错误恢复。Syntax Tree/语法树节点 CPSyntaxTree.h。Built In Parsers/开箱即用的 CPJSONParser.h JSON 解析器README 提到的演示性内置解析器。CoreParseTests/完整测试套件其中 Expression.m 就是 README 数值表达式例子的可运行实现另有Expression2、Term、Term2、RuleBase等辅助类与各类 delegate 测试桩。三、从零构建词法分析器TokenisationCoreParse 的词法分析器类是CPTokeniser。其核心思想是按优先级顺序注册一组 token 识别器CPTokenRecognisertokeniser 在输入字符串的每个位置按优先级依次尝试匹配命中后回调 delegate 决定是否产出 token。3.1 注册识别器注意优先级以 README 的数值表达式语言为例——包含数字、空白、注释与若干符号CPTokeniser *tokeniser [[[CPTokeniser alloc] init] autorelease]; [tokeniser addTokenRecogniser:[CPNumberRecogniser numberRecogniser]]; [tokeniser addTokenRecogniser:[CPWhiteSpaceRecogniser whiteSpaceRecogniser]]; [tokeniser addTokenRecogniser:[CPQuotedRecogniser quotedRecogniserWithStartQuote:/* endQuote:*/ name:Comment]]; [tokeniser addTokenRecogniser:[CPKeywordRecogniser recogniserForKeyword:]]; [tokeniser addTokenRecogniser:[CPKeywordRecogniser recogniserForKeyword:-]]; [tokeniser addTokenRecogniser:[CPKeywordRecogniser recogniserForKeyword:*]]; [tokeniser addTokenRecogniser:[CPKeywordRecogniser recogniserForKeyword:/]]; [tokeniser addTokenRecogniser:[CPKeywordRecogniser recogniserForKeyword:(]]; [tokeniser addTokenRecogniser:[CPKeywordRecogniser recogniserForKeyword:)]];README 特别强调注释识别器必须注册在除号/关键字识别器之前。因为识别器按优先级顺序尝试若除号先注册遇到/* ... */注释时首字符/会被当作除法运算符吞掉把CPQuotedRecogniser前置注释的第一个斜杠才能被正确识别为注释开头。这是理解CPTokeniser优先级模型的关键点。从源码看CPTokeniser.h 提供了三档注册 APIaddTokenRecogniser:追加到优先级队列末尾insertTokenRecogniser:atPriority:插入到指定优先级该位置及以下的识别器整体下移priority 越界抛NSRangeExceptioninsertTokenRecogniser:beforeRecogniser:插入到某个识别器之前nil或不在队列中则抛NSInvalidArgumentException。在 iTerm2 的真实代码 iTermExpressionParser.m 中可以看到同一条规则的实践OptionalPath识别器必须先于标识符与?关键字注册否则name?会被拆成两个 token多字符运算符、!、、、、||必须先于单字符、注册否则会被拆成两个。这与 README 中按优先级添加识别器的原则完全一致。3.2 通过 delegate 过滤 token接下来把对象自身设为 tokeniser 的 delegate实现CPTokeniserDelegate协议定义见 CPTokeniser.h让空白与注释被消费但不进入输出流- (BOOL)tokeniser:(CPTokeniser *)tokeniser shouldConsumeToken:(CPToken *)token { return YES; } - (void)tokeniser:(CPTokeniser *)tokeniser requestsToken:(CPToken *)token pushedOntoStream:(CPTokenStream *)stream { if (![token isWhiteSpaceToken] ![[token name] isEqualToString:Comment]) { [stream pushToken:token]; } }两个回调的职责与CPTokeniserDelegate头文件注释一致tokeniser:shouldConsumeToken:必选决定 tokeniser 是否消费该 token 对应的输入文本。返回NO时tokeniser 会在同一位置继续尝试其余识别器返回YES才消费并进入产出阶段。tokeniser:requestsToken:pushedOntoStream:可选推荐在此将 token 推入输出流可换一个 token或完全不输出上例即利用该回调丢弃空白与注释。头文件中还有一个被标记废弃的tokeniser:willProduceToken:返回数组形式新代码应使用requestsToken:pushedOntoStream:。此外该协议还提供两个进阶回调tokeniser:didNotFindTokenOnInput:position:error:用于处理任何识别器都无法匹配当前位置的情况可返回新位置继续或返回NSNotFound终止并可写出错误信息到CPErrorTokentokeniserWillFinish:stream:允许在EOFtoken 推入前追加 token头文件注释中举的例子是 Python tokeniser 追加作用域闭合 token。3.3 调用 tokeniserCPTokenStream *tokenStream [tokeniser tokenise:5 (2.0 / 5.0 9) * 8];tokenise:会返回一个CPTokenStream如果整个输入被完整 tokenise流末尾会追加一个CPEOFToken表示输入结束若中途失败则无 EOF token。多线程场景可用tokenise:into:写入预分配的流把该流同时传给 tokeniser 线程与 parser 线程。四、用 BNF 文法构建解析器Parsing4.1 用 BNF 字符串描述文法CPGrammar支持用类 BNF 的 DSL 直接描述文法。README 示例NSString *expressionGrammar Expression :: termTerm | exprExpression opAddOp termTerm; Term :: factFactor | factFactor opMulOp termTerm; Factor :: numNumber | ( exprExpression ); AddOp :: | -; MulOp :: * | /;; NSError *err; CPGrammar *grammar [CPGrammar grammarWithStart:Expression backusNaurForm:expressionGrammar error:err]; if (nil grammar) { NSLog(Error creating grammar:); NSLog(%, err); } else { CPParser *parser [CPLALR1Parser parserWithGrammar:grammar]; [parser setDelegate:self]; ... }文法语法要点详见 CPGrammar.h 头文件注释中的 BNF 元文法定义规则形式nonTerminal :: 产生式;多个备选产生式用|分隔每条规则以;结束。非终结符用尖括号包裹如Term终结符用引号包裹如Number终结符名称对应 token 名称——这里Number正是CPNumberRecogniser产出的 token 名。标签tagtagNonTerminal或tagTerminal形式如exprExpression、opAddOp、numNumber。标签语义上等价于直接写NonTerminal但便于后续从语法树快速取回对应子节点的值。一个规则项可以打多个标签例如range :: minNumber - maxNumber | ... | minmaxNumber。EBNF 扩展规则项后可跟*0 次或多次、1 次或多次、?0 次或 1 次支持括号分组子规则。使用这些 EBNF 结构时parser 返回的结果是NSArray。错误处理推荐使用带error:参数的grammarWithStart:backusNaurForm:error:旧的grammarWithStart:backusNaurForm:已被标记废弃只打印错误。错误域为CPEBNFParserErrorDomain错误码包括CPErrorCodeCouldNotParseEBNFBNF 无法解析1、CPErrorCodeDuplicateTag标签重复2、CPErrorCodeUndefinedNonTerminal引用了未定义的非终结符3。4.2 让解析结果变成你的数据模型CoreParse 的两条产出路径机制见 CPParser.h结果类 CPParseResult协议当一条规则被归约时CoreParse 会尝试以规则左部非终结符命名的类如Expression、Term、Factor新建实例并调用其initWithSyntaxTree:方法。parser delegate 兜底若不存在对应类则调用 delegate 的parser:didProduceSyntaxTree:方法。README 中为Expression、Term、Factor各实现了一个类AddOp、MulOp交由 delegate 处理。Expression的initWithSyntaxTree:实现- (id)initWithSyntaxTree:(CPSyntaxTree *)syntaxTree { self [self init]; if (nil ! self) { Term *t [syntaxTree valueForTag:term]; Expression *e [syntaxTree valueForTag:expr]; if (nil e) { [self setValue:[t value]]; } else if ([[syntaxTree valueForTag:op] isEqualToString:]) { [self setValue:[e value] [t value]]; } else { [self setValue:[e value] - [t value]]; } } return self; }CPSyntaxTreeCPSyntaxTree.h是语法树节点携带归约所用的CPRule、子节点children与标签值tagValuesvalueForTag:按标签名取回子语法树/值——README 用它区分单产生式Expression - Term与二元运算产生式childAtIndex:按下标取子节点还有rule、children、tagValues三个只读属性可遍历整棵树。需要说明的是仓库测试套件中的 Expression.m 给出了该类的实际可运行版本其实现略有不同——它通过[syntaxTree children]的数量判断是单元素产生式还是二元运算产生式count 1时直接取Term的值否则取Expression Term做加法。这印证了两种风格皆可行标签方式更直观按下标/子节点数组方式更贴近规则结构两种方式 README 与测试均有覆盖。delegate 处理运算符非终结符- (id)parser:(CPParser *)parser didProduceSyntaxTree:(CPSyntaxTree *)syntaxTree { return [(CPKeywordToken *)[syntaxTree childAtIndex:0] keyword]; }即把AddOp/MulOp归约出的语法树直接替换为底层CPKeywordToken的关键字字符串、-、*、/供上层Expression/Term的判断逻辑使用。这正是 CPParser.h 中CPParserDelegate的用途用 delegate 把产生的语法树替换成你想要的任何数据结构。头文件注释还点明了一个优化思路数值表达式解析器的 delegate 可以边解析边求值把每个语法树直接替换为结果NSNumber一趟完成解析与计算。4.3 执行解析NSLog(%f, [(Expression *)[parser parse:tokenStream] value]);输出80.2CPParser的parse:方法CPParser.h接收CPTokenStream返回整条流对应的语法树或自定义对象解析失败返回nil并用NSLog记录错误。注意CPParser是抽象基类必须使用其子类CPSLRParser/CPLR1Parser/CPLALR1Parser构建实例。4.4 错误恢复进阶CPParserDelegate还提供错误处理入口parser:didEncounterErrorOnInput:expecting:旧签名parser:didEncounterErrorOnInput:已废弃当 parser 遇到既不能移进、也不能归约、也不能接受的 token 时被调用。参数acceptableTokens是当前状态下能让 parser 继续前进的 token 名集合。方法返回一个CPRecoveryAction定义于Parsers/Error Recovery/CPRecoveryAction.h执行恢复返回nil时若问题 token 是CPErrorToken解析栈会回退一层交给父规则处理。仓库的CoreParseTests/中提供了CPTestErrorHandlingDelegate、CPTestErrorEvaluatorDelegate等测试桩验证该机制。五、解析器选型与最佳实践Best Practices5.1 三类 shift/reduce 解析器的权衡README 给出的权威对比与三个具体子类的头文件注释完全一致见 CPSLRParser.h、CPLR1Parser.h、CPLALR1Parser.h解析器语言覆盖生成速度运行速度内存适用建议SLR最小最快最快低默认首选LR(1)最大慢慢高显著仅在极端情况下使用LALR(1)几乎与 LR(1) 相同比 SLR 慢与 SLR 相当与 SLR 相当文法在 SLR 下无法生成时的升级选择推荐路径先试 SLR 解析器除非你明确知道文法需要更强的能力当文法无法生成解析器时升级到 LALR(1)。LR(1) 虽然覆盖语言集合最大但内存占用大、速度慢README 明确不推荐仅限极端场景。5.2 用 NSKeyedArchiver 缓存解析器解析表生成尤其是 LALR(1)可能耗时。README 强烈建议对于需要 LALR(1) 的较大文法用NSKeyedArchiver把解析器归档到文件运行时直接反归档避免每次启动都重新生成。这一建议在框架设计上是有保证的CPTokeniser、CPGrammar、CPParser全家都实现了NSCoding。iTerm2 主程序把这一实践做成了完整的工程化方案——CPParserCache.m 中实现了基于NSKeyedArchiver的解析器磁盘缓存以App 版本号 parser 类名 BNF 内容哈希 起始符号组合成缓存 keyit_keyWithBNF:start:保证文法变化后缓存自动失效查找顺序进程内内存缓存 → 磁盘缓存文件位于 caches 目录parsers/下用NSKeyedArchiver以二进制属性列表格式写出→ 现场构建并写盘parser 释放时it_releaseParser会归还到内存缓存池供后续复用。这正是 README归档解析器避免重复生成建议的生产级落地同时也验证了 CoreParse parser 可被归档/反归档的能力。六、iTerm2 中的真实应用表达式与函数调用解析作为补充佐证本仓库中 CoreParse 的实际消费方是 iTerm2 自身的表达式解析器 iTermExpressionParser.m其使用模式与 README 示例一一对应tokeniser 组装newTokenizer方法同文件第 155 行起按严格优先级注册CPKeywordRecogniser运算符、括号、true/false、CPNumberRecogniser、CPWhiteSpaceRecogniser、CPIdentifierRecogniser并组合自定义识别器iTermOptionalPathRecognizer与iTermSwiftyStringRecognizer继承自 CoreParse 的CPQuotedRecogniser带转义序列处理见同文件addSwiftyStringRecognizers与setEscapeReplacerInStringRecognizer文法与解析器通过iTermGrammarProcessoriTermGrammarProcessor.h负责组装 BNF 规则并运行转换块产出backusNaurForm再调用CPLALR1Parser parserWithBNF:start:构建 LALR(1) 解析器——对应 README 中较大文法用 LALR(1)的建议结果转化parser 与 tokeniser 的 delegate 都是iTermExpressionParser自身把语法树转换为iTermParsedExpression等模型对象——即 README用 delegate 把语法树替换为数据模型的实践解析器实例以单例缓存expressionParser/callParser两个 dispatch_once 单例并配合上述CPParserCache做磁盘级归档复用。此外iTerm2 对 CoreParse 识别器还做了针对自身语法的扩展sources/Language/iTermQuotedRecognizer.h、sources/Language/iTermTruncatedQuotedRecognizer.h、sources/Language/iTermSwiftyStringRecognizer.h等均派生自 CoreParse 的识别器体系在iTerm2SharedARC-Bridging-Header.h中统一导入说明 CoreParse 的扩展点delegate 协议、识别器子类化在实际工程中是经得起考验的。七、内置解析器与测试资源若你只想快速验证 CoreParse 的能力仓库提供了开箱即用的 JSON 解析器 CPJSONParser.hparse:方法把 JSON 字符串解析为标准 Objective-C 数据结构数字与布尔 →NSNumber字符串 →NSStringnull→NSNull数组 →NSArray对象 →NSDictionary。注意其实现刻意不支持 Unicode 转义字符——头文件说明这仅用于演示 CoreParse 用法Unicode 处理与演示主题无关故略去。完整的测试套件位于 ThirdParty/CoreParse/CoreParseTests/覆盖表达式求值Expression.m、Expression2.m、Term.m、Term2.m、RuleBase.m正则识别器CPRegexpRecogniserTest.m各类 delegate 行为求值、错误处理、忽略空白、MapCSS tokenising 等测试桩结束回调CPWillFinishDelegateTest.m对应tokeniserWillFinish:stream:。这些测试文件是理解 README 示例在真实工程中如何组织类与 delegate 的最佳范本。八、结语一个示例三步套路回顾 README 的完整流程CoreParse 的使用可以凝练为三步词法分析创建CPTokeniser按优先级注册识别器长匹配/注释优先通过 delegate 过滤无意义 token产出CPTokenStream文法与解析用 BNF/EBNF 字符串构造CPGrammar可带标签与*//?扩展选择 SLR / LR(1) / LALR(1) 解析器结果映射为规则左部非终结符实现initWithSyntaxTree:类或用CPParserDelegate把语法树替换为自定义模型——甚至可以在这一阶段边解析边求值。在此基础上借鉴 iTerm2 的做法单例复用、NSKeyedArchiver 磁盘缓存、多字符运算符识别器优先级处理即可把 CoreParse 稳定地嵌入真实应用。深入实现细节可继续研读 ThirdParty/CoreParse/README.md、CPGrammar.h、CPTokeniser.h 与 CPParser.h 的完整文档注释。【免费下载链接】iTerm2iTerm2 is a terminal emulator for Mac OS X that does amazing things.项目地址: https://gitcode.com/gh_mirrors/it/iTerm2创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考