Как заставить функцию Parsec chainl1 следовать правилам приоритета операторов

Question

Я программирую стандартную математическую нотацию ->DC POSIX-совместимый формат конвертер. Он берет входную строку, анализирует ее в промежуточный тип данных и затем превращает ее в выходную строку на show.

Этот тип данных используется. У меня нет никаких проблем с типом данных -> Вывод строки преобразования, он работает безотказно:

data Expression = Expression :+ Expression 
       | Expression :- Expression 
       | Expression :* Expression 
       | Expression :/ Expression 
       | Expression :^ Expression 
       | Cons String 

infixr 0 :+ 
infixr 0 :- 
infixr 1 :* 
infixr 1 :/ 
infixr 2 :^ 

instance Show Expression where 
    show (x :+ y) = unwords [show x, show y, "+"] 
    show (x :- y) = unwords [show x, show y, "-"] 
    show (x :* y) = unwords [show x, show y, "*"] 
    show (x :/ y) = unwords [show x, show y, "/"] 
    show (x :^ y) = unwords [show x, show y, "^"] 
    show (Cons y) = y 

Парсек парсер часть, однако, отказывается соблюдать определенные правила старшинство операторов. Очевидно, из-за способом chainl1 используется в определении subexpression парсера:

expression :: Parser Expression 
expression = do 
    spaces 
    x <- subexpression 
    spaces >> eof >> return x 

subexpression :: Parser Expression 
subexpression = (
    (bracketed subexpression) <|> 
    constant 
) `chainl1` (
    try addition    <|> 
    try substraction   <|> 
    try multiplication  <|> 
    try division    <|> 
    try exponentiation 
) 

addition  = operator '+' (:+) 
substraction = operator '-' (:-) 
multiplication = operator '*' (:*) 
division  = operator '/' (:/) 
exponentiation = operator '^' (:^) 

operator :: Char -> (a -> a -> a) -> Parser (a -> a -> a) 
operator c op = do 
    spaces >> char c >> spaces 
    return op 

bracketed :: Parser a -> Parser a 
bracketed parser = do 
    char '(' 
    x <- parser 
    char ')' 
    return x 

constant :: Parser Expression 
constant = do 
    parity <- optionMaybe $ oneOf "-+" 
    constant <- many1 (digit <|> char '.') 
    return (if parity == Just '-' 
    then (Cons $ '_':constant) 
    else Cons  constant) 

Есть ли способ сделать синтаксический анализатор принимать во внимание правила оператора очередности без необходимости переписывать полноту моего кода?

Answer 1

Ну, вам не нужно переписывать весь код, но так как ваш subexpression анализатор не превалируют во внимание на всех, вы должны переписать, что - по существу.

Одна возможность состоит в том, чтобы построить его с анализаторов для подвыражения с операторами верхнего уровня с одинаковым приоритетом,

atom :: Parser Expression 
atom = bracketed subexpression <|> constant 

-- highest precedence operator is exponentiation, usually that's 
-- right-associative, hence I use chainr1 here 
powers :: Parser Expression 
powers = atom `chainr1` try exponentiation 

-- a multiplicative expression is a product or quotient of powers, 
-- left-associative 
multis :: Parser Expression 
multis = powers `chainl1` (try multiplication <|> try division) 

-- a subexpression is a sum (or difference) of multiplicative expressions 
subexpression :: Parser Expression 
subexpression = multis `chainl1` (try addition <|> try substraction) 

Другим вариантом, чтобы старшинства и ассоциативности позаботятся библиотекой и использовать Text.Parsec.Expr , а именно buildExpressionParser:

table = [ [binary "^" (:^) AssocRight] 
     , [binary "*" (:*) AssocLeft, binary "/" (:/) AssocLeft] 
     , [binary "+" (:+) AssocLeft, binary "-" (:-) AssocLeft] 
     ] 

binary name fun assoc = Infix (do{ string name; spaces; return fun }) assoc 

subexpression = buildExpressionParser table atom 

(который требует, чтобы bracketed parser и constant потребляют пробелы после используемых маркеров).