論文の概要: An Empirical Comparison of General Context-Free Parsers

• arxiv url: http://arxiv.org/abs/2606.08465v1
• Date: Sun, 07 Jun 2026 05:58:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-09 14:42:06.121423
• Title: An Empirical Comparison of General Context-Free Parsers
• Title（参考訳）: 一般文脈自由パーザの実証比較
• Authors: Huan Vo, Danushka Liyanage, Hong Jin Kang, Sasha Rubin, Rahul Gopinath,
• Abstract要約: パーシングは、コンパイラや静的アナライザから言語サーバーやファズテストツールに至るまで、幅広いソフトウェアエンジニアリングタスクを支えている。 実際にデプロイされるほとんどのアルゴリズムは決定論的(LLまたはLR)であり、開発者は解析性のために設計した言語に適合するように文法をゆがめざるを得ない。 我々は、Rustで実装された6つの汎用構文解析アルゴリズムを、共有データ構造とパースツリー抽出で統一し、制御した最初のベンチマークを示す。 決定論的文法では、GLRファミリーは狭く予測可能な3倍の減速しか生じない。
• 参考スコア（独自算出の注目度）: 9.393047946491487
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Parsing underpins a vast range of software engineering tasks, from compilers and static analyzers to language servers and fuzz testing tools. Yet most parsers deployed in practice are deterministic (LL or LR), forcing developers not only to contort their grammars to fit the parser, but to simplify the very languages they design sacrificing expressiveness for the sake of parseability. General context-free parsers eliminate this constraint. Yet, despite decades of algorithmic development, no rigorous head-to-head comparison exists across the major families of parsing algorithms. We present the first unified, controlled benchmark of six generalized parsing algorithms: CYK, Valiant, Earley, GLL, RNGLR, and BRNGLR, plus deterministic LL(1) and LR(1) baselines, all implemented in Rust with shared data structures and parse-tree extraction, and evaluated across 22 grammars ranging from simple expressions to full C++ and Java. Our results show that the cost of generality is lower than widely assumed. On deterministic grammars, the GLR family incurs only a 3x median slowdown over LR(1), with a narrow and predictable variance. GLR is the clear performance winner among generalized parsers and a practical default choice for software engineering tools.
• Abstract（参考訳）: パーシングは、コンパイラや静的アナライザから言語サーバーやファズテストツールに至るまで、幅広いソフトウェアエンジニアリングタスクを支えている。 しかし、実際にデプロイされるほとんどのパーサーは決定論的(LLまたはLR)であり、開発者はパーサーに適合するように文法を歪ませるだけでなく、パーセビリティのために表現性を犠牲にする言語をシンプルにする。 一般的な文脈自由パーサは、この制約を排除します。 しかし、アルゴリズム開発が何十年にもわたって続いているにもかかわらず、パースアルゴリズムの主要なファミリー間で厳密な比較は存在しない。 CYK, Valiant, Earley, GLL, RNGLR, BRNGLR, さらに決定論的LL(1)とLR(1)のベースラインをRustで実装し,データ構造とパースツリー抽出を行い, 単純な式から完全なC++, Javaまで,22の文法にわたって評価した。 その結果,一般コストは広く想定されるよりも低いことがわかった。 決定論的文法では、GLRファミリーはLR(1)に対して3倍の中央値の減速しか生じず、狭く予測可能なばらつきがある。 GLRは、一般的なパーサーの中で明らかなパフォーマンスの勝者であり、ソフトウェアエンジニアリングツールの事実上のデフォルト選択である。

関連論文リスト

• Prefix Parsing is Just Parsing [53.010152712125766]
  プレフィックスパーシングは、入力プレフィックスを与えられた文法によって生成された完全な文字列に拡張できるかどうかを問う。 そこで我々は,プレフィックス文法変換を導入し,プレフィックス解析を通常の構文解析に効率よく還元する。 また,次点重みベクトルを計算するためのアルゴリズム微分に基づく戦略も提案する。
  論文  参考訳（メタデータ） (2026-04-23T01:20:40Z)
• Superset Decompilation [7.989066784325648]
  decompilationはコンパイルの逆で、モジュラーパスのシーケンスとして構成できる。 我々はこれを、バイナリに関する事実を一元的にリレーショナルストアに導出するフレームワークである、証明誘導スーパーセットデコンパイル(PGSD)として定式化する。 Mandelは、宣言的なリバースエンジニアリングフレームワークとしてPGSDを実装しており、Linux ELFバイナリを35K行のRustとDatalogの粒度の中間表現を通じてC99に引き上げている。
  論文  参考訳（メタデータ） (2026-03-30T03:47:19Z)
• Towards the Systematic Testing of Regular Expression Engines [8.561133495117675]
  ReTestは、正規表現エンジンを体系的にテストするフレームワークである。 文法を意識したファジィングをハイコードカバレッジとメタモルフィックテストを組み合わせて、方言に依存しないテストオラクルを生成する。 PCREに関する予備評価では、ReTestは既存のファジィ手法よりも3倍高いエッジカバレッジを実現している。
  論文  参考訳（メタデータ） (2026-02-27T21:00:31Z)
• EquiBench: Benchmarking Large Language Models' Reasoning about Program Semantics via Equivalence Checking [58.15568681219339]
  大規模言語モデル(LLM)を評価するための新しいベンチマークであるEquiBenchを紹介する。 このタスクは、プログラムのセマンティクスについて推論するモデルの能力を直接テストする。 19の最先端LCMを評価し、最も難しいカテゴリでは、最高の精度は63.8%と76.2%であり、50%のランダムベースラインよりわずかに高い。
  論文  参考訳（メタデータ） (2025-02-18T02:54:25Z)
• Leveraging Code to Improve In-context Learning for Semantic Parsing [48.66031267718704]
  In-context Learning (ICL) は、その少数ショットの性質と一般化の改善により、意味解析に魅力的なアプローチである。 我々は,(1)DSLの代わりにPythonなどの汎用プログラミング言語を用いた意味解析におけるICLの有効性を向上し,(2)ドメイン記述を構造化したプロンプトを増強する。
  論文  参考訳（メタデータ） (2023-11-16T02:50:06Z)
• Compositional Program Generation for Few-Shot Systematic Generalization [59.57656559816271]
  コンポジションプログラムジェネレータ(CPG)と呼ばれるニューロシンボリックアーキテクチャに関する研究 CPGには3つの重要な特徴がある: 文法規則の形で、テキストモジュラリティ、テキストコンポジション、テキストタストラクションである。 SCAN と COGS のベンチマークでは,SCAN の14例と COGS の22例を使用して,完全な一般化を実現している。
  論文  参考訳（メタデータ） (2023-09-28T14:33:20Z)
• Happy-GLL: modular, reusable and complete top-down parsers for parameterized nonterminals [0.0]
  本稿では,モジュール型再利用可能な完全トップダウン文法を生成するための戦略を提案する。 この戦略は、Happyジェネレータの新しいバックエンドとして議論され、実証されている。
  論文  参考訳（メタデータ） (2023-03-14T16:23:23Z)
• The LL(finite) strategy for optimal LL(k) parsing [0.0]
  k を知らなくてもよい LL(k) 文法を解析するための LL(finite) 解析戦略を示す。 この戦略は入力を線形時間で解析し、任意だが常に最小限のルックアヘッドを使って非終端の代替品を曖昧にする。
  論文  参考訳（メタデータ） (2020-10-15T16:52:29Z)
• A Simple Global Neural Discourse Parser [61.728994693410954]
  本稿では,手作業で構築した特徴を必要とせず,学習したスパン表現のみに基づく簡易なグラフベースニューラル談話を提案する。 我々は,我々のモデルが世界規模で最高の性能を達成し,最先端の欲求に匹敵する性能を実証的に示す。
  論文  参考訳（メタデータ） (2020-09-02T19:28:40Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。