質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

89.63%

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

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 2
  • VIEW 202

misubakari

score 1

知りたい事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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • xebme

    2020/02/09 01:39

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

    キャンセル

  • misubakari

    2020/02/14 12:20

    了解です。

    キャンセル

回答 1

checkベストアンサー

+1

こんにちは。

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

知りたい事1

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

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

知りたい事2

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

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

知りたい事3

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

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

知りたい事4

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/02/14 18:15

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

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

    キャンセル

  • 2020/02/14 19:18

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

    キャンセル

  • 2020/02/15 12:49

    了解です。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 89.63%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る