Processing math: 100%

2013/07/10

カテゴリー : , ,

HaskellのパーサコンビネータParsecを使ってみた

※注意: この記事は古い記事です。import周り等、最新versionのparsecライブラリにし追随ていません。一応、2013年(7月10日)当時はこうだったという形で記録として残してあります。(追記: 2017/7/17)

Haskellの勉強がてらParsecを使ってみました。

　コードを眺めただけだと、再帰的下向き構文解析を手で書いているのとあまり変わらないように見えますが、実際に書いてみると非常に簡単ですね。モナド使ってるっていうのが、気に入りませんが。構文解析のコードしか書いてないのに、字句解析器もやってくれます。

　次の文法をS式に書き直すパーサを書いてみました。中置記法を前置記法に変換します。LLパーサなので、左再帰しないように気を使います。
Infix  → Exp
Exp    → Term "+" Exp | Term "-" Exp | Term
Term   → Factor "*" Term | Factor "/" Term | Factor
Factor → ident | number | "(" Exp ")"

さらに、これを変換して、
Infix  → Exp
Exp    → Term Exp*
Exp*   → "+" Term Exp* | "-" Term Exp* | ε
Term   → Factor Term*
Term*  → "*" Factor Term* | "/" Factor Term* | ε
Factor → ident | number | "(" Exp ")"

を構文解析させます。変換したのは、演算子の適用順序を正しくするためです。εは、空を表します。

以下が、コードと実行結果。実行環境はghci 7.4.2。
module Parser where
import Text.ParserCombinators.Parsec
import qualified Text.ParserCombinators.Parsec.Token as TokenSymbols
import Text.ParserCombinators.Parsec.Language
lexer :: TokenSymbols.TokenParser ()
lexer = TokenSymbols.makeTokenParser(emptyDef)
symbol = TokenSymbols.symbol lexer
number = TokenSymbols.natural lexer
ident = TokenSymbols.identifier lexer
generateS_exp :: String -> String -> String -> String
generateS_exp op left right = "(" ++ op ++ " " ++ left ++ " " ++ right ++ ")"
parseInfix = (do {exp <- psExp; return exp})
psExp = (do {left<- psTerm; exp <- (psExpStar left); return exp})
psExpStar left = (do {symbol "+";
right <- psTerm;
append <- psExpStar (generateS_exp "+" left right);
return append})
<|> (do {symbol "-";
right <- psTerm;
append <- psExpStar (generateS_exp "-" left right);
return append})
<|> return left
psTerm = (do {left<- psFactor; exp <- (psTermStar left); return exp})
psTermStar left = (do {symbol "*";
right <- psFactor;
append <- psTermStar (generateS_exp "*" left right);
return append})
<|> (do {symbol "/";
right <- psFactor;
append <- psTermStar (generateS_exp "/" left right);
return append})
<|> return left
psFactor = (do {obj <- number; return (show obj)})
<|> (do {obj <- ident; return obj})
<|> (do {symbol "(";
obj <- psExp;
symbol ")";
return obj})
convertI2S s = parse parseInfix "i2s" s
view raw parsecSample.hs hosted with ❤ by GitHub
Prelude> :load "parsecSample.hs"
[1 of 1] Compiling Parser ( parsecSample.hs, interpreted )
Ok, modules loaded: Parser.
*Parser> convertI2S "1+2 * 3"
Right "(+ 1 (* 2 3))"
*Parser>
*Parser> convertI2S "1+2 * (3 + 4)"
Right "(+ 1 (* 2 (+ 3 4)))"
*Parser> convertI2S "1/2 * (3 - 4 - 5)"
Right "(* (/ 1 2) (- (- 3 4) 5))"
*Parser> convertI2S "1/2 * (3 - 4 - 5) @gmail.com"
Right "(* (/ 1 2) (- (- 3 4) 5))"
*Parser> convertI2S "http://1/2 * (3 - 4 - 5)"
Right "http"
*Parser> convertI2S "+http://1/2 * (3 - 4 - 5)"
Left "i2s" (line 1, column 1):
unexpected "+"
expecting natural, identifier or "("
*Parser>
view raw result.hs hosted with ❤ by GitHub

　Parsecは、ひたすら読めるまで読み続けて、パターンにマッチしない文字列が来たら、エラーを出さずに、マッチした部分の文字列の実行結果を返して、終了するようです。文字列を最後まで読み込み、エラーを出す為には、文法にEOF記号を混ぜる必要がありそうですね。Infix → Exp '$'、みたいな書き方にすればよかったってことでしょうか。

参考文献


0 件のコメント :

コメントを投稿