DianQK

我可以肯定的说，OP 你可以忽略这个习题，因为作者回复我了，说这是个不重要的习题。我跟随作者给出的一些提示 /答案，总结大概如下（我的理解不一定对）：

首先我可以肯定，这是将自动机（ FA ）相关的问题，前置知识在龙书的第 3.6 小节（不推荐看网上的一些介绍，感觉没有龙书写的详细易懂）。Type Analysis 虽然也是静态分析？但通常提到的静态分析对应的应当是本书后面章节的内容。Type Analysis 应该划分为另一个范畴了吧，我觉得忽略这章看本书更合适一些。

这里一直提到的 language 翻译过来虽然是语言，但我觉得解释为句子 /一段话更贴切一些。比如“很高兴见到你”，这是一段话，也是中文（对应的 language ）。
所以这里说的就是正则语言（表达式），只不过不是平常理解的正则表达式，而是更通用的概念。即符合某种正确规则的具体描述语言（一段话）。

抱歉，我没有继续把龙书的 3.7-3.9 看了，这几节应该是讲 FA 的应用部分。Ex 3.3 也**只是说怎么把定义的各种类型画成对应的 FA**，至于啥用，我不知道。作者回我的图片很模糊，感觉不是标准的 FA 。（抱歉，我不能直接贴这张图，因为我忘记了要一份授权，但我基于自己的理解重新画一遍应该没问题吧。）

OP 你把 3.6 小节看了之后，应该就可以了解底下的内容（如果没有，那一定是我转述 /理解的不对）。

画出来的 FA 如图：


有些字符我还不知道怎么打出来，就平替一下。这里 FA 用来判断能否接受一个描述对应类型的语言。
一些设定：
- 虚线圈似乎表示这里可以自由发挥 /匹配，什么类型都可以接受
- 1 、2 、3 数字用来表示状态转换的顺序 /参数？，当遇到一个 TypeVar （ t ）时候，回到初始状态按照数字顺序匹配
- ut.(&int, t)->int 中的 t 是受限（递归的）的，t 必须满足自身的 (&int, t)->int 类型，这种时候可以回到初始状态接着匹配

所以图中的 FA 可以接受 ut.(&int, t)->int ，首先匹配参数 1 ，&int 成功，然后参数 2 是 t 回到开始状态，参数 3 直接一个 int 结束。