Rob Pike Replaces Lex and Regex With Recursive State Functions in Go

Rob Pike 在 Go 中以递归状态函数替代 Lex 与正则表达式 将并发视为架构结构而非并行工具可化解输入输出结构不匹配的问题，使开发者能够用自推进的递归状态函数消除 switch 语句分发循环。 Rob Pike 探讨了 Go 模板包词法分析器的架构重构，重点围绕解决标记生成器与消费者之间经典的结构性不匹配问题。Pike 没有依赖重量级的正则表达式、Lex 等代码生成工具或臃肿的 switch-case 分发循环，而是引入了一种基于返回下一个待执行状态的递归状态函数的优雅模式。他展示了 Go 通道和 goroutine 如何通过零拷贝字符串切片将扫描器与解析器解耦，并说明了如何利用小型内部通道缓冲区和 select 循环将该并发模型无缝转换为同步的 nextItem API，以适配 Go 的包初始化规则。 Rob Pike 介绍了一种地道的 Go 词法扫描器，使用递归状态函数（`type stateFn func(*lexer) stateFn`）替代传统的基于 switch 的状态机，将分发循环缩减为单行自推进代码。 (13:46) 通过将词法分析器作为 goroutine 并发运行并通过 Go 通道进行通信，该设计无需复杂的前瞻缓冲即可清晰解决迈克尔·杰克逊提出的经典输入输出结构不匹配问题。 (0:02) 由于 Go 不允许在包 `init()` 执行期间运行 goroutine 直至完成，因此可以使用 select 循环和大小为 2 的通道缓冲区将并发词法分析器转换为同步的 `nextItem()` API。 (33:39) 扫描器通过直接切片原始输入字符串来实现零拷贝标记生成，而无需分配中间字符缓冲区。 (44:32)

Rob Pike demonstrates that Go's first-class functions and concurrency primitives can solve the classical structural mismatch in lexical scanning without relying on regular expressions, external generation tools, or switch-based state machines. State Functions and Direct Execution (13:46) Traditional handwritten lexers alternate between an outer control loop and action handlers using a switch statement, discarding contextual state after each step and forcing the program counter to re-evaluate where to branch next. Pike replaces this mechanism with recursive state functions defined as 'type stateFn func(*lexer) stateFn'. Each function executes its scanning logic and directly returns the next function pointer to invoke. This recursive definition reduces the lexer's primary driver to a three-line while-loop: 'for state := startState; state != nil; { state = state(l) }'. Transitions execute without intermediate dispatch overhead, terminating cleanly when a state function returns nil upon encountering EOF or an unrecoverable syntax error via 'l.errorf'. Decoupling Token Delivery via Channels (15:48) Lexers and parsers frequently encounter the structural mismatch described by Michael Jackson, where input data arrives in chunks misaligned with parser requirements. Pike decouples the two stages by running the lexer in a separate goroutine via 'go l.run()' and streaming tokens over a Go channel. The parser consumes items asynchronously, while the lexer pushes tokens across the channel boundaries using an emit helper and advances its internal string slice cursors. Within actions, scanning relies on character-stepping primitives—'next', 'backup', 'peek', 'accept', and 'acceptRun'—rather than complex regular expressions. Numbers, string literals, and identifiers are extracted directly as substring slices over the input, achieving zero-copy token generation while delegating semantic validity checks to downstream parsers. Resolving Initialization Deadlocks Without Concurrency (33:39) Although the concurrent design cleanly decouples parser and lexer, it introduces a critical limitation under Go's runtime semantics: goroutines created during package-level variable initialization do not run to completion until all initializations conclude. Because web servers frequently parse templates into global variables at startup, the concurrent lexer deadlocked waiting on tokens. Pike circumvents this limitation by restructuring the public interface into a synchronous 'nextItem()' method. Under this model, the lexer encapsulates an internal channel buffered to a capacity of two—the maximum number of tokens emitted in any single state transition. A 'select' statement attempts to read from the channel; if empty, its default case advances the state machine by exactly one step, eliminating external goroutines while preserving the internal function-pointer architecture. Concurrency as a Design Tool (38:28) Pike argues that concurrency should be treated as an architectural structuring technique rather than solely a mechanism for parallel performance. Even though Nigel Tao proposed an alternative change list using an in-memory token list that would eliminate channel overhead, Pike retained the channel-based architecture for its aesthetic clarity and structural separation. While jumping through function pointers approaches peak dispatch performance for handwritten state machines, Pike concedes that channel operations introduce minor inner-loop overhead. Furthermore, while well suited for the 10 to 15 states of a template lexer, adapting the pattern to complete parsers remains challenging due to the hundreds of states required, which would generate substantial boilerplate without automated tooling. Pike presents this state-function architecture as an idiomatic synthesis of Go's typing, methods, and concurrency. While highly extensible for lexical scanning, expanding the pattern to large-scale parsers would require automated generation tools to manage the expansive state space.

Rob Pike 提出了一种基于 Go 语言特性重构词法扫描器（Lexer）的设计方案，主张摒弃笨重的词法生成工具、正则表达式以及冗长的 switch 状态机，转而利用递归状态函数与并发通道来优雅化解输入输出间的结构不匹配问题。 结构不匹配与传统词法分析方案的缺陷 (0:02) Pike 引用了计算机科学家 Michael Jackson 提出的“结构不匹配”理论，指出数据输入形式与消费需求往往无法一一对应，而在词法分析器与语法分析器之间，这种控制流扭曲尤为严重。历史上协程的出现正是为了让数据读取端与消费端能各自独立维护控制流并按需交接控制权。Pike 回顾了早期 Go 语言模板引擎的脆弱实现，为了重写该引擎，他审视并否决了三种传统实现方式：专用生成工具（如 Lex、Ragel）、正则表达式以及基于 switch 的手写状态机。 Pike 解释称，Lex 等专用工具不仅报错信息晦涩，还要求开发者学习额外的规范语言，生成的代码往往包含庞大的状态表且运行沉重；而正则表达式功能过于宽泛且底层状态空间复杂，用来做单字符步进的词法分析属于大材小用。至于最常见的手写 switch 状态机，Pike 批评其在架构上存在“丢弃已知状态”的缺陷：动作函数在执行完毕时本已清楚下一步该去向何处，却被迫退出并返回状态值给中央分发循环，再由外层 switch 重新匹配分支，这不仅打断了 CPU 的程序计数器流向，还增加了不必要的代码复杂度。 状态函数与无分发循环的核心机制 (13:46) 为了消除 switch 带来的中转开销，Pike 将状态（词法分析器当前所处位置及预期）与动作（对输入字符执行的操作）统一抽象为函数概念，定义了递归函数类型 `type stateFn func(*lexer) stateFn`。在这个模型下，每个状态函数执行完自身扫描后，直接返回下一个待执行的状态函数指针；当扫描完毕或遇到错误时返回 `nil`。由此，整个扫描器的外层运行循环精简为仅有三行的 `for state != nil { state = state(l) }`，使执行流能够顺畅地在不同状态间直接跃迁。 在输入流导航方面，词法分析器通过记录起始位置 `start`、当前光标 `pos` 和当前 Unicode 字符（rune）字节宽度 `width`，配套构建了 `next`、`backup` 和 `peek` 等轻量助手方法。配合按集合匹配字符的 `accept` 与连续贪婪匹配的 `acceptRun`，扫描器可以轻松处理前缀符号、十六进制基数、浮点指数以及 Go 虚数单位。Pike 强调，词法分析器的职责是圈定最大化有效 token 的切片边界，复杂的数值语义验证应委托给下游解析器；此外，所有生成的 token 均直接切片自原始字符串，实现了零内存拷贝的高效处理。 并发流水线设计与 Go 包初始化陷阱 (15:48) 在最理想的模型中，Pike 将词法分析器置于独立的 goroutine 中运行，扫描出的每个 token 直接“抛过墙”，通过 Go 通道（channel）传递给消费端的语法分析器。错误处理也天然嵌入该机制中：辅助方法 `errorf` 会格式化生成带有错误说明的合成 token 并送入通道，随后返回 `nil`，从而在无需异常处理机制或中断标志的情况下立即终止扫描循环。 然而，这一完全并发的原型在实际应用中遭遇了 Go 运行时规则的制约。在 Web 服务场景中，模板通常在包级别的 `init()` 阶段被编译进全局变量；但 Go 运行时为了保证确定性的包初始化顺序，规定初始化期间创建的 goroutine 会被挂起，直至全部初始化结束。这导致并发词法分析器在 `init()` 阶段等待消费时直接死锁。为了化解这一限制，Pike 将公开 API 重构成同步拉取模式的 `nextItem()`，并利用容量为 2 的带缓冲通道将通道退化为私有环形缓冲区。通过在无限循环内结合 `select` 接收与 `default` 单步执行状态函数，Pike 在未破坏状态函数内核的前提下，完全向调用方隐蔽了并发依赖。 并发作为设计思维与工程落地权衡 (38:28) Pike 借此澄清，并发首先是一种解耦复杂软件架构的设计理念，而非仅仅用于多核并行计算的性能工具。即使在单线程逻辑下，将词法扫描与语法解析视作两个独立运作的协程实体，也能显著降低状态回溯与代码管理的认知负担。在实际演进中，得益于状态函数的清晰隔离，随着模板语法的扩充，新增字面量和关键字支持往往只需添加一到两行逻辑或一个简短的独立状态函数即可完成。 针对现场观众对性能和数据流设计的疑问，Pike 坦承该实现尚未经过严格的基准测试，通道内部调度的开销确实会使内层循环速度受到一定影响，但函数指针的直接调用在效率上已逼近查表分发的理论上限。虽然贡献者 Nigel Tao 曾提交过使用简单切片列表批量收集 token 的优化补丁且性能可能更高，但 Pike 因其破坏了流式交互的设计美感而坚持保留通道方案。此外，Pike 指出状态机目前仅针对模板的 10 至 15 个状态手写维护，对于拥有数百个状态的通用语法解析器，手写该模式会带来大量样板代码，届时仍需代码生成工具辅助。 Pike 总结指出，词法分析本身并非固有并发的业务场景，但并发思维为解耦数据生产与消费提供了极具表现力的架构手段。尽管在高吞吐场景下通道切换会引入轻微性能损耗，且该模式难以直接外推至状态庞杂的通用解析器，但它仍充分展现了 Go 语言在函数类型、零拷贝切片及轻量通信层面的工程美学。

## Background 该视频由 YouTube 频道 GoogleFOSSSydney 于 2011 年 8 月 30 日发布。内容为 Rob Pike 在悉尼 Google 技术用户组（GTUG）聚会上的技术演讲，主题是介绍 Go 语言中一种基于状态函数与并发模型构建的新型词法扫描器（Lexical Scanning in Go）。 ## TL;DR Rob Pike 深入探讨了编译器前端中常见的“结构不匹配”问题，并批判了传统词法生成工具（如 Lex）和正则表达式在分词任务中的局限与冗余。他展示了 Go 标准库重构模板系统时采用的一种极简方案：将状态与动作统一为递归类型定义的状态函数（`stateFn`），使主循环收敛为单行代码，并通过 Goroutine 与 Channel 优雅解耦词法分析器与语法解析器。针对 Go 包初始化期间禁止后台 Goroutine 运行的死锁问题，他进一步利用 Channel 缓冲与 `select` 语句将并发逻辑无缝收拢为传统的 `nextItem` API。最后，演讲强调并发不仅关乎并行性能，更是理顺程序控制流与消除样板代码的强大设计思维。 ## Atmosphere & style 现场氛围亲切、松弛且洋溢着浓厚的极客幽默，Rob Pike 举重若轻地在白板式的幻灯片前拆解复杂的编译器概念。他的讲解风格直率而富有洞察力，既有对早期粗糙实现的坦诚自嘲，也有对正则表达式滥用者的风趣调侃，令台下的技术受众不时报以会心笑声。整场演讲兼具底层架构的严谨推演与语言哲学的写意表达，最后因真实的日程冲突在略显匆忙却热烈掌声中戛然而止，真实感与启发性拉满。 ## Bulletin - [11:46](https://www.youtube.com/watch?v=HxaD_trXwRE&t=706s) Rob Pike 提出利用 Go 语言的状态函数与递归类型定义（`type stateFn func(*lexer) stateFn`）替代传统的庞大 switch 语句，使词法分析器的主循环精简至单行代码。 - [15:41](https://www.youtube.com/watch?v=HxaD_trXwRE&t=941s) 词法分析器最初被设计为与解析器并行的协程（goroutine），通过 channel 进行类似 Unix 管道的单向通信，从架构上解耦了输入缓冲与解析控制流。 - [33:39](https://www.youtube.com/watch?v=HxaD_trXwRE&t=2019s) 由于 Go 规范严禁在包初始化（`init`）阶段等待并发 goroutine 完成，团队通过带缓冲 channel 与 select-default 轮询机制，在不破坏状态机架构的前提下将并发逻辑改造成同步的 `nextItem` API。 - [44:32](https://www.youtube.com/watch?v=HxaD_trXwRE&t=2672s) 整个词法扫描过程对输入文本实现了零内存拷贝，所有向解析器传递的词法项（item）均直接复用底层输入字符串的切片（slice）。 ## Key takeaways - [00:02](https://www.youtube.com/watch?v=HxaD_trXwRE&t=2s) 协程（Coroutines）的历史初衷正是为了解决控制流与数据块之间的“结构不匹配（structural mismatch）”，而非分布式或并行计算。 - [02:30](https://www.youtube.com/watch?v=HxaD_trXwRE&t=150s) Go 早期模板系统因缺乏形式化的词法与语法分析，导致引入数字常量与带引号字符串时代码变得极其脆弱和臃肿。 - [05:07](https://www.youtube.com/watch?v=HxaD_trXwRE&t=307s) 词法项定义为包含类型的结构体，词法扫描阶段保留原始文本字符串（如 `23.2`），避免过早将其转换为浮点数等机器类型。 - [09:03](https://www.youtube.com/watch?v=HxaD_trXwRE&t=543s) 词法生成工具（如 Lex）生成的代码体积庞大且难以生成高质量错误信息，而通用正则表达式对于静态确定的词法分析过于沉重，属于“杀鸡用牛刀”。 - [11:46](https://www.youtube.com/watch?v=HxaD_trXwRE&t=706s) 状态函数的本质是将“状态”与“动作”合二为一，使程序计数器直接指向下一个待执行逻辑，彻底规避了跳回外层 switch 重新解析状态的损耗。 - [15:41](https://www.youtube.com/watch?v=HxaD_trXwRE&t=941s) 将词法分析器拆解为独立的 goroutine 并通过 channel 投递 token，使词法分析与语法解析双方可以完全独立编写并自动协调控制权。 - [19:11](https://www.youtube.com/watch?v=HxaD_trXwRE&t=1151s) 利用 `start` 和 `pos` 两个整数游标界定滑动窗口，配合 `emit` 方法投递切片并推进游标，保证了轻量高效的词法单元生成。 - [28:17](https://www.youtube.com/watch?v=HxaD_trXwRE&t=1697s) 借助 `accept` 和 `acceptRun` 等辅助函数，词法分析器能以流水线方式清晰地扫描包含进制、浮点、指数和虚数后缀的复杂数字常量。 - [28:17](https://www.youtube.com/watch?v=HxaD_trXwRE&t=1697s) 词法分析器的职责是贪婪匹配潜在的数字边界，严格的语法与数值合法性验证应合理交给下游解析器去完成。 - [32:10](https://www.youtube.com/watch?v=HxaD_trXwRE&t=1930s) 错误处理函数 `errorf` 发送带有格式化错误描述的 `itemError` 并返回 `nil`，使主循环自然停机退出，避免了异常机制并简化了错误传递。 - [33:39](https://www.youtube.com/watch?v=HxaD_trXwRE&t=2019s) Go 语言禁止在包全局变量初始化期间等待 goroutine 完成，这迫使设计必须规避在模板初始化阶段产生并发死锁。 - [35:25](https://www.youtube.com/watch?v=HxaD_trXwRE&t=2125s) 通过引入 `nextItem` 与小容量缓冲 channel，在保持状态函数优雅内部结构的同时，对外部调用方隐藏了并发并消除了初始化死锁。 - [38:28](https://www.youtube.com/watch?v=HxaD_trXwRE&t=2308s) 并发的核心价值在于作为一种解耦问题的程序设计手段，它支持并行但并不等同于并行，在词法分析中更体现为同步的线性控制流。 - [44:32](https://www.youtube.com/watch?v=HxaD_trXwRE&t=2672s) 整个词法分析流程坚持零拷贝（zero-copy）设计，词法项直接持有原输入字符串的切片，面对超大静态文本时开销极低。 - [46:40](https://www.youtube.com/watch?v=HxaD_trXwRE&t=2800s) 词法分析器的底层字符吞入逻辑仅需对 `next` 方法稍作抽象，即可由固定字符串输入平滑迁移至支持 `io.Reader` 流式读取。 ## Detailed walkthrough ### [00:02](https://www.youtube.com/watch?v=HxaD_trXwRE&t=2s) 结构不匹配问题与协程的历史渊源 在悉尼举办的 Google 技术用户组（GTUG）聚会上，主持人 Tim 宣布活动开始后，Rob Pike 登台带来了关于“Go 语言中的词法扫描（Lexical Scanning in Go）”的分享。Rob Pike 首先向台下抛出了一个看似与编译器无关的问题：“你们有多少人熟悉迈克尔·杰克逊（Michael Jackson）的研究工作？”面对台下零星的举手和会心的笑声，他解释此处的杰克逊并非流行音乐之王，而是开创了“杰克逊结构化程序设计”（Jackson Structured Programming, JSP）的计算机科学家。JSP 的核心在于解决计算领域极其普遍的“结构不匹配（structural mismatch）”问题。当程序试图将一种形态的数据转换为另一种形态，而两边的控制流无法自然契合时，代码就会迅速陷入混乱——比如读取固定数据块并尝试解析为文本行时，面对半截行和半个块的交错状态，程序不得不充斥着两端各自的缓冲区、前瞻窥探（look ahead/peek）、回溯状态以及繁琐的边界条件检查。无论是数据包重组还是词法解析，本质上都是这一痛点的体现。 ```mermaid flowchart LR accTitle: 数据结构不匹配与传统解析困境 accDescr: 展示输入块与输出行由于流控制不匹配所导致的复杂缓冲与状态管理。 subgraph InputSide["输入端 (数据源)"] Block["原始数据块 (Blocks)"] end subgraph Mismatch["控制流不匹配核心区"] Buffer["缓冲区 / 前瞻窥探 (Lookahead)"] State["繁琐的边界与状态机管理"] end subgraph OutputSide["输出端 (解析目标)"] Lines["目标逻辑单元 (Tokens / Lines)"] end Block --> Buffer Buffer <--> State Buffer --> Lines ``` Rob Pike 指出，计算机科学史上一个有趣的巧合在于，协程（Coroutines）这一并发概念的诞生，其实早在杰克逊明确归纳结构不匹配问题之前，就是专门为了解决这种本地数据流转换而发明的。通常大家把协程视为现代并发编程的先驱，但其最初动机却是一个非常纯粹的非分布式数据管理问题。如果采用协程模型，开发者可以分别编写独立运行的数据块读取器和文本行处理器，让两者在需要时自动交出控制权并切换执行，这会让整个程序的代码结构变得极其清晰优雅。Rob Pike 强调，这种利用并发模型解耦控制流的思想，正是他接下来要展示的词法扫描器架构的基础：“When you do a coroutine model right, you get to write both pieces of the problem the block reader and the line processor or whatever completely independently and they switch control as necessary and the program can become quite a bit nicer as a result.” - 结构不匹配在计算中无处不在，典型场景包括数据分块与解块、网络数据包重组以及词法与语法解析。 - 协程的最初诞生正是为了在无需复杂外部调度的情况下优雅解决双向缓冲与状态前瞻的问题。 --- ### [02:30](https://www.youtube.com/watch?v=HxaD_trXwRE&t=150s) 旧模板引擎的缺陷与新系统的语法构成 Rob Pike 进而切入本次演讲的实际工程背景：Go 语言标准库中的模板系统。在 Go 语言早期开发阶段，他曾亲手实现过一个文本模板包（即后来的 `text/template` 前身），尽管初衷是作为更通用的系统，但形式上类似 HTML 模板。对此他非常坦率地自我批评道，团队当时自以为做得很酷，但后来事实证明他们完全错了。初版实现不仅僵化且缺乏表现力，社区贡献者不得不频繁实现自己的替代方案，更严重的是其内部代码极其脆弱：“As it developed, we started to want to add things like numerical constants and quoted strings, and the whole code just sort of didn't accept it very well, it was clunky.” 当需要引入数值常量、带引号的字符串等现代语法特性时，既有代码框架根本无法顺畅承载，变得臃肿不堪。因此在 2011 年初，基于对模板应有形态的深刻认识，Rob 决定彻底重构，将其打造成一个具备正规词法分析与语法分析（Lex/Parse）的系统，并在此过程中摸索出了一套格外漂亮的词法分析器架构。 ```mermaid flowchart TD accTitle: Go 模板语法解析层次 accDescr: 模板内容被拆分为外部原生文本与被双花括号包裹的内部动作。 RawInput["模板原始输入"] RawInput --> PlainText["普通文本 (Actions 外部内容)"] RawInput --> Action["动作块 {{... }}"] subgraph ActionDetails["动作内部语法元素"] Field[".title (上下文数据字段)"] Func["函数调用 (如 printf)"] Const["数值 / 复数常量 (Complex)"] Control["控制结构 (range / if / else)"] end Action --> ActionDetails ``` 虽然本次讲座的重点并非教授模板使用，但 Rob 简要梳理了词法分析器需要处理的目标语法结构。模板由两部分组成：普通的静态文本，以及由双大括号包围的求值指令——动作（Actions，即 `{{... }}`）。动作内部承载着需要被求值的表达式、方法调用或数据结构字段： - **简单字段访问**：如 `{{.title }}`，在一个隐式的当前上下文环境中求值； - **函数与格式化**：如调用 `printf` 并传入十六进制格式化指令； - **复杂常量**：支持数值甚至包含复数常量（Rob 开玩笑表示这或许是第一个把复数常量写进演示幻灯片的模板系统）； - **控制流结构**：用于循环遍历（`range`）与条件分支（`else`、`end`）等逻辑。 除了 Perl 那些极为特化的语法之外，这个模板动作内部几乎具备了现代通用编程语言所拥有的一切基础词法要素。词法分析器的职责，就是从连续的输入字符流中把这些语义块切分成语法分析器（Parser）能够理解的标记（Token / Lex Item），以便后续构建语法分析树。 --- ### [05:07](https://www.youtube.com/watch?v=HxaD_trXwRE&t=307s) 词法项（Item）建模与 Go 特性实践 词法扫描器的核心产物是“项”（Rob 将其命名为 `item`）。传统编译器实现中，一个词法项通常由两部分组成：类型（type）和值（value）。类型用来向解析器指示当前项的语法类别（如数字、标识符或操作符），在底层通常表示为一个整数；值则是对应的字面内容。Rob 明确指出，在词法扫描阶段，数值项如 `23.2` 的值应当保留为其原始的文本字符串 `"23.2"`，而非过早转换为浮点数或机器类型，这一规则对绝大多数词法分析器均适用。为了表示词法类型，他在 Go 中将其定义为一个独立类型：`type itemType int`。Rob 强调，虽然这表面上类似于 C/C++ 的 `typedef`，但在 Go 语言中它是一个货真价实的新定义类型，无法直接与普通整数混用，从而提供了更强的静态类型安全，并允许在其上附加专有方法。 ```go type itemType int const ( itemError itemType = iota // 错误项，值为 0 itemDot // 字段操作符. itemEOF // 文件结束标志 itemElse // 关键字 else itemEnd // 关键字 end itemLeftMeta // 左定界符 {{ itemRightMeta // 右定界符 }} itemNumber // 数字字面量 //... ) ``` 在枚举常量的定义上，Go 的 `iota` 语法展现出了极简的工业美感。常量声明块的第一行写为 `itemError itemType = iota`，指示编译器开启枚举自增计数，随后的常量会自动依次获得递增的整型值（如 `itemDot` 为 1，`itemEOF` 为 2），且每个常量的底层类型都牢牢锁定为 `itemType`。除了常规的代码元素外，枚举列表中特别包含了 `itemError` 与 `itemEOF` 这类特殊标记。 ```mermaid flowchart TD accTitle: Item 结构与 String 方法打印逻辑 accDescr: 根据 itemType 分支判断输出格式，包括 EOF、错误项以及过长文本截断。 A["调用 item.String()"] --> B{"匹配 item.typ"} B -->|itemEOF| C["输出字符串 'EOF'"] B -->|itemError| D["直接输出由 val 携带的错误消息"] B -->|其他类型| E{"val 长度是否过长?"} E -->|超过限制| F["截断字符并追加 '...' 输出"] E -->|未超限制| G["原样格式化输出 (类型与字面值)"] ``` 紧接着，Rob 展示了如何利用 Go 的接口机制为词法项提供优雅的调试支持。Go 的 `fmt.Printf` 拥有一项独特性质：“Any type that has a method called String that returns string as a basic type is known to Printf and can be used by Printf so you get a default pretty print for that type value.” 只要为 `item` 结构体实现 `String() string` 方法，它便能自动被格式化打印。在 `String()` 的分支处理中隐藏着两个精妙的设计： 1. **错误传递技巧**：当类型为 `itemError` 时，词法扫描器会直接将人类可读的错误文本保存在该项的 `val` 字段中（即便这串文字并非来自模板源代码），打印方法直接将其原样输出，简化了错误状态流转； 2. **大文本防御性截断**：由于外部静态文本块可能长达上万字符，如果在调试时直接全量打印会导致终端刷屏，因此代码中加入了长度检测，对于超出限制的长字符串自动截断并追加省略号（`...`），保证调试输出紧凑清晰。 - 词法项（`item`）设计为包含 `typ itemType` 和 `val string` 两个字段，数值和标识符均以原生字符串形式暂存。 - `itemType` 依靠 `iota` 机制实现类型安全的自增枚举，避免了裸使用 `int` 带来的混淆隐患。 - 借由 Go 标准库约定的 `String()` 签名实现优雅打印，集成了错误文本承载和长文本自动截断保护机制。 ### [09:03](https://www.youtube.com/watch?v=HxaD_trXwRE&t=543s) 为什么不用现成工具：Lex 与正则表达式的局限性 一旦为 `item` 实现了格式化输出方法，就可以直接用 `fmt.Printf` 打印出整洁的词法项。但随之而来的核心问题是：如何对输入流进行分词（tokenization）？行业内有许多广为人知的方法，例如使用生成工具（如 Mike Lesk 最初编写、后来由实习期的 Eric Schmidt 重写的著名工具 Lex），或者使用正则表达式，抑或是通过状态、动作与 `switch` 语句手写状态机。Rob Pike 明确表示自己不会使用上述任何一种方案，并逐一分析了它们的不足。 首先针对词法分析生成工具（如 Lex），Rob Pike 澄清自己并不否定这类工具的价值，但他强调了工具常被忽视的缺陷：“在解析输入时，生成优质的错误信息非常重要，而工具往往让输出良好的错误信息变得比预期更加困难；在词法分析阶段，这尤其是一个棘手的问题。”此外，开发者不仅要学习工具本身，通常还得学习一门专门用来为工具编写规则的辅助语言。既然手中已经有了像 Go 这样功能完备的编程语言，为何还要倒退一步去学另一门语言？更严重的问题在于尺寸和性能。Lex 以针对极其简单的词法状态机生成极其庞大的数据结构而著称，因此在他看来，Lex 已经不再适合胜任现代任务（尽管像 Ragel 这样的后继者要优秀得多）。 针对正则表达式，Rob Pike 提到他在演讲前一周刚写过一篇相关博文，起因是在代码审查中有一位开发者试图使用正则表达式编写词法分析器。Rob Pike 指出正则引擎对于词法分析这样简单的任务来说“过于庞大且沉重”： - 正则表达式引擎庞大且复杂，必须在庞大的状态空间中进行评估。 - 正则引擎所求解的问题往往远比词法分析所需的复杂得多——开发者只需要判断下一个字符是什么，根本不需要去匹配 55 个可能存在的关键字。 - 正则表达式是非常动态、极具表现力且精美的机制（Rob Pike 本人也曾多次实现并十分喜爱正则），但词法分析语法是完全静态且已知的，引入动态匹配机制属于典型的“杀鸡用牛刀”（Overkill）。 ```mermaid flowchart TD accTitle: 传统词法分析方案的缺陷对比 accDescr: 对比词法生成工具与正则表达式在做词法分析时的核心劣势 subgraph Tools["词法分析生成工具 (如 Lex)"] T1["错误信息难以精细控制"] T2["需要额外学习 DSL / 工具专用语言"] T3["生成的数据结构庞大且运行缓慢"] end subgraph Regex["正则表达式 (RegEx)"] R1["引擎复杂，状态空间评估开销巨大"] R2["计算模型过重 (Overkill)"] R3["高度动态机制难以匹配静态词法需求"] end ``` --- ### [11:46](https://www.youtube.com/watch?v=HxaD_trXwRE&t=706s) 传统手写状态机的困境与突破：从 switch 转向状态函数 既然不用生成工具也不用正则，手写词法分析器便成了自然的选择。现代编程语言的词法结构极为相似，学会为一门语言编写分词器后，几乎可以直接套用到其他任何语言中。传统的手写做法通常是定义一系列状态（例如“在注释中”、“在普通文本中”、“在动作标签中”）以及对应的动作（如吸收字符直至数字末尾），然后用一个外层的 `switch` 语句包裹状态：根据当前状态跳转执行动作，动作消耗输入并返回一个新状态以及词法项。 Rob Pike 指出，这种典型的 `switch` 模型虽然简单直观，但极其单调乏味，且存在逻辑设计上的倒退：“当你从动作 2 返回并附带返回一个状态时，你必须退回到调用者，接着再次进入 `switch` 重新推导自己的位置；状态变量在此刻丢失了程序刚才所处的上下文。”明明刚退出动作 2 时已经清楚接下来该去状态 1，为何还要离开、重新进循环、再次做一遍条件判断，而不是直接跳转到状态 1？ 为了彻底消除这个繁琐的调度损耗，Rob Pike 提出了将“状态”（State）与“动作”（Action）合二为一的优雅方案： 1. **状态的本质**：代表我们在输入中所处的位置，以及接下来预期会看到什么。 2. **动作的本质**：代表在该状态下针对特定输入所执行的具体操作。 3. **状态函数（State Function）**：执行该函数即执行了对应动作，执行完毕后，它的返回值直接就是下一个状态函数。 由此，Go 语言中诞生了一个极具美感的递归类型定义： ```go type stateFn func(*lexer) stateFn ``` Rob Pike 形容这个定义“有点令人脑洞大开（mindblower）”，因为一个状态函数的定义正是返回其自身类型的函数。通过将状态的推进直接交由函数指针维系，词法分析器的内部主循环被压缩成了仅有一行的极其纯粹的形式： ```go for state:= startState; state!= nil; { state = state(l) } ``` “原先的 `switch` 语句被折叠成了一行不断自我运行的代码：获取一个状态、调用它、得到新状态、再次调用它……程序计数器（PC）永远精确地指向我们下一步要去的地方。” --- ### [15:41](https://www.youtube.com/watch?v=HxaD_trXwRE&t=941s) 引入并发模型：基于 Channel 的词法分析器架构 将整个词法分析器折叠进单行 `state = state(l)` 循环之后，随之暴露出了一个明显的工程问题：在纯粹的状态流转中，根本看不到向外发射（emit）Token 的机制。如果外部的解析器（Parser）需要获取词法项，应该如何与这套闭环的状态机交互？ Rob Pike 在此展示了 Go 语言原生并发能力的威力。传统架构通常让解析器主动调用 `lex.nextToken()`，而 Rob Pike 选择将词法分析器设计为一个与解析器并行运行的协程（Goroutine）： ```mermaid flowchart LR accTitle: 词法分析器与语法解析器的并发管道模型 accDescr: 展示词法分析器如何通过 Go Channel 将 Item 传递给解析器 subgraph LexMachine["词法分析协程 (Lexer)"] L1["状态循环: state = state(l)"] L2["扫描字符并构造 Item"] end subgraph Comm["通信桥梁"] CH["chan item (类似 Unix Pipe)"] end subgraph ParseMachine["语法解析协程 (Parser)"] P1["从通道接收 Token"] P2["构建 AST / 语法树"] end L1 --> L2 L2 -->|"发射词法项 (lob over the wall)"| CH CH -->|"接收并驱动解析"| P1 P1 --> P2 ``` 词法分析器和解析器被拆分为两个完全独立的实体。词法分析器专注遍历输入并发射词法项，每当构造出一个新的 `item` 时，直接借助 Go 的 `channel` 将其“隔墙扔给”解析器。Rob Pike 将这种通道比喻为带有更严格语义的 Unix 管道（Pipe）。在具体的数据结构定义中，`lexer` 结构体聚合了所有内部解析状态，而最为关键的对外出口正是一个通道字段： - `items chan item`：作为词法分析器向解析器输送数据的管道通道。 在工厂函数的早期版本中，创建词法分析器的函数会同时返回 `*lexer` 指针与 `chan item`。Rob Pike 坦承这种 API 显得有些怪异，但强调“这是真实生产环境下的早期代码，后续会逐步对其进行修正与重构”，从而为下一步完整展示字符扫描与并发通道结合的具体代码埋下了伏笔。 ### [17:35](https://www.youtube.com/watch?v=HxaD_trXwRE&t=1055s) 启动词法分析器与并发通道通信 Rob Pike 讲解了词法分析器的启动函数 `lex`。该函数接收模板名称和输入字符串作为参数，创建 `lexer` 结构体并初始化相关字段。在 Go 语言中，结构体初始化只需显式填写关心的字段，其余未填字段均会自动赋予零值。随后，Rob Pike 指出核心逻辑所在的语句：通过 `go l.run()` 启动一个独立的并发执行流。 ```mermaid flowchart LR accTitle: 词法分析器并发运行与管道交互 accDescr: 描述词法分析器在独立的 goroutine 中运行并通过 channel 将 token 发送给语法解析器的流程 subgraph S1["并发执行流 (Goroutine)"] A["词法分析器 run()"] -->|"遍历状态"| B["状态函数 (stateFn)"] B -->|"emit(item)"| C["items channel"] end subgraph S2["调用方主线程"] C -->|"接收 token"| D["语法解析器 (Parser)"] end ``` 此时状态机作为独立的 goroutine 与调用者并行运行，随后 `lex` 函数立即向调用方（通常是语法解析器 parser）返回构造好的词法分析器实例。解析器接着开始解析，并通过通道（channel）持续接收由后台运行器投递过来的词法单元（lexemes）。随后他展示了真正的 `run` 方法实现，强调这段代码真实不带半点水分：它首先设定初始状态为普通文本状态 `lexText`，接着进入 `state = state(l)` 循环不断执行状态函数，并在循环终结时调用 `close(l.items)` 关闭通道，明确通知语法解析器不会再有后续 token。 “Notice in Go you don't only have to fill in the ones you care about; the rest will be initialized to zero, and then this line here is where the magic starts: `go l.run()`.” - 启动函数 `lex(name, input string) *lexer` 负责实例化并派发 goroutine。 - 真实的 `run` 方法以 `lexText` 为起始状态，并在状态循环结束后关闭 `items` 通道。 ### [19:11](https://www.youtube.com/watch?v=HxaD_trXwRE&t=1151s) 游标管理与词法单元发射机制 (`emit`) 为了将切分出来的 token 传送回调用者，Rob Pike 解释了 `lexer` 内部控制扫描位置的两个核心整型游标：`start` 与 `pos`。尽管他开玩笑说这两个名字算不上特别优雅，但含义极其明确。扫描沿字符串单向推进时，`start` 标记当前正在扫描（即将发射）的 token 起始偏移量，而 `pos` 则是当前扫描器所探查到的最新字符位置。两者之间的子切片 `input[start:pos]` 便构成了完整的词法单元。 ```mermaid flowchart TD accTitle: Token 扫描与发射切片示意图 accDescr: 说明 input 字符串中 start 和 pos 游标如何界定词法单元并在 emit 时更新游标 subgraph Slice["输入字符串切片"] T["... 已处理..."] --- S["start"] S --- W["当前待发射词法单元 (Token)"] W --- P["pos"] P --- R["... 未处理输入..."] end W -->|"emit(itemType)"| CH["l.items 通道"] CH -->|"推进游标"| UP["start = pos"] ``` 在 `emit` 方法中，接收一个 token 类型参数 `itemType`，随后使用 Go 语言的通道发送操作符 `<-` 将构造好的 `item` 推入 `l.items` 通道中。完成向解析器“越墙投掷”token 的动作后，词法分析器只需执行 `start = pos` 将起始点移动到当前位置。Rob Pike 生动地将该流程比喻为一路快跑扫描：“扫描、扫描、扫描，啊哈！这里有个 item，把它扔过围栏，接着处理下一个再扔过去，这就是整个运作模型。” - `input[start:pos]` 确立了当前词法单元的文本范围。 - `l.items <- item{typ, l.input[l.start:l.pos]}` 将切分后的数据投递到通道。 - 投递后执行 `l.start = l.pos` 完成滑动窗口更新。 ### [20:26](https://www.youtube.com/watch?v=HxaD_trXwRE&t=1226s) 文本状态扫描与定界符匹配 (`lexText` 与 `lexLeftMeta`) 在明确了游标与发射机制后，Rob Pike 回顾了初始状态 `lexText` 的具体实现细节。词法分析器首要任务是寻找动作定界符（即模板标记的左双大括号 `{{`，在代码中定义为常量 `leftMeta`）。`lexText` 函数内部使用 `for` 循环不断步进输入，如果在当前位置 `pos` 遇到了左定界符，且 `pos > start` 说明之前累积了非空的纯文本内容，就会立即调用 `emit(itemText)` 将其作为普通文本 token 发送给解析器。 ```mermaid flowchart TD accTitle: 状态转移流程：纯文本到动作块 accDescr: 展现从扫描普通文本到识别左定界符并进入动作块的状态转移 T["lexText 状态"] -->|"未见 leftMeta"| T T -->|"发现 leftMeta"| ET["emit(itemText)"] ET -->|"返回新状态"| LM["lexLeftMeta 状态"] LM -->|"pos += len(leftMeta)"| ELM["emit(itemLeftMeta)"] ELM -->|"返回新状态"| IA["lexInsideAction 状态"] ``` 发出文本之后，`lexText` 并不直接在当前函数里拆解定界符，而是返回一个新的状态函数 `lexLeftMeta`。“Here's a state function, and it returns a state function.” Rob Pike 解释道，`lexLeftMeta` 的工作极其纯粹：因为前置判断已经确认定界符的存在，它直接使 `pos += len(leftMeta)` 跳过两个大括号，紧接着调用 `emit(itemLeftMeta)` 抛出定界符 token，然后将状态自然切换到 `lexInsideAction`，正式步入动作块内部。 - 模板中普通文本与模板动作的交界处由常量 `leftMeta` 触发判定。 - 每个状态函数各司其职，`lexText` 只管纯文本，识别到定界符后将控制权交由 `lexLeftMeta`。 - 文本扫描遭遇 EOF 的处理机制十分整洁，不会干扰主逻辑状态跳转。 ### [23:04](https://www.youtube.com/watch?v=HxaD_trXwRE&t=1384s) 动作块内部状态分支调度 (`lexInsideAction`) 进入动作块内部后，词法分析面对的是更为复杂多变的语法元素。Rob Pike 展示了 `lexInsideAction` 的实现，指出这非常具有手写词法分析器的代表性：由于程序无法预知接下来会遇到数字、标识符还是字符串，因此需要通过单字符窥视来展开一系列多路分支提问。 首先检查是否遇到闭合定界符 `rightMeta`，若匹配成功则返回 `lexRightMeta` 准备退回到纯文本逻辑。若未闭合，则调用辅助方法 `l.next()` 读取下一个字符（Rune）并做模式匹配：遇到 EOF 或换行符直接返回报错，因为模板系统不允许动作块跨行；遇到空白字符则直接忽略跳过；遇到管道符 `|` 则做相应处理；遇到双引号 `"` 返回 `lexQuote`；遇到反引号 ``` ` ``` 则切换到 Go 特有的原始字符串状态 `lexRawQuote`。当读到加号 `+`、减号 `-` 或数字字符时，表明扫描器已经迈入了数值常量的第一个字符，此时只需调用 `backup` 后退一步，接着转移到 `lexNumber` 状态；同理，遇到字母时同样退回一步并转移到标识符状态。 “And compared to what a regular expression does to work this out, it's actually in some senses simpler; of course there's more code, but it's really nice how you just sort of pick a one character, what do I do now, I move on.” - 模板系统强制规定动作块不得跨换行符存在，否则触发语法错误 `l.errorf`。 - 通过识别首字符并在状态跳转前执行 `backup` 回退，实现了优雅的分支预测与状态衔接。 ### [25:14](https://www.youtube.com/watch?v=HxaD_trXwRE&t=1514s) 字符级辅助工具函数：`next`、`ignore` 与 `backup` 为了支撑上述状态函数的高效切换，Rob Pike 深入解释了底层的几个关键辅助函数。首先是 `next()`，它负责从输入流提取下一个字符。在 Go 语言中，这被称为 `rune`，因为它代表经过完整 UTF-8 解码的 Unicode 码点，而不仅仅是单个字节。`next()` 在读取到字符串末尾时返回一个代表 EOF 的带外特殊符；否则利用 UTF-8 解码提取字符，依该字符的字节宽度相应推进 `pos` 游标，并将读到的 `rune` 返回给调用方。 此外还有两个操作游标极简却强大的辅助工具： 1. `ignore()`：直接执行 `l.start = l.pos`。当在动作块中遇到无意义的空格或间隔符时，直接调用该函数将起始游标同步推进，丢弃无用字符。 2. `backup()`：作为 `next()` 的逆操作，将 `pos` 游标按当前字符的宽度向后回退。Rob Pike 强调，正是由于 `next` 负责吞入字符判断类型，当判定属于数字或标识符时，`backup` 能够立即撤销这单步移动，使得专门的状态函数（如 `lexNumber`）能够从该 Token 的首个字符处重新干净地开始解析。 - Go 语言中使用 `rune` 来完整支持 UTF-8 字符解码。 - `ignore` 通过重设起始索引 `start = pos`，不发送任何 token 即可丢弃空白字符。 - `backup` 提供了单字符回退能力，配合状态机在关键分支处无缝平移。 ### [026:29] 基础光标移动：backup 与 peek Rob Pike 介绍了词法分析器用于在输入流中调整读取位置的关键辅助方法。词法分析器的 `next` 方法在前进时会自动记录读取的字符宽度（width），因此当分析器读取过头时——比如本来并不想步入某个数字字符——执行回退极为简便：只需调用 `backup`，将内部位置 `pos` 减去刚记录的宽度即可。正如 Rob Pike 所言：“Oops, nope, that was wrong, back up.”（“哎呀，不对，读错了，退回去。”） 与此配合的是许多同类文本处理软件中常见的 `peek` 方法。它的核心需求是：“我不打算真正向前推进，但我必须提前知道接下来是什么。”在当前的词法分析器架构下，实现 `peek` 异常平凡：只需调用一次 `next` 读取下一个 rune，紧接着立即调用 `backup` 退回一步。这种组合虽然简单，却赋予了分析器无损向前窥探单个字符的能力，为后续构建更高级的匹配逻辑铺平了道路。 ### [027:06] 字符接收器：accept 与 acceptRun 拥有了基础的位置游标操作后，Rob Pike 引入了两个强大的字符接收器（acceptor）方法，用以极为干净地扫描复杂的文本片段。第一个方法是 `accept`，它是绑定在 `lexer` 上的一个方法。调用方会向它传入一个包含合法字符集的字符串（例如一串纯数字或一组字母），询问当前输入中的下一个字符是否属于这个字符集。其内部通过 `strings.IndexRune` 来判断下一个字符是否存在于指定字符串中。如果匹配成功，字符被正式消费并返回 `true`；如果匹配失败，说明读取超出了预期范围，分析器会自动调用 `backup` 撤销这一步操作并返回 `false`。 第二个辅助方法是 `acceptRun`。它的参数与 `accept` 相同，但内部置于一个 `for` 循环中，意图是“尽可能多地吸收匹配字符”——例如直接吃掉一整串连续的数字或连续的英文字母。在当前的模板词法分析器实现中，`acceptRun` 甚至不需要返回值，只要持续贪婪地循环吸收合法字符即可；不过在其他场景下，也可以让其返回是否匹配到了任何内容。这两个接收器极大地简化了复杂的匹配逻辑，免去了手写大量条件分支和位置计算的麻烦。 ### [028:17] 解析数字常量与解析器的分工协作 为了展示 `accept` 与 `acceptRun` 的威力，Rob Pike 以数字的词法分析为例。数字的解析实际上相当棘手：它涵盖十进制、八进制、十六进制，还包括带有小数点或不带小数点的浮点数、正负符号、正负指数以及各种变体。Rob Pike 调侃道，如果试图用正则表达式来完整匹配所有数字形式，“你可以试着写写看，写出来的表达式大概有这么长，会让你大吃一惊”。而在本词法分析器中，由于底层机制一直在通过 `pos` 指针自动追踪切片范围，代码根本不需要手动维护提取出的子串，只需要一路找到数字的边界即可。 扫描数字的完整流程如同流水线般优雅推进：首先调用 `accept("+-")` 吸收可能存在的前置正负号；接着默认将候选字符集设为十进制数字；随后调用 `accept("0")` 与 `accept("xX")` 探测是否为十六进制，若成立则将字符集切换为十六进制的 `0-9a-fA-F`；紧接着调用 `acceptRun` 贪婪吸收整串基数对应的数字。在此之后，若能通过 `accept(".")` 接收到小数点，则继续吸收小数点后的数字；若能接收到指数符号 `eE`，则继续处理其符号与后续指数数字。Go 语言还原生支持虚数常量，因此末尾还尝试调用 `accept("i")` 吸收虚数单位。当到达数字的最长边界后，分析器还会做一项错误校验：紧随其后的下一个字符绝不能是字母数字字符，必须是空格或标点等合法分隔符，否则就属于非法语法。 ```mermaid flowchart TD accTitle: 数字词法分析流程 accDescr: 展示 Lexer 扫描数字字面量时依次调用 accept 与 acceptRun 处理符号、进制、小数、指数及虚数后缀的完整逻辑。 subgraph SignAndBase["1. 符号与基数探测"] A["进入 lexNumber"] --> B["accept('+-')<br/>可选正负号"] B --> C{"探测 0x/0X?"} C -->|"是"| D["基数设为十六进制<br/>acceptRun('0-9a-fA-F')"] C -->|"否"| E["基数设为十进制<br/>acceptRun('0-9')"] end subgraph Parts["2. 浮点、指数与虚数"] D --> F["accept('.') 探测小数"] E --> F F --> G["accept('eE') 探测指数"] G --> H["accept('i') 探测虚数单位"] end subgraph ValidationAndEmit["3. 校验与发射"] H --> I{"下一个字符是否为<br/>合法边界标点/空白?"} I -->|"否 (仍为字母数字)"| J["l.errorf 报错"] I -->|"是"| K["emit(itemNumber)"] K --> L["返回 lexInsideAction 状态"] end ``` Rob Pike 特别强调了词法分析器（lexer）与语法解析器（parser）之间的合理分工：当前逻辑确实可能匹配出并非合法常量的字符串（例如十六进制中带有浮点指数形式的 `0x3e4`）。但他明确指出：“It's fine for a lexer to say, 'I think I know what this is,' and still the parser to validate it.”（“词法分析器说‘我觉得我知道这是什么’，并留给解析器去验证，这是完全没问题的。”）词法分析器的职责只是负责找出最大长度的潜在数字串，然后将其发射为 `itemNumber`，直接交由 Go 标准库中现成的数值转换函数去严格校验。一旦发射完成，状态函数将返回 `lexInsideAction`，让状态机继续在动作内部运转。 ### [032:10] 优雅的错误状态与终止机制 随后 Rob Pike 剖析了代码中的错误处理设计。在状态函数中，报错并不是抛出异常，而是通过 `return l.errorf(...)` 来完成。因为任何状态函数都必须返回一个状态函数类型（`stateFn`），所以这里的 `errorf` 本身也设计成了一个返回 `stateFn` 的函数。`errorf` 的接口形式类似于 `fmt.Printf`，接收格式化字符串与变长参数（即 `interface{}`，Rob Pike 类比为通用对象或 C 语言的 `void *`），能够输出包含出错上下文文本的高质量错误信息。 在 `errorf` 内部，它会将构造好的 `itemError` 与格式化文本发送到 `items` 通道中，随后关键的一步是直接返回 `nil`。由于前文定义的词法状态机在当前状态变为 `nil` 时会自动终止循环，返回 `nil` 意味着词法分析器彻底关闭停机。Rob Pike 强调，他坚信极佳的错误提示至关重要，而这种设计提供了一种极简且优雅的报错路径。对于模板扫描而言，一旦遇到语法错误，停下来正是最合理的选择，它完美契合了当前的并发状态模型。 - `errorf` 具有类似 `printf` 的格式化签名，通过 `items` 通道发射 `itemError`。 - `errorf` 执行完毕后返回 `nil`，使主循环 `for state!= nil` 自然退出并关闭状态机。 - 采用提前探测错误并生成携带上下文文本的错误信息，免去下游解析器猜测错误原因的负担。 ### [033:39] 初始化阶段的并发死锁困境 在总结这套词法分析器的构建体验时，Rob Pike 表示自己仅用了一个晚上（甚至更短的时间）就完成了原型。在推翻并丢弃了前几种令人不快的实现方式后，一旦将词法分析与解析器之间的结构性不匹配问题视作并发问题来解决，通过 Go 语言切片、状态函数闭包和通道，一切都变得异常顺畅且富有乐趣。然而，这套自鸣得意的设计却遭遇了一个致命现实问题：Go 语言的包初始化规范（package initialization）。 在真实的 Web 场景中，开发者通常希望将 HTML 模板声明为全局变量，并在程序启动的 `init` 阶段完成模板解析，以便服务启动后立即可用。然而，Go 语言为了维持清晰确定、没有歧义的包初始化语义，做出了非常严格的语言规范决策：禁止在初始化函数执行期间运行并发的 goroutine 直至其完成。Rob Pike 严肃地解释了这一规则背后的权衡：“It was a difficult decision, but we decided you just simply cannot run a goroutine to completion during initialization. You can create one, but it won't run — it doesn't run until initialization is done.”（“这是一个艰难的决定，但我们最终决定：在初始化期间，你绝不能让一个 goroutine 运行直到完成。你可以创建一个 goroutine，但它不会运行——直到初始化全部完成它才会跑。”） 这就导致了严重的冲突：由于当前的词法分析器严重依赖后台独立 goroutine 与解析器通过通道并发通信，如果在包全局变量初始化（或 `init` 函数）中解析模板，词法分析器的 goroutine 根本不会被调度执行，通道读取将陷入永久阻塞与死锁。这一限制险些彻底推翻“并发词法分析”的实用价值，但他随即安抚听众不必担心：这个问题不仅有解，而且解决起来出奇地容易。 ### [35:25](https://www.youtube.com/watch?v=HxaD_trXwRE&t=2125s) 移除显式并发：封装传统的 NextItem API Rob Pike 谈到，可能有人会觉得大费周章设计了如此优美的并发模型，现在却要“把并发拿掉”听起来很糟糕。但实际上，只通过极少的代码改动就能把原先基于 channel 的词法分析器改造成传统的词法分析 API（即调用者只需反复调用一个函数来获取下一个 token，完全不需要关心 channel）。在改造过程中，构造函数 `lex` 不再直接把 channel 返回给调用方，而是返回词法分析器本身的句柄（handle）。在内部，程序依然创建了一个 channel，但将其隐藏起来并加上了缓冲（buffering）。通过给 channel 添加两三个单元的缓冲容量，它实质上变成了一个环形缓冲区（ring buffer）：词法分析器可以向其中 emit 若干 token，稍后再自行读取，从而摆脱了原本严格的同步限制。 ```mermaid flowchart TD accTitle: 传统 nextItem API 执行流 accDescr: 展示 nextItem 函数内部通过 select 消费 channel 并在无就绪 token 时驱动单步状态机的逻辑流程 subgraph API["nextItem() 内部循环"] Start(["调用 nextItem()"]) --> Sel{"select 多路监听"} Sel -->|"channel 中已有就绪 item"| Ret["直接取出并 return item"] Sel -->|"default: channel 为空"| Step["执行单步状态函数: state = state(l)"] Step --> LoopCheck{"是否有 token 吐出到 channel?"} LoopCheck -->|"已生成 token"| Sel LoopCheck -->|"未生成（继续循环）"| Sel end ``` 为了让外部解析器（parser）能够按照传统方式拉取 token，Pike 引入了 `nextItem` 方法。虽然表面上它替代了原本常驻后台的 `run` 循环，但内部运行机制完全相同，只是进行了解构：在一个无限循环（`for {}`）内放置一个 `select` 语句。如果内部的 item channel 中已经有词法分析好的 token，`select` 分支立即将其读出并返回给调用者；如果 channel 为空，则走 `default` 分支，在该分支下驱动状态机向前推进单步迭代（`state = state(l)`）。如果这次推进没有生成 token，循环继续，`select` 再次走 `default` 推进状态机，直到成功生成 token 为止。 Rob Pike 称赞这段实现说：“So it's kind of magic this is sort of the most magical slide of the ones I'm showing you but if you don't understand this that's okay all I want to show you is that that's all that was required to remove the concurrency from the picture.” 外部使用者看到的只是一个再普通不过的 API：创建一个词法分析器，并在循环中调用 `nextItem` 直至遇到 `EOF`；然而在底层，内部依然保留着利用并发思想构建出的干净、清晰的架构。 --- ### [38:28](https://www.youtube.com/watch?v=HxaD_trXwRE&t=2308s) 并发作为设计手段与模板系统的演进 Rob Pike 强调，如果一开始就从编写 `nextItem` 这个 API 出发，开发者很可能写不出这么优雅的词法分析器。传统方式通常需要使用庞大的 `switch` 语句，每次重新进入函数时都必须痛苦地做状态恢复（state recovery）、判断当前所处位置并不断重启。而利用并发与状态函数的设计，重启不过是将状态机稍作不同形式的运转，状态函数原本的清晰度与表达力完全得以保留。 Pike 由此引出了关于并发的核心观点：“Concurrency is a design approach it's not about parallelism concurrency enables parallelism doesn't require it it's really about thinking about your problem as independently executing items that may run at the same time or not but conceptually each one is an independently executing item.” 他幽默地指出，这里用来解决结构失配（structural mismatch）的理论来自于计算机科学家 Michael Jackson，“顺便说一句，他并不是那位音乐家，以免你们以为是同一个人。” 并发不是灵丹妙药，但它带来了一种优雅的设计维度；结合 Go 语言的方法与面向对象特性，使得整个架构具有极强的适应性。演讲中所展示的词法分析器代码其实是他从版本库里翻出的第一天写的早期版本，随着模板语言在边设计边开发的过程中增加大量功能与 token 类型，每次调整都仅仅是修改一两行代码或增加一个两行的状态函数，这种扩展性是旧版模板系统所完全不具备的。 - 总结寄语：“Lexers are fun concurrency is fun and go is a lot of fun so I encourage you to play around with it.” - 官方资源与版本计划：所有 Go 代码与相关信息均托管在 `golang.org`。演讲中介绍的新模板系统将在下一个版本中取代旧系统，旧系统已被废弃（deprecated）。 --- ### [41:04](https://www.youtube.com/watch?v=HxaD_trXwRE&t=2464s) 问答环节：构建产物、性能开销与状态机步进 进入问答阶段后，现场观众就构建产物形态、执行性能以及并发执行细节提出了具体问题： 一位观众询问编译输出的形式，比如在.NET 场景下它是否表现为可引用的库文件。Rob Pike 回答，Go 通常编译为静态链接的独立二进制文件（statically compiled binary），其性能特征是编译型语言而非解释器。词法分析器则是作为标准库代码链接进程序中。Go 官方支持多种 CPU 架构和操作系统，当时社区也有人在开发面向.NET 的实现，但 Go 的核心定位始终是高效的静态编译型语言。 另一位观众询问该词法分析器是否有性能测试数据（performance stats）。Pike 坦承自己在开场前就料到会有人问性能，但他目前还没有做基准测试： > “The answer is it's probably okay but not great because I'm using the language a little too having a little too much fun with the language and doing the channel communication and and that kind of stuff actually puts more overhead into the inner loop than that needs to be there.” 他进一步分析，如果追求极致性能，内部循环中由 channel 通信带来的开销是可以被进一步优化的；不过状态函数本身的性能在理论上已经非常接近最优解。唯二能比它更快的做法只有手写状态机、利用数组查表并跳转函数指针，但结构本质其实相差无几。 针对取消外部 goroutine 后的执行机制，另一位观众提问如果存在多个处理阶段，能否重新把 goroutine 加回来在初始化外部运行，以及 `nextItem` 是否会在没有 token 时发生阻塞。Pike 解释道，在模板解析阶段必须让词法分析执行完毕以构建解析树，不可能将其无限期搁置。至于 channel 缓冲大小，数字 `2` 是一个很精妙的设计（magic number），因为在当前实现中，词法分析器单次调用最多只会吐出两个 token；虽然将缓冲区设置得更大也完全可行，但没有必要。在调用 `nextItem` 时，词法分析器在生产出所需 token 前会持续运转，若是跨 goroutine 通信，在未获得下一个 token 时确实会等待阻塞；如果把 channel 缓冲区设得极大，词法分析器确实可以跑到很远之前，但在当前场景下并没有超前执行的必要。 ### [44:32](https://www.youtube.com/watch?v=HxaD_trXwRE&t=2672s) 并发与线性的执行模型 Rob Pike 在回答现场观众前强调了当前词法分析器（lexer）的运行特性。虽然通过 goroutine 和 channel 实现了结构上的解耦，但整个设计完全是同步的，因此根本不存在复杂的调度问题。从底层的控制流来看，它始终是单线程且线性执行的：词法分析器吐出一个 token 就会停下来等待解析器（parser）读取，解析器需要 token 时才会推进词法分析器。这种模式属于并发（concurrency）而非并行（parallelism），线程无需频繁切换上下文。 ```mermaid flowchart LR accTitle: 词法分析器与解析器的同步控制流 accDescr: 展示词法分析器与解析器通过无缓冲 Channel 实现严格同步的交替线性执行 subgraph LexerSide["词法分析器 (Goroutine)"] L1["运行状态函数 stateFn"] L2["向 Channel 发送 item"] end subgraph ParserSide["解析器 / 客户端"] P1["从 Channel 接收 nextItem()"] P2["处理抽象语法树 AST / 逻辑"] end L1 --> L2 L2 -->|"阻塞等待接收"| P1 P1 --> P2 P2 -.->|"请求下一个 Token"| L1 ``` 随后主持人转达了来自 IRC 聊天室的提问：是否可以放弃 channel，改用列表（list）或向量（vector）将所有 token 收集起来？Rob Pike 透露，在他写完这套代码后，同事 Nigel Tao 确实提交过一个修改清单（Changelog / CL），把 channel 换成预存列表，这样能消除可能的微小性能开销。“The solution gets pretty because you can use concurrency to solve the problem and there's nothing inherently concurrent about the problem only the solution,” Rob Pike 明确指出。问题本身并没有并发属性，但引入并发能让代码设计变得优雅；如果未来遇到极其苛刻的性能瓶颈，他也会毫不犹豫地手写约 10 行代码实现一个环形缓冲区（ring buffer）。 现场有观众询问整个分析流程中输入文本被拷贝了多少次。Rob Pike 斩钉截铁地回答是“零次”。整个词法分析器接收一个原始字符串，后续所有传递给解析器的 token 都是基于原字符串的切片（slice）。即使输入包含数兆字节（MB）的纯文本而没有任何模板标记，Go 也绝不会复制这几兆字节的数据，切片操作开销极小且无内存拷贝。 - 内存开销极低：词法分析器对输入文本实现零拷贝（zero-copy），仅通过底层字符串切片（string slicing）传递 token 内容。 - 架构权衡：用并发通道传递 token 主要是为了代码结构的优雅与清晰；若要极致性能，可无缝替换为手写的环形缓冲区（ring buffer）。 ### [46:39](https://www.youtube.com/watch?v=HxaD_trXwRE&t=2799s) 拓展支持 io.Reader 与 Go 语言的设计哲学 现场观众接着提问，如果要让词法分析器支持 `io.Reader` 接口而不是预先读取好的字符串，需要改动多少工作量。Rob Pike 解释说这非常容易实现：`io.Reader` 是 Go 语言中表示任何可读流（如文件、网络连接、内存缓冲区）的标准接口。若要改为流式驱动，只需在词法分析器结构体中增加相应的字段，并改写内部的 `next()` 方法去读取流。虽然在流上实现字符回退（backup）可能会稍显繁琐，但并不困难。在专注小模板解析的 `template` 包中，直接传字符串足以胜任；若用于通用正则表达式扫描器，基于 `io.Reader` 就会合理很多。 谈及这种设计是否会推广到 Go 标准库的其他解析器（如 XML、HTTP 或日期解析）时，Rob Pike 表示目前没有专门针对这些进行重构，但他提到了前一周的轶事：有人在博客上写文章用正则表达式去解析 HTML，结果被他“迎头痛击”（Smackdown）。值得称赞的是，那位作者认真接受了意见并修正了实现方式。 关于为何选择这个主题做分享，Rob Pike 总结道，词法分析虽然是一个冷门的极客问题（“Not very many people write lexers for a living”），但这套代码完整展现了地道的 Go 语言风格（Idiomatic Go）： “It's not clear that it's the solution to world hunger, but it's a solution to Lexing my templates,” Rob Pike 幽默地解释道。它巧妙融合了适度的并发、小巧的面向对象封装、灵活的字符串操作以及方法与一等函数（first-class functions）的协作。 - 适配扩展：只要将内部读取字符的 `next` 逻辑绑定至 `io.Reader` 接口，就能以极小的改造成本支持流式输入。 - 核心设计元素：兼顾了函数作为状态（state functions）、goroutine 同步解耦、无类型转换的多态调用。 ### [48:39](https://www.youtube.com/watch?v=HxaD_trXwRE&t=2919s) 语法分析生成器对比与事件监控 一位观众探讨了该技术是否可拓展用于语法分析生成器（parser generator），让工具自动生成类似的 Go 代码。Rob Pike 认为理论上完全可行，因为词法分析器和语法分析器本质上都是状态机。但他指出两者的复杂度不在同一个数量级：当前的模板词法分析器大约只有 10 到 15 个状态函数，而一个通用的语法分析器通常拥有数百个状态，纯手工编写会产生大量模版样板代码（boilerplate），更适合交由生成器生成。他还提到了状态机编译器 Ragel，指出 Ragel 生成的代码在底层逻辑上与这种状态机模型同构，只是机器生成的跳转更晦涩难懂。 随后观众追问：若处理非常大的文件，如何向外发送进度更新（progress updates）或事件通知，甚至将某些内容写入磁盘？Rob Pike 指向了幻灯片中的并发 `select` 语句。借助 `select` 的多路复用能力，仅需增加大约四行代码，就可以增加一个信号通道： - 外部可在任意时刻“ping”词法分析器以轮询当前处理偏移量； - 或者让词法分析器在主循环中设置计数器，每处理 1KB 或 10KB 自动向通道推送一次进度通知。 至于在特定条件下将数据写入文件，Rob Pike 笑着表示 Go 是完整的通用编程语言，随时都能执行写文件操作，“Files are cool, underrated.” 分享进入尾声时，Rob Pike 看了一下时间，突然向全场观众致歉：由于出现了极其糟糕的日程冲突（scheduling conflict），他在半小时前（讲座刚开始时）本该准时出席另一场重要安排，因此不得不立刻离场，演讲在匆忙而热烈的氛围中结束。 ## Notable quotes > [38:28](https://www.youtube.com/watch?v=HxaD_trXwRE&t=2308s) Concurrency is a design approach it's not about parallelism concurrency enables parallelism doesn't require it it's really about thinking about your problem as independently executing items that may run at the same time or not but conceptually each one is an independently executing item. — Rob Pike > [09:03](https://www.youtube.com/watch?v=HxaD_trXwRE&t=543s) 在解析输入时，生成优质的错误信息非常重要，而工具往往让输出良好的错误信息变得比预期更加困难；在词法分析阶段，这尤其是一个棘手的问题。 — Rob Pike > [28:17](https://www.youtube.com/watch?v=HxaD_trXwRE&t=1697s) It's fine for a lexer to say, 'I think I know what this is,' and still the parser to validate it. — Rob Pike ## Mentioned Rob Pike, Michael Jackson, Go, Google, Google Technology User Group, GTUG, Lex, Mike Lesk, Eric Schmidt, Ragel, text/template, Nigel Tao, Unix ## Video description Lexical Scanning in Go, a talk by Rob Pike at Google Technology User Group given on Tuesday, 30 August 2011. The slides: http://rspace.googlecode.com/hg/slide/lex.html [Source](https://www.youtube.com/watch?v=HxaD_trXwRE)

[38:28] Rob Pike: Concurrency is a design approach it's not about parallelism concurrency enables parallelism doesn't require it it's really about thinking about your problem as independently executing items that may run at the same time or not but conceptually each one is an independently executing item. [9:03] Rob Pike: 在解析输入时，生成优质的错误信息非常重要，而工具往往让输出良好的错误信息变得比预期更加困难；在词法分析阶段，这尤其是一个棘手的问题。 [28:17] Rob Pike: It's fine for a lexer to say, 'I think I know what this is,' and still the parser to validate it.

[28:17] Rob Pike: It's fine for a lexer to say, 'I think I know what this is,' and still let the parser validate it. [44:32] Rob Pike: The point about this is there's nothing inherently concurrent about the problem only the solution; the solution gets pretty because you can use concurrency to solve the problem. [0:02] Rob Pike: When you do a coroutine model right, you get to write both pieces of the problem—the block reader and the line processor, or whatever—completely independently, and they switch control as necessary and the program can become quite a bit nicer as a result.

[0:02] okay we're now [0:03] recording hi everyone um again welcome [0:06] to uh tonight's GTG the August Google [0:09] technology User Group here in Sydney um [0:12] um tonight uh Rob Pike and myself will [0:14] be giving a pair of talks about the go [0:16] programming language um and I'd like to [0:17] welcome Rob uh first up to talk about [0:21] lexical scanning and [0:27] go thank you are we good Tim yep okay uh [0:31] yeah I'm here to talk about let's go [0:33] scanning and go excuse me um thanks [0:35] everyone for coming and of course this [0:37] is streaming out live and will be [0:39] available I think on YouTube later yes [0:42] um yes I hear okay um so how many of you [0:45] are familiar with the work of Michael [0:48] Jackson really quite a few a couple [0:51] maybe all right well as you know Michael [0:52] Jackson developed Jackson structural [0:54] programming which was a model uh based [0:57] uh for solving uh structural mismatch [1:00] problems in Computing um and these come [1:03] up a lot and he really pointed out I [1:05] think correctly that many programming [1:07] problems deal with having data in one [1:09] form and data in another form trying to [1:11] connect them up and you find that the [1:12] flow of control on both sides doesn't [1:14] really work very well so you've got [1:16] blocks coming in you want to turn to [1:18] lines and you have partial lines and [1:19] partial blocks and it's all kind of a [1:21] mess and a lot of programming is very [1:23] difficult to get right when you have to [1:24] deal with these things and pretty much [1:26] any sort of data processing problem has [1:28] at least some aspect of that flavor in [1:30] it examples are obvious blocking [1:32] unblocking packet assembly and even to [1:34] some extent Lexing and [1:36] parsing um these these two pieces are [1:39] particularly difficult because usually [1:40] you've got some maybe some buffering on [1:42] each side you've got some look ahead [1:43] some State you got a peek ahead look [1:45] behind and you're doing it on both sides [1:46] at once and it's quite messy um it's [1:49] actually I believe true that co-routines [1:52] were dis invented discovered as a way of [1:55] solving this particular problem before [1:57] even Jackson had pointed out that this [1:58] was a problem in itself and so [2:01] coroutines are kind of the the origin of [2:03] of concurrent programming and yet they [2:04] were solv they were invented for this [2:06] notion very simple sort of distributed [2:08] not sorry non-distributed data [2:10] management problem which is kind of [2:11] interesting when you do a cotin model WR [2:14] you get to write both pieces of the [2:16] problem the the block reader and the [2:18] line processor or whatever completely [2:20] independently and they switch control as [2:22] necessary and the program can become [2:23] quite a bit nicer as a result and I'd [2:26] like to look at that sort of approach on [2:28] the concept of uh lexical scanner [2:30] um and the context for lexical St [2:32] scanner is a template system I did a a [2:36] text template system which you can think [2:38] of as an HTML template system but it was [2:39] a little more General than that uh very [2:41] early in the development of the go [2:43] libraries and it to be honest it wasn't [2:44] very good we thought it was really cool [2:45] of the time uh we were wrong um it was [2:49] pretty inflexible and inexpressive [2:50] people stumbled on it a lot of other uh [2:52] contributors came up with other [2:54] approaches to templates that were [2:55] probably more suited to what they wanted [2:57] to do but most important for me the code [3:00] was very fragile and as it developed we [3:02] started to want to add things like [3:04] numerical constants and quoted strings [3:06] and the whole code just sort of didn't [3:08] accept it very well it was clunky and so [3:10] a while ago uh earlier this year I [3:12] decided to write a new one knowing what [3:14] we know about what templates ought to [3:15] look like but this time building them as [3:17] a proper Lex parsed template thing that [3:21] I could then write clean good code and [3:23] what I want to show you today is how the [3:24] Lexa Works in that which is about as [3:26] nerdy a thing as you can talk about but [3:28] I think you'll find that it's actually [3:30] quite pretty how it turned out so what [3:32] we have is a new template system I'm not [3:34] going to teach you the template system [3:35] it's beyond the scope of this talk [3:37] although it's probably a good talk on [3:38] its own um I just want to point out what [3:41] it is we're actually looking for when [3:42] we're Lexing the templates so we have [3:44] this arbitrary text and these things [3:46] called actions which are delimited by [3:47] pairs of braces two open braces two [3:49] closing braces everything between is an [3:52] action that might be some text to an [3:54] expression to evaluate or a method to [3:56] call or some field of a data structure [3:59] and so on so here's some examples um the [4:01] simple evaluator just consists of of a [4:03] field of a data structure. title there's [4:05] sort of an implicit context in which [4:06] that's evaluated um there are constants [4:09] and functions so you can do things like [4:11] call Print F inside there and it knows [4:12] how to format that number as a hex [4:15] number and yes that truly is a complex [4:17] constant in there uh this might be the [4:19] first introductory template slide that [4:20] has a complex number on it but hey it's [4:22] there uh there are control structures [4:24] obvious things for looping and and [4:26] conditional evaluation and stuff like [4:27] that so you can see what we have is is [4:29] the basic lexes of just about any [4:31] programming language you're going to use [4:33] except Pearl um so today I want to talk [4:36] about the lexer itself what it does and [4:38] that means we have to think about the [4:40] things we want to extract from the input [4:41] stream and deliver as what are called [4:43] tokens so obviously there's the stuff [4:45] outside the actions that's trivial [4:46] that's just text but then we have the [4:48] delimiters for the actions the [4:50] identifiers and thing other things [4:52] inside the actions like numeric [4:54] constants strings odds and ends bits and [4:57] pieces and these are the individual [4:59] usually multi character pieces that the [5:01] parser will use to construct a parth [5:03] tree with which you can evaluate the [5:05] template so how do you how do you [5:08] represent a Lex item a thing you deliver [5:10] to the the parser now the usual way you [5:12] do this is you you have a lexer that [5:14] delivers these things called lexs or [5:16] items I call them items Lex items and [5:19] they consist of two pieces there's a [5:21] type and there's a value and the type is [5:24] usually just an integer that identifies [5:26] what it is and so for example if you're [5:28] delivering the number [5:30] 23.2 the typee of the item is going to [5:32] be number or some some constant that [5:34] represents the type number and the value [5:37] is going to be 23.2 and it turns out for [5:39] this particular lecture and in fact true [5:41] for most lectures what you really want [5:43] is the string not the number 23.2 as a [5:46] floating Point number or anything like [5:47] that but just the textual string of the [5:49] Lexi so an item is a is the number and [5:52] the string represent the number or the [5:54] word or an identifier and the value of [5:55] identifier and so on and so on so [5:57] there's this thing called an item type [5:59] in there that's an actual defined type [6:02] and it's really trivial it's just an [6:03] integer so we Define and go type item [6:06] type int um which is a little bit like a [6:09] type def in in C or C++ but not really [6:12] because it it's not an alias it's a true [6:14] new type and it means that you can do [6:17] things with that type you couldn't do [6:19] with an integer and I'll show you one in [6:20] a minute and then we Define a bunch of [6:23] of uh definitions variables values [6:26] constants with that type to identify the [6:29] various lexam types we're going to be [6:30] emitting and we start with a list uh [6:32] there's a thing called item error which [6:34] is actually going to be helpful we'll [6:35] see why in a minute item dot item EF [6:37] which is very special and there's some [6:39] more coming up on the next slide but I [6:40] want to point out this first line inside [6:42] the constant block there that says item [6:44] error item type equals Iota that means [6:46] declare the constant called item error [6:49] whose type is item type and that equals [6:51] Iota is a um a nice little piece of go [6:54] code that says start counting as though [6:58] I'm going to create an enumerated [6:59] concept and then after that all of the [7:01] other items in the con block are going [7:03] to get sequential values so item error [7:05] is going to be zero item dots going to [7:06] be one item UF is going to be two but [7:09] those are not regular 012 they're 012 of [7:12] type item type okay and here's the rest [7:15] of them uh at least a lot of them uh so [7:17] you can see we've got some keyword [7:18] identifiers like else and end uh range [7:21] is a keyword there's the meta left meta [7:24] string and the right meta strings [7:25] represented as as types because that's [7:27] how you do this um and then an [7:29] interesting one here is item number [7:31] which I showed you earlier as an example [7:33] so when you want to emit 23.2 that's the [7:35] constant value of the item type that [7:38] goes along with that number so now we've [7:39] defined these what we know what a type [7:41] is just for the record let's show how [7:43] you print it and go even though we're [7:44] not going to print it in the examples [7:46] we're using it's great for debugging and [7:47] it's an interesting piece of go code now [7:50] the formatted library for go has uh [7:52] called print F which is very much like C [7:54] print a that you're probably at least a [7:56] little familiar with but it has one nice [7:58] property that's that's to go which is [8:00] that any type that has a method called [8:04] string Capital string that returns [8:07] string as a basic type is known to print [8:10] F and can be used by print F so you get [8:12] a default pretty print for that type [8:14] value so here is the type uh the item [8:18] now not the item type the actual item [8:21] which is a type remember it has those [8:22] two fields in it and here's the string [8:24] method that prints it out neatly for [8:26] probably debugging not much else um so [8:28] you switch on the actual contr type of [8:30] the item which is going to be like item [8:31] eof or something like that and there's [8:33] two special cases if it's eof chances [8:35] are you just want to say print it pretty [8:37] print as eof uh if it's got an error I'm [8:40] going to show you errors later the trick [8:42] is we're going to store the value of the [8:44] item as the actual error string even [8:46] though it's not inside the input we're [8:47] going to make up a value and store it [8:49] there and otherwise we just print it out [8:50] kind of neatly but there's a little [8:52] trick here because if you've got maybe [8:54] um a text block it might be like 10,000 [8:56] characters long you don't want to have [8:57] the printed out as a 10,000 character [8:59] blob so we check if the value is really [9:01] long we truncate it and put a dot dot [9:03] dot on so that is that little piece of [9:05] code there it's not particularly [9:06] interesting but once you've written this [9:08] you can just print F any item and it'll [9:10] print neatly on the on the [9:12] output okay those are items now what how [9:15] do we tokenize how do we take our input [9:17] stream and break it into the things of [9:20] of [9:23] item uh there's lots of ways to do it [9:25] that are are welln uh we could use a [9:27] tool Lex is a very famous one uh [9:30] originally written by Mike Les and then [9:31] re redone when he was an intern by [9:33] someone called Eric Schmidt um we could [9:35] use regular Expressions to do it uh we [9:37] can also write the code ourselves using [9:38] States actions and a switch statement [9:40] I'll show you that in a second we're not [9:42] going to do any of these but let me talk [9:43] about why I'm not using any of these [9:45] first of all tools there's nothing wrong [9:47] with using a tool to do this don't don't [9:49] take away from this that I think these [9:50] tools are a bad idea some of them are [9:52] pretty cool but I do think they have [9:53] problems that are often neglected one [9:55] thing is when you're parsing input it's [9:57] very important to get good error [9:58] messages and tools make it actually [10:00] harder than it should be to get good air [10:01] messages out and when you're Lexing it [10:03] tends to to be a particular problem you [10:06] also if you're using a tool you have to [10:07] learn the tool and you have to often [10:08] learn a language with which to program [10:10] the tool and so I think we already have [10:12] a language in hand why do we need to [10:14] learn another one it's it's sort of a [10:16] step back um a real problem though is [10:18] that the things can be large and even [10:20] slow um Lex is famous for generating [10:23] enormous data structures to run even [10:25] simple Lex machines and so I I think [10:27] it's actually not a very good program [10:29] for doing this anymore although things [10:31] like ragle are quite a bit better and it [10:33] can often be a fairly poor fit that the [10:35] tools that the Lang that the the tools [10:37] that the tool gives you to do the Lexing [10:39] can sometimes not fit very well what it [10:41] is you're actually trying to do um and [10:43] so Lexing is easy to yourself maybe we [10:46] just should but how do we do that well [10:47] we have regular expressions are a [10:48] standard thing and I don't want to talk [10:50] too much about this I actually wrote a [10:51] blog post about a week ago on this topic [10:54] just coincidentally I happen to be um uh [10:57] talking about uh a codee review with [10:59] somebody who was trying to do some [11:00] Lexing and he was using regular [11:01] expressions and I tried to explain him [11:02] why I thought that was a bad idea the [11:04] key point is that it's kind of too big a [11:06] tool for such a small job um Regular [11:08] Expressions engines are big and they're [11:10] complicated and they tend to have to [11:12] evaluate a large State space and often [11:14] the questions they're asking are much [11:15] harder than the question you need to ask [11:18] you don't need to see if any of these 55 [11:20] keywords when all you really need to [11:21] know is what the next character is and [11:23] things like that also it's a they're [11:25] very fancy bre expressions are beautiful [11:26] things I've implemented them I love [11:28] playing with [11:29] but they're a very Dynamic sort of [11:31] interesting expressive way of of doing [11:34] things um but when you're Lexing [11:35] everything's very static it's very [11:36] simple you know what the grammar is you [11:38] know what the lexes are and the dynamic [11:40] in Machinery is probably overkill for [11:42] this but it's not a it's not a bad way [11:44] to do it I just don't like to do it so [11:46] we should write our own because it's [11:47] easy right anybody can write code [11:49] especially programmers and so um there's [11:53] also a trick here to notice which is [11:54] once you've written a lexer for a modern [11:56] language by water I mean any kind of [11:58] programming language you'd see today [12:00] chances are it's almost the same lecture [12:01] as you use for any other language so [12:02] once you know how to do it once you can [12:04] do it for anything you want to write and [12:05] some of us tend to play with languages [12:06] for living so it's nice to know how to [12:08] do that um being able to adapt them [12:10] easily is great but of course that's [12:11] also an argument both for and against [12:13] tools because if the tool can do it once [12:14] then you can you can do it second time [12:16] just as easily I'll take it as an [12:18] argument against tools though so here's [12:20] how most people would write uh alexir if [12:22] they were decided to do it this way they [12:24] Define some states like inside a comment [12:27] inside text inside an action and then [12:29] they Define actions themselves like uh [12:32] you know absorb the next absorb up till [12:35] the end of the number or whatever and [12:37] then you switch you come in with the [12:39] state you decide what state you're in [12:41] you execute some action the result of [12:43] that action is probably to emit some [12:44] tokens but also give you back the new [12:46] state so when you hit the beginning of a [12:48] comment the action consumes the text [12:51] starts the comment and the new state is [12:52] inside comment um and so you you go [12:55] around here and it looks really simple [12:56] right anybody could write this but it's [12:57] kind of boring it's kind of repetitive [12:59] code it usually looks a little less [13:01] boring than this but it's still pretty [13:02] boring but I'd like to point out that [13:04] when you're in here let's say you're on [13:05] action two you return a state and then [13:07] you go back to the collar with your Lex [13:09] and you come back in again and you you [13:12] knew what state you were in but now the [13:13] system has to work it out again the [13:15] state variable has lost the place where [13:17] you were when you came back from action [13:19] two you knew that you were say in state [13:22] one so why do you need to leave and come [13:25] back and then figure out where you were [13:26] again and get back to where you were why [13:27] not just go right to state one there's [13:30] something wrong with this model right [13:32] it's not bad but you can do better so I [13:35] want to do better I want to not throw [13:38] away the state when we know what it is I [13:40] want to just continue to move to the [13:41] next state so we're always in this state [13:43] machine crunching along and so we have [13:46] to figure out what a state is and what [13:48] an action is so a state represents where [13:50] we are in the input and what we're [13:52] expecting to see next which may be a [13:53] number of different things that affect [13:55] what we do and the action represents [13:57] what we're going to do in that state [13:58] given us certain piece of input once you [14:00] execute the action you get a new state [14:03] and you go around again that's pretty [14:04] much the code so let's define a state [14:07] function we put we combine the concept [14:10] of a state and an action into a function [14:13] and that function has Type which I call [14:14] State function the bottom line of this [14:16] slide is a definition and go of a state [14:18] function and it's a little bit of a a [14:20] mindblower because a state function is a [14:23] function that returns a state [14:25] function and I give it the argument of [14:27] alexir here because we're going to need [14:28] that but don't worry about that lexer [14:30] detail it it could be a method of lexer [14:33] but then they'd be State methods and [14:34] that doesn't sound right so we'll just [14:35] call them State functions so I want to [14:36] point out this is a recursive type [14:38] definition a state function is a [14:41] function that returns a state [14:43] function okay now what do you do with [14:46] that well you run the state function [14:48] like this here is this here's the inner [14:50] loop of our lecture no switch anymore [14:52] instead what we do is we just hang [14:53] around looping we set state to the start [14:56] State whatever that is we'll come back [14:58] to that and then as long as the state is [15:00] not nil We Run The lexer and we run it [15:02] one state at a time by saying State [15:04] equals state of lexer what that means is [15:07] call the lexer sorry call the state [15:10] function with the lexer as an argument [15:12] the return value of a state function is [15:13] a state function so that's the new state [15:15] function you store it inside the [15:16] variable State and go around the loop [15:18] again so the switch statement we had [15:21] back here has now been folded into a [15:23] single line of code that just runs [15:25] itself constantly get a state call it [15:28] get a state call it get a state call it [15:30] and we don't have to work out every time [15:32] what state we we in and do a switch [15:33] statement to get back to where we just [15:34] were we're always in the right place the [15:36] PC is always pointing at where we want [15:38] to be next does everybody see that it's [15:41] it's at some level trivial at some level [15:42] it's kind of amazing but it's kind of [15:45] cute okay so now let's get real the [15:49] problem with this is of course nowhere [15:51] in here do you see anyone emitting any [15:52] tokens all we have is a state machine [15:55] somebody's got to get the tokens coming [15:56] out of Lexa and have and we've covered [15:57] that up so we do do that by adding the [16:00] concurrent step which is where go [16:02] actually comes in pretty nicely here the [16:04] idea is we're going to run the lexer as [16:06] a [16:09] co-routine in concurrently with the [16:12] client which is probably something like [16:13] a parser and they're just two [16:15] independent machines doing their own [16:17] thing Lexing generating lexim parsing [16:20] generating parse trees and then whenever [16:22] the lexer has a new thing it actually [16:23] lobs it over the wall to the parser [16:26] using a go Channel and if you don't know [16:28] what that is is just think of it as [16:30] being like a pipe in Unix terms except [16:32] it's got some you know stricter [16:33] semantics but essentially it's just a [16:35] way to deliver data over over a to [16:38] another part of the program that may be [16:40] uh running completely independently and [16:42] so we actually break the program into [16:44] the lexer running as one program over [16:46] here parser is another one and they [16:47] communicate using this channel of items [16:50] so let's define the lexer now we know [16:52] roughly what we're doing and here's [16:54] here's the definition of the lexer type [16:56] it's got a bunch of fields in it that [16:57] are not relevant yet but they will be [16:59] later the bottom one here is the one [17:01] that matters right now it says items and [17:03] that's a Chan of item so that declares [17:05] in go terminology a Channel of items [17:07] that is the pipe if you will on which [17:10] the lexer is going to deliver items to [17:12] the parser okay so now we got to create [17:15] one of these things and get it running [17:17] so let's write a little function that [17:19] creates alexir we give uh the function [17:22] returns alexir a pointer to alexir [17:24] actually but alexir and a Channel of [17:26] items it's kind of weird API there's a [17:27] reason for it this is all real code by [17:29] the way uh so there's some glitches in [17:31] here which are going to get fixed later [17:33] this is a very early version of the code [17:35] um and we have this function Lex that [17:37] takes a name and an input [17:39] string creates this lexer data structure [17:41] by filling in the relevant Fields notice [17:43] in go you don't only have to fill in the [17:44] ones you care about the rest will be [17:46] initialized to zero and then this line [17:49] here is where the magic starts go l. run [17:52] that starts up remember we had this run [17:54] Loop l. run like [17:57] that we're going to run it can currently [17:59] run the state machine in parallel with [18:02] us and then return so the state machine [18:04] is now off ready waiting for input of [18:06] generating lexs and now we return back [18:09] to the caller probably the parser that [18:10] started us and he's going to parse and [18:13] he's going to receive the lexim from the [18:15] channel That the runner is delivering on [18:17] so here's what the real run routine [18:18] looks like it's now a method of lexer [18:20] but still called run the only [18:22] differences between this and the little [18:24] sort of schematic version I showed you [18:25] before this is honest code there's no [18:27] cheats here uh we now know what what the [18:29] original initial state is it's going to [18:31] be plain text we probably start at the [18:32] beginning of the file expecting some [18:34] plain text for a while so we'll start in [18:35] the text state I'll show you that in a [18:37] second then we run the state equals [18:39] state of L Loop just like we did before [18:41] and then a little piece of go magic [18:43] don't worry about it close of l. itms [18:44] when we're done means uh tell it's a way [18:46] to tell the parser that it's not going [18:47] to get any more tokens that's kind of a [18:49] Nuance but I want to be honest about [18:51] what the code really looks like but it's [18:52] still the same loop as before and now we [18:54] know where to start we have to write a [18:56] state function called Lex text that's [18:58] what you do when your state is I'm just [19:01] processing regular text and I haven't [19:03] hit an action yet so in order to do that [19:06] we're going to have to find a way to [19:07] emit tokens back to the caller so here's [19:11] a couple more fields from that lecture [19:13] they were on the previous slide but I've [19:14] Vic them here the input string we [19:16] remembered that when we created the [19:17] lexer and we've got two integer [19:19] variables start and pause which aren't [19:21] particularly good names but that's what [19:22] they are um and the idea is you've got [19:24] this string that you're you're scanning [19:26] you're you're running I guess from your [19:27] you're running this way right and so [19:29] start is where the this token we're the [19:32] next token we're going to send out [19:33] actually begins and pause is where we [19:35] are in our scanning so when we have a [19:38] token that is the substring between [19:40] start and pause of the [19:42] input okay and so that's all we need to [19:44] know to do an emit so here's a me emit [19:47] method on lexer it takes an argument [19:50] which is the type and it sends on the [19:53] channel that little left Arrow less than [19:55] minus thing is a send operation it ends [19:58] on the items Channel an item constructed [20:01] from the type and the input string [20:03] sliced from the start to the position so [20:06] that lobs the the item over the wall to [20:08] the parser and then to move ahead in the [20:11] input all we do is move start up to [20:13] pause so you go scan scan scan SC aha [20:16] here's an item throw it over the fence [20:19] then do the next one throw it that's the [20:22] model okay it's all pretty [20:24] clean okay now we have almost everything [20:26] we need [20:29] to get it going I just need to focus now [20:31] on this is exactly the same code as [20:33] before I haven't changed it I just [20:34] wanted to put up again because there's [20:35] that Lex text word that's the start [20:37] state which is a really important thing [20:38] about a scanner what state do you start [20:40] in and what what Lex text is going to do [20:43] is scan the input until he finds an [20:45] action which is that left curly brace [20:46] started thing right so we have a [20:48] constant called Left meta which is what [20:50] Lex Tex is going to look for and when as [20:52] soon as it finds one of those it throws [20:53] out all the text that's found so far as [20:55] a plain text item and starts working on [20:58] actions so I think we're ready yes so [21:01] this is Lex text there's a lot of code [21:03] here um actually not that much but it's [21:06] really pretty simple at the top there's [21:07] a for Loop remember this is a state [21:10] function notice it's a it returns a [21:11] state function what we do is we loop on [21:14] the input advancing start until and [21:18] you'll see I'll show you how start gets [21:19] moved um and as long as you're not [21:22] sitting on a uh uh opening action left [21:27] brace pair so forever if the place you [21:30] are in the POS in the input which is [21:32] pause has a left meta that means you're [21:35] sitting on the left brace starting an [21:36] action and so everything from there back [21:38] to start is plain text so if that's if [21:43] it if that's a non-empty string if pause [21:45] is greater than start emit a text token [21:48] we showed you Emit and now the new state [21:51] is left Lex left meta because now we're [21:53] sitting we're right before the left meta [21:55] now we've got a lexim that we have to [21:57] find called Left meta we know how to do [21:59] that we do that by returning a state [22:01] function that knows how to scan a left [22:03] meta pair right so here's a state [22:06] function and it returns a state function [22:08] and then there's some stuff around how [22:09] to deal with eoff it's actually pretty [22:11] clean but I think it's more of a [22:12] distraction than anything so just think [22:14] of that for Loop uh you scan till you [22:16] find a left meta uh when you do you emit [22:19] any text that you found and then the new [22:20] state is Lex a left meta so let's s a [22:23] left meta it's a trivial one and it may [22:26] be actually an easier one to to see [22:28] what's going on here's a left meta [22:29] function uh State function so first of [22:32] all you know because of how you got here [22:35] that the input is sitting on that left [22:38] meta and so all you have to do is [22:40] Advance the position by the length of a [22:42] left meta you know it's there because [22:43] you've already checked that so you just [22:45] say pause plus equals now you've got [22:47] you've done that you're now sitting on [22:48] the pair of braces emit a left meta item [22:51] which you'll pull out the races and say [22:53] it's a left meta and now we've entered [22:55] inside one of these bracketed action [22:57] blocks [22:58] and so now our new state is Lex inside [23:01] and [23:02] action okay everybody following along [23:04] what's going on here it's pretty trivial [23:06] it looks it looks like there's a lot [23:07] going on but it's actually very simple [23:09] okay I'm going to go two more functions [23:11] into this to show you the model because [23:12] we want to get to a state where we can [23:14] really do some fun so this is what [23:16] inside and action looks like and this is [23:17] fairly representative of what you see [23:19] when you write [23:22] lectures what we do is we're looking for [23:24] what's next okay and inside action when [23:29] we're inside action we we're inside an [23:30] action we don't know what we're on is is [23:32] a number coming up is a identifier [23:34] coming up a string constant we don't [23:36] know so we got to ask what are we [23:37] sitting on right now so it's basically a [23:39] bunch of questions uh does the input at [23:42] this point have a right meta if that's [23:44] true we're no longer inside the action [23:46] and so we return to Lex the right meta [23:48] and I bet you guys could write that one [23:49] now right otherwise we better look at [23:52] what the next Rune is that's l. next the [23:54] next input character and we ask some [23:55] questions about it is the eof or new [23:57] line that's an error because that means [23:59] there's an we don't want actions [24:01] spanning a new line so there's an un [24:03] it's like an unbounded parenthesis here [24:04] so we return l. error F of that and I'll [24:06] show you how errors are handled later it [24:08] fits in beautifully uh if it's a space [24:10] we don't care it just means there's a [24:11] space in between the words and we just [24:13] ignore it I'll show you ignore in a [24:14] minute and then we get some interesting [24:15] ones if it's a pipe that's a pipe [24:17] character which is important to the [24:18] template system doesn't matter what it [24:19] does um then there's some more the [24:22] details uh if it's a double quote well [24:25] we go into Lex quote state if it's a [24:27] back quote we into the Le raw quote [24:29] state which is a different kind of [24:30] string and go which is useful to have in [24:32] the template system and then a couple of [24:33] interesting cases if it's a A plus a [24:36] minus or a digit then we've stepped into [24:39] a number we've gone one character into a [24:41] number so what we want to do is actually [24:43] back up I'll show you how to do that uh [24:46] and then say now we're going to Lex a [24:47] number and I'm going to show you Lex [24:48] number because it's kind of cool okay [24:50] and otherwise if that didn't work but [24:52] you're now on an alpha numeric you know [24:54] it's not a digit so it must be an alpha [24:56] and so now you back up again and now [24:58] you're doing an identifier okay and [25:00] there's about four more cases but I [25:01] think this gives you the flavor of how [25:02] this works and compared to what a [25:04] regular expression does to work this out [25:06] it's actually in some senses simpler of [25:08] course there's more code but it's really [25:10] nice how you just sort of pick a one [25:11] character what do I do now I move on [25:13] it's kind of [25:14] nice okay now I'm going to show you a [25:16] few helper functions that are important [25:17] to make this all work and then I'm going [25:18] to show you how to Le a number which is [25:20] kind of amazing so um next is the thing [25:23] that gives you the next input character [25:24] which we call a rune and go because it's [25:26] a full utf8 decoded character character [25:29] okay and so we ask um if the position if [25:33] we've reached the end of the string [25:34] we've got eof there's no more characters [25:35] to come eoff is sort of a Magic outof [25:38] Band Rune signal otherwise we parse the [25:41] next utf8 encoded character from the [25:44] input and set Advance the position by [25:46] that because this is next we're [25:47] absorbing that that string out of the [25:49] sorry that character out of the string [25:51] so we advance next best start and we [25:54] return the Rune that we actually got [25:56] which is probably going to be something [25:57] like an A or nine or parenthesis or [25:59] whatever so that gets you the next [26:01] character and moves steps you through [26:02] the input so you understand if you step [26:04] back what's happening is we're just [26:05] calling next to step through until we [26:07] find the transition out of this lexim [26:10] and that lexim goes out to the [26:12] parser okay now we got some helper [26:14] functions that are really nice to have [26:15] here's ignore remember when we saw space [26:17] we ignored it to ignore something just [26:19] said start to pause you just ignore it I [26:22] don't care what that is I don't need it [26:23] we're done okay backup is kind of the [26:26] inverse of next because next next [26:29] Advanced pause and remembers the width [26:31] so to back up one character in the input [26:33] because you've gone one too far you [26:34] stepped into the number but you didn't [26:35] really want to all you have to do is [26:37] back up pause you know I do I did this [26:39] oops nope that was wrong back up okay so [26:43] that back up and then there's this [26:44] lovely thing called Peak um which is in [26:47] a lot of this kind of software which [26:49] basically says I don't want to advance [26:51] but I need to know what's coming [26:53] sometimes you want to sort of literally [26:54] peek ahead one in the input without [26:55] actually reading it and that's trivial [26:57] you just call next and and then back up [26:59] right that's easy you can do it other [27:00] ways but that's that's an easy way to do [27:02] it and now we're ready to uh write a [27:06] couple of helpers that are really really [27:08] great for scanning complicated stuff [27:10] these are the acceptors and there's two [27:12] accept functions one is called accept [27:14] it's actually a method on lexer and what [27:16] you do is you give it a string of [27:18] characters that you think are okay to [27:20] have now you ask the question can I [27:22] accept one of these into the input and [27:24] it might be like a string of digits or a [27:26] string of alphabetics these are things [27:27] that might happen now and so what you do [27:30] is you just say does the string [27:32] basically that line there index Rune [27:34] says does the charact the next character [27:37] of the input is it an element of that [27:40] string and if the answer is yes you [27:42] return true you call next so you've [27:44] accepted it and you report back yes I [27:46] accepted one of those if it's false [27:49] you've actually gone too far so you back [27:50] up and say no I I can't accept one of [27:52] those now I'm on something else okay and [27:55] then accept run is the same except it's [27:57] in a four it just says accept as many of [28:00] these as you can I want a run of digits [28:02] or a run of alphabetics or whatever so [28:03] you give it a string same as you did for [28:05] accept but now it Loops absorbing as [28:07] many as it can and because of this [28:09] particular lecture we don't need a [28:10] return value but you could imagine [28:12] returning whether or not you got [28:13] anything okay now now we can do a number [28:17] and numbers are actually quite hard to [28:19] Lex especially if you think of a number [28:21] in all of their forms there's decimal [28:23] there's octal there's heximal there may [28:26] be other bases who knows there there are [28:28] floating Point floating point with [28:30] decimal floating point with uh without a [28:32] decimal exponents positives negatives [28:35] positive exponents negative exponents a [28:37] lot of formats for fun try to write the [28:39] right expression that matches a number [28:41] you will be surprised it's about this [28:43] long okay but now we're going to use the [28:45] tools we've built to Lex one really [28:47] neatly and here's how it goes now [28:50] remember we don't have to keep track of [28:53] where what we're actually pulling out of [28:55] the string because the the underlying [28:57] mechanis of the lexer just advancing [28:59] pause through the string is doing that [29:01] for us all we have to find is the end of [29:04] it so we just start at the top accept a [29:07] plus or minus notice it's a it's not we [29:10] don't care what the return value is if [29:11] it's a plus or minus that's fine we can [29:12] accept one of those doesn't matter if [29:14] it's not there we just accept it if we [29:15] can now we know we're probably looking [29:18] for a decimal number so we set the [29:19] digits to all the decimal [29:21] digits but it might be an octal or a hex [29:25] constant so ask the question can we [29:27] accept a zero and and an X if the answer [29:30] is yes then we have like 0x something [29:32] it's a hex number so Advance the base [29:34] set to 0 to F hexa decimal now we're [29:38] scanning a hex number now we accept a [29:40] run of those digits whatever base [29:42] they're in I noticed I didn't do octal [29:44] but I'll come back to that um now we're [29:47] at the end of the number maybe there's a [29:48] decimal point except if we can accept a [29:50] decimal point then there might be more [29:52] digits then if I can accept an exponent [29:55] there might be a sign for the exponent [29:57] in which case there might be more uh [30:00] digits to come for the exponent itself [30:02] and so we're sort of sucking up all of [30:03] this stuff now this is go go has complex [30:06] numbers and it's got imaginary constants [30:09] and this is actually a constant not a [30:10] true complex number so now we have to [30:12] question well maybe maybe I can accept [30:14] an I now because it's an imaginary [30:15] number and we're still just sucking all [30:17] this up as we go and then we do an error [30:20] check to make sure that things make [30:22] sense because when we get to this point [30:24] this is the longest we can possibly go [30:26] into a number and still be a number the [30:28] very next character can't be something [30:30] that it has to be something like a space [30:32] or a punctuation it can't be an alpha [30:34] numeric or the input's bad so there's an [30:36] error check but you kind of don't need [30:38] that but it's nice to get it early now [30:40] notice that if you think about this you [30:42] can write down constants that aren't [30:44] actually valid you might write 0x3 E4 [30:47] which isn't actually a valid constant [30:49] because you can't have heximal floting [30:50] Point numbers um and that's because it's [30:54] it's fine for Alexa to say I think what [30:56] I know what this is and still the parser [30:58] to validate it and there's a lot of edge [31:00] cases around numbers that are very [31:02] tricky to get right and so that's why we [31:03] didn't worry about octal versus decimal [31:05] and any of that stuff we said this is a [31:07] maximum length thing that might be a [31:08] number and now the parser I'm not going [31:11] to show you that code but the parser is [31:12] going to actually try to convert it to a [31:14] number and there's a number parser in [31:16] the library and it'll complain if [31:18] there's a mistake in that as a number so [31:20] we just have to find a maximal string [31:21] and let the pars do the hard work which [31:23] is kind of nice so you see how much [31:25] these accept functions are helping and [31:27] all this magic going on the covers it's [31:28] actually really it's actually kind of [31:29] fun to write this the first time you go [31:31] through it because you go that's really [31:32] easy kind of cool okay and then finally [31:35] once we're done we've moved pause up to [31:37] the end of the number so we emit item [31:40] type number that's almost the first [31:42] thing I showed you is the type number [31:44] idea item number so youit the number so [31:47] it's a number and it's this value is [31:48] this string from the input and now the [31:50] new state is we're back inside actions [31:53] again because we we know we started [31:54] inside an action we found a number we're [31:56] done with a number we're back in the [31:58] inside action State and so the state [32:00] machine will grind out okay everybody [32:03] reasonably comfortable with what's going [32:04] on here two or three of you are shaking [32:06] your heads most of you are noing it's [32:08] good okay now notice this error thing [32:10] one reason I want to show you this slide [32:12] is there's return l. error F and notice [32:14] it's a return this is a state function [32:16] so it has to return a state function [32:18] notice that the error is actually a [32:19] state state function itself in in a [32:21] sense errors look like this there's a [32:24] function called error F and using Go's [32:26] nice uh function call stuff you actually [32:29] error f is kind of a form of [32:35] printf so it looks like print there's a [32:37] format string and some arguments which [32:39] are the dot if you don't know what [32:41] interface open close means just think of [32:43] it as like a generic object or a void [32:45] star and so this lets you print anything [32:47] to that format um and what you do is [32:51] it's it's folded funny but that state [32:52] fun on the second line there is actually [32:54] the return type so error is actually a [32:56] state function that returns State [32:58] function and so now you send out on the [33:00] items Channel item that consists of [33:02] error and the nicely formatted error [33:05] that was printed by the tokenizers which [33:06] will include the text of the thing that [33:08] had the bad syntax I believe in really [33:11] good error messages this is a really [33:12] easy way to make them and now we return [33:15] nil remember that the state machine [33:17] stops when the state goes to nil so this [33:20] when we get an error we stop we just [33:21] shut down the machine we've got an error [33:23] we can't go on and of course you can [33:24] imagine doing other things to recover [33:26] and keep going but but still it's that's [33:28] pretty neat for the application of the [33:29] template scanner if there's an error in [33:31] the input you really don't want to keep [33:32] going you want to [33:34] stop so those are errors they fit in [33:36] really nicely to the model okay so [33:39] what's the story here well we've built [33:40] this little lexer You could argue that [33:42] it's more complicated than you wanted to [33:44] write you could be right I think it's [33:46] kind of cool how the state Machine Works [33:48] how goes slicing of strings managed to [33:50] make it all fit together really neatly [33:52] the idea of the tokens going over the [33:53] channel it's really it was really fun to [33:56] write it was really easy to write uh I [33:58] did it in an evening probably less than [34:00] that the first time around um after [34:03] throwing away a couple of other lectures [34:04] that were done other ways that I wasn't [34:06] happy with and I once I accepted it as a [34:08] concurrent problem to deal with this [34:10] structural mismatch between the lexer [34:12] and the parser and the input it all [34:14] worked out really neatly so you get this [34:16] these go routines running the channels [34:18] it's all really nice okay but there's a [34:21] problem the problem is when you want to [34:24] create a variable in in a go program as [34:27] a global like a template for an H for [34:29] HTML server and you want to be able to [34:32] deliver uh stuff to the user using a [34:34] parse template ready to run you want to [34:36] be able to build that template at [34:37] initialization time but you can't do [34:39] that in go because it would mean running [34:42] a go routine in initialization function [34:45] and that's actually against the rules [34:47] it's the reason it's against the rules [34:48] is go has very clean initialization [34:50] semantics and if you have concurrent [34:52] execution during initialization the [34:54] sematics get very very fuzzy and so it [34:56] was a difficult decision but we decided [34:58] you just simply cannot run a go routine [35:00] to completion during initialization you [35:02] can create one but it won't run it [35:03] doesn't run until initialization is done [35:06] and now we have a problem because this [35:07] lexer is concurrent but it can't run [35:09] during initialization which was which [35:11] sort of defeats the purpose of having H [35:14] HTML templates parsed at initialization [35:16] time but turns out it's easy to fix I [35:19] wouldn't be here okay now we have a [35:21] design for alexir that's really clean [35:24] and really nice but we have to take the [35:25] concurrency out again that sounds awful [35:29] right we've done all this work to set [35:30] this beautiful concurrent model but it [35:32] turns out it's like trivial code to take [35:34] it out again and that's kind of cool [35:36] what we do is we change the input what [35:39] we a sort of traditional Lexing API [35:42] doesn't involve channels and stuff like [35:44] that it's just got a function to get me [35:45] the next item so how do we transform our [35:47] existing code into that it's actually [35:49] just a couple of small changes first of [35:51] all we in the Lex Creator we don't [35:53] return the channel anymore we just want [35:55] the lexer the guy just wants a handle [35:56] for the Lex that makes sense okay okay [35:58] and then in the channel that we create [36:00] we still make a channel we're still [36:01] going to use one we're going to hide it [36:02] and we're going to buffer it and the [36:04] effect of buffering it is that it turns [36:06] it kind of into a ring buffer in the [36:08] sense that you can the lecture can emit [36:09] a few things into the channel and then [36:11] pick them up itself later it doesn't [36:13] it's not synchronously bound if you [36:14] don't know what that means don't worry [36:15] about it the point is we're sort of [36:17] cheating and turning a channel into a [36:18] ring buffer by just adding a couple of [36:21] sales of buffering to the channel so we [36:24] created just like we did before we [36:25] change the channel slightly and we [36:27] return the light [36:28] but no Channel back to the caller so now [36:30] he's got a handle on the [36:31] lexer now we write the next item [36:34] function which is the thing that most [36:36] lexes would expect to have used in order [36:38] to get the next token out for the parser [36:41] but remember we have this run Loop [36:42] running but and yet we can't stop [36:45] execution but it turns out it's very [36:46] easy to do it doesn't look like the old [36:49] run Loop but it's exactly the same thing [36:50] going on it's just decomposed a little [36:53] bit there's a Forever Loop and inside [36:55] this forever Loop we have a select [36:57] statement and select is goes concurrent [37:00] multi-way switch it says does any of [37:02] these things can any of these things [37:05] happen now and if the answer is not we [37:07] wait if the answer is yes that then one [37:09] of them will proceed so the thing the [37:12] way it works here is we have a select [37:15] and if the item can be received from the [37:18] channel of items that means we've Le [37:20] something that's ready then we just [37:22] return it and it's taken out of the [37:23] channel and delivered to the the caller [37:26] okay if not then we fall to the default [37:28] state which is what happens when nothing [37:30] can run and there only one of the case [37:33] so it means the other guy can't run and [37:34] now there's the inner loop of the Inner [37:37] Line of our Loop we just run State one [37:39] machine one iteration that may or may [37:41] not emit some tokens if it doesn't emit [37:43] tokens we'll go around again select will [37:47] fail we'll fall through default we'll [37:48] run it them again and we'll keep running [37:50] the state machine going around this Loop [37:51] until eventually we manage to emit a [37:54] token into the channel and once that [37:55] happens the caller will get it [37:58] so it's kind of magic this is sort of [37:59] the most magical slide of the ones I'm [38:01] showing you but if you don't understand [38:02] this that's okay all I want to show you [38:04] is that that's all that was required to [38:07] remove the concurrency from the picture [38:10] and yet and so now we have a totally [38:11] traditional API for lexer create alexir [38:14] and call next item on until you get eof [38:16] that's the whole API but under the [38:18] covers there's this very clean sort of [38:20] pretty lexical structure with [38:22] concurrency going on that we actually [38:24] use to design it a really nice internal [38:26] design [38:28] so we now have this traditional API and [38:31] it's really concurrent on the covers but [38:33] you can't see it and if you think about [38:35] it if you started trying to write the [38:37] next item API you probably wouldn't have [38:39] built such a nice lexer because you [38:41] would have had to do that state recovery [38:43] thing that you do in switches where [38:44] you're always coming back and figuring [38:46] what state you're in and restarting and [38:47] restarting the beauty of this thing is [38:49] the restart is just running the machine [38:51] a little differently it's still the same [38:53] machine it still feels like State [38:55] functions it still has all that clarity [38:57] so the design is still really good and [39:00] this is a really important point about [39:01] concurrency concurrency is this design [39:03] concept it's not about the way a lot of [39:06] people think about it sort of [39:07] parallelism it's actually a design idea [39:09] and we use it here to deal with this [39:11] structural mismatch from from Michael [39:13] Jackson Who by the way was not the [39:15] musician in case you think it was the [39:16] same guy um so Cony is a design approach [39:20] it's not about parallelism concurrency [39:22] enables parallelism doesn't require it [39:25] it's really about thinking about your [39:26] problem as independently executing items [39:29] that may run at the same time or not but [39:32] conceptually each one is an [39:34] independently executing item and it [39:35] gives you a real sort of Grace in design [39:38] that you don't get with a lot of other [39:39] approaches and sometimes concurrency is [39:41] a real win it's not a Panacea um but [39:44] it's still pretty nice and notice we [39:46] we're using methods and stuff like that [39:47] so we had objectoriented programming [39:48] along with concurrency it's kind of kind [39:50] of neat how that works and you get this [39:52] wonderful sort of adaptable model this [39:55] lecture has been this is the one I [39:57] showed you except for the last slide um [39:59] was like the first days version I went [40:01] back in the in the logs and pulled out a [40:03] really early one and it's been adapted [40:04] quite a bit as the le as the template [40:06] language has been worked out it was sort [40:08] of designed on the Fly um so there's a [40:11] lot more features to the Lexing a lot [40:13] more tokens to be found things like that [40:15] but each time it was like a one or two [40:16] line change or a two line State function [40:19] had to be added it was just I just loved [40:20] how easily it it changed as I needed it [40:23] which is something that was sadly [40:25] missing from the predecessor template [40:27] system [40:28] so in conclusion lectures are fun [40:31] concurrency is fun and go is a lot of [40:34] fun so I encourage you to play around [40:37] with it if you want to know more about [40:38] it of course golang.org is the website [40:40] where all this go stuff lives uh the new [40:43] template system is actually kind of [40:45] interesting I think uh and Andrew will [40:47] show you a little tiny bit of it later [40:49] um and it's it's also on the go.org site [40:53] um it will become the standard templates [40:54] in the next release so we we're we're [40:56] deprecating the old ones so these [40:58] templates will be available you didn't [40:59] see what they can do but they're kind of [41:00] cool um and so with that I guess I'll [41:04] take [41:07] questions and please use a microphone [41:09] for questions so people at home can [41:11] follow [41:12] along what's the build output for this [41:14] so is it is it like a binary um what [41:17] what areas can it be used in um like for [41:19] example with net is it just a library [41:21] that you can include and start making [41:22] references into it is it integrated [41:32] both linked binary that you can then run [41:35] and the lexer that I showed you is a [41:37] piece of that's actually been broken out [41:39] now separately but it's a it's a piece [41:41] of a library in effect that you link [41:42] into your program when you want to do [41:44] Lexing and so it's a statically compiled [41:46] binary that runs we have uh [41:48] implementations for several [41:50] architectures and several operating [41:52] systems um but it's it's not net there [41:56] is actually a net implementation [41:57] underway I don't know how far long it is [41:59] I think reasonably far but it's not done [42:01] yet but for the most part go we think of [42:03] as a statically compiled language that [42:06] has uh you know the performance [42:07] characteristics of a of such a language [42:09] as opposed to an [42:14] interpreter um have you had any [42:15] performance stats on that Lexa uh I was [42:19] thinking of that just before this talks [42:20] I figured oh someone's going to ask me [42:21] on the performance test and I haven't [42:23] checked it the answer is it's probably [42:25] okay but not great because I'm using the [42:27] language a little too having a little [42:29] too much fun with the language and doing [42:31] the channel communication and and that [42:34] kind of stuff actually puts more [42:35] overhead into the inter Loop than that [42:37] needs to be there with a little more [42:38] work I could take that out but as as [42:40] demonstrated here I think it would it [42:42] would be the performance would be good [42:44] but not great I think you could do [42:46] significantly better by eliminating some [42:47] of that the other stuff about how the [42:49] state functions work and all that should [42:50] be essentially as good as it can go to a [42:53] first approximation the only way you can [42:55] do better is to have uh to build the [42:57] state Machine by hand with switches that [42:59] are indexed into a table and have [43:01] function pointers in the table and just [43:03] grind like that but it amounts to the [43:04] same thing and I think there's a chance [43:06] this is just as good as as that would be [43:09] if not it'd be very close but no to be [43:11] honest I have not measured it and I [43:12] probably [43:13] should hi uh sorry um with the [43:18] concurrency where you removed the GU [43:20] routine if you had multiple [43:22] stages um could the could the go routine [43:26] be put back and and then say we'll kick [43:28] it off outside of the [43:30] initialization um and does does it well [43:33] the problem is you want the gotin to run [43:34] to completion during initialization [43:36] because you want to Lex your input and [43:38] generate the pars Tre for the template [43:40] so you can't you can't put it on hold [43:43] until later that just blocks everything [43:45] what you can do is uh depending on [43:48] there's this magic step it is pretty [43:50] magic I admit but I thought it was magic [43:52] enough to show you that two is a very [43:54] magic number it uh in the buffering you [43:57] because the we know that the lexer never [43:59] emits more than two items per invocation [44:01] you could make that an arbitrarily [44:02] bigger number to be fine but there's no [44:04] point in making it bigger than it needs [44:05] to be but as far as restarting the lexer [44:08] while it's running uh it'll sit and wait [44:10] for you until you come back so it will [44:12] do that staging them together doing [44:14] parsing the same kind of way would work [44:16] fine too you could you could gang them [44:19] up and is it is it in the next token [44:22] where it's sitting now does it actually [44:23] block yes it will block waiting for the [44:25] next token to be parsed if if you wanted [44:27] to if you unbuffered the if you made the [44:28] channel arbitrarily buffered it could [44:30] get arbitrarily far ahead but why do [44:32] that it's just using up memory it [44:33] doesn't need [44:34] to and it's also remember totally [44:36] synchronous here so there's no there's [44:38] no scheduling issues there's no this is [44:40] a single-threaded thing even in the [44:42] other in the other guy showed you it's [44:43] still single-threaded it's concurrent [44:45] it's not parallel so the thread of [44:48] control is very direct it never it never [44:50] has to switch between threads or [44:52] anything like that so it doesn't look it [44:54] but it's actually linear execution all [44:56] the time [44:59] do we have any com any questions from [45:01] the IRC room I should [45:04] handle we don't need to scroll back the [45:07] question was um could the concurrency [45:10] component so instead of using the [45:11] channel could you just create like a [45:13] list or a vector and push all of the [45:15] token all the items onto that list [45:17] instead of absolutely and in fact after [45:20] I did this Nigel sent me a cl to do [45:23] exactly that um and I kept it I I it's [45:27] probably better it probably fix the what [45:29] performance problems there may be if any [45:31] um but I it just wasn't as pretty so I [45:34] pushed back I I like this better but you [45:36] know if this turned out to be cr [45:37] performance critical I would definitely [45:39] switch to a a regular by hand ring [45:41] buffer it only add about 10 lines to [45:43] code to the whole thing it'd be pretty [45:44] easy but there's nothing inherent the [45:47] point about this is there's nothing [45:48] inherently concurrent about the problem [45:51] only the solution the solution gets [45:53] pretty because you can use concurrency [45:55] to solve the problem and I just want to [45:57] to ask a KN question for me but in terms [45:59] of efficiency how many times do you copy [46:01] the input text you copy the input text [46:05] um zero times there's no copying [46:09] whatsoever the parser might make a copy [46:10] I don't it's what the client does but [46:12] the Lexa receives an input string and [46:14] everything it delivers to the to the uh [46:16] parser is coming directly out of the [46:18] input so if you have a megabyte string [46:20] with no actions in it it will not make a [46:23] copy of that megabyte string you you'll [46:25] just get a you a slice of it which is [46:27] actually really cheap and does not copy [46:29] the data so it's efficient in that [46:30] respect if that's what you're getting at [46:33] yeah any other [46:39] questions how much work would be [46:41] involved in uh making accept a reader [46:44] rather than a pre- red string uh to do a [46:47] reader from this would be very easy [46:49] um a reader is a a interface ID in go [46:53] that is the generic representation of [46:55] anything it knows how to read like a [46:57] file or a network or a buffer and uh it [47:00] would uh Clumsy up a little bit of the [47:03] code but I think all you really have to [47:04] do is modify a little bit of the Lexus [47:06] structure the actual object and change [47:09] the next function to go for the reader [47:12] and I think backing up might be a little [47:14] trickier but not very much I've done it [47:16] in in other contexts it it would make it [47:18] it' be a little more noise but it would [47:20] work just fine and you could actually do [47:22] it in the abstract by turning the string [47:24] into a reader and using the reader for [47:26] everything and then any input would work [47:28] uh in the in the narrow confines of the [47:30] template package that didn't make a lot [47:31] of sense in a more General context uh [47:34] like a regular expression scanner or [47:36] something like that it might make [47:37] perfect sense that that that follows on [47:40] uh has this inspired you to look at [47:42] other other areas in inside go like XML [47:46] date passing things like that the HT [47:48] HTTP passing uh it hasn't inspired me to [47:51] do that although as I said there was [47:53] this blog post last week where somebody [47:54] was parsing HTML with regular [47:56] expressions and I gave him a Smackdown [47:58] so uh I hope to to his credit he he said [48:01] it was interesting to read my response [48:03] and he did change the way he was doing [48:04] it um but I I don't think I the reason I [48:07] chose this program to present it is I [48:08] think it's it's in a lot of ways it's [48:11] idiomatic go there's a little bit of [48:13] concurrency a little bit of object [48:15] objectoriented stuff there's some nice [48:18] use of strings and you see methods and [48:19] functions there sort of a lot of things [48:21] going on and it's a problem that's a [48:22] very nerdy problem Ian not very many [48:24] people write lectures for a living um [48:26] but it's kind of nice to see how all the [48:28] pieces fit together and how the design [48:30] works it's not clear that it's the [48:31] solution to world hunger but it's a [48:33] solution to Lexing my [48:37] templates anyone [48:39] else yeah do you think this technique [48:41] could be used um for a pause generator [48:44] could could a pause generator spit up [48:46] code that looks like this um it could [48:50] um par are more complicated because they [48:52] have more State [48:54] um but the short answer is yes I mean [48:56] this is this is this is a state machine [48:58] right and a parser is a state machine so [49:00] it yes you can do it uh I'm not sure it [49:03] would be a win state functions might be [49:05] clunkier but they might not I I I [49:07] haven't thought about it it would it [49:08] would certainly be doable um if you look [49:11] at what ragle does I think it's how you [49:13] pronounce it uh it's the Elixir [49:15] generator what it generates internally [49:17] you if you squint the right way it's [49:19] kind of you know the isomorphism to this [49:21] code but much harder to see but that's [49:23] okay it's generated code you don't care [49:25] what it looks like so yeah you could do [49:27] that but that's that's a different [49:28] problem but parsing you could do this [49:30] way yep absolutely not it' be a lot of [49:32] States parsing has many many states [49:35] right there's only about maybe 10 or 15 [49:37] State functions in this lexer there [49:39] probably be several hundred in a typical [49:40] parser so there' be a lot of boiler [49:42] plate you probably want a machine to [49:43] help you write [49:45] it [49:49] yep I'll speak up no don't use the use [49:52] the mic [49:58] um how would you tackle progress updates [50:00] and is there any way to receive event [50:02] notification while the electrical par is [50:04] operating um I don't understand the [50:07] first question so okay so if you've got [50:09] a very long process that's going through [50:12] uhuh is there any way that you could [50:13] receive updates about how far it's it's [50:15] been procing through it just pass see [50:18] the select statement here the select [50:20] statement allows multi-way concurrent [50:22] communication so you could easily put [50:24] inside here with probably like four [50:27] lines a way to Signal The Lex says I [50:29] want to know where you are and it could [50:31] respond so whenever you C care about the [50:33] result you could ping it and say tell me [50:35] how far you are and it could respond [50:36] that could be done in the same Loop or [50:38] you could just have it periodically emit [50:40] an update notice I've done a k I've done [50:42] 10K whatever it is and it could be [50:44] easily put inside the the select block [50:46] or on a counter inside here can you have [50:49] any way of um under certain conditions [50:52] writing things to a file for example [50:54] sure yeah I mean it's a programing like [50:56] language you can write the files anytime [50:58] you want okay yeah I mean it's it's very [51:00] very yes absolutely okay files are cool [51:04] underrated yeah um I apologize I have a [51:08] horrible scheduling conflict and I'm [51:09] supposed to be somewhere else half an [51:10] hour ago which is when my talk started [51:13] um so I have to run and I'm really sorry [51:14] about that this was very unfortunate [51:16] scheduling