diff options
Diffstat (limited to 'content')
| -rw-r--r-- | content/article/token-translation.md | 43 |
1 files changed, 41 insertions, 2 deletions
diff --git a/content/article/token-translation.md b/content/article/token-translation.md index b64b45f5..30a14937 100644 --- a/content/article/token-translation.md +++ b/content/article/token-translation.md @@ -27,7 +27,46 @@ toc = true 不仅桌游里的代币是 Token，游戏厅里的游戏机和赌场里的老虎机使用的代币，也叫作 Token coin，不过如今更多地被 *ticket*（票券）取代了。 -在计算机中，Token 有两类。一类是用来表示「执行某种操作的权限」的对象，另一类是自然语言处理（NLP）中划分的词法记号（Lexical token）或别的语言单元——在将第二类的时候，我会讲到「词元」这个翻译不仅犯了范畴问题，本身的表意也不准确。 +在计算机中，Token 有三类。一类是用来表示「执行某种操作的权限」的对象，另一类是编译器和解释器中划分的语法单元，还有一类是自然语言处理（NLP）中划分的词法记号（Lexical token）或别的语言单元——在讲第三类的时候，我会讲到「词元」这个翻译不仅犯了范畴问题，本身的表意也不准确。 -第一类 Token 通常叫作「令牌」， +第一类 Token 通常叫作「令牌」，往往与密码学相关。常见的场景是客户端输入账号密码之后，服务端生成一个（多半有期限）的凭证，一般是字符串，之后客户端只需要在访问时提供这个凭证就好，期限时间内不需要再次输入密码。这个字符串一般保存在 Cookies 里，服务端自动读取，或者客户端携带在 HTTP 请求头里： + +``` +Authorization: Bearer eyJhbGci...<snip>...yu5CSpyHI +``` + +`Bearer` 之后的部分就是 Token。最常见的令牌之一是 [JWT](https://en.wikipedia.org/wiki/JSON_Web_Token)，其他的应用场景也不少，不限于 HTTP 通信。任何能够在通信过程中，从密码学意义上验证用户身份的凭证字符串，都叫令牌。 + +第二类 Token 在解析代码的过程中产生，解析（parse）还没有到编译（compile）或者解释（interpret）的地步，无论编译器还是解释器都有这个步骤。仔细想想，源代码只是储存在文件里的文本而已，可以当作字符串处理，解释器和编译器是怎么把字符串变成有意义、可执行的语句的？我们可以现场写个 Lisp 解释器来理解其过程。 + +程序员极有可能接触过简单的解释器，比方说，如何给下面这个算式字符串求值？ + +``` +(1 + 3) - 4 * 7 +``` + +答案是构造抽象语法树（AST）。不难发现，上述算式可以表示为树形结构，`(1 + 3)` 是一个整体，`4 * 7` 因为乘法的优先级更高，也作为一个整体，那么就可以把 `-` 当作根，前面两个整体作为 `-` 的左右子树。继续递归，不难发现 `(1 + 3)` 是 `+` 为根，`1` 和 `3` 为叶子结点的子树，而 `4 * 7` 是 `*` 为根，`4` 和 `7` 为叶子结点的子树。 + + + +接下来只要深度优先遍历 AST 就好了，不难发现结点有两类，非叶子结点是操作符，叶子结点是数字。遍历时若是遇到数字，就直接返回值；若是遇到操作符，就根据操作符计算左右子树的值。在一系列奇妙的递归之后，程序就能求出这棵树的值为 `-24`。 + +回顾一开始的算式，能不能把它写成这个样子？ + +```lisp +(- (+ 1 3) (* 4 7)) +``` + +也就是说，把中置操作符换成**前置**操作符，把所有的括号**显式**地写出来。如果把 `()` 看成列表，前置操作符的写法其实是嵌套的列表，而嵌套的列表就是树。这样一来，把字符串解析成 AST 的算法就好写多了。 + +假设我们现在不仅仅是要表示算式，要表示程式…… + +```lisp +(format t "it's ~a~%" + (- (+ 1 3) (* 4 7))) +``` + +上面这段代码应该打印 `it's -24`。 + + |