Довольно стандартный способ написания синтаксических анализаторов с нуля на функциональных языках заключается в написании функций, которые принимают в качестве аргумента «оставленный ввод», пытаются проанализировать начальную часть этого ввода и вернуть результат анализа плюс "оставшийся ввод". Поскольку вы обычно хотите разрешить синтаксическому анализатору «изящно провалиться» (см. Ниже), вы обычно заключаете это возвращаемое значение в Maybe или что-то в этом роде.
Например, функция синтаксического анализа, которая пытается проанализировать целое число в начале строки будет выглядеть примерно так:
import Data.Char
import Data.List
number :: String -> Maybe (Int, String)
number str = case span isDigit str of
([], _) -> Nothing -- no digits found
(a, rest) -> Just (read a, rest)
Вот как это работает:
> number "34*x-4"
Just (34,"*x-4")
> number "x+2"
Nothing
Не так уж сложно написать синтаксический анализатор для простых полиномиальных выражений, используя это подходить. Вот синтаксический анализатор для имен односимвольных переменных:
-- read a single-character variable name
var :: String -> Maybe (Char, String)
var (x:rest) | isAlpha x = Just (x, rest)
| otherwise = Nothing
Из этого вы можете создать синтаксический анализатор для «терминов» в форме «2 * x», «y» или «18».
-- read a "term": "2*x" or "y" or "18"
data Term = TermPoly Int Char | TermConstant Int
deriving (Show)
term :: String -> Maybe (Term, String)
term str
= case number str of
Just (n, '*':str1) -> case var str1 of
Just (x, str2) -> Just (TermPoly n x, str2)
Nothing -> error "expected variable"
Just (n, str3) -> Just (TermConstant n, str3)
Nothing -> case var str of
Just (x, str4) -> Just (TermPoly 1 x, str4)
Nothing -> error "expected term"
Обратите внимание, как мы используем потенциальный сбой исходного number str синтаксического анализатора (т. Е. Ветвь Nothing самого верхнего case), чтобы попытаться проанализировать альтернативу переменной без коэффициента ( например, "y"). Вот почему полезно, чтобы синтаксические анализаторы «изящно терпели неудачу».
Теперь мы можем написать синтаксический анализатор для сумм и различий в терминах. Неловкое использование вспомогательной функции go здесь гарантирует, что "2*x-4*y+3" будет проанализирован как (2*x-4*y)+3 вместо 2*x-(4*y+3), что может произойти, если вы используете более очевидный рекурсивный метод определения poly без go helper:
-- read a polynomial as a sum of terms
data Poly = Single Term | Plus Poly Term | Minus Poly Term
deriving (Show)
poly :: String -> Maybe (Poly, String)
poly str = case term str of
Just (t, rest) -> go (Single t) rest
Nothing -> error "expected term"
where go :: Poly -> String -> Maybe (Poly, String)
go p ('+':str1) = case term str1 of
Just (t', str2) -> go (Plus p t') str2
Nothing -> error "expected term"
go p ('-':str1) = case term str1 of
Just (t', str3) -> go (Minus p t') str3
Nothing -> error "expected term"
go p str4 = Just (p, str4)
С приведенным выше кодом вы получите:
> poly "34*x-4"
Just (Minus (Single (TermPoly 34 'x')) (TermConstant 4),"")
> poly "34*x+92*x-3*x"
Just (Minus (Plus (Single (TermPoly 34 'x')) (TermPoly 92 'x')) (TermPoly 3 'x'),"")
> poly "x+y"
Just (Plus (Single (TermPoly 1 'x')) (TermPoly 1 'y'),"")
Он не обрабатывает ведущий знак минус, хотя:
> poly "-2*x+y"
*** Exception: expected term
CallStack (from HasCallStack):
error, called at PolyParser.hs:27:20 in main:Main
он также не обрабатывает x*5 или 2*5*x или скобки, или пробелы, или множество других случаев.
Кроме того, самый большой недостаток этого подхода заключается в том, насколько сложно объединять простые анализаторы компонентов в большие анализаторы. Например, term на самом деле концептуально очень прост: проанализируйте или number раз var, или одинокий number или одинокий var, но у нас есть все эти сложные операторы case для объединения number и var и проанализируйте символ '*'. Именно здесь важными становятся «комбинаторы синтаксического анализа» или «синтаксические анализаторы monadi c», так как они предоставляют простой и простой синтаксис для объединения синтаксических анализаторов.
По этой же причине опытный программист Haskell не пишет парсеры с нуля. Есть много отличных и мощных библиотек monadi c для анализа. Они занимают некоторое время, чтобы научиться использовать, но они того стоят. Достаточно полнофункциональный синтаксический анализатор Megaparse c для языка выражений занимает около 30 минут для записи в 60 с лишним строк и может обрабатывать сложные выражения (как пример в функции main ниже):
import Data.Void
import Text.Megaparsec
import Text.Megaparsec.Char
import qualified Text.Megaparsec.Char.Lexer as L
import Control.Monad.Combinators.Expr
type Parser = Parsec Void String
-- standard boilerplate for space handling
spaces :: Parser ()
spaces = L.space space1 empty empty
lexeme :: Parser a -> Parser a
lexeme = L.lexeme spaces
symbol :: String -> Parser String
symbol = L.symbol spaces
-- parse a number
number :: Parser Float
number = lexeme $ try L.float <|> fromIntegral <$> L.decimal
-- parse an identifier (e.g., "x_4")
identifier :: Parser String
identifier = lexeme $ (:) <$> (letterChar <|> char '_') <*> many (alphaNumChar <|> char '_')
-- abstract syntax tree for expressions
data Expr
= Num Float
| Var String
| Negate Expr
| BinOp BinOp Expr Expr
deriving (Show)
data BinOp
= Add | Sub | Mult | Div | Power
deriving (Show)
-- parse a "term": number, identifier, or expression in parentheses
term :: Parser Expr
term = Num <$> number
<|> Var <$> identifier
<|> between (symbol "(") (symbol ")") expr
-- parse an expression combining terms with operators
expr :: Parser Expr
expr = makeExprParser term
[ [binaryR "^" Power]
, [Prefix (Negate <$ symbol "-")]
, [binary "*" Mult, binary "/" Div]
, [binary "+" Add, binary "-" Sub]
]
where binary name f = InfixL (BinOp f <$ symbol name)
binaryR name f = InfixR (BinOp f <$ symbol name)
-- parse a whole string as an expression
fullExpr :: Parser Expr
fullExpr = spaces *> expr <* eof
main = parseTest fullExpr "(pi*r^2 - 4*pi*r) / (c^2 - a^2 - b^2)"
Как я уже сказал, до того момента, когда вы сможете писать такие парсеры, требуется довольно много времени, но стоит пройтись по некоторым учебникам, даже если вы еще не достигли того момента, когда сможете писать парсеры все по своему. Некоторые ресурсы, которые могут быть полезны для начала работы: