パーサーに関して、調べたことと疑問を書いておきます。パーサーに詳しい人に答えて頂けると、とても嬉しいです。
チョムスキー階層によれば、以下のような関係が成り立ちます。
正規文法 < 文脈自由文法 < 文脈依存文法 < 制限のない文法
それで、文脈自由文法の中は、こういう関係が成り立ちます。
LL法 < SL法 < LALR法 < LR法 < GLR法
GLR法は、文脈自由文法の全体を解析できる能力を持ちます。
- 疑問1) GLR法は、文脈依存文法(の一部)も解析できるのか？
LALR(1)
LALR(1)に、収まっているのは、ほとんどのコンピュータ言語です。たとえば、C や Java。
GLR
GLRに収まっているのは、C++ です。たとえば、D 言語の「テンプレート再訪」には、以下のように文脈がないと比較なのかテンプレートなのか判断できない例が載っています。
a<b,c>d;
- 疑問2) C++ は GLR で解析できますが、文脈依存文法でしょうか？
- 疑問3) Perl も、LALR ではなく GLR を使わないと解析でないと聞きましたが本当でしょうか？ 簡単な例はありますか？
- 疑問4) Ruby の << や BASIC の = も GLR を使わないと解析できませんか？
Parsec
Parsec のチュートリアルの訳は、間違っていますね。
Parsec は Haskell のモナドパーサコンビネータライブラリで、文脈依存文法や無限先読み文法を解析できますが、 LL(1) 文法と同等の性能を出します。
原文はこうです。
Parsec is an industrial strength, monadic parser combinator library for Haskell. It can parse context-sensitive, infinite look-ahead grammars but it performs best on predictive (LL[1]) grammars.
僕が訳すとこうなります。
Parsec は、Haskell の実用的なモナディク・パーサー・コンビネーター・ライブラリです。無限先読みの文脈依存文法を解析でき、LL(1)のときに最高の性能を発揮します。
つまり、Parsec は、いくらでも後戻りでき、最悪すべてのパスを検査できるが、後戻りがない場合に一番効率がいいということですね。
モナディック・パーサー
以前、書いた「モナディック・パーサー」の記事に関してです。
これまた Graham Hutton さんが書いた、Progoramming in Haskell を読んでいて気付きました。bind や <|> は、以下のように定義すると、初心者には分りやすいですね。
instance Monad Parser where p >>= f = Parser $ \cs -> case parse p cs of [] -> [] [(a,cs')] -> parse (f a) cs' p <|> q = Parser $ \cs -> case parse p cs of [] -> parse q cs [x] -> [x]
つまり、>>= を AND、<|> を OR として定義すればいいのです。
このパーサは、<|> で後戻りできるので、LL(1) 以上の能力があります。q には p と同じ入力 cs を与えていますから。つまり、cs は消費されてないので、後戻りしたこと同じです。
ま、chainl のおかげで、左再帰も OK なので LL(1) 以上なのは明らかですが。また、パスを一つしか返さないので、リストではなく Maybe を使う方がいいかもしれません。
以下のように、すべてのパスを探索するように bind と <|> を定義した場合、解析能力はさらに大きくなります。
instance Monad Parser where p >>= f = Parser $ \cs -> concat [parse (f a) cs' | (a,cs') <- parse p cs] instance MonadPlus Parser where mplus p q = Parser $ \cs -> parse p cs ++ parse q cs p <|> q = p `mplus` q
- 疑問5)BNFは、文脈自由文法全体を表現する能力があるか？
- 疑問6)このパーサーは、文脈自由文法全体を解析する能力があるか？
