Edward Kmettによる「Introduction to Monoids」という名前のスライドから、モノイド解析という用語を偶然見つけました。スライド全体で haskell を使用しています。
今、この用語を検索すると、同じ著者からの言及がほとんどなく、ほとんどの言及しか見つかりませんでした。したがって、この用語はここで説明できると思います。
では、モノイド構文解析は興味深い新しいものですか? リンク先のスライド以外のどこかに表示されていますか? そして最も重要なことは、それは何ですか？スライド自体は、定義を与えたり、強調したりするようには見えませんでした。
パーサーが通常どのように機能するかから始めます。大まかに言うと、パーサーは入力トークンを順番に受け取ります。ある時点で (通常、すべてのトークンが使い果たされた後)、パーサーは出力を返します。このモデルの欠点の 1 つは、本質的にシーケンシャルであることです。パーサーは一連のトークンを順番に操作するため、プロセスを並列化する方法が明確ではありません。
ただし、部分的な解析結果を単一の結果に結合できる操作にアクセスできる場合は、解析を並列化できます。たとえば、言語が文脈自由文法で表現できる場合、すべてのトップレベルの定義を個別に並列に解析し、後で結合操作を使用して断片を組み立てることができます。
モノイド解析とは、パーサーが適切な結合関数にアクセスできることを意味します。モノイドは、ゼロ要素とバイナリ結合演算子を持つ構造です。たとえば、リストはモノイドを形成します。ゼロは空のリストであり、結合演算子は連結です。結合性とは を意味することを覚えておいてください(a++b)++c == a++(b++c)。これは、解析結果を適切な方法で再結合できるようにするために必要なプロパティです。各サブパースが適切なシーケンス位置に保持されている限り、サブパースが再結合される正確な順序は重要ではありません。
もちろん、実際に並列パーサーを作成するには、チャンクも適切に分割する必要があります。最上位の定義を並行して解析したい場合は、その定義がどこから始まるかを認識できる必要があります。このタスクは通常、パーサー自体によって実行されます。私が覚えているように、彼のスライドの大部分はこのトピックをカバーしています。最上位の定義での分割はかなり粗いものです。理想的には、パーサーは任意のトークンから開始し、後でモノイド演算子が適用されたときに断片から意味を理解できるようになります。
残念ながら、私は文献に特に精通していないため、「モノイド構文解析」が新しいものかどうかはわかりません。ただし、明示的に名前が付けられていなくても、並列解析のモデルまたはアルゴリズムにはモノイド構造が含まれているのではないかと思います。モノイドが問題の並列化に適していることは以前からよく知られているので、この手法がパーサー研究者の間で一般的であっても驚かないでしょう。
このページで彼の別のプレゼンテーションを試してみてください。あなたが読んでいるプレゼンテーションの 2 番目です。これは何か新しいことであり、私が実際にできることは、彼のスライドを言い換えて、(Parsec のような) 単項構文解析を採用し、より弱い代数構造を使用して、計算を再構築する余地を増やす試みであることを伝えることだけです。アイデアは、並列処理を改善することです。
編集: ページのコメントは、2 つの講演が連続して予定されていたことを示唆しているため、おそらく、あなたが見たスライドの言及は、2 番目の講演の前兆でした.