wanabe/class.md

## class.md

      
    Raw
  

              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

      
    Raw
  

              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

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


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


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


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

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

TODO