Очень простой парсер sexp

Question

Для назначения нам нужно было реализовать что-то вроде очень простого синтаксического анализатора, например, для ввода:

"((a b) ((c d) e) f)"

Возвращалось бы:

[["a", "b"], [["c", "d"], "e"], "f"]

Так какчасть большего присваивания, синтаксический анализатор только дает допустимый ввод (совпадающие символы & c).Я предложил следующее решение в Ruby:

def parse s, start, stop
  tokens = s.scan(/#{Regexp.escape(start)}|#{Regexp.escape(stop)}|\w+/)

  stack = [[]]

  tokens.each do |tok|
    case tok
    when start
      stack << []
    when stop
      stack[-2] << stack.pop
    else
      stack[-1] << tok
    end
  end

  return stack[-1][-1]
end

Возможно, это не лучшее решение, но оно делает свою работу.

Теперь я заинтересован в идиоматическом решении Haskellдля основной функциональности (т. е. меня не волнует лексизация или выбор разделителей, хорошо бы взять уже лексированный ввод), если это возможно, используя только "основной" haskell, без расширений или библиотек, таких как parsec.Обратите внимание, что это НЕ является частью задания, я просто заинтересован в способе действий Haskell.

Answer 1

[["a", "b"], [["c", "d"], "e"], "f"]

Недопустимый тип в haskell (поскольку все элементы списка должны быть одного типа в haskell), поэтому вам необходимо определить собственную структуру данных для вложенных списков, например:

data NestedList = Value String | Nesting [NestedList]

Теперь, если у вас есть список токенов, где токен определен как data Token = LPar | RPar | Symbol String, вы можете разобрать его в NestedList следующим образом:

parse = fst . parse'

parse' (LPar : tokens) =
    let (inner, rest) = parse' tokens
        (next, outer) = parse' rest
    in
      (Nesting inner : next, outer)
parse' (RPar : tokens) = ([], tokens)
parse' ((Symbol str) : tokens) =
    let (next, outer) = parse' tokens in
    (Value str : next, outer)
parse' [] = ([],[])

Answer 2

Идиоматическим способом в Haskell будет использование парсек для синтаксического анализа комбинатора.

В сети много примеров, в том числе

• Этот хороший ответ на SO .
• Или вот еще один .

Answer 3

В то время как более красивые парсеры, такие как Parsec, хороши, вам не нужна вся эта сила для этого простого случая. Классический способ анализа - использование ReadS введите из прелюдии. Это также способ, которым вы бы дали свой тип Sexp Read экземпляр.

Хорошо бы хоть немного познакомиться с этим стилем разбор, потому что есть немало примеров в стандартные библиотеки.

Вот одно простое решение в классическом стиле:

import Data.Char (isSpace)

data Sexp = Atom String | List [Sexp]
  deriving (Eq, Ord)

instance Show Sexp where
  show (Atom a ) = a
  show (List es) = '(' : unwords (map show es) ++ ")"

instance Read Sexp where
  readsPrec n (c:cs) | isSpace c = readsPrec n cs
  readsPrec n ('(':cs)           = [(List es, cs') |
                                      (es, cs') <- readMany n cs]
  readsPrec _ (')':_)            = error "Sexp: unmatched parens"
  readsPrec _ cs                 = let (a, cs') = span isAtomChar cs
                                   in [(Atom a, cs')]

readMany :: Int -> ReadS [Sexp]
readMany _ (')':cs) = [([], cs)]
readMany n cs       = [(e : es, cs'') | (e, cs') <- readsPrec n cs,
                                        (es, cs'') <- readMany n cs']

isAtomChar :: Char -> Bool
isAtomChar '(' = False
isAtomChar ')' = False
isAtomChar c   = not $ isSpace c

Обратите внимание, что параметр Int для readsPrec, который обычно указывает на приоритет оператора, не используется здесь.