2

標準の数学表記法をプログラミングしています-> DC POSIX準拠のフォーマットコンバーター。入力文字列を受け取り、それを中間データ型に解析し、それをshowing して出力文字列に変換します。

これは使用されるデータ型です。データ型 -> 出力文字列の変換に問題はありません。問題なく動作します。

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

ただし、Parsec パーサー部分は、定義された演算子の優先順位規則への準拠を拒否します。明らかに、パーサー定義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)

コード全体を書き直さなくても、パーサーに演算子の優先順位規則を考慮させる方法はありますか?

4

1 に答える 1

7

コード全体を書き直す必要はありませんが、subexpressionパーサーは優先順位をまったく考慮しないため、大幅に書き直す必要があります。

1 つの可能性は、同じ優先順位を持つ最上位の演算子を持つ部分式のパーサーから構築することです。

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

于 2013-05-03T22:04:29.683 に答える