Вопрос по haskell – Реализация `read` для левоассоциативного дерева в Haskell

8

Мне трудно реализоватьЧитать для древовидной структуры. Я хочу взять левоассоциативную строку (с паренами), какABC(DE)F и преобразовать его в дерево. Этот конкретный пример соответствует дереву

tree.

Вот тип данных, который я использую (хотя я открыт для предложений):

data Tree = Branch Tree Tree | Leaf Char deriving (Eq)

Это конкретное дерево будет в Хаскеле:

example = Branch (Branch (Branch (Branch (Leaf 'A')
                                         (Leaf 'B'))
                                 (Leaf 'C'))
                         (Branch (Leaf 'D')
                                 (Leaf 'E')))
                 (Leaf 'F')

мойshow функция выглядит так:

instance Show Tree where
    show (Branch l [email protected](Branch _ _)) = show l ++ "(" ++ show r ++ ")"
    show (Branch l r) = show l ++ show r
    show (Leaf x) = [x]

Я хочу сделатьread функционировать так, чтобы

read "ABC(DE)F" == example

Ваш Ответ

3   ответа
6

Это очень похоже на структуру стека. Когда вы сталкиваетесь с вашей входной строкой"ABC(DE)F", выLeaf любой атом, который вы найдете (без скобок) и поместите его в список аккумуляторов. Когда у вас есть 2 пункта в списке, выBranch их вместе. Это может быть сделано с помощью чего-то вроде (обратите внимание, не проверено, просто чтобы дать идею):

read' [r,l] str  = read' [Branch l r] str
read' acc (c:cs) 
   -- read the inner parenthesis
   | c == '('  = let (result, rest) = read' [] cs 
                 in read' (result : acc) rest
   -- close parenthesis, return result, should be singleton
   | c == ')'  = (acc, cs) 
   -- otherwise, add a leaf
   | otherwise = read' (Leaf c : acc) cs
read' [result] [] = (result, [])
read' _ _  = error "invalid input"

Это может потребовать некоторой модификации, но я думаю, что этого достаточно, чтобы вы встали на правильный путь.

13

Это ситуация, когда использование библиотеки синтаксического анализа делает код удивительно коротким и чрезвычайно выразительным. (Я был поражен, что это былоso аккуратно когда я экспериментировал чтобы ответить на это!)

Я собираюсь использоватьпарсек (эта статья содержит несколько ссылок для получения дополнительной информации) и использования ее в «аппликативном режиме». (а не монадический), так как нам не нужна дополнительная способность монад к стрельбе по ногам.

Code

Сначала различные импорта и определения:

import Text.Parsec

import Control.Applicative ((<*), (<$>))

data Tree = Branch Tree Tree | Leaf Char deriving (Eq, Show)

paren, tree, unit :: Parsec String st Tree

Теперь основной единицей дерева является либо один символ (который не является круглой скобкой), либо дерево в скобках. Обращенное в скобки дерево - это просто нормальное дерево между( а также), А нормальное дерево - это просто единицы, помещенные в ветви слева (это очень саморекурсивно). В Хаскеле с Парсек:

-- parenthesised tree or `Leaf <character>`
unit = paren <|> (Leaf <$> noneOf "()") <?> "group or literal"

-- normal tree between ( and )
paren = between (char '(') (char ')') tree  

-- all the units connected up left-associatedly
tree = foldl1 Branch <$> many1 unit

-- attempt to parse the whole input (don't short-circuit on the first error)
onlyTree = tree <* eof

(Да, это весь синтаксический анализатор!)

Если бы мы хотели, мы могли бы обойтись безparenError: User Rate Limit Exceededunit но приведенный выше код очень выразителен, поэтому мы можем оставить его как есть.

В качестве краткого пояснения (я предоставил ссылки на документацию):

  • (<|>) basically means "left parser or right parser";
  • (<?>) allows you to make nicer error messages;
  • noneOf will parse anything that's not in the given list of characters;
  • between takes three parsers, and returns the value of the third parser as long as it is delimited by the first and second ones;
  • char parses its argument literally.
  • many1 parses one or more of its argument into a list (it appears that the empty string is invalid hence many1, rather than many which parses zero or more);
  • eof matches the end of the input.

Мы можем использоватьparse функция для запуска парсера (возвращаетEither ParseError Tree, Left это ошибка иRight это правильный разбор).

As read

Используя это какread Like функция может быть что-то вроде:

read' str = case parse onlyTree "" str of
   Right tr -> tr
   Left er -> error (show er)

(Я использовалread' чтобы избежать конфликта сPrelude.read; если вы хотитеRead Например, вам придется проделать немного больше работы для реализацииreadPrec (или все, что требуется), но это не должно быть слишком сложно с фактическим анализом, уже завершенным.)

Examples

Некоторые основные примеры:

*Tree> read' "A"
Leaf 'A'

*Tree> read' "AB"
Branch (Leaf 'A') (Leaf 'B')

*Tree> read' "ABC"
Branch (Branch (Leaf 'A') (Leaf 'B')) (Leaf 'C')

*Tree> read' "A(BC)"
Branch (Leaf 'A') (Branch (Leaf 'B') (Leaf 'C'))

*Tree> read' "ABC(DE)F" == example
True

*Tree> read' "ABC(DEF)" == example
False

*Tree> read' "ABCDEF" == example
False

Демонстрирующие ошибки:

*Tree> read' ""
***Exception: (line 1, column 1):
unexpected end of input
expecting group or literal

*Tree> read' "A(B"
***Exception: (line 1, column 4):
unexpected end of input
expecting group or literal or ")"

И, наконец, разница междуtree а такжеonlyTree:

*Tree> parse tree "" "AB)CD"     -- success: ignores ")CD"
Right (Branch (Leaf 'A') (Leaf 'B'))

*Tree> parse onlyTree "" "AB)CD" -- fail: can't parse the ")"
Left (line 1, column 3):
unexpected ')'
expecting group or literal or end of input

Conclusion

Парсек потрясающий! Этот ответ может быть длинным, но суть всего 5 или 6 строк кода, которые выполняют всю работу.

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
3

Ответ parsec от dbaupp очень прост для понимания. В качестве примера «низкого уровня» подход, вот рукописный парсер, который использует продолжение успеха для обработки левоассоциативного построения дерева:

instance Read Tree where readsPrec _prec s = maybeToList (readTree s)

type TreeCont = (Tree,String) -> Maybe (Tree,String)

readTree :: String -> Maybe (Tree,String)
readTree = read'top Just where
  valid ')' = False
  valid '(' = False
  valid _ = True

  read'top :: TreeCont -> String -> Maybe (Tree,String)
  read'top acc [email protected](x:ys) | valid x =
    case ys of
      [] -> acc (Leaf x,[])
      (y:zs) -> read'branch acc s
  read'top _ _ = Nothing

  -- The next three are mutually recursive

  read'branch :: TreeCont -> String -> Maybe (Tree,String)
  read'branch acc (x:y:zs) | valid x = read'right (combine (Leaf x) >=> acc) y zs
  read'branch _ _ = Nothing

  read'right :: TreeCont -> Char -> String -> Maybe (Tree,String)
  read'right acc y ys | valid y = acc (Leaf y,ys)
  read'right acc '(' ys = read'branch (drop'close >=> acc) ys
     where drop'close (b,')':zs) = Just (b,zs)
           drop'close _ = Nothing
  read'right _ _ _ = Nothing  -- assert y==')' here

  combine :: Tree -> TreeCont
  combine build (t, []) = Just (Branch build t,"")
  combine build (t, [email protected](')':_)) = Just (Branch build t,ys)  -- stop when lookahead shows ')'
  combine build (t, y:zs) = read'right (combine (Branch build t)) y zs

Похожие вопросы