Как скобки работают с пользовательскими типами данных? - PullRequest
Новая
       29

Как скобки работают с пользовательскими типами данных?

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

В настоящее время я работаю над проблемой разбора и отображения выражений в Haskell. 

type Name = String
data Expr = Val Integer
          | Var Name
          | Expr :+: Expr
          | Expr :-: Expr
          | Expr :*: Expr
          | Expr :/: Expr
          | Expr :%: Expr

Это код моего типа данных Expr, и вот как я определяю функцию show: 

instance Show Expr where
  show (Val x) = show x
  show (Var y) = y
  show (p :+: q) = par (show p ++ "+" ++ show q)
  show (p :-: q) = par (show p ++ "-" ++ show q)
  show (p :/: q) = par (show p ++ "/" ++ show q)
  show (p :*: q) = par (show p ++ "*" ++ show q)
  show (p :%: q) = par (show p ++ "%" ++ show q)

par :: String -> String
par s = "(" ++ s ++ ")"

Позже я попытался преобразовать ввод строки в выражение, но столкнулся со следующей проблемой: я не понимаю, как скобки во втором случае реализованы в Haskell. 

*Main> Val 2 :*:Val 2 :+: Val 3 
((2*2)+3)
*Main> Val 2 :*:(Val 2 :+: Val 3) 
(2*(2+3))

Из-за этогоЯ немного сбит с толку относительно того, как я должен преобразовать скобки из моей строки в выражение. В настоящее время я использую следующую функцию для разбора, но сейчас она просто игнорирует круглые скобки, которые не предназначены для поведения: 

toExpr :: String -> Expr
toExpr str = f (lexer str) (Val 0)
   where 
    f [] expr = expr
    f (c:cs) expr
     |isAlpha (head c)  = f cs (Var c)
     |isDigit (head c)  = f cs (Val (read c))
     |c == "+"  = (expr :+: f cs (Val 0))
     |c == "-"  = (expr :-: f cs (Val 0))
     |c == "/"  = (expr :/: f cs (Val 0))
     |c == "*"  = (expr :*: f cs (Val 0))
     |c == "%"  = (expr :%: f cs (Val 0))
     |otherwise = f cs expr

Редактировать: несколько грамматических ошибок

Ответы [ 2 ]

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

Я не понимаю, как скобки во втором случае реализованы в Haskell.

Скобки просто дают приоритет определенной части выражения для разбора. Проблема не в круглых скобках. Я думаю, проблема в том, что вы не присваивали приоритет своим операторам. Таким образом, это означает, что, если вы не укажете скобки, Haskell будет считать, что все операторы имеют одинаковый приоритет, и анализирует их слева направо. Таким образом, это означает, что x ⊕ y ⊗ z анализируется как (x ⊕ y) ⊗ z .

Вы можете определить приоритет вашего :+:, *Операторы 1014 * и т. Д. С infixl: 

infixl 7 :*:, :/:, :%:
infixl 5 :+:, :-:

type Name = String
data Expr = Val Integer
          | Var Name
          | Expr :+: Expr
          | Expr :-: Expr
          | Expr :*: Expr
          | Expr :/: Expr
          | Expr :%: Expr

Что касается вашего синтаксического анализатора (toExpr), вам потребуется механизм синтаксического анализа, такой как LALR-анализатор [wiki] , которая сохраняет результаты в стеке и, таким образом, выполняет правильные операции.

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

Это был мой последний парсер, который дал мне нужный мне результат. Чтобы получить результат, я хотел, чтобы была добавлена ​​правильная грамматика, и я написал анализ в соответствии с грамматикой. Спасибо всем за помощь. 

{-
  parser for the following grammar:
  E  -> T E'
  E' -> + T E' | - T E' | <empty string>
  T  -> F T'
  T' -> * F T' | / F T' | % F T' | <empty string>
  F  -> (E) | <integer> | <identifier> 
-}

parseExpr :: String -> (Expr,[String])
parseExpr tokens = parseE (lexer tokens)

parseE :: [String] -> (Expr,[String])
parseE tokens = parseE' acc rest where (acc,rest) = parseT tokens

parseE' :: Expr -> [String] -> (Expr,[String])
parseE' accepted ("+":tokens) = let (acc,rest) = parseT tokens in parseE' (accepted :+: acc) rest
parseE' accepted ("-":tokens) = let (acc,rest) = parseT tokens in parseE' (accepted :-: acc) rest
parseE' accepted tokens = (accepted,tokens)

parseT :: [String] -> (Expr,[String])
parseT tokens = let (acc,rest) = parseF tokens in parseT' acc rest

parseT' :: Expr -> [String] -> (Expr,[String])
parseT' accepted ("*":tokens) = let (acc,rest) = parseF tokens in parseT' (accepted :*: acc) rest
parseT' accepted ("/":tokens) = let (acc,rest) = parseF tokens in parseT' (accepted :/: acc) rest
parseT' accepted ("%":tokens) = let (acc,rest) = parseF tokens in parseT' (accepted :%: acc) rest
parseT' accepted tokens = (accepted,tokens)

parseF :: [String] -> (Expr,[String])
parseF ("(":tokens) = (e, tail rest) where (e,rest) = parseE tokens 
parseF (t:tokens)
  | isAlpha (head t) = (Var t,tokens)
  | isDigit (head t) = (Val (read t),tokens)
  | otherwise = error ""
parseF [] = error ""


lexer :: String -> [String]
lexer [] = []
lexer (c:cs)
  | elem c " \t\n"        = lexer cs   
  | elem c "=+-*/%()" = [c]:(lexer cs)
  | isAlpha c             = (c:takeWhile isAlpha cs):lexer(dropWhile isAlpha cs)
  | isDigit c             = (c:takeWhile isDigit cs):lexer(dropWhile isDigit cs)
  | otherwise             = error ""
...