Хаскелл рекурсивная проблема, крошечный парсер. Несколько вещей

Question

data Expr =  Var Char | Tall Int | Sum Expr Expr | Mult Expr Expr | Neg Expr | Let Expr Expr Expr
    deriving(Eq, Show) 

Это тип данных для Expr, у меня есть несколько вопросов. Я предполагаю, что для анализа выражений, таких как *(Expr,Expr), как показано в определении типа данных. Однако у меня есть некоторые проблемы с «созданием» действительного Expr. Я использую сопоставление с образцом для распознавания различных вещей, которыми может быть Expr. Еще немного кода:

parseExpr :: String -> (Expr, String)
parseExpr ('*':'(':x:',':y:')':s)   = (Mult (parseExpr [x] parseExpr [y]),s) 

Это не работает, очевидно. Тип возврата parseExpr должен возвращать остаток выражения, которое должно быть проанализировано, в части проанализированного кода как Expr. Правая сторона этого кода является проблемой. Я не могу сделать действительный Expr. Предполагается, что функция рекурсивно вызывает себя, пока проблема не будет решена.

ДРУГАЯ проблема в том, что я не знаю, как выполнить сопоставление с шаблоном Var и Tall. Как я могу проверить, что Var является заглавным символом между A-Z и что Tall равен 0-9, и вернуть его как действительный Expr?

Обычно я могу просто посмотреть на несколько частей строки, чтобы понять, с какой частью Expr я имею дело.

Input like: parseProg "let X be 9 in *(X , 2)" Would spit out: Let (Var 'X') (Tall 9) (Mult (Var 'X') (Tall 2)) 

Answer 1

Ваша функция parseExpr возвращает пару, поэтому, конечно, вы не можете напрямую использовать ее результат для построения Expr. То, как я написал бы это, было бы что-то вроде

parseExpr ('*':'(':s) = (Mult x y, s'')
    where (x,',':s') = parseExpr s
          (y,')':s'') = parseExpr s'

Основная идея состоит в том, что, поскольку parseExpr возвращает оставшуюся строку в качестве второго аргумента пары, вам необходимо сохранять эту строку в каждом выполняемом вами рекурсивном вызове, а когда вы обработали все подвыражения, вам нужно вернуть все, что осталось. И, очевидно, обработка ошибок здесь отстой, так что вы можете подумать об этом немного больше, если это предназначен для надежного синтаксического анализатора.

Обработка Var и Tall Я бы сделал, просто извлекая первый символ как есть, и имел бы if для создания Expr соответствующего типа.

И если вы хотите писать более сложные синтаксические анализаторы в Haskell, вам нужно взглянуть на библиотеку Parsec, которая позволяет вам написать синтаксический анализатор почти как грамматику языка, который вы анализируете.