論文の概要: Inferring Input Grammars from Code with Symbolic Parsing

• arxiv url: http://arxiv.org/abs/2503.08486v1
• Date: Tue, 11 Mar 2025 14:40:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-12 15:44:37.004325
• Title: Inferring Input Grammars from Code with Symbolic Parsing
• Title（参考訳）: 記号解析を用いたコードからの入力文法の推定
• Authors: Leon Bettscheider, Andreas Zeller,
• Abstract要約: 一般的なテスト生成技術は、サンプル入力に依存しており、マッチした文法に抽象化され、テストカバレッジによってガイドされる/または進化する。 本研究では,降下符号から入力文法を記号的に自動生成する最初の手法を提案する。 結果として得られる文法は入力空間全体をカバーし、包括的で効果的なテスト生成、リバースエンジニアリング、ドキュメントを可能にする。
• 参考スコア（独自算出の注目度）: 12.567395326774754
• License:
• Abstract: Generating effective test inputs for a software system requires that these inputs be valid, as they will otherwise be rejected without reaching actual functionality. In the absence of a specification for the input language, common test generation techniques rely on sample inputs, which are abstracted into matching grammars and/or evolved guided by test coverage. However, if sample inputs miss features of the input language, the chances of generating these features randomly are slim. In this work, we present the first technique for symbolically and automatically mining input grammars from the code of recursive descent parsers. So far, the complexity of parsers has made such a symbolic analysis challenging to impossible. Our realization of the symbolic parsing technique overcomes these challenges by (1) associating each parser function parse_ELEM() with a nonterminal <ELEM>; (2) limiting recursive calls and loop iterations, such that a symbolic analysis of parse_ELEM() needs to consider only a finite number of paths; and (3) for each path, create an expansion alternative for <ELEM>. Being purely static, symbolic parsing does not require seed inputs; as it mitigates path explosion, it scales to complex parsers. Our evaluation promises symbolic parsing to be highly accurate. Applied on parsers for complex languages such as TINY-C or JSON, our STALAGMITE implementation extracts grammars with an accuracy of 99--100%, widely improving over the state of the art despite requiring only the program code and no input samples. The resulting grammars cover the entire input space, allowing for comprehensive and effective test generation, reverse engineering, and documentation.
• Abstract（参考訳）: ソフトウェアシステムの効果的なテストインプットを生成するには、これらのインプットが有効であることが要求される。 入力言語の仕様がない場合、一般的なテスト生成技術はサンプルの入力に依存しており、それは一致した文法に抽象化され、テストカバレッジによってガイドされる/または進化する。 しかし、サンプル入力が入力言語の特徴を見逃している場合、これらの特徴をランダムに生成する可能性は低い。 本研究では,再帰的降下解析器のコードから入力文法を記号的かつ自動マイニングする最初の手法を提案する。 これまでのところ、パーサーの複雑さは、このような象徴的な分析を不可能にしている。 シンボル解析技術の実現は,(1) パーサ関数 parse_ELEM() を非終端<ELEM> に関連付けること,(2) 再帰的な呼び出しとループの繰り返しを制限すること,(2) パース_ELEM() のシンボル解析が有限個のパスのみを考慮しなければならないこと,(3) パス毎に<ELEM> の拡張代替案を作成すること,など,これらの課題を克服します。 純粋に静的であるため、シンボリックパーシングはシード入力を必要としない。 我々の評価は記号解析が極めて正確であることを約束する。 STALAGMITEの実装はTINY-CやJSONなどの複雑な言語のパーサーに適用され、99-100%の精度で文法を抽出する。 結果として得られる文法は入力空間全体をカバーし、包括的で効果的なテスト生成、リバースエンジニアリング、ドキュメントを可能にする。

関連論文リスト

• Automatic Prediction of the Performance of Every Parser [0.0]
  機械翻訳性能予測システム(MTPPS)を用いた新しい性能予測(PPP)モデルを提案する。 この新しいシステムであるMTPPS-PPPは、任意の言語の性能を予測することができ、テキストを理解する際の文法的難易度を推定するのに有用である。
  論文  参考訳（メタデータ） (2024-07-06T15:49:24Z)
• MRL Parsing Without Tears: The Case of Hebrew [14.104766026682384]
  形態的にリッチな言語(MRL)では、トークンごとに複数の語彙単位を識別する必要があるが、既存のシステムはレイテンシとセットアップの複雑さに悩まされている。 決定は、専門家の分類器によって、各ユニットが1つの特定のタスクに特化して行われる。 この信じられないほど高速なアプローチは、HebrewのPOSタグ付けと依存性解析に新しいSOTAを設定し、他のHebrewタスクではほぼSOTAのパフォーマンスを実現している。
  論文  参考訳（メタデータ） (2024-03-11T17:54:33Z)
• SeqXGPT: Sentence-Level AI-Generated Text Detection [62.3792779440284]
  大規模言語モデル(LLM)を用いた文書の合成による文レベル検出の課題について紹介する。 次に,文レベルのAIGT検出機能として,ホワイトボックスLEMのログ確率リストを利用した textbfSequence textbfX (Check) textbfGPT を提案する。
  論文  参考訳（メタデータ） (2023-10-13T07:18:53Z)
• Improved Tree Search for Automatic Program Synthesis [91.3755431537592]
  重要な要素は、有効なプログラムの空間における効率的な探索を可能にすることである。 ここでは2つの大きな異なるDSL上でのアート結果の状態を導くMCTSの変種を提案する。
  論文  参考訳（メタデータ） (2023-03-13T15:09:52Z)
• SPINDLE: Spinning Raw Text into Lambda Terms with Graph Attention [0.8379286663107844]
  モジュールは、原文入力をラムダ項で表現された意味合成のためのプログラムに変換する。 その出力は多モーダル型論理文法の階層的導出から成り立っている。
  論文  参考訳（メタデータ） (2023-02-23T14:22:45Z)
• Compositional Task-Oriented Parsing as Abstractive Question Answering [25.682923914685063]
  タスク指向構文解析は、自然言語をアラームの設定など特定のタスクの機械可読表現に変換することを目的としている。 TOP に対する一般的なアプローチは、線形化されたパースツリーを生成するために seq2seq モデルを適用することである。 より最近の研究は、事前訓練されたSeq2seqモデルは、それ自体が自然言語である出力を生成するのに優れており、線形化されたパースツリーを標準自然言語のパラフレーズに置き換えていると主張している。
  論文  参考訳（メタデータ） (2022-05-04T14:01:08Z)
• On The Ingredients of an Effective Zero-shot Semantic Parser [95.01623036661468]
  我々は、標準発話とプログラムの訓練例を文法から言い換えて、ゼロショット学習を分析する。 改良された文法,より強力なパラフレーズ,効率的な学習手法を用いて,これらのギャップを埋めることを提案する。 我々のモデルはラベル付きデータゼロの2つの意味解析ベンチマーク(Scholar, Geo)で高い性能を達成する。
  論文  参考訳（メタデータ） (2021-10-15T21:41:16Z)
• Zero-Shot Cross-lingual Semantic Parsing [56.95036511882921]
  7つのテスト言語に対する並列データを持たないゼロショット問題として,言語間セマンティックパーシングについて検討した。 英文論理形式ペアデータのみを用いて解析知識を付加言語に転送するマルチタスクエンコーダデコーダモデルを提案する。 このシステムは、ゼロショット解析を潜時空間アライメント問題としてフレーム化し、事前訓練されたモデルを改善し、最小のクロスリンガル転送ペナルティで論理形式を生成することができる。
  論文  参考訳（メタデータ） (2021-04-15T16:08:43Z)
• Pareto Probing: Trading Off Accuracy for Complexity [87.09294772742737]
  我々は,プローブの複雑性と性能の基本的なトレードオフを反映したプローブ計量について論じる。 係り受け解析による実験により,文脈表現と非文脈表現の統語的知識の幅広いギャップが明らかとなった。
  論文  参考訳（メタデータ） (2020-10-05T17:27:31Z)
• A Simple Global Neural Discourse Parser [61.728994693410954]
  本稿では,手作業で構築した特徴を必要とせず,学習したスパン表現のみに基づく簡易なグラフベースニューラル談話を提案する。 我々は,我々のモデルが世界規模で最高の性能を達成し,最先端の欲求に匹敵する性能を実証的に示す。
  論文  参考訳（メタデータ） (2020-09-02T19:28:40Z)

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

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