あどけない話

インターネットに関する技術的な話など

とりとめのないパーサー談義

パーサーに関して、調べたことと疑問を書いておきます。パーサーに詳しい人に答えて頂けると、とても嬉しいです。

チョムスキー階層によれば、以下のような関係が成り立ちます。

正規文法 < 文脈自由文法 < 文脈依存文法 < 制限のない文法

それで、文脈自由文法の中は、こういう関係が成り立ちます。

LL法 < SL法 < LALR法 < LR法 < GLR法

GLR法は、文脈自由文法の全体を解析できる能力を持ちます。

  • 疑問1) GLR法は、文脈依存文法(の一部)も解析できるのか?

LL(1)

LL(1)に、収まっているのは XMLLisp です。

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)このパーサーは、文脈自由文法全体を解析する能力があるか?

追記

疑問5)の答えは、ドラゴン本(「コンパイラI」)の338ページに書いてありました。「BNF と文脈自由文法の等価性はいちはやく認められ...」