Функция разбора в Haskell, проблема с созданием функции карты - PullRequest
Новая
       16

Функция разбора в Haskell, проблема с созданием функции карты

2 голосов
/ 04 октября 2019

Я новичок в Haskell и работаю над заданием, в котором я пытаюсь создать функцию синтаксического анализа для простого языка калькулятора.

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

Предполагается, что грамматика будет 

Expr -> Int | -Expr | + Expr Expr | * Expr Expr
Int -> Digit | Digit Int 
Digit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Поэтому моя функция принимает в качестве аргумента строку на языке Expr и создает абстрактное синтаксическое дерево в этом формате 

data Ast = Tall Int | Sum Ast Ast | Mult Ast Ast| Min Ast| Var String deriving (Eq, Show)

Аст должен быть абстрактным синтаксическим деревом

И это то, что я до сих пор получил в своей функции синтаксического анализа 

parseEx :: [String] -> (Ast, [String])
parseEx [] = error "empty string"
parseEx (s:ss) | all isDigit s = (Tall (read s), ss)
               | s == "-"      = let (ast, ss') = parseEx ss in (Min ast, ss') 
               | s == "+"      = let (ast, ss'), let(ast',ss'') = parseEx ss in (Sum ast ast', ss') parseEx ss' (ast', ss'')  
               | s == "*"      = (Mult ast ast', ss'') where
                   (ast, ss'')   = parseEx ss'
                   (ast', ss''') = parseEx ss''

Я ясно вижу, что условие с + неправильно, и что я не могу иметь два let там. Кроме того, я как бы потерялся во всех этих списках. Я думал, что map -функция может быть решением моей проблемы, и, возможно, это сделает мой код более аккуратным. Но я не уверен, с чего начать, так как это должно быть в форме [String]->Ast. И проще ли просто придерживаться имеющегося у меня кода и попытаться заставить его работать?

Ответы [ 2 ]

5 голосов
/ 04 октября 2019

parseEx может возвращать только две вещи в соответствии с сигнатурой типа, поэтому 

let (ast, ast', ss') = parseEx ...

не имеет смысла. Вам необходимо цепочка let с - то есть, передать переменную, связанную в единицу, на вход следующего разбора: 

let (ast, ss') = parseEx ss
    (ast', ss'') = parseEx ss'
in ...

(Убедитесь, что выровнены предложенияиз let, это имеет значение в Haskell!)

Обратите внимание, как мы передали ss', остаток от первого разбора, в качестве входных данных для второго. Это говорит: "разберите AST из ss и верните мне остаток строки в ss'; и в этом остатке , проанализируйте еще AST".

Тщательно продумайте, какой остаток вы вернете после анализа полного + -выражения.

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

parseEx :: [String] -> (Ast, [String])
parseEx [] = error "empty string"
parseEx (s:ss) | all isDigit s = (Tall (read s), ss)
               | otherwise     = undefined

, скомпилируйте его (исправьте) и протестируйте в ghci (для интерпретации результатов может потребоваться немного понимания нюансов undefined и лени - но это будеттакже построить эту интуицию). Затем выполните следующее предложение, скомпилируйте, протестируйте, промойте и повторите.

1 голос
/ 04 октября 2019

Я не уверен, с чего начать, так как это должно быть в форме [String] -> Ast.

И проще ли просто придерживаться кода, который у меня есть, ипытаться заставить его работать?

Одна вещь - это сигнатура типа, которую вы экспортируете, а другая - ваша внутренняя реализация.

Например, вы можете создать свой парсер так: 

parseEx :: String -> Ast
parseEx s = parseTokens (tokenize s [])

data Token = TokDigit Int | TokPlus | TokMinus | TokMult
type DigitStack = String

tokDigit :: DigitStack -> Token
tokDigit s = TokDigit (read (reverse s))

tokenize :: String -> DigitStack -> [Token]
tokenize [] digits =
  if null digits
  then []
  else [tokDigit digits]

tokenize (c:cs) digits
  | isDigit c = tokenize cs (c:digits)
  | not (null digits) = tokDigit digits : tokenize (c:cs) []
  | isSpace c = tokenize cs digits
  | otherwise = case c of
      '+' -> TokPlus : tokenize cs digits
      '-' -> TokMinus : tokenize cs digits
      '*' -> TokMult : tokenize cs digits
      _ -> error ("Unknown symbol " + show c)

parseTokens :: [Token] ->  Ast
parseTokens (t:ts) = ...

Не то чтобы токенизация строго необходима для вашей простой грамматики, но дело в том, что внутреннее представление вашего синтаксического анализатора не должно быть ограничено сигнатурой [String] -> Ast. Вы даже можете использовать библиотеку синтаксических анализаторов, например Мегапарсек , и при этом экспортировать функцию [String] -> Ast.

...