パックラットパーサー

Type of parser

パックラットパーサー

クラス	PEGの構文解析文法
データ構造	弦
最悪の パフォーマンス	${\displaystyle O(n)}$または反復コンビネータの特別な処理なしで ${\displaystyle O(n^{2})}$
最高の パフォーマンス	${\displaystyle O(n)}$
平均的な パフォーマンス	${\displaystyle O(n)}$
最悪の場合の 空間複雑度	${\displaystyle O(n)}$

Packratパーサーは、その構造において再帰下降パーサーと類似点を持つパーサーの一種です。しかし、 LL文法ではなく、構文解析式文法（PEG）を入力として受け取る点が異なります。^[1]

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]

シンボル

• 非終端記号は大文字で示されます（例：） ${\displaystyle \{S,E,F,D\}}$
• 端末記号は小文字で示されます（例：） ${\displaystyle \{a,b,z,e,g\}}$
• 表現は小文字のギリシャ文字で示されます（例：） ${\displaystyle \{\alpha ,\beta ,\gamma ,\omega ,\tau \}}$
  • 式は終端記号、非終端記号、演算子を混在させることができます。

オペレーター

構文規則

オペレーター	セマンティクス
順序 ${\displaystyle \alpha \beta }$	成功:とが認識されれば ${\displaystyle \alpha }$ ${\displaystyle \beta }$ 失敗:またはが認識されない場合 ${\displaystyle \alpha }$ ${\displaystyle \beta }$ 消費： 成功した場合 ${\displaystyle \alpha }$ ${\displaystyle \beta }$
順序付けられた選択 ${\displaystyle \alpha /\beta /\gamma }$	成功:左から認識された場合 ${\displaystyle \{\alpha ,\beta ,\gamma \}}$ 失敗:すべてが一致しない ${\displaystyle \{\alpha ,\beta ,\gamma \}}$ 消費:成功を生成したアトミック式。複数の成功があった場合は、常に最初のものが返されます。
そして述語 ${\displaystyle \&\alpha }$	成功:認識された場合 ${\displaystyle \alpha }$ 失敗:認識されない場合 ${\displaystyle \alpha }$ 消費済み:入力は消費されません
述語ではない ${\displaystyle !\alpha }$	成功:認識されない場合 ${\displaystyle \alpha }$ 失敗:認識された場合 ${\displaystyle \alpha }$ 消費済み:入力は消費されません
1つ以上 ${\displaystyle \alpha +}$	成功: 1回または複数回認識してみてください ${\displaystyle \alpha }$ 失敗:認識されない場合 ${\displaystyle \alpha }$ 消費：認識される最大数 ${\displaystyle \alpha }$
0個以上 ${\displaystyle \alpha *}$	成功: 0回または複数回認識する ${\displaystyle \alpha }$ 失敗:失敗できない 消費：認識される最大数 ${\displaystyle \alpha }$
ゼロか1か ${\displaystyle \alpha ?}$	成功: 0または1回認識するようにしてください ${\displaystyle \alpha }$ 失敗:失敗できない 消費： 認識された場合 ${\displaystyle \alpha }$
端末範囲 [ ] ${\displaystyle a-b}$	成功:範囲内の端末を認識します。 の場合、はhからzまでの任意の文字になります。 ${\displaystyle c}$ ${\displaystyle [a-b]}$ ${\displaystyle [{\textbf {'}}h{\textbf {'}}-{\textbf {'}}z{\textbf {'}}]}$ ${\displaystyle c}$ 失敗:内部の端子が認識できない 場合 ${\displaystyle [a-b]}$ 消費： 認識された場合 ${\displaystyle c}$
任意の文字 ${\displaystyle .}$	成功:入力された文字を認識する 失敗:入力に文字がない場合 消費:入力内の任意の文字

ルール

導出規則は、非終端記号と式で構成されます。 ${\displaystyle S\rightarrow \alpha }$

特殊表現は文法の開始点となる。^[2]が指定されていない場合は、最初のルールの最初の表現が使用される。 ${\displaystyle \alpha _{s}}$ ${\displaystyle \alpha _{s}}$

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

この規則の極端な例は、文法が任意の文字列に一致することです。 ${\displaystyle S\rightarrow x*}$

これは文法を次のように書き直すことで回避できます。 ${\displaystyle S\rightarrow x*!.}$

例

${\displaystyle {\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}}}$

この文法は、アルファベット上の回文と、その中間の任意の数字を認識します。 ${\displaystyle \{a,b\}}$

文法によって受け入れられる文字列の例には、およびが含まれます。 ${\displaystyle {\texttt {'aa'}}}$ ${\displaystyle {\texttt {'aba3aba'}}}$

左再帰

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

反復コンビネータ

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

オリジナル	翻訳済み
${\displaystyle S\rightarrow \alpha +}$	${\displaystyle S\rightarrow \alpha S/\alpha }$
${\displaystyle S\rightarrow \alpha *}$	${\displaystyle S\rightarrow \alpha S/\epsilon }$

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

メモ化技術

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

Packrat解析は、結果を行列または類似のデータ構造に保存し、迅速な検索と挿入を可能にします。生成規則に遭遇すると、行列内でそれが既に出現しているかどうかがチェックされます。既に出現している場合は、行列から結果が取得されます。そうでない場合は、生成規則が評価され、結果が行列に挿入されて返されます。^[9]行列全体を表形式で評価する場合、スペースが必要になります。^[9]ここで、は非終端記号の数、は入力文字列のサイズを表します。 ${\displaystyle m*n}$ ${\displaystyle \Theta (mn)}$ ${\displaystyle m}$ ${\displaystyle n}$

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

Packratパーサーは、各部分式木を深さ優先で巡回することで、行列内の必要なセルのみを更新するように改良できます。その結果、次元の行列を使用すると、ほとんどのエントリが空のままになるため、無駄が多くなります。^[5]これらのセルは、文法の非終端記号ではなく、入力文字列にリンクされています。つまり、入力文字列のサイズを増やすとメモリ消費量は常に増加しますが、構文解析規則の数が増えても、空間計算量は最も悪くなるだけです。^[1] ${\displaystyle m*n}$

カット演算子

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

オペレーター	セマンティクス
カット ${\displaystyle {\begin{array}{l}\alpha \uparrow \beta /\gamma \\(\alpha \uparrow \beta )*\end{array}}}$	が認識されるが、そうでない場合は、代替の評価をスキップします。 ${\displaystyle \alpha }$ ${\displaystyle \beta }$ 最初のケースでは、が認識されたかどうかを評価しません。 2 番目のルールは と書き直すことができ、同じルールを適用できます。 ${\displaystyle \gamma }$ ${\displaystyle \alpha }$ ${\displaystyle N\rightarrow \alpha \uparrow \beta N/\epsilon }$

Packratパーサがカット演算子を使用すると、バックトラックスタックが実質的にクリアされます。これは、カット演算子が順序付き選択肢における可能な選択肢の数を減らすためです。文法定義の適切な場所にカット演算子を追加することで、結果として得られるPackratパーサは、メモ化に必要なスペースがほぼ一定になります。^[10]

アルゴリズム

Luaのような擬似コードによるPackratアルゴリズムの実装のスケッチ。^[5]

INPUT ( n ) -- n番目の位置の文字を返す ルール（R ：ルール、P ：ポジション）       entry = GET_MEMO ( R , P ) -- ルール R の位置 P で以前に一致した要素の数を返します。    エントリ== nilの場合     EVAL ( R , P )を返します。   終わり 戻りエントリ; EVAL ( R :ルール、P :位置)       開始= P ;    Rのchoices関数。choices関数-- 選択肢のリストを返す     acc = 0 ; for symbol in choice then -- ルールの各要素（終端と非終端）を返す      シンボルがis_terminalの場合   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 ;     終わり if symbol == choice . last -- choiceの最後のシンボルと一致しているかどうかをチェックし、一致している場合は return     accを返します。  終わり 終わり 失敗を返す; --選択肢が一致しない場合は失敗を返す  

例

次のコンテキストでは、合計、乗算、括弧が交互に配置された 1 桁の数字で構成される単純な算術式を認識するフリー 文法です。

${\displaystyle {\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}}}$

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

の導出2*(3+4)⊣

構文木	アクション	パックラットテーブル
	導出規則 入力シフト ${\displaystyle {\begin{array}{l}S\rightarrow A\\A\rightarrow M\ {\texttt {'+'}}\ A\\M\rightarrow P\ {\texttt {'*'}}\ M\\P\rightarrow {\texttt {'('}}\ A\ {\texttt {')'}}\end{array}}}$ ɛ 注記 左に入力 入力が導出の最初の要素と一致しません。 未探索の代替案を持つ最初の文法規則に戻る ${\textstyle P\rightarrow {\texttt {'('}}\ A\ {\texttt {')'}}\ /\ {\underline {D}}}$ 2*(3+4)⊣	索引 1 2 3 4 5 6 7 S あ M P D 2 * （ 3 + 4 ） 端末が認識されなかったため更新されません
	導出規則 入力シフト ${\displaystyle P\rightarrow D}$ ${\displaystyle D\rightarrow 2}$ 2 注記 左に入力 端子2を導出後、入力を1つシフトする *(3+4)⊣	索引 1 2 3 4 5 6 7 S あ M P 1 D 1 2 * （ 3 + 4 ） アップデート： D(1) = 1; P(1) = 1;
	導出規則 入力シフト ${\displaystyle M\rightarrow P\ {\texttt {'*'}}\ M}$ ${\displaystyle P\rightarrow {\texttt {'('}}\ A\ {\texttt {')'}}}$ 2*( 注記 左に入力 2つの端子によるシフト入力 ${\displaystyle \{{\texttt {*}},{\texttt {(}}\}}$ 3+4)⊣	索引 1 2 3 4 5 6 7 S あ M P 1 D 1 2 * （ 3 + 4 ） 非終端記号が完全に認識されなかったため更新されません
	導出規則 入力シフト ${\displaystyle A\rightarrow M\ {\texttt {'+'}}\ A}$ ${\displaystyle M\rightarrow P\ {\texttt {'*'}}\ M}$ ${\displaystyle P\rightarrow {\texttt {'('}}\ A\ {\texttt {')'}}}$ 2*( 注記 左に入力 入力が導出の最初の要素と一致しません。 未探索の代替案を持つ最初の文法規則に戻る ${\textstyle P\rightarrow {\texttt {'('}}\ A\ {\texttt {')'}}\ /\ {\underline {D}}}$ 3+4)⊣	索引 1 2 3 4 5 6 7 S あ M P 1 D 1 2 * （ 3 + 4 ） 端末が認識されなかったため更新されません
	導出規則 入力シフト ${\displaystyle P\rightarrow D}$ ${\displaystyle D\rightarrow 3}$ 2*( 注記 左に入力 端子3を導出後、入力を1つシフトする しかし、新しい入力は内部では一致しないので、展開が必要になります。 ${\displaystyle M\rightarrow P\ {\texttt {'*'}}\ M}$ ${\displaystyle M\rightarrow P\ {\texttt {'*'}}\ M\ /\ {\underline {P}}}$ 3+4)⊣	索引 1 2 3 4 5 6 7 S あ M P 1 1 D 1 1 2 * （ 3 + 4 ） アップデート： D(4) = 1; P(4) = 1;
	導出規則 入力シフト ${\displaystyle M\rightarrow P}$ 2*(3+ 注記 左に入力 ロールバック ${\displaystyle M\rightarrow P\ {\texttt {'*'}}\ M\ /\ {\underline {P}}}$ メモ化テーブルP(4)≠0にヒットするので、展開は行いません。入力をP(4)だけシフトします。 ${\displaystyle +}$ ${\displaystyle A\rightarrow M\ {\texttt {'+'}}\ A}$ 4)⊣	索引 1 2 3 4 5 6 7 S あ M 1 P 1 1 D 1 1 2 * （ 3 + 4 ） P(4)にヒット Mが認識されたのでM(4) = 1に更新する
	導出規則 入力シフト ${\displaystyle A\rightarrow M\ {\texttt {'+'}}\ A}$ ${\displaystyle M\rightarrow P\ {\texttt {'*'}}\ M}$ ${\displaystyle P\rightarrow {\texttt {'('}}\ A\ {\texttt {')'}}}$ 2*(3+ 注記 左に入力 入力が導出の最初の要素と一致しません。 未探索の代替案を持つ最初の文法規則に戻る ${\textstyle P\rightarrow {\texttt {'('}}\ A\ {\texttt {')'}}\ /\ {\underline {D}}}$ 4)⊣	索引 1 2 3 4 5 6 7 S あ M 1 P 1 1 D 1 1 2 * （ 3 + 4 ） 端末が認識されなかったため更新されません
	導出規則 入力シフト ${\displaystyle P\rightarrow D}$ ${\displaystyle D\rightarrow 4}$ 2*(3+ 注記 左に入力 端子4を導出後、入力を1つシフトする しかし、新しい入力は内部では一致しないので、展開が必要です ${\displaystyle M\rightarrow P\ {\texttt {'*'}}\ M}$ 4)⊣	索引 1 2 3 4 5 6 7 S あ M 1 P 1 1 1 D 1 1 1 2 * （ 3 + 4 ） アップデート： D(6) = 1; P(6) = 1;
	導出規則 入力シフト ${\displaystyle M\rightarrow P}$ 2*(3+ 注記 左に入力 ロールバック ${\displaystyle M\rightarrow P\ {\texttt {'*'}}\ M\ /\ {\underline {P}}}$ そして、メモ化テーブルP(6)≠0にヒットするので、展開せず、入力をP(6)だけシフトします。 しかし、新しい入力は内部では一致しないので、展開が必要です ${\displaystyle +}$ ${\displaystyle A\rightarrow M\ {\texttt {'+'}}\ A}$ 4)⊣	索引 1 2 3 4 5 6 7 S あ M 1 1 P 1 1 1 D 1 1 1 2 * （ 3 + 4 ） P(6)にヒット Mが認識されたのでM(6) = 1に更新する
	導出規則 入力シフト ${\displaystyle A\rightarrow M}$ 2*(3+4) 注記 左に入力 ロールバック ${\displaystyle A\rightarrow M\ {\texttt {'+'}}\ A\ /\ {\underline {M}}}$ メモ化テーブルM(6)≠0にヒットするので展開せず、入力をM(6)だけシフトします。 また、 ${\displaystyle )}$ ${\displaystyle P\rightarrow {\texttt {'('}}\ A\ {\texttt {')'}}}$ ⊣	索引 1 2 3 4 5 6 7 S あ 3 M 1 1 P 1 5 1 1 D 1 1 1 2 * （ 3 + 4 ） M(6)にヒット Aが認識されたため、A(4) = 3を更新します。 Pが認識されたためP(3)=5に更新
	導出規則 入力シフト 2* 注記 左に入力 ターミナルとしてロールバック ${\displaystyle M\rightarrow P\ {\texttt {'*'}}\ M\ /\ {\underline {P}}}$ ${\displaystyle *\neq \dashv }$ (3+4)⊣	索引 1 2 3 4 5 6 7 S あ 3 M 1 1 P 1 5 1 1 D 1 1 1 2 * （ 3 + 4 ） 端末が認識されなかったため更新されません
	導出規則 入力シフト ${\displaystyle M\rightarrow P}$ 2*(3+4) 注記 左に入力 メモ化テーブルP(3)≠0にヒットがあるので展開せず、入力をP(3)だけシフトします。 ⊣	索引 1 2 3 4 5 6 7 S あ 3 M 7 1 1 P 1 5 1 1 D 1 1 1 2 * （ 3 + 4 ） P(3)にヒット Mが認識されたため、M(1)=7に更新する
	導出規則 入力シフト 注記 左に入力 ターミナルとしてロールバック ${\displaystyle A\rightarrow M\ {\texttt {'+'}}\ A\ /\ {\underline {M}}}$ ${\displaystyle +\neq \dashv }$ 2*(3+4)⊣	索引 1 2 3 4 5 6 7 S あ 3 M 7 1 1 P 1 5 1 1 D 1 1 1 2 * （ 3 + 4 ） 端末が認識されなかったため更新されません
	導出規則 入力シフト ${\displaystyle A\rightarrow M}$ 2*(3+4)⊣ 注記 左に入力 メモ化テーブルM(1)≠0にヒットがあるので展開せず、入力をM(1)だけシフトします。 S が完全に削減されたため、入力文字列が認識されました。	索引 1 2 3 4 5 6 7 S 7 あ 7 3 M 7 1 1 P 1 5 1 1 D 1 1 1 2 * （ 3 + 4 ） M(1)にヒット Aが認識されたため、A(1)=7を更新 Sが認識されたためS(1)=7に更新

実装

名前	解析アルゴリズム	出力言語	文法、コード	開発プラットフォーム	ライセンス
オースティンX	パックラット（改造）	ジャワ	別	全て	フリー、BSD
オーロックス	パックラット	C、OCaml、Java	混合	全て	無料、GNU GPL
キャノピー	パックラット	Java、JavaScript、Python、Ruby	別	全て	無料、GNU GPL
CLペグ	パックラット	コモンリスプ	混合	全て	無料、MIT
ちくしょう！	パックラット	D	混合	全て	無料、GNU GPL
フリスビー	パックラット	ハスケル	混合	全て	フリー、BSD
文法::ペグ	パックラット	Tcl	混合	全て	フリー、BSD
アイアンメタ	パックラット	C#	混合	ウィンドウズ	フリー、BSD
PEGパーサー	Packrat（左再帰と文法の曖昧さをサポート）	C++	同一	全て	フリー、BSD
イッカク	パックラット	C	混合	POSIX、Windows	フリー、BSD
ネオトーマ	パックラット	アーラン	別	全て	無料、MIT
Oメタ	Packrat（修正版、部分的なメモ化）	JavaScript、Squeak、Python	混合	全て	無料、MIT
パックCC	Packrat（修正版、左再帰サポート）	C	混合	全て	無料、MIT
パックラット	パックラット	スキーム	混合	全て	無料、MIT
パピー	パックラット	ハスケル	混合	全て	フリー、BSD
パースニップ	パックラット	C++	混合	ウィンドウズ	無料、GNU GPL
PEG.js	Packrat（部分的なメモ化）	JavaScript	混合	全て	無料、MIT
ペギー[11]	Packrat（部分的なメモ化）	JavaScript	混合	全て	無料、MIT
ペガサス	再帰降下、パックラット（選択的）	C#	混合	ウィンドウズ	無料、MIT
プチパーサー	パックラット	Smalltalk、Java、Dart	混合	全て	無料、MIT
PyPy rlib	パックラット	パイソン	混合	全て	無料、MIT
ネズミだ！	パックラット	ジャワ	混合	Java仮想マシン	無料、GNU LGPL
ゴーパックラット	パックラット	行く	同一	全て	無料、GPLv3

参照

• CYKアルゴリズム
• 文脈自由文法
• 解析アルゴリズム
• Earleyパーサー

参考文献

1. Ford, Bryan (2006). 「Packrat Parsing: Simple, Powerful, Lazy, Linear Time」. arXiv : cs/0603077 .
2. 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。
3. Flodin, Daniel. 「実世界の文法と入力に対するPackrat解析と従来のShift-Reduce解析の比較」(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。
5. 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版）. ボストン・ミュンヘン: Pearson Addison-Wesley. ISBN 978-0-321-48681-3。
7. Norvig, Peter (1991-03-01). 「自動メモ化技術と文脈自由構文解析への応用」.計算言語学. 17 (1): 91–98 . ISSN  0891-2017.
8. Dubroy, Patrick; Warth, Alessandro (2017-10-23). 「インクリメンタル・パックラット・パーシング」.第10回ACM SIGPLAN国際ソフトウェア言語工学会議論文集. SLE 2017. ニューヨーク州ニューヨーク: Association for Computing Machinery. pp.  14– 25. doi :10.1145/3136014.3136022. ISBN 978-1-4503-5525-4. S2CID  13047585。
9. Science、International Journal of Scientific Research、Ijsrset、Engineering and Technology。「Packrat Parserの調査」。Packrat Parserの調査。
10. 水島 幸太; 前田 篤志; 山口 佳則 (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のフォークをメンテナンス

外部リンク

• Packrat Parsing: シンプル、強力、遅延、線形時間
• 構文解析表現文法：認識に基づく統語的基礎

Retrieved from "https://en.wikipedia.org/w/index.php?title=Packrat_parser&oldid=1322440778"