Разобрать строку в Ast - PullRequest
Новая
       43

Разобрать строку в Ast

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

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

Вот моя грамматика (я не могу изменить это): 

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

Мой тип данных (ядолжен был заполнить для Min и Mult, и я думаю, что я понял это правильно): 

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

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

tokenize :: String -> [String]
tokenize [] = []
tokenize xs @ (x : xs')
    | x `elem` t = [x] : tokenize xs'
    | isDigit x = [y | y <- takeWhile isDigit xs] : (tokenize (dropWhile isDigit xs))
    | otherwise = tokenize xs'
        where t = ['+', '-', '*']

Это работает как надо.

Далее я сделал parseExpr :: [String] -> (Ast, [String]). Что он делает, так это просматривает список, составленный tokenize :: String -> [String] и рекурсивно производит Ast (я думаю, по крайней мере) 

parseExpr :: [String] -> (Ast,[String])
parseExpr [] = error "Error!"
parseExpr (s:ss) | all isDigit s = (Num (read s),ss)
             | s == "-" = let (e,ss') = parseExpr ss in (Min e,ss')
             | s == "*" = (Mult e e',ss'')
             | s == "+" = (Sum e e',ss'') where
                          (e,ss') = parseExpr ss
                          (e',ss'') = parseExpr ss'

Сейчас я борюсь с тем, как я могу объединить их в функциюparse :: String -> Ast. Моя попытка сделать это (что может быть далеко) что-то вроде этого. parseExpr производит вывод вида (Ast, [String]): 

parse :: String -> Ast
parse [] = error "Empty string"
parse str = parseExpr x
  where x = tokenize str

Моя проблема здесь такова:

Допустим, у меня есть простая строка str = "+ 1 4". 

tokenize str = ["+", "1", "4"]

Выполнение этого в parseExpr рекурсивно проходит по списку из токенизации и выдает такой вывод:

(Sum (Num 1) (Num 4),[])

Выводит Ast и пустой список строк,

Теперь вопрос под рукой. Мне нужно сделать так, чтобы parse "+ 1 4" вернул (Sum (Num 1) (Num 4)) Как я могу это сделать? Я рассматриваю вывод из parseExpr как список и беру Ast из 0-го индекса, или это невозможно? Должен ли я изменить способ, которым мой parseExpr проходит по списку? Любая помощь с благодарностью! Кстати, я не могу изменить ни определения функций, ни грамматику или тип данных для Ast.

1 Ответ

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

(Sum (Num 1) (Num 4),[]) - это кортеж, и вам нужен первый элемент.

Вы можете получить первый элемент из кортежа с помощью функции fst. 

parse :: String -> Ast
parse [] = error "Empty string"
parse str = fst $ parseExpr x
  where x = tokenize str
...