Packratパーサー

Packratパーサーは、その構造において再帰下降パーサーと類似点を持つタイプのパーサーです。ただし、 LL 文法ではなく構文解析式文法 (PEG) を入力として受け取る点で異なります。^[¹^]

1970 年、アレクサンダー・バーマンは「TMG 認識スキーム」（TS）と「一般化 TS」（gTS）を導入し、パックラット構文解析の基礎を築きました。TS はロバート M. マクルーアのTMGコンパイラコンパイラに基づいており、gTS はデューイヴァルショールの METAコンパイラコンパイラに基づいています。バーマンの研究は後にアホとウルマンによって改良され、それぞれトップダウン構文解析言語（TDPL）と一般化 TDPL（GTDPL）と改名されました。これらのアルゴリズムは、バックトラッキングを用いた決定論的トップダウン構文解析を採用した最初のアルゴリズムでした。^{[ 2 ]}^{[ 3 ]}

ブライアン・フォードは、GTDPLとTSの拡張としてPEGを開発しました。CFGとは異なり、 PEGは曖昧さがなく、機械語とよく一致します。PEGは、GTDPLやTSと同様に、すべてのLL(k)とLR(k)を表現することもできます。フォードはまた、単純なPEGパーサーの上にメモ化技術を使用するパーサーとしてPackratを導入しました。これは、PEGが無制限の先読み機能を持ち、最悪の場合に指数時間のパフォーマンスを持つパーサーになるためです。 ^{[ 2 ]}^{[ 3 ]}

Packrat は、相互再帰的な構文解析関数の中間結果を追跡します。各構文解析関数は、特定の入力位置で一度だけ呼び出されます。Packrat の実装によっては、メモリが不足している場合、特定の構文解析関数が同じ入力位置で複数回呼び出される必要があり、その結果、パーサーの処理時間が線形時間よりも長くなることがあります。^{[ 4 ]}

構文

パックラットパーサーは、PEGと同じ構文を入力として受け取ります。単純なPEGは、終端記号と非終端記号で構成され、場合によっては1つまたは複数の導出規則を構成する演算子が混在します。^{[ 2 ]}

シンボル

非終端記号は大文字で示されます（例： $\{S,E,F,D\}$ ）
終端記号は小文字で示されます（例： $\{a,b,z,e,g\}$ ）
表現は小文字のギリシャ文字で示されます（例： $\{\alpha ,\beta ,\gamma ,\omega ,\tau \}$ $\{\alpha ,\beta ,\gamma ,\omega ,\tau \}$ ）
- 式は、終端記号、非終端記号、および演算子の組み合わせで構成できます。

オペレーター

ルール

導出規則は、非終端記号と式から構成される。 $S\rightarrow \alpha$ 。

特別な表現 $\displaystyle \alpha _{s}}$ は文法の出発点です。^{[ 2 ]}の場合、 $\displaystyle \alpha _{s}}$ が指定されている場合、最初のルールの最初の式が使用されます。

入力文字列は、パーサーによって受け入れられたとみなされます。 $\displaystyle \alpha _{s}}$ 認識されます。副作用として、文字列 $x$ 完全に消費されていなくても、パーサーによって認識される可能性がある。^{[ 2 ]}

この規則の極端な例は、文法が $S\rightarrow x*$ 任意の文字列に一致します。

これは、文法を書き換えることで回避できます。 $S\rightarrow x*!.$

例

${\begin{cases}S\rightarrow A/B/D\\A\rightarrow {\texttt {'a'}}\ S\ {\texttt {'a'}}\\B\rightarrow {\texttt {'b'}}\ S\ {\texttt {'b'}}\\D\rightarrow ({\texttt {'0'}}-{\texttt {'9'}})?\end{cases}}$

この文法は、アルファベット上のいくつかの回文を認識する。 $\{a,b\}$ 中央に任意の数字を入れることができます。

文法で受け入れられる文字列の例は次のとおりです。 ${\texttt {'aa'}}$ そして ${\texttt {'aba3aba'}}$ しかし、受け入れることができない ${\texttt {'aaaa'}}$ 。

左再帰

左再帰は、文法生成規則が直接的または間接的に自身をその最左の要素として参照する場合に発生します。Packrat は再帰下降パーサーであるため、左再帰を直接処理することはできません。^{[ 5 ]}開発の初期段階で、左再帰の生成規則を右再帰の生成規則に変換できることが分かりました。^{[ 6 ]}この変更により、Packrat パーサーのタスクが大幅に簡素化されます。ただし、間接的な左再帰が関係する場合、書き換えのプロセスは非常に複雑で困難になる可能性があります。時間計算量の要件を線形から超線形に緩和すれば、入力文法を変更することなく、Packrat パーサーのメモ化テーブルを変更して左再帰を許可することが可能になります。^{[ 5 ]}

反復コンビネータ

反復コンビネータ $\alpha +$ そして $\alpha *$ Packrat パーサーで使用する場合は特別な注意が必要です。これらのコンビネータは、中間結果を結果マトリックスに記録しない秘密の再帰を導入するため、パーサーが超線形動作で動作する可能性があります。この問題は、次の変換を適用することで解決できます。^{[ 1 ]}

この変換により、中間結果を適切にメモ化することができる。

メモ化テクニック

メモ化は、コストのかかる関数呼び出しの結果を保存することでプログラムの高速化を目指す、コンピューティングにおける最適化手法です。この手法は基本的に、結果をキャッシュすることで機能します。同じ入力が再び発生した場合、キャッシュされた結果が単純に返されるため、時間のかかる再計算プロセスが回避されます。^{[ 7 ]}パックラット構文解析とメモ化を使用する場合、各非終端記号の構文解析関数は入力文字列のみに基づいていることに注意が必要です。構文解析プロセス中に収集された情報には依存しません。基本的に、メモ化テーブルのエントリは、特定の時点におけるパーサーの状態に影響を与えたり、依存したりしません。^{[ 8 ]}

Packrat構文解析では、結果を行列または同様のデータ構造に格納し、迅速な検索と挿入を可能にします。生成規則に遭遇すると、行列がチェックされ、それが既に発生しているかどうかを確認します。発生している場合は、結果が行列から取得されます。発生していない場合は、生成規則が評価され、結果が行列に挿入されて返されます。^{[ 9 ]}全体を評価する際には、 $m*n$ 表形式のアプローチでマトリックスを作成するには、 $\Theta (mn)$ 空間。^{[ 9 ]}ここで、 $m$ は非終端記号の数を表し、 $n$ 入力文字列のサイズを表します。

単純な実装では、入力文字列の末尾から始めて、テーブル全体を導出することができます。

Packrat パーサーは、各サブ式ツリーを深さ優先探索することで、行列内の必要なセルのみを更新するように改善できます。したがって、次元の行列を使用すると、 $m*n$ これは多くの場合無駄であり、ほとんどのエントリは空のままになります。^{[ 5 ]}これらのセルは入力文字列にリンクされており、文法の非終端記号にはリンクされていません。つまり、入力文字列のサイズを増やすと常にメモリ消費量が増加しますが、構文解析規則の数は最悪の空間計算量のみを変更します。^{[ 1 ]}

切断作業員

Packrat には、平均空間複雑度をさらに削減するためにcutと呼ばれる別の演算子が導入されました。この演算子は、多くのプログラミング言語の形式的な構造を利用して、不可能な導出を排除します。たとえば、標準プログラミング言語の制御文の解析は、最初に認識されたトークンから相互に排他的です。 $\{{\mathtt {if,do,while,switch}}\}$ [ ¹⁰^]

Packrat パーサーがカット演算子を使用すると、バックトラッキングスタックが効果的にクリアされます。これは、カット演算子が順序付き選択における可能な選択肢の数を減らすためです。文法の定義の適切な場所にカット演算子を追加することで、結果として得られる Packrat パーサーはメモ化にほぼ一定の量のスペースしか必要としません。しかし、Packrat パーサーが O(n) のスペースを必要とするという根本的な問題は解決されていません。^{[ 10 ]}

アルゴリズム

Luaライクな擬似コードによるパックラットアルゴリズムの実装の概略。^{[ 5 ]}

INPUT ( n ) -- n の位置にある文字を返すルール（R ：ルール、P ：ポジション）entry = GET_MEMO ( R , P ) -- ルール R の位置 P で以前に一致した要素の数を返しますエントリがnilの場合return EVAL ( R , P );終わりエントリを返す;EVAL ( R :ルール, P :位置)開始= P ;for choice in R . choices -- 選択肢のリストを返しますacc = 0 ;for symbol in choice then -- ルールの各要素（終端記号と非終端記号）を返すシンボルが終端記号である場合INPUT ( start + acc ) == symbol.terminalの場合acc = acc + 1 ; --正しい端末が見つかったのでスキップして通過するそれ以外壊す;終わりそれ以外res = RULE ( symbol . nonterminal , start + acc ); -- start+acc の位置にある非終端記号を認識しようとするSET_MEMO ( symbol . nonterminal , start + acc , res ); -- 特殊な値 fail を持つ失敗もメモ化しますres == failの場合壊す;終わりacc = acc + res ;終わりシンボルが選択の最後のシンボルと一致したかどうかを確認します。一致した場合は、return acc ;終わり終わりreturn fail ; -- 一致する選択肢がない場合は return fail

例

以下の文脈において、和、乗算、括弧によって交互に構成された1桁の数字からなる単純な算術式を認識する自由文法。

${\begin{cases}S\rightarrow A\\A\rightarrow M\ {\texttt {'+'}}\ A\ /\ M\\M\rightarrow P\ {\texttt {'*'}}\ M\ /\ P\\P\rightarrow {\texttt {'('}}\ A\ {\texttt {')'}}\ /\ D\\D\rightarrow ({\texttt {'0'}}-{\texttt {'9'}})\end{cases}}$

⊣で示される行末記号を用いてパックラットアルゴリズムを適用できます。

実装

参考文献

1 2 3 Ford, Bryan (2006). "Packrat Parsing: シンプル、パワフル、レイジー、線形時間". arXiv : cs/0603077 .
1 2 3 4 5 Ford, Bryan (2004-01-01). "構文解析式文法" .第31回 ACM SIGPLAN-SIGACT プログラミング言語の原理に関するシンポジウム議事録. POPL '04. ニューヨーク州ニューヨーク、米国: Association for Computing Machinery. pp. 111–122 . doi : 10.1145/964001.964011 . ISBN 978-1-58113-729-3. S2CID 7762102 .
1 2 Flodin, Daniel. 「実世界の文法と入力における Packrat 構文解析と従来のシフトリデュース構文解析の比較」(PDF)。
↑水島幸太、前田篤志、山口義則 (2010-05-06)「Packratパーサーは実用的な文法をほぼ定数空間で処理できる」。第9回ACM SIGPLAN-SIGSOFTプログラム解析ソフトウェアツールおよびエンジニアリングワークショップ論文集。ACM。pp . 29–36。doi : 10.1145 / 1806672.1806679。ISBN 978-1-4503-0082-7. S2CID 14498865 .
1 2 3 4 Warth, Alessandro; Douglass, James R.; Millstein, Todd (2008-01-07). "Packrat パーサーは左再帰をサポートできます" . 2008 ACM SIGPLAN 部分評価と意味論に基づくプログラム操作に関するシンポジウム議事録. PEPM '08. ニューヨーク州ニューヨーク、米国: Association for Computing Machinery. pp. 103–110 . doi : 10.1145/1328408.1328424 . ISBN 978-1-59593-977-7. S2CID 2168153 .
↑ Aho, Alfred V.; Lam, Monica S.; Sethi, Ravi; Ullman, Jeffrey D. 編 (2007).コンパイラ：原理、技術、ツール（第2版）. ボストン・ミュンヘン：ピアソン・アディソン・ウェスリー. ISBN 978-0-321-48681-3。
↑ Norvig, Peter (1991-03-01). "文脈自由構文解析への応用を伴う自動メモ化の手法" . Computational Linguistics . 17 (1): 91–98 . ISSN 0891-2017 .
↑ Dubroy, Patrick; Warth, Alessandro (2017-10-23). "Incremental packrat parsing" . Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering . SLE 2017. New York, NY, USA: Association for Computing Machinery. pp. 14–25 . doi : 10.1145/3136014.3136022 . ISBN 978-1-4503-5525-4. S2CID 13047585 .
1 2 Science、International Journal of Scientific Research in; Ijsrset、Engineering and Technology。「Packrat Parser の調査」。Packrat Parser の調査。
1 2水島幸太、前田篤志、山口義則 (2010-05-06) 「Packratパーサーは実用的な文法をほぼ定数空間で処理できる」 .第9回ACM SIGPLAN-SIGSOFTプログラム解析ソフトウェアツールおよびエンジニアリングワークショップ議事録. PASTE '10. ニューヨーク州ニューヨーク、米国: Association for Computing Machinery. pp. 29–36 . doi : 10.1145/1806672.1806679 . ISBN 978-1-4503-0082-7. S2CID 14498865 .
↑ PEG.jsの保守されたフォーク

外部リンク

Packrat構文解析：シンプル、パワフル、遅延評価、線形時間
構文解析式文法：認識に基づく構文基盤

[:3-1] 1 2 3 Ford, Bryan (2006). "Packrat Parsing: シンプル、パワフル、レイジー、線形時間". arXiv : cs/0603077 .

[:1-2] 1 2 3 4 5 Ford, Bryan (2004-01-01). "構文解析式文法" .第31回 ACM SIGPLAN-SIGACT プログラミング言語の原理に関するシンポジウム議事録. POPL '04. ニューヨーク州ニューヨーク、米国: Association for Computing Machinery. pp. 111–122 . doi : 10.1145/964001.964011 . ISBN 978-1-58113-729-3. S2CID 7762102 .

[:0-3] 1 2 Flodin, Daniel. 「実世界の文法と入力における Packrat 構文解析と従来のシフトリデュース構文解析の比較」(PDF)。

[4] 水島幸太、前田篤志、山口義則 (2010-05-06)「Packratパーサーは実用的な文法をほぼ定数空間で処理できる」。第9回ACM SIGPLAN-SIGSOFTプログラム解析ソフトウェアツールおよびエンジニアリングワークショップ論文集。ACM。pp . 29–36。doi : 10.1145 / 1806672.1806679。ISBN 978-1-4503-0082-7. S2CID 14498865 .

[:2-5] 1 2 3 4 Warth, Alessandro; Douglass, James R.; Millstein, Todd (2008-01-07). "Packrat パーサーは左再帰をサポートできます" . 2008 ACM SIGPLAN 部分評価と意味論に基づくプログラム操作に関するシンポジウム議事録. PEPM '08. ニューヨーク州ニューヨーク、米国: Association for Computing Machinery. pp. 103–110 . doi : 10.1145/1328408.1328424 . ISBN 978-1-59593-977-7. S2CID 2168153 .

[6] Aho, Alfred V.; Lam, Monica S.; Sethi, Ravi; Ullman, Jeffrey D. 編 (2007).コンパイラ：原理、技術、ツール（第2版）. ボストン・ミュンヘン：ピアソン・アディソン・ウェスリー. ISBN 978-0-321-48681-3。

[7] Norvig, Peter (1991-03-01). "文脈自由構文解析への応用を伴う自動メモ化の手法" . Computational Linguistics . 17 (1): 91–98 . ISSN 0891-2017 .

[8] Dubroy, Patrick; Warth, Alessandro (2017-10-23). "Incremental packrat parsing" . Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering . SLE 2017. New York, NY, USA: Association for Computing Machinery. pp. 14–25 . doi : 10.1145/3136014.3136022 . ISBN 978-1-4503-5525-4. S2CID 13047585 .

[:4-9] 1 2 Science、International Journal of Scientific Research in; Ijsrset、Engineering and Technology。「Packrat Parser の調査」。Packrat Parser の調査。

[:5-10] 1 2水島幸太、前田篤志、山口義則 (2010-05-06) 「Packratパーサーは実用的な文法をほぼ定数空間で処理できる」 .第9回ACM SIGPLAN-SIGSOFTプログラム解析ソフトウェアツールおよびエンジニアリングワークショップ議事録. PASTE '10. ニューヨーク州ニューヨーク、米国: Association for Computing Machinery. pp. 29–36 . doi : 10.1145/1806672.1806679 . ISBN 978-1-4503-0082-7. S2CID 14498865 .

[11] PEG.jsの保守されたフォーク

[ 4 ]

[ 6 ]

[ 7 ]

[ 8 ]

Packratパーサー

構文

シンボル

オペレーター

ルール

例

左再帰

反復コンビネータ

メモ化テクニック

切断作業員

アルゴリズム

例

実装

関連項目

参考文献

外部リンク

関連するトピック

再帰下降パーサー

パーサーです。ただし、

LL 文法

構文解析式文法 (PEG) を