論文の概要: Happy-GLL: modular, reusable and complete top-down parsers for
parameterized nonterminals
- arxiv url: http://arxiv.org/abs/2303.08044v1
- Date: Tue, 14 Mar 2023 16:23:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-15 14:06:26.469672
- Title: Happy-GLL: modular, reusable and complete top-down parsers for
parameterized nonterminals
- Title（参考訳）: Happy-GLL:パラメータ化された非終端に対するモジュラー、再利用可能な完全なトップダウンパーサ
- Authors: L. Thomas van Binsbergen and Damian Frolich
- Abstract要約: 本稿では,モジュール型再利用可能な完全トップダウン文法を生成するための戦略を提案する。
この戦略は、Happyジェネレータの新しいバックエンドとして議論され、実証されている。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Parser generators and parser combinator libraries are the most popular tools
for producing parsers. Parser combinators use the host language to provide
reusable components in the form of higher-order functions with parsers as
parameters. Very few parser generators support this kind of reuse through
abstraction and even fewer generate parsers that are as modular and reusable as
the parts of the grammar for which they are produced. This paper presents a
strategy for generating modular, reusable and complete top-down parsers from
syntax descriptions with parameterized nonterminals, based on the FUN-GLL
variant of the GLL algorithm.
The strategy is discussed and demonstrated as a novel back-end for the Happy
parser generator. Happy grammars can contain `parameterized nonterminals' in
which parameters abstract over grammar symbols, granting an abstraction
mechanism to define reusable grammar operators. However, the existing Happy
back-ends do not deliver on the full potential of parameterized nonterminals as
parameterized nonterminals cannot be reused across grammars. Moreover, the
parser generation process may fail to terminate or may result in exponentially
large parsers generated in an exponential amount of time.
The GLL back-end presented in this paper implements parameterized
nonterminals successfully by generating higher-order functions that resemble
parser combinators, inheriting all the advantages of top-down parsing. The
back-end is capable of generating parsers for the full class of context-free
grammars, generates parsers in linear time and generates parsers that find all
derivations of the input string. To our knowledge, the presented GLL back-end
makes Happy the first parser generator that combines all these features.
This paper describes the translation procedure of the GLL back-end and
compares it to the LALR and GLR back-ends of Happy in several experiments.
- Abstract（参考訳）: パーサジェネレータとパーサコンビネータライブラリは、パーサを生成する最も一般的なツールである。
パーサコンビネータはホスト言語を使用して、パーサをパラメータとして高階関数の形で再利用可能なコンポーネントを提供する。
抽象化によるこの種の再利用をサポートするパーサジェネレータはごくわずかであり、生成する文法の一部と同じくらいモジュール化され再利用されるパーサも少なくない。
本稿では,GLL アルゴリズムの FUN-GLL 変種に基づいて,パラメータ付き非終端項を用いた構文記述から,モジュール型で再利用可能な完全なトップダウンパーサを生成する戦略を提案する。
この戦略はhappy parser generatorの新たなバックエンドとして議論され、実証されている。
幸せな文法は、パラメータが文法記号を抽象化し、再利用可能な文法演算子を定義する抽象化メカニズムを与える「パラメータ化された非終端」を含むことができる。
しかし、既存のHappyバックエンドは、パラメータ化された非終端が文法で再利用できないため、パラメータ化された非終端の完全なポテンシャルを発揮できない。
さらに、パーサ生成プロセスは終了に失敗したり、指数的に大きなパーサが指数的な時間で生成される可能性がある。
本稿では, パーサコンビネータに類似した高次関数を生成し, トップダウン解析の利点をすべて継承することによって, パラメータ化された非終端関数をうまく実装する。
バックエンドは、文脈自由文法の全クラスのパーサを生成し、線形時間でパーサを生成し、入力文字列のすべての派生を見つけるパーサを生成する。
私たちの知る限り、提示されたGLLバックエンドにより、Happyはこれらの機能をすべて組み合わせた最初のパーサジェネレータになります。
本稿では,GLLバックエンドの翻訳手順を説明し,HappyのLALRおよびGLRバックエンドと比較する。
関連論文リスト
- Automatic Prediction of the Performance of Every Parser [0.0]
機械翻訳性能予測システム(MTPPS)を用いた新しい性能予測(PPP)モデルを提案する。
この新しいシステムであるMTPPS-PPPは、任意の言語の性能を予測することができ、テキストを理解する際の文法的難易度を推定するのに有用である。
論文 参考訳（メタデータ） (2024-07-06T15:49:24Z) - ChatGPT is a Potential Zero-Shot Dependency Parser [5.726114645714751]
事前訓練された言語モデルが、ゼロショットシナリオに付加的な構造を導入することなく、自発的に依存性解析の能力を発揮できるかどうかについては、未検討のままである。
本稿では,ChatGPTなどの大規模言語モデルの依存性解析能力について検討し,言語解析を行う。
論文 参考訳（メタデータ） (2023-10-25T14:08:39Z) - Compositional Program Generation for Few-Shot Systematic Generalization [59.57656559816271]
コンポジションプログラムジェネレータ(CPG)と呼ばれるニューロシンボリックアーキテクチャに関する研究
CPGには3つの重要な特徴がある: 文法規則の形で、テキストモジュラリティ、テキストコンポジション、テキストタストラクションである。
SCAN と COGS のベンチマークでは,SCAN の14例と COGS の22例を使用して,完全な一般化を実現している。
論文 参考訳（メタデータ） (2023-09-28T14:33:20Z) - Adapting Language Models to Compress Contexts [71.98287002918941]
トランスフォーマーベースの言語モデル(LM)は強力で広く適用可能なツールであるが、その有用性は有限コンテキストウィンドウによって制限される。
本稿では,事前学習したLMを,長いコンテキストをコンパクトな要約ベクトルに圧縮可能なAutoCompressorに適応させることを提案する。
最大30,720個のトークンのシーケンスでOPTとLlama-2モデルを微調整し、AutoCompressorが長いコンテキストを使ってパープレキシティを向上できることを示す。
論文 参考訳（メタデータ） (2023-05-24T06:42:44Z) - SPINDLE: Spinning Raw Text into Lambda Terms with Graph Attention [0.8379286663107844]
モジュールは、原文入力をラムダ項で表現された意味合成のためのプログラムに変換する。
その出力は多モーダル型論理文法の階層的導出から成り立っている。
論文 参考訳（メタデータ） (2023-02-23T14:22:45Z) - Evaluating the Impact of Source Code Parsers on ML4SE Models [3.699097874146491]
名前予測言語でSupernorm2SeqとTreeLSTMの2つのモデルを評価する。
異なる木によって構築された木は、その構造や内容によって異なることを示す。
そして、この多様性がモデルの品質にどのように影響するかを分析する。
論文 参考訳（メタデータ） (2022-06-17T12:10:04Z) - Generalized Funnelling: Ensemble Learning and Heterogeneous Document
Embeddings for Cross-Lingual Text Classification [78.83284164605473]
emphFunnelling (Fun)は、最近提案された言語間テキスト分類手法である。
Emph Generalized Funnelling (gFun) はFunの一般化である。
gFunは、Funや最先端のベースラインよりも大幅に改善されていることを示す。
論文 参考訳（メタデータ） (2021-09-17T23:33:04Z) - Head-driven Phrase Structure Parsing in O($n^3$) Time Complexity [48.683350567504604]
2つの古典的な構文解析形式である構成解析と依存性解析は、統一的な形式主義の下での共同訓練と復号化の恩恵を受けている。
本稿では,O$($n3$) の時間的複雑さで新たなパフォーマンス保存を実現するために,改良されたヘッドスコアラを提案する。
論文 参考訳（メタデータ） (2021-05-20T15:33:51Z) - The LL(finite) strategy for optimal LL(k) parsing [0.0]
k を知らなくてもよい LL(k) 文法を解析するための LL(finite) 解析戦略を示す。
この戦略は入力を線形時間で解析し、任意だが常に最小限のルックアヘッドを使って非終端の代替品を曖昧にする。
論文 参考訳（メタデータ） (2020-10-15T16:52:29Z) - Glushkov's construction for functional subsequential transducers [91.3755431537592]
グルシコフの構成は多くの興味深い性質を持ち、トランスデューサに適用するとさらに明らかになる。
正規表現の特別な風味を導入し、効率よく$epsilon$-free 機能的次数重み付き有限状態トランスデューサに変換することができる。
論文 参考訳（メタデータ） (2020-08-05T17:09:58Z) - Towards Instance-Level Parser Selection for Cross-Lingual Transfer of
Dependency Parsers [59.345145623931636]
我々は、インスタンスレベルの選択(ILPS)という、新しい言語間移動パラダイムを論じる。
本稿では,デレキシライズドトランスファーの枠組みにおけるインスタンスレベルの選択に着目した概念実証研究を提案する。
論文 参考訳（メタデータ） (2020-04-16T13:18:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。