如何处理可选的二维编程语言文法

这文章一看就是标题党，真正二维编程语言都是 esolang，我这么正经的人什么时候跑去研究过 esolang。再说，就算研究过也不可能往自己的博客里灌水，484 呀。

本文说的二维文法，对于编程语言小白来说，可以理解为 Python 那种基于缩进的语法。 解析这种语法的难度在于，缩进具有了语义，你不能在 Lexer 里面像 Java 的 lexer 一样直接忽视除了字符串里面之外的空白字符。

预警：本文会黑 Python。但我必须贴出这段聊天记录来证明我的立场：

> 黑 Python 控制不住了……
< 我可以用一分钟让cpython本项目+yapypy支持多行lambda。只看前端不亦图样乎？
> 不考虑红姐加持的python
< 他们都会
< 你去问py core dev, 没人不会
< 为什么不加，你们可能觉得很没道理
> 那不做的原因呢？
< 我忘了
< 但我记得我看过之后是认同的

一个很简单的例子，下面的 Python 代码：

if a:
    if b:
        print('road roller da!!!')
else:
    print('ora ora ora!!!')

第四行的 else 根据缩进，应该对应第一行的 if ，这就是一个和 Java 风格语法的简单区别（C/C++/Java 中是就近原则嘛）。

然而，我怎么可能在正经的博客里介绍如何 parse Python 这么弱智的语言呢？这么简单的事情， PyCharm 里面 lexer 加了一道 pass 就解决了。

等等……？“Lexer 加了一道 pass”？这似乎令人直接产生一种联想：是不是其实是在解析的时候把缩进转成了一种无形的 Token，用来表示 line break 和 block 的结构呢？

没错！就是这样。

这种基于缩进的语法中，带语义的缩进又叫布局（Layout）。

制作这种语法的难点在于，表达式断行和缩进语义本身的冲突问题。

在 Haskell 中，这被处理的很好：

starPlatinum = \case
  a -> \case
    e -> f
    _ -> __IMPOSSIBLE__
  c -> d

然而，辣鸡语言 Python 还 不支持多行的 Lambda ，真令人头大。 与此同时，正常人做出来的语言，不仅有基于布局的语法，有多行 Lambda，而且还同时提供了不基于布局的语法。也就是说，你这样的代码

rua = do
  a <- b
  c <- d
  e <- p <|> do
    f
    g <- h
    return i
  j

在你不想这么一行一行写的时候，完全可以使用非布局的语法改成一行：

rua = do { a <- b ; c <- d ; e <- p <|> do { f ; g <- h ;return i }; j }

然鹅 Python 把多行语句放在一行，遇到嵌套的结构就跪了 。 所以无论如何，Python 的语法都只能用两个字概括——辣鸡。

不过，Python 给我们开了一个好头。本身缩进就是使你的代码变得美观的一环，给语言设计分号和大括号来管理代码块的层级结构是不是会显得有点繁琐？ 我们明明可以让缩进来代替大括号和分号。

所以，Haskell 这种提供可选的基于布局的语法的行为，就是可取而且值得推荐的。 并且，Haskell 没有钦点 4 空格，而是你想几个就几个，只要对齐就可以了（叹气）。

当然，Haskell 这么做的缺点就是——在 IDE 之外（aka 在命令行之中），报错信息变得不那么可读了。

那么问题来了，这种布局和非布局共存的语法要怎么 parse 呢？

Lexer 实现

首先，我们的 Lexer 需要额外保存一个状态——是一个栈，每个元素保存“是否处于布局中，以及如果有布局的时候我要知道目前布局的缩进个数”。 把这段话表达成 Haskell 代码，就是：

{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE LambdaCase    #-}

import Data.Maybe (listToMaybe)
import GHC.Generics (Generic)

data LayoutContext
  = NoLayout
  | Layout Int
  deriving (Eq, Generic, Ord, Show)

-- | See @OwO.Syntax.Position@
data AlexUserState = AlexUserState
  { layoutStack    :: [LayoutContext]
  , alexStartCodes :: [Int]
  } deriving (Eq, Generic, Show)

然后，本身还需要一个 Int 状态，表示目前是处在即将开启一个新布局的状态下还是正在常规代码中。

我们首先需要一个函数来判断哪些 Token 需要开启新布局。 对于 Python，就是冒号。对于 Haskell，就是 do where 等。

isStartingNewLayout :: TokenType -> Bool
isStartingNewLayout WhereToken     = True
isStartingNewLayout PostulateToken = True
isStartingNewLayout InstanceToken  = True
isStartingNewLayout _              = False

我们需要提供 Lexer 状态的出入栈函数：

pushLexState :: Int -> Alex ()
pushLexState nsc = do
  sc <- alexGetStartCode
  s@AlexUserState { alexStartCodes = scs } <- alexGetUserState
  alexSetUserState s { alexStartCodes = sc : scs }
  alexSetStartCode nsc

popLexState :: Alex Int
popLexState = do
  csc <- alexGetStartCode
  s@AlexUserState { alexStartCodes = scs } <- alexGetUserState
  case scs of
    []        -> alexError "State code expected but no state code available"
    sc : scs' -> do
      alexSetUserState s { alexStartCodes = scs' }
      alexSetStartCode sc
      pure csc

以及布局状态的出入栈函数：

popLayout :: Alex LayoutContext
popLayout = do
  s@AlexUserState { layoutStack = lcs } <- alexGetUserState
  case lcs of
    []        -> alexError "Layout expected but no layout available"
    lc : lcs' -> do
      alexSetUserState s { layoutStack = lcs' }
      pure lc

getLayout :: Alex (Maybe LayoutContext)
getLayout = do
  AlexUserState { layoutStack = lcs } <- alexGetUserState
  pure $ listToMaybe lcs

在即将开启新布局的状态下，如果遇到 { ，就退回去（丢掉一个状态），然后开始无视布局开始解析基于 {;} 的代码块，否则进入布局。以及，我们还要无视所有空行：

$white_no_nl  ;

<layout> {
  \n          ;
  \{          { explicitBraceLeft }
  ()          { newLayoutContext }
}

丢掉状态：

explicitBraceLeft :: AlexAction PsiToken
explicitBraceLeft ((AlexPn pos line col), _, _, _) size = do
  popLexState
  pushLayout NoLayout
  toMonadPsi pos line col size BraceLToken

对于普通状态下，我们有可能会进入布局：

<0> {
  \n          { beginCode bol }
  import      { simple ImportToken }
  where       { simple WhereToken }
  postulate   { simple PostulateToken }
  instance    { simple InstanceToken }
  infixl      { simple InfixLToken }
}

然后这个 beginCode 每进入新的一行，就要看布局是否变化； 而 simple 需要处理开启新布局的 Token 的情况：

beginCode :: Int -> AlexAction PsiToken
beginCode n _ _ = pushLexState n >> alexMonadScan

simple :: TokenType -> AlexAction PsiToken
simple token ((AlexPn pos line col), _, _, _) size = do
  -- run `pushLexState` when it's `where` or `postulate`
  if isStartingNewLayout token then pushLexState layout else pure ()
  toMonadPsi pos line col size token

在布局状态下，每进入新的一行，就要看布局是否变化：

<bol> {
  \n          ;
  ()          { doBol }
}

如果变化，就需要修改当前的布局状态：

doBol :: AlexAction PsiToken
doBol ((AlexPn pos line col), _, _, _) size =
  getLayout >>= \case
    Just (Layout n) -> case col `compare` n of
      LT -> popLayout   >> addToken BraceRToken
      EQ -> popLexState >> addToken SemicolonToken
      GT -> popLexState >> alexMonadScan
    _ -> popLexState    >> alexMonadScan
  where addToken = toMonadPsi pos line col size

怎么样？是不是几乎没有难度？

本文的代码来自 OwO 。

啊，灵乌路空真帅气啊。