class.md

classDiagram

Parser --> LrMemoTable: memos
Parser --> Thunk: thunks[]
LrMemoTable --> LrMemo: memos[pos][rule_name]
LrMemo --> ThunkChunk: answer

Thunk <|-- ThunkNode
Thunk <|-- ThunkLeaf
ThunkChunk --> Thunk: thunks[]
ThunkNode --> Thunk: thunks[]
ThunkChunk --> Capture: capts[i]
ThunkChunk --> Value: values[i]
ThunkNode --> Value: values[index]
ThunkLeaf --> Capture: capt0
ThunkLeaf --> Value: value_refs[i]

class Parser {
  - LrMemoTable memos
  - Thunk[] thunks
}

class LrMemoTable {
  - Hash[Integer, Hash[String, LrMemo]] memos
}

class LrMemo {
  - ThunkChunk answer
  - Integer offset
  - Bool grow
  - Bool fail
}

class ThunkChunk {
  - Array[Thunk] thunks
  - Hash[Integer, Capture] capts
  - Hash[Integer, Value] values
}

class Thunk
class ThunkLeaf {
  - Capture: capt0
  - Hash[Integer, Value] value_refs
  - String action
}
class ThunkNode {
  - Array[Thunk] thunks
  - Hash[Integer, Value] values
  - Integer index
}

class Capture
class Value

Loading

gistfile1.md

概要

PackCR が生成するパーサーの動作を日本語で書き下してみます。 用語はよく知らないので適当です。

アルゴリズムは「日本ソフトウェア科学会第 38 回大会 (2021 年度) 講演論文集」の「複数箇所で発生する多head左再帰を扱えるpackrat parser（梅田 理生、前田 敦司、齋藤 俊哉）」のものを使わせていただいています。 ref: http://jssst.or.jp/files/user/taikai/2021/papers/48-L.pdf

packcr_parse

packcr_parse() では、入力に対してルール群の先頭を適用してみて、マッチしたら各アクションを実行し、マッチしなかったらエラーにします。 この「ルールを適用してみる」部分を司るのが packcr_apply_rule() です。 この先頭ルールを適用してマッチするかどうか判定する一連の操作を仮に「パース」または「パーシング」と呼ぶことにします。 文法やパーサーの種類によって、入力に対して一度だけパースすることも、失敗するか入力が枯渇するまで繰り返しパースすることもありえます。

パース操作ではコンテキストが保持されます。 コンテキストにはさまざまな情報が含まれています。 ctx->buffer_start_position には、「入力内の、バッファ開始位置」すなわち「過去の入力分のうち、パースが完了してバッファから捨てられた文字数」が入っています。 ctx-position_offset には、「バッファ内の現在の位置」が入っています。 ctx->buf はバッファです。ここに入力文字列が入ります。また、パースが完了した後はバッファの内容は破棄され、次回のパースでは新しい状態から始まります。

アクションを実行するとき、マッチした入力の文字列表現や、別のアクションの実行結果の値を情報として受け渡します。 「どのアクションに対して」「どの情報を受け渡すか」を記録したものを Thunk と呼びます。 「アクションの実行結果」を仮に Value と呼びます。

Thunk とは

Thunk は PEG やパーサーに限った用語ではなく、一般に遅延実行に対して用いられるコンピューター用語です。クサビなどを刺した「ズン」という擬音語らしいです。 PackCR やその元となった PackCC では、Thunk の一次元配列を ThunkChunk、Thunk の木構造を ThunkNode と ThunkLeaf で表します。 ルールのマッチ結果は、成功であれば ThunkChunk で、失敗であれば NULL (Ruby では nil) で表現されます。

packcr_apply_rule（limits が NULL のとき）

packcr_apply_rule() は引数として、以下のものを受け取ります。

• パースのコンテキスト ctx
• 判定するルール rule
• 判定で取得した Thunk を記録する Thunk 配列 thunks
• 新しい Thunk に記録するための Value への参照 value
• offset（後述）
• limits（後述）

packcr_apply_rule() では、引数 limits が NULL かどうかで分岐します。最初の呼び出しでは limits に NULL を渡すので、まずそのケースから説明します。

limits が NULL のとき、入力が引数 rule で表されるルールにマッチするかを判定します。 判定はルール自体を評価するのではなく、packcr_get_rule_thunk_chunk() を介してなされます。 packcr_get_rule_thunk_chunk() による判定を仮に「ルールに対応する ThunkChunk の取得」と呼ぶことで、「ルールの評価」と区別することにします。 マッチした場合には value と結果の ThunkChunk から ThunkNode を作成し、thunks に対して追加します。

packcr_get_rule_thunk_chunk

packcr_get_rule_thunk_chunk() は引数として、以下のものを受け取ります。

• パースのコンテキスト ctx
• 判定するルール rule

packcr_get_rule_thunk_chunk() では、現在の位置の rule に対応するメモの値によって分岐します。

メモ

メモにはいくつかの状態があります。

• 存在しない
• 「保留」状態（初期状態）
• 「成功」状態
• 「失敗」状態
• 「成功 grow」状態
• 「失敗 grow」状態

grow は再帰のために用いられる概念です。 メモが新規作成された場合、「保留」状態で作成されます。

graph LR
  a-->b
  b-->c

Loading

graph TB
  none-->fail
  fail-->match
  fail-->nomatch
  match-->nomatch
  nomatch-->match
  fail-->grow_nomatch
  grow_nomatch-->grow_match
  grow_match-->grow_nomatch
  grow_nomatch-->nomatch
  grow_match-->match
  none["存在しない"]
  fail["保留"]
  match["成功"]
  nomatch["失敗"]
  grow_match["成功 grow"]
  grow_nomatch["失敗 grow"]

Loading

メモがまだ存在しない場合

1. メモを「保留」状態で新規に作成し、現在の位置の rule に対応するメモとして記録します。
2. 次に limits なしで現在地に対してルールを評価し、成功（ThunkChunk）または失敗（NULL）を取得します。
3. 成功か失敗かに関わらず、評価結果をメモに記録します。

• このとき、メモの「保留」状態は取り消され、「記録済み」状態になります。
• 評価が終わった後の現在地もメモに記録します。つまり、「マッチ開始地点」のルールには「マッチ終了地点」が記録されていることになります。

1. メモが grow 状態であれば、packcr_grow_lr() を呼び出して grow 操作を行います。
2. TODO

メモが「保留」状態の場合

TODO