如何解析 SKI 组合子微积分的左结合记号

Question

我尝试了很多东西，它们似乎总是导致以下两件事之一：

• 程序永远挂起（无限左递归）
• 右结合（右递归）

我现在唯一的想法是从字符串的末尾而不是开头进行解析，但是对 haskell 字符串的列表性质进行解析，这需要遍历每个字符的列表，或者解析反转的字符串。这两个选项听起来都不错。

这是我当前代码中的相关位（这是右关联的）。我试过左递归，但结果是无限循环。

{-# LANGUAGE PatternGuards #-}

data C = S | K | I deriving (Read,Show,Eq)
data T = N T T | C C deriving Eq

parse :: String -> T
parse s | (e,rest) <- parseStep s = if rest == "" then e else N e (parse rest)

parseStep :: String -> (T,String)
parseStep ('(':s) = parseParen s 
parseStep (c:s) = (C $ read [c],s)

parseParen (c:')':s) = (C $ read [c],s)
parseParen s = parseStep s

Answer 1

由于 luqui 的评论，弄清楚了：

parse :: String -> T
parse = foldTs . parseList

foldTs :: [T] -> T
foldTs (t:ts) = foldl N t ts

parseList :: String -> [T]
parseList "" = []
parseList s = let (x,r) = parseStep s in x:parseList r

parseStep :: String -> (T,String)
parseStep ('(':s) = let (ts,r) = parseParenList s in (foldTs ts,r)
parseStep (c:s) = (C $ read [c],s)


parseParenList :: String -> ([T],String)
parseParenList (')':s) = ([],s)
parseParenList s =
  let
    (x,r) = parseStep s
    (xs,r') = parseParenList r
  in (x:xs,r')