用导数解析
Parsing with Derivatives
频道:Stanford · 时长:1:13:09 · 发布:2011-06-03 · 播放:13456
简介
Matthew Might 在斯坦福的演讲,关于用导数解析,一种编写解析器的新方法,以及为什么需要更好的解析工具。它讨论了语言理论并批评了临时手写解析器。
HN 为什么推荐
在关于解析技术的讨论中被提及为一次精彩的演讲和相关阅读。
他还做了一个关于用导数解析的精彩演讲 — HN, 2018
中文字幕节选
斯坦福大学。 哦。欢迎。嗯,欢迎来到2010-2011年春季的W 380课程。 我是Andy Freeman。这门课的另一位讲师是Dennis Allison。 我们正在进入这个学期,所以插入一段关于跟上进度的唠叨。 嗯,正如我上周提到的,今天的讲座是关于一种编写解析器的新方法, 生成解析器。呃,为什么这很重要,标准论点是 解析器和语言理论一直是计算机科学的核心。 等等等等。然而,除了正则表达式之外,呃,解析器 解析器生成器很少被实际领域的人们大量使用。 这很奇怪,因为它们出现在令人惊讶的地方并产生巨大效果。 我最喜欢的例子之一是一个叫做TechMeme的推荐网站。 那和解析器有什么关系? 但是呃,Gabe Kaplan利用他的编译器工作,你知道,做出了一个 相当有趣的网站,呃,管理通信和信息流。 我认为正则表达式的过度使用表明了对更好 解析工具的需求,而这类工具的易用性是关键障碍。 今天的演讲者,犹他大学的Matt Might,从事静态分析工作, 以改进各种系统的行为,他来这里谈论用导数进行 解析。谢谢。所以,有点奇怪,在2011年 关于解析竟然还有什么可说的,但我就在这里。 嗯,所以,我不知道,我日常工作不做解析,但大约一年前,当我 和犹他大学的一个本科生合作时,呃,我们偶然发现了一种方法, 将正则表达式的导数扩展到上下文无关文法,从而 用它来进行解析。呃,所以,这就是我今天要讲的。 但我必须给你们一个警告,嗯,大约一年前,我们把这项工作提交给 同行评审,它很快被拒绝了。 呃,所以,我们确实计划重新提交,我很确定它会在 不久的将来某个时候被接受,但就目前而言,这使这项工作 处于呃认识论上模糊的类别:尚未成真。 嗯,但相信我,我们我们已经证明了它。 我们已经实现了它。我们已经测试了它。 确实有效。嗯,但请请遵守这个警告。 嗯,所以,我假设你们大多数人都知道什么是解析,呃,但如果你不知道,这里是我 对解析的简要介绍。 解析通常是从非结构化数据到结构化 信息的转换。在计算机科学中,这通常采取 从序列到树的转换形式。 呃,所以,例如,如果你想理解像X + 3 * 10这样的表达式的含义,我们目前将其解释为字符序列, 呃,我们需要将其转换为一棵树,编码这个表达式的 结合性和优先级。呃,所以,这正是解析器所做的。 所以,当你得到树时,如果你想理解 那个表达式的含义,你可以构建类似递归树遍历的东西 来弄清楚它的含义。 事实证明,正如Andy提到的,解析无处不在。 现在,我不是第一个做出这个观察的人,就在最近的Popl 2010上,Trevor Jim 列出了解析在计算机科学中出现的各种地方。 嗯,你知道,例如,嗯,它显然出现在编译器和 解释器之类的地方。我们都知道。 我们有很多解析工具来处理这些情况。 呃,它应该更多地出现在语法高亮中,尽管它并不总是出现在 语法高亮之类的地方。
HN 上的讨论
题外话,他还做了一个关于导数解析的精彩演讲 [VIDEO],被 Clojure 团队使用 [LINK] — cellularmitosis, 2018-09
除此之外,我总是想到 Matt Might 的“导数解析”。[1] 我得读读 flap,因为它似乎使用了基于导数的词法分析器。[1]: [VIDEO] — ThatGeoGuy, 2023-05
是的,我正在浏览介绍导数解析的原始视频[1]。解析的需求无处不在,然而,别说是计算机科学学生,根据我的经验,相当数量的专业程序员也无法从头开始或使用标准工具创建基本的解析器。编辑:视频批评了手写的 C 解析器。如果它是在形式推导的递归下降解析器中,这样的事情不一定坏。但只是没有语法指导的临时解析几乎是在等待灾难。[1] [VIDEO] — joe_the_user, 2016-06
相关视频
- Ruby Midwest 2011 - 主题演讲:迷失的架构岁月 by Robert Martin · Confreaks · 1:06:38
- Clojure 并发 - Rich Hickey · ClojureTV · 2:32:38
- CppCon 2014: Mike Acton “面向数据的设计与C++” · CppCon · 1:27:46
- Zig:为健壮性、最优性和清晰性而设计的编程语言 – Andrew Kelley · Recurse Center · 54:13
- Ruby Conf 12 - Y Not- 函数式编程历险记 by Jim Weirich · Confreaks · 53:21
- Erlang和Elixir的灵魂 • Sasa Juric • GOTO 2019 · GOTO Conferences · 42:02
- “简单造就易用” - Rich Hickey (2011) · Strange Loop Conference · 1:01:38
- Rich Harris - 重新思考响应式 · You Gotta Love Frontend · 36:45
- Richard Feldman 谈“让不可能的状态不可能” · elm-conf · 25:06
- Go 中的词法扫描 - Rob Pike · GoogleFOSSSydney · 51:17
- William Byrd 谈“有史以来最美丽的程序” [PWL NYC] · PapersWeLove · 1:31:05
- Rich Hickey 谈价值的价值 · InfoQ · 31:43
- 为什么函数式编程没有成为主流?—— Richard Feldman · Metosin · 46:09
- 也许不 - Rich Hickey · ClojureTV · 1:03:28
- 用 Clojure 的方式解决问题 - Rafal Dittwald · Clojure/north · 1:02:26
- 第一讲A:Lisp概述与简介 · MIT OpenCourseWare · 1:12:55