パーサコンビネータとは、何なのでしょうか

Question

知りたい事1

パーサコンビネータを知りたくて、質問をしました。
例えばですが、quitaの記載にあるパーサコンビネータには以下のようなソースコード(1文字取得のパーサ)がありますが
一文字取得のパーサは字句解析と明確な違いは何でしょうか？

public class Test {
    static char anyChar(String s) {
        return s.charAt(0);
    }
    public static void main(String[] args) {
        System.out.println(anyChar("abc"));
    }
}

知りたい事2

次に、パーサコンビネータはパーサではなくパーサを生成したり、組み合わせるプログラムという事でよろしいでしょうか？
例えば、特定の文字を切り取るパーサを生成する時に、構文規則(指定する文字)を引数として受け取り構文解析するプログラムはパーサとするのかパーサを生成するプログラムとなるのか確認したいです。

知りたい事3

最後に、パーサコンビネータに関わらずコンパイラの構文解析は何を表しているのでしょうか？
字句解析→構文解析→中間コード生成→コード最適化→コード生成
(中間コード生成がなぜ構文解析から成り立つのかが分かりません(構文解析が構文解析木を作成している事は分かっています))
できれば、参照したサイトのパーサコンビネータからやっている事から教えて頂けると助かります。

そして、パーサコンビネータは種類や記載する内容にもよりますがどこまで解析するのでしょうか？
字句解析と構文解析をまとめて行っているや構文解析や意味解析や文脈解析まで行うなど

知りたい事4

代表的なパーサコンビネータライブラリはどのようなものがありますか？
HaskellのPersecなど

参照サイト

https://qiita.com/7shi/items/68228e19552c271bea81

Comments

[xebme]

[コンパイラ]や[関数型プログラミング]タグを付けると専門家の注意を惹きますよ。

[misubakari]

了解です。

Answer 1

こんにちは。

詳しく解説すると文字数がいくらあっても足りないので、疑問点にだけ答えていこうと思います。

知りたい事1

参考記事のパーサは字句解析を行わず、一文字を一トークンとして扱うパーサを作成しています。
字句解析は文字列をトークン列に加工するものですが、文字をそのままトークンとみなす何もしない字句解析を行っていると考えても良いです。

一文字取得のパーサは、文字列がトークン列であるとみなす場合は単なるパーサの一つですが、文字列からトークン列に変換する道具として扱った場合は字句解析器に相当します。
それ単体だけでは判別することはできません。

知りたい事2

パーサコンビネータは「パーサジェネレータ」の一種であり、小さなパーサを無数に組み合わせて一つの大きなパーサを作る方針でパーサを生成するフレームワークを指します。

構文規則からパーサを生成するプログラムは「パーサジェネレータ」ではありますがパーサコンビネータではないです。
パーサジェネレータは言い換えると「構文規則を受け取ってパーサを返す関数」なので、それ自体はパーサではありません。
ただし、見方を変えると、「構文規則を解析するパーサ」と表現することも可能ではあります。

知りたい事3

中間コード、あるいはプログラムを組み立てるためには、まずプログラムの構造を知らないといけないわけですが、その「構造」が AST (抽象構文木) なわけです。
何もしなければただの文字の集まりでしかないソースコードからプログラムの構造を取り出すフェーズが構文解析なのです。

パーサがどこまでやるのかは、あなたがどのような規則を書くかに拠ります。
文字列を分割するだけでも、構文木を作るでも、何らかの処理に利用して計算結果にしてしまうことだってできます。
プログラミング言語のパーサに限ると、基本的には全て抽象構文木を最終成果物にしているはずです。

知りたい事4

パーサコンビネータの代表は知っての通り Haskell の parsec でしょう。
仕組みを覚えるにはこれの周囲を探るのが手っ取り早いと思います。

知りたいことへの直接の回答となると、パーサコンビネータ <プログラミング言語> でググれば無限に出てくるので自分で探してくださいとしか言えません。
デファクトスタンダードを見つけたければ、パッケージのダウンロード数や GitHub のスター数などを参考にしていけば良いかと思います。

Comments

[misubakari]

分かり易く丁寧にありがとうございます。

一点、気になったのですが
知りたい事2の
｛構文規則からパーサを生成するプログラムは「パーサジェネレータ」ではありますが
　パーサコンビネータではないです。｝
というのは、
構文規則にパーサがあれば(パーサの連接など)、パーサコンビネータと言えるのでしょうか？
ない場合は、ジェネレータ？
なんか、言葉尻をとらえるようで申し訳ありません。

[tamoto]

より正確には (狭義的には)、パーサコンビネータとは、パーサからパーサを生成する、「パーサを渡すとパーサを返す関数」のことを指します。
構文規則それ自体はパーサではない (構文規則を組み合わせて構文規則を作成することがあっても) ので、第一級パーサを扱うことによってのみ成り立つパーサコンビネータには該当しないことになるのです。

[misubakari]

了解です。