从零开始的编译器前端之Parser与Lexer的一些其他的细节（待更新）

这篇文章讲一些相比前几篇比较无关紧要的细节，算是写Parser/Lexer时候的踩坑的记录吧。之后遇到了更多的坑，也会写在这篇文章里。

主要的一个大坑就是例如val a = sum<int>(3 + 4) 或者val b = foo<int, char>(...) 这里面用尖括号包起来的泛型类型标记，起初试验了许多不同的办法，也一度想过放弃，不过最后还是获得了相对比较令人满意的写法。

关于Display和Show

其实本身并没有Display这个类，之所以专门设置这么一个类，还是为了在debug和测试的时候能够方便地打印出数据类型的结构。之所以专门设置一个Display而不是直接去继承已有的Show类型，则是为了避免「隐式习惯」可能带来的坑。

其实就类似于同样是* -> String的约束，不去重写命令式语言里的toString()而去主动设置专门的类型一样，因为toString()携带了许多隐式的定义，会把输出结果搞得乱七八糟。比如在Java或者JS里面会经常看到类似[Object object]或者[Object@11451419]之类的完全不是想要看到的结果。除此之外，也可能在不同的场合会用到不同的输出或者需要对输出的生成策略做进一步的控制，在这种情况下直接覆写toString()就是个不太好的想法了，因为它本身不能提供任何可配置性也不能把不同的场景区分开来。

不过这里也有一些限制，比如说不能把约束加到type alias上面，再比如说String本质上是[Char]，所以一方面不能对String做约束，另外一方面如果想要display的类型刚好是个字符串，会被当作一个char的list，结果就是会使用为[a]提供的定义：

instance Display a => Display [a] where
    display a = "[" ++ (intercalate ", " . map display $ a) ++ "]"

虽然也不是不能用但总归是怪怪的。

组合子的组合顺序

Parser Combinator的匹配规则是从上到下，对于<|>，如果左侧匹配失败会转到右侧且不吃入任何token，也就是说顺序是一件很重要的事情。

比如说要匹配x和x + 3，如果直接匹配id，会在吃掉x后直接返回，在buffer里面留下剩下的加号和3。解决办法就是在匹配id后试着匹配一下剩下的部分，如果失败的话再把吃掉的id pure出来：

match = do idx <- identifier
           (do plus
               nn <- num
               pure $ BinaryExpr ADD idx nn)
               <|> pure $ Variable idx

这个思路其实就是提取出左公因子。

除此之外，在foo和foo(1 + 2)这种在表达式里面区分出变量名和函数调用的情况，因为foo是两种匹配的公因子，换句话说就是如果读到foo，同时可能是变量名或者函数调用，但是如果读到foo(1 + 2)就只有可能是函数调用。

这样的话，就要在primary里面把functionCallPrimary放在variablePrimary的左边，先匹配函数调用，如果失败了再回溯回去匹配变量名。

当然比较好的办法可能是抽取出公因子。

Do-notation里的一些小坑

Do-notation其实是Haskell的语法糖，相当于用一种比较declarative的方式去书写>>=函数套娃。不过Do-notation还是有一些地方写起来并不是理所当然的就是看上去的那么简单的。

首先一点就是do的<-右方其实是一个完整的组合子单元，换句话说如果有

aCombinator = do xxx
                 y <- yyy
                 z <- zzz
                 pure (y, z) <|> ...
anotherCombinator = do (x, y) <- aCombinator
                    ...

其实完全可以写成：

aCombinator = do (x, y) <- (do xxx
                               y <- yyy
                               z <- zzz
                               pure (y, z) <|> ...)
              ...

当然在可读性上可能会不如分开来写的可读性强。只能说按照具体情况来判断了。

我在吃exprLevel1里面吃>>的地方使用了这个写法，主要原因是这是唯一一个吃两个token产生一个op的情况了。当然其实也可以抽离开写一个单独的组合子。

另外一个有趣的事情是Haskell的do-notation里面的作用域是根据缩进来判断的，比如说

do a <- foo <|> bar <|> baz
   b <- bbb
   ...

这里的a的匹配规则可以是foo，bar，baz的任一个，b的匹配紧接在a后面，显然的，如果在bar前面加个do然后把b对齐到bar下面，那么bar直到b之间的部分都会作为一个组合子用于匹配a：

do a <- foo <|> do bar <|> baz
                   b <- bbb
                   ...
   ...

另一方面，似乎括号本身的作用要小于缩进（至于括号具体的作用，比如说什么情况下是不可或缺的，还需要另外的研究），表现为：

do a <- xxx
   (do b
       c <- ...
       <|> pure a)
       
do a <- xxx
   (do b
       c <- ...)
       <|> pure a
       
do a <- xxx
   do b
      c <- ...
      <|> pure a

这三种写法实际上是等价的。相对应的，以下写法里面pure a是无法找到变量的：

do a <- xxx
   (do b
       c <- ...)
   <|> pure a

也就是说do-notation主要还是依靠空格缩进来确定不同的作用域。当然这也可以通过拆分不同的语句块为>>=的函数调用来判断出来（但是估计没人愿意这样拆）

当然了，括号本身必须紧跟在do开辟的作用域里，然后也能更好的表明程序的思路和逻辑。

尖括号泛型标记带来的二义性和解决方法

在要实现的编程语言里面，计划实现简单的泛型的功能，为此，也需要有能够在声明处注明使用哪些泛型标记符或者在调用处注明泛型对应的类型的能力。

比如说声明一个函数fn add<a>(left: a, right: a): a，然后在调用处显式标记类型例如val a = add<int>(3, 4)或者val b = add<real>(3.14, 2.15)。

当然，如果有了简易的类型推导功能，这个类型标注应该可以被省略，像这样：val c = add<>(1.5, 3.5)或者val d = add(3.5, 4)。

一个比较合理的类型系统还应该有类型约束来为参数化多态提供更多可以继承的信息，这里因为只实现一个最简单的语言所以就不展开了。

然后，在这种情况下，会出现一个很大的问题，就是很难把尖括号用于泛型标记的情况和表示二元运算的情况分离开来，例如，val a = add<int>(3, 4)和val b = a < c所生成的token流，最前面的部分是一致的，不能用简单的办法去区分开两种情况。

在StackOverflow上也有几篇讨论提到过这个情况，例如这里和这里。

简单概括一下结论，就是没有很好的办法（包括回溯和向前看）来区分这两种情况，尤其是当诸如x < y > z或者if x < y, y > z {...}都是有效的表达式的情况下。（在假设lexer阶段不做区分的前提下）parser需要知道当前作用域里可用的函数名来决定要使用哪一种情况。

另一个不错的办法是使用一些不太可能会被其他情况使用到的语法，比如说

• 用::<a, b>来做泛型标记，似乎是Rust里面的做法？
• 用!来表示之后是泛型标记，这是D语言的做法
• 用[]来标记泛型，对应的，通常语言里常见的a[18]之类的用法就不能再用了，这是Scala的做法
• 或者，索性把泛型标记移到其他地方，比如在Java里放置在类里面的方法名前方并且放在点标记符后面

这边的写法里面，观察到无论是声明处的泛型声明，还是调用处的泛型参数，都不会有层叠的（比如说foo<a, b<c<d>, e>>这种）情况出现，同时参数后面必然紧跟函数参数的左括号，所以在lexer里面动了手脚，在进入一个名称然后读到<后向后搜索，如果紧接着的是>和(的连续组合的话，单独解析这中间的部分，然后和剩下的「正常解析」的部分合并起来。

这种写法要不产生歧义性的另一个要求就是左括号不能出现在一个语句块的最前面，也就是说不能有诸如(a, b) = foo()这样的写法，当然，因为这边的语法里面所有变量都是强制用val和var声明并且只有在声明时才能解构，所以也不会出现问题。

因为泛型参数的写法非常简单，只会有变量名、逗号和可能会出现的空格，所以这个专门处理的函数也就很简单了。

除此之外的情况，如果读到了<但后面没有出现这样的结构，那么会直接作为<（LRT）符号存入token流。

大致写法如下：

tokenize ('<' : xs@(x:_)) n m r p | not $ isSymbolChar x = handleGenericClause xs n m r p

handleGenericClause :: String -> Int -> [Int] -> Int -> Int -> ([Token], Int, [Int])
handleGenericClause xs n m r p 
    | isEnclosed rem = let (_:ys) = rem in
        let (tok, n', m') = tokenize cls n m r (p + 1) in
        let (tok', n'', m'') = tokenize ys n' m' (r + newrow) (p + 1 + newpos) in
            (Token GENERIC_LEFT r p : tok ++ [Token GENERIC_RIGHT (r + newrow) (p + newpos)] ++ tok', n'', m'')
    | otherwise = (Token LRT r p : tripleFst (tokenize xs n m r (p + 1)), n, m)
        where (newrow, newpos) = (length rows - 1, length . last $ rows)
              rows = split '\n' $ cls
              (cls, rem) = matchUntil (isPrefixOf ">") xs
              isEnclosed ('>' : '(' : _) = True
              isEnclosed ('>' : ax) = beginWithLparen ax
              isEnclosed _ = False
              beginWithLparen (' ' : ax) = beginWithLparen ax
              beginWithLparen ('(' : _) = True
              beginWithLparen _ = False

这里定义了两个局部函数beginWithLparen和isEnclosed，前者用来判断一个字符串去除空格后是否以左括号开头，后者调用前者，在已知被当前函数处理的字符串必定以<开头的情况下，判断该字符串是否「封闭的」，换句话说就是只要提供一段字符串判断它是不是由连续的>和(开头的就行了。在这里，空格会被忽略掉，就像进行正常的tokenize一样。

然后根据下一个>的出现情况把字符串分隔为两个部分，利用函数isEnclosed进行分类讨论，在泛型语句块「是封闭的」情况下，分别对泛型语句块和剩余的部分进行tokenize，利用tokenize函数可以传入初始化行/列数的参数来做必要的偏移，最后把两个token流串接起来并且插入必要的GENERIC_LEFT和GENERIC_RIGHT标记。

大致就是这样。在这种情况下，也就不允许>开头的自定义符号了，所有使用到的以>开头的符号都要以tokenize ('>' : ... : xs)的形式单独写在tokenize函数里。相反，<开头的操作符是根据<后面是否立即紧跟一个有效的操作符字符来决定的，也就是not $ isSymbolChar x，不过其实也只会在匹配到字母和空格的时候进入泛型语句块就是了。

除此之外，也有一些细节：

• 对于<>的情况，已经cover在前面那个函数里面了，不需要单独写个规则去匹配，实际上有这么几种情况：
  • <>会tokenize为[LRT, GRT]，因为实际上并不会用到这个符号，所以也就没有影响了，不过，这时候不能自定义一个这样的符号
  • <>(会tokenize为[GENERIC_LEFT, GENERIC_RIGHT,LPAREN]
  • < >和< >(的解析和前面的效果一致
• 在不同的token之间的空格会被正常地过滤掉
• 至于其他部分，比如变量/参数的类型声明部分，例如val a: pair<int, list<real>>或者fn foo(a: pair<list<pair<int, real>>, char>)之类的情况，所有<和>都只会解析为LRT和GRT，然后在Parser部分也不会产生歧义。

对应的，泛型标记的解析部分如下：

genericClause = do  genericLeft 
                    xs <- sepBy identifier comma
                    genericRight
                    pure $ map (identifierName . tokenType) xs

目前暂不支持使用<和>标记的类型（简单的语言里面[]、()和->已经足够），不过有需要的时候，也不会产生歧义。

算是一个相对满意的结果吧。

之前也有试过把类型标记里面的<和>翻译成和泛型标记一样的token的，并且为此尝试过在:后面开一个新的搜索范围来tokenize的思路，不过失败了，一方面，没有解决泛型标记二义性的问题，另一方面，使用了:后，所有其他的地方，例如switch表达式，就都不能用这个符号了。

总之大概是这样。