日本ソフトウェア科学会第 38 回大会 (2021 年度) 講演論文集

複数箇所で発生する多 head 左再帰を扱える packrat

parser
梅田 理生

前田 敦司

齋藤 俊哉

再帰下降構文解析法で左再帰を含む文法を解析しようとすると，入力文字列を消費せずに同じ解析処理関数を無限に再帰呼び出しするため，解析が終了しないという問題がある．再帰下降構文解析手法の一つに packrat parsing がある．packrat parsing は PEG (Parsing Expression Grammar) で記述した文法をバックトラックを用いながら解析し，解析結果をメモ化することで解析時間を線形に抑えるアルゴリズムである．先行するいくつかの研究ではpackrat parser における左再帰呼び出しの問題を解決するために，メモ化表に手を加え，再帰呼び出しを許す深さに上限を設け，その上限を大きくしながら繰り返し同じ関数を呼び出して，解析範囲を広げていく手法が提案されている．
しかしこれら従来の手法では，いくつかの問題があり，解析が失敗する場合やプログラムがクラッシュする場合がある．筆者らは以前にこれらの問題を解消した手法を提案しており，本論文ではこの手法に対して形式的に意味論を定義し，その性質や他の PEG パーサの意味論との関連について述べている．

数の解析結果が生じる曖昧さが存在するが，PEG は

1 序論

順序付き選択を採用しており，選択による曖昧さは存

1. 1 研究背景

在しない．また，無制限の先読みができるため CFG

1. 1. 1 Parsing Expression Grammar (PEG)

では扱うことのできない範囲の文法を記述すること

Parsing Expression Grammar (PEG) [2] は Con-ができるとされている．

text Free Grammar（CFG，文脈自由文法）や正則表現（Regular Expression）と並ぶ形式文法のひとつ

PEG は解析表現 e と非終端記号 N を用いて次のように表される．

であり，形式言語をトップダウンに解析する手順を表<N> ← e

した規則群を記述するために使用される．CFG は選また，解析表現 e は空文字列を表す ε，終端記号の集択の解析に優先順位がないため同一の文に対して複合 T と非終端記号の集合 N T の要素に次の規則を適用して再帰的に定義される．

Packrat parsers can support multi-head left recursion
at multiple positions
Masaki Umeda, 筑 波 大 学 理 工 情 報 生 命 学 術 院 シ
ス テ ム 情 報 工 学 研 究 群 情 報 理 工 学 位 プ ロ グ ラ ム,
Graduate School of Science and Technology Degree
Programs in Systems and Information Engineering
Master’s Program in Computer Science, Universityof Tsukuba .
Atusi Maeda, 筑波大学 システム情報系 情報工学域,
Department of Information Engineering, Faculty ofEngineering, Information and Systems, Universityof Tsukuba .
Toshiya Saitou, 筑波大学 情報学群 情報科学類, College of Information Science, School of Infomatics,
University of Tsukuba.

• 空文字列 ε は解析表現である．
• 終端記号 t(t ∈ T ) は解析表現である．
• 任意の終端記号を表す · は解析表現である．
• 非終端記号 <N>(N ∈ N T ) は解析表現である．
• 解析表現 e1 , e2 を連結したもの e1 e2 は解析表現である．

• 解析表現 e1 , e2 を順序付きで選択するもの e1 /e2は解析表現である．

• 解析表現 e を 0 回以上繰り返すもの e∗ は解析表
現である．

• 解析表現 e を 1 回以上繰り返すもの e+ は解析

算した結果は同じ結果になることを利用し，引数と結表現である．

• 解析表現 e を肯定的先読みするもの &e は解析

果の組み合わせを記録して，同様の計算を再度行う場
合はその記録を利用するというものである．再帰下降表現である．

• 解析表現 e を否定的先読みするもの !e は解析表

構文解析の場合は，各規則と入力中の解析位置を引数とみなし，同じ規則と解析位置による再度の解析は記現である．

• 解析表現 e の任意の一致を表すもの e? は解析表

録した解析結果を利用している．
このメモ化によって最悪時間計算量を線形に抑え現である．
本論文では終端記号の列 str を str と表し，文法たものが Packrat Parsing [1] である．また，Packrat

定義に使用する非終端記号 NT を <NT> と表す．PEG

Parsing を実装した構文解析器を Packrat Parser とで記述された文脈自由でない文法の例は次のとおり

呼ぶ．

1. 1. 3 PEG による左再帰の記述

である．

<S>

←

&(<A>!b)a + <B>! ·<A>←

a<A>?b解析する際に，入力文字列とある非終端記号とのマッ<B>←

b<B>?cチを試みる過程で入力文字列を消費することなく同PEG によって記述された文法による入力文字列をじ非終端記号とのマッチが再び行われることを左再帰
この文法は任意の同じ長さ n の a，b および c の列をといい，左再帰が発生する可能性のある規則を左再帰

この順に連結した文字列 {a b c , n ≥ 1} にマッチ的な規則という．また，左再帰的な規則を含む文法をする．つまり，aaabbbccc にはマッチするが，abbcc

左再帰的な文法という．

n n nにはマッチしない．

左再帰が発生する際に，2 度の非終端記号とのマッ

上記の規則のうち 0 回または 1 回以上の繰り返し

チの間に他の非終端記号とのマッチを含む場合を特にと肯定的先読み，任意の一致の解析表現は構文糖であ

間接左再帰という．他の非終端記号とのマッチを含まるとされ，それぞれ次に定義される非終端記号 N でない場合は直接左再帰という．

書き換えることが可能である．

各非終端記号をノードとし，ある非終端記号から，

e の 0 回以上の繰り返し e∗

その非終端記号のマッチを試みる際に入力文字列を<N> ← e<N>/εe の 1 回以上の繰り返し e+<N> ← e<N>/ee の肯定的先読み &e

消費せずにマッチを試みる可能性のある非終端記号
を有向辺で結んだグラフを非消費グラフ (仮) という．
この非消費グラフにおける閉路を左再帰サイクルと呼ぶ．

<N> ←!!ee の任意の一致 e?

1. 1. 3. 1 head ルールと involved ルール
入力文字列の解析時に左再帰サイクルを構成する<N> ← e/ε

非終端記号のうち，最初にマッチを試みた非終端記号

1. 1. 2 Packrat Parsingに対応する規則を head ルール (規則)，それ以外の規PEG によって記述された文法による言語の解析は則を involved ルール (規則) と呼ぶ．

バックトラックが可能な再帰下降構文解析によって行

1. 1. 3. 2 多 head 左再帰

うことができる．しかし，バックトラックをすると同ある文法の非消費グラフの複数の左再帰サイクル

一の入力と規則の組み合わせに対して再度の解析をのノードが共通している場合，その文法は多 head 左

行なってしまうことがあるため，最悪時間計算量が指再帰的であるという．

数オーダーとなり現実的ではない．この問題を解決するためにメモ化という技術を用いる．
メモ化とは，関数で計算を行う場合，同じ引数で計

1. 1. 4 先行研究による左再帰の解析
通常の Packrat Parser では左再帰的な文法による解析を行うと，入力文字列を消費しないまま同じ規則群による解析処理を繰り返すため，解析が終了し似点を挙げ，今後の課題や展望について述べている．

ないという問題がある．この問題に対して，Packrat

Parser のメモ化表を利用した解析手法が先行する研2 Packrat Parser

究により提案されている．これらの手法に共通する手

本章では本研究で使用する Packrat Parser の構造

順は次のとおりである：と動作について説明する．なお本研究における構文解

1. 左再帰サイクル内の規則による解析を開始する

析器は PEG で記述された文法と文字列を入力とし，直前にメモ化表のエントリに失敗を意味する情報与えられた文字列の全部分が文法に一致するか否かを記録し，解析を行う．これにより，左再帰的なを判別するレコグナイザに限り，構文木の構築などは規則で解析することを前提とした文字列が入力行わないものとする．

されれば，最小の解析結果であるシードが得られる．このとき，入力文字列が該当の規則で解析す

2. 1 Packrat Parser の構造

ることを前提としない文字列の場合は，左再帰的本研究で用いる基本的な Packrat Parser は eval 関

でない規則の場合と同様に失敗を意味する解析

数と applyRule 関数によって定義され，2 つの関数結果が得られる．この解析結果が失敗であればこが相互に呼び出されることで解析を行う．解析の結果の規則による解析は失敗として結果が返される．

は Ast 型で表され，これは Match, MisMatch の

2. 解析前に記録したメモ化表の値を得られた解析結果で上書きし，再度同じ規則による解析を実行
する．

3. 2 の解析が成功し，かつその解析結果がメモ化

2 つの値をとる．
また，これらの関数の他にグローバル変数として次の変数が定義されている．

POS: 入力文字列の現在の解析位置を示す．Po-

表に記録されている解析位置よりも先に進んだ

sition 型．0 で初期化される．

ものであれば 2 を繰り返す．

MEMO: Position と文法内で定義されている非4. メモ化表から最長の解析結果を取得し，この規則による解析の結果として返す．

終端記号を軸にとった表であり，解析結果である

Ast 型の ans と次の解析開始位置を示す Position

先行する手法にはそれぞれ次のような問題がある．

型の pos next の組を格納する．解析結果は全て• Warth らの提案手法 [5] では多 head 左再帰を含

Null で初期化される．

む文法による解析を行うと，プログラムが異常終2. 1. 1 eval 関数

了する場合がある．

eval 関数は解析表現を引数にとる関数である．与• 後藤らの提案手法 [6] では多 head 左再帰を含むえられた解析表現を適切に分解し，入力文字列の解析

一部の文法による解析を行うことができるが，入を試みる．分解した各要素が終端記号列であれば入力

力文字列の複数箇所で左再帰的な規則による解文字との一致を確認し，非終端記号であればその記号析が発生するような文法と入力文字列では解析に対して applyRule 関数を適用する．

結果が意図したものと異なる場合がある．

eval 関数の擬似コードを図 1 に示す．与えられる

1. 1. 5 論文の構成

解析表現は糖衣を剥がし，代替表現によって置き換え

第 2 章では基本的な構造の Packrat Parser や筆者られているものと仮定する．

らが以前に提案した多 head 左再帰を扱える Packrat

Parser について疑似コードを用いて説明する．続く

本研究の実装では順序付き選択，連結ともに，左から右に深さ優先で解析処理を行なっている．

第 3 章では多 head 左再帰を扱える Packrat Parser

2. 1. 2 applyRule 関数

に対する意味論を疑似コードに即した形で定義していapplyRule 関数は非終端記号と Position を引数にる．最後の第 4 章では今回定義した意味論についてとる関数である．与えられた非終端記号に対して定義関数同士の類似点や他に提案されている意味論との類されている解析表現を用いて入力文字列の解析を行

1Ast eval ( 解析表現 e){2

p = POS3

if (e が空文字列 ε)4return Match5

if (e が終端記号列 str ){6if ( 入力文字列の POS から始まる部分列の先頭が str ){78

POS = POS + (str の長さ)

9return Matchif ( MEMO (N , p ) == Null){3

exp = getRuleDef (N )4ans = eval ( exp )5

MEMO (N , p ) = { ans , POS }return ans

6} else {7

POS = MEMO (N , p ). pos_next

8

return MEMO (N , p ). ans}

10

return MisMatch11

Ast applyRule ( 非終端記号 N , p ){2

9} else

10

1

11

}

}

12
13

if (e が否定的先読み !ein ){14

図2

applyRule 関数

if ( eval (ein ) == Match){

15

POS = p16

return MisMatch17} else18}

20

Grow 関数の 4 つの関数を新たに加える．Ast 型を拡

21

if (e が非終端記号 N )22return applyRule (N , POS )23

本の構成に使用される eval 関数を使用し，applyRule
関数と growLR 関数，evalGrow 関数，applyRule-

return Match

19

張し，Match，MisMatch に加えて Fail の 3 つの値をとる．ここで Fail は左再帰の検出に関連する場

24
25

if (e が順序つき選択 e1 /e2 ){26

if ( eval (e1 ) == Match)
else

28

return eval (e2 )29に記録する内容は ans と pos next に加え，左再帰呼び出しが発生していることを上の呼び出しに伝える}

30

面では特別な値としての意味を持つが，それ以外では MisMatch と同様の意味を持つ．また，MEMO

return Match

27

31bool 型の grow とする．

if (e が連結 e1 e2 ){32

if ( eval (e1 ) == Match){

33

applyRule 関数を新たに定義する．この関数は基35POS = p36

return MisMatch} else37} else39

return MisMatch

40

}

41

本の Packrat Parser の applyRule 関数の動作に加えて，メモ化表を用いた左再帰発生の検知とそれに対す

return Match

38

42

2. 2. 1 applyRule 関数

if ( eval (e2 ) == MisMatch){34

る対応を行う．
新たな applyRule 関数の疑似コードを図 3 に示す．

}

2. 2. 2 growLR 関数
図1eval 関数

新たな applyRule 関数から呼び出される growLR関数を定義する．この関数は左再帰が検出された場

う．また，メモ表 MEMO を管理し，以前に解析を行合，決定された最小の解析結果であるシードをもとなっている場合はその記録を活用する．

に，再帰ではなく繰り返しによる解析を行う．繰り返

applyRule 関数の擬似コードを図 2 に示す．補助関しによる解析は 1 度の解析の結果が失敗するか，解数として，getRuleDef 関数を導入する．これは非終析位置がメモ化表に記録されているものより進まな

端記号 N を引数に取り，その非終端記号 N に対してくなるまで行われる．

定義されている解析表現 e を返す．

growLR 関数の疑似コードを図 4 に示す．
2. 2. 3 evalGrow 関数

2. 2 多 head 左再帰対応の Packrat Parser

evalGrow 関数を定義する．この関数は growLR 関

多 head 左再帰的な文法による解析が可能な Packrat

数から繰り返し呼ばれ，1 度の呼び出しで再帰の深さ

Parser [3] について説明する．本 Packrat Parser は基を制限した解析を行う．後述する applyRuleGrow 関

1

Ast applyRule ( 非終端記号 N , p ){2

if ( MEMO (N , p ) == Null){

3

MEMO (N , p ) = {Fail, p , False}

4m = MEMO (N , p )5

exp = getRuleDef (N )6ans = eval ( exp )7

m . ans = ans

8m . pos_next = POS

9

if ( m . grow == True){

10

growLR (N , p )11m . grow = False

12

ans = m . ans

13

POS = m . pos_next

14

}

15

return ans

if (e が空文字列 ε)3return Match

4

POS = POS + (str の長さ)

7return Match8} else9

return MisMatch

10

}

11
12

if (e が否定的先読み !ein ){13

if ( evalGrow (ein , p , limits ) == Match){return MisMatch

16

18

MEMO (N , p ). grow = True

18

19

return MEMO (N , p ). ans} else {POS = p15

17

} elsereturn Match
}

19
20

21

m = MEMO (N , p )22

POS = m . pos_next

23

return m . ans

25

if ( 入力文字列の POS から始まる部分列の先頭が str ){6

MEMO (N , p ). ans = MisMatch}24

if (e が終端記号列 str ){

5

17

20

Ast evalGrow ( 解析表現 e, p , limits ){2

14} else if ( MEMO (N , p ). ans == Fail){

16

1

21

if (e が非終端記号 N ){22

if ( POS == p && N
else

24

}

return applyRule (N , POS )

25

}

26

図3

提案手法の applyRule 関数

27

if (e が順序つき選択 e1 /e2 ){28

if ( evalGrow (e1 , p , limits ) == Match)29

return Match30
1void growLR (N , p ){while (True){

2

33

4

POS = p34

5exp = getRuleDef (N )35

6ans = evalGrow ( exp , p , {N })367if ( ans != Match || POS <= old_pos )37

MEMO (N , p ). ans = ans

39

10

MEMO (N , p ). pos_next = POS

40

12

}
if (e が連結 e1 e2 ){if ( evalGrow (e1 , p , limits ) == Match){if ( evalGrow (e2 , p , limits ) == MisMatch){
POS = p

38

9

}

11

return evalGrow (e2 , p , limits )32

old_pos = POS

break

else

31

3

8

return MisMatch} elsereturn Match41}} else42

return MisMatch

43

}

44

図4

提案手法の growLR 関数

数と相互に呼び出し合い，eval 関数・applyRule 関数

̸∈ limits )return applyRuleGrow (N , POS , limits )

23

45

}

図5

提案手法の evalGrow 関数と同じように解析を行う．

eval 関数と異なる点は，現在解析を行なってい関数を呼び出す．左再帰的規則による解析を開始した

る入力文字列の位置に応じて applyRule 関数と ap-

入力文字列の位置は引数によって呼び出し先に伝播さplyRuleGrow 関数の呼び出しを切り替える点である．

れる．この関数は eval 関数と同様に再帰による解析

現在の解析位置が左再帰的規則による解析を始めた位を行うものの，引数の limits によって再帰の深さを制置と同じであれば，左再帰的規則による解析を行うべ

限しているため，無限に再帰呼び出しすることによっきだと判断し，applyRuleGrow 関数を呼び出して再て解析が終了しなくなるということは発生しない．

帰による解析を行う．解析位置が異なる場合は，左再evalGrow 関数の疑似コードを図 5 に示す．

帰的規則による解析は必要ないとみなして applyRule3. 2 applyRule 関数
1

Ast applyRuleGrow ( 非終端記号 N , p , limits ){2limits . add (N )3

exp = getRuleDef (N )applyRule4

ans = evalGrow ( exp , p , limits )5

if ( ans != Match || POS <= MEMO (N, p ). pos_next ){ans = MEMO (N , p ). ans

6

POS = MEMO (N , p ). pos_next

7

力文字列，M, M ′ はメモ化表，smatch はマッチ文字列，ssuff ix は接尾部である．
applyRule

MEMO (N , p ). ans = ans

9

MEMO (N , p ). pos_next = POS

10

3. 3 growLR 関数

11

}

12

return ans

13とする．ここでそれぞれ N T は非終端記号，s は入この関係 −−−−−−→ の定義を図 8 に示す．

} else {8

applyRule 関数に対応する関係をapplyRule(N T, s, M ) −−−−−−→ (smatch , ssuff ix , M ′ )growLR 関数に対応する関係を}(N T, s, M ) −−−−−→ (smatch , ssuff ix , M ′ )growLR

図6

提案手法の applyRuleGrow 関数とする．ここでそれぞれ N T は非終端記号，s は入力文字列，M, M ′ はメモ化表，smatch はマッチ文字

2. 2. 4 applyRuleGrow 関数
applyRuleGrow 関数を定義する．この関数は eval-列，ssuff ix は接尾部である．
growLR

この関係 −−−−−→ の定義を図 9 に示す．

Grow 関数と相互に呼び出し合うことで再帰による解析を行う．上述のように evalGrow 関数とこの関数の3. 4 evalGrow 関数

関係は eval 関数と applyRule 関数の関係と非常に似evalGrow 関数に対応する関係をている．

(e, s, sLR , M, L) −−−−−−→ (smatch , ssuff ix , M ′ , L′ )evalGrow

applyRuleGrow 関数の疑似コードを図 6 に示す．

とする．ここでそれぞれ e は解析表現，s は入力文
字列，sLR は左再帰開始文字列，M, M ′ はメモ化表，

3 提案手法の意味論

L, L′ は limit 集合，smatch はマッチ文字列，ssuff ix

本章では 2. 2 で説明した多 head 左再帰的文法に対は接尾部である．

応した Packrat Parser の疑似コードに対応する意味

evalGrow

この関係 −−−−−−→ の定義を図 10, 11 に示す．

論を定義する．意味論は各関数に対応した関係を定義し，その関係を用いて定義される．
各関数に対して，(関数への入力, 関数からの出力) ∈ 関数名という関係をそれぞれ定義し，この関係を
関数名(関数への入力) −−−→ (関数からの出力)と表記する．

3. 5 applyRuleGrow 関数
applyRuleGrow 関数に対応する関係をapplyRuleGrow(e, s, sLR , M, L) −−−−−−−−−−→(smatch , ssuff ix , M ′ , L′ )とする．ここでそれぞれ e は解析表現，s は入力文
字列，sLR は左再帰開始文字列，M, M ′ はメモ化表，L, L′ は limit 集合，smatch はマッチ文字列，ssuff ix
は接尾部である．

3. 1 eval 関数

applyRuleGrow

eval 関数に対応する関係を(e, s, M ) −−→ (smatch , ssuff ix , M ′ )この関係 −−−−−−−−−−→ の定義を図 12 に示す．

eval

4 結論

とする．ここでそれぞれ e は解析表現，s は入力文
字列，M, M ′ はメモ化表，smatch はマッチ文字列，

ssuff ix は接尾部である．
eval

この関係 −−→ の定義を図 7 に示す．

本論文では筆者らが以前に提案した多 head 左再帰を扱える Packrat Parser [3] に対する意味論を形式的に定義した．この定義では eval 関数と evalGrow 関
数や，applyRuleGrow 関数と growLR 関数は類似し

eval(ε, x, M ) −−→ (ε, x, M )[空文字列]eval(a, ax, M ) −−→ (a, x, M )eval(a, bx, M ) −−→ (MisMatch, bx, M )where a ̸= b

[終端記号 (失敗 1)][終端記号 (失敗 2)]

eval(a, ε, M ) −−→ (MisMatch, ε, M )(e1 , x1 x2 y, M0 ) −−→ (x′1 , x2 y, M1 )[終端記号 (成功)](e1 , x2 y, M1 ) −−→ (x′2 , y, M2 )

eval

eval

[連接 (成功)](e1 e2 , x1 x2 y, M0 ) −−→ (x′1 x′2 , y, M2 )
eval

eval

(e1 , x, M0 ) −−→ (MisMatch, x, M1 )

[連接 (失敗 1)]eval(e1 e2 , x, M0 ) −−→ (MisMatch, x, M1 )(e1 , xy, M0 ) −−→ (x′ , y, M1 )
eval

eval

(e2 , y, M1 ) −−→ (MisMatch, y, M2 )eval

(e1 e2 , xy, M0 ) −−→ (MisMatch, xy, M2 )(e1 , xy, M0 ) −−→ (x′ , y, M1 )

[連接 (失敗 2)]

eval(e1 /e2 , xy, M0 ) −−→ (x′ , y, M1 )
eval

eval

(e1 , xy, M0 ) −−→ (MisMatch, xy, M1 )[選択 1](e2 , xy, M1 ) −−→ (x′ , y, M2 )eval

(e1 /e2 , xy, M0 ) −−→ (x′ , y, M2 )
eval

eval

(e1 , x, M0 ) −−→ (MisMatch, x, M1 )[選択 2]eval(e2 , x, M1 ) −−→ (MisMatch, x, M2 )eval

(e1 /e2 , x, M0 ) −−→ (MisMatch, x, M2 )(e, xy, M0 ) −−→ (x′ , y, M1 )

[選択 (失敗)]

eval

eval

(!e, xy, M0 ) −−→ (MisMatch, xy, M1 )[否定的先読み 1]

eval(e, x, M0 ) −−→ (MisMatch, x, M1 )eval(!e, x, M0 ) −−→ (ε, x, M1 )[否定的先読み 2]

applyRule(A, xy, M0 ) −−−−−−→ (x′ , y, M1 )(A, xy, M0 ) −−→ (A[x′ ], y, M1 )eval

[非終端記号 (成功)]

applyRule(A, x, M0 ) −−−−−−→ (MisMatch, x, M1 )eval(A, x, M0 ) −−→ (MisMatch, x, M1 )図7

[非終端記号 (失敗)]eval

関係 −−−→ の定義ており，規則をまとめて共通化することが可能である化によって動作を効率化したプログラムの意味論と捉と予想している．また，この意味論は Medeiros らがえることも可能である．今後の課題として，類似した示した PEG パーサによる左再帰の意味論 [4] をメモ

規則の共通化による意味論の簡略化や Medeiros らのM (A, x) = (y, z, g)
applyRule(A, x, M ) −−−−−−→ (y, z, M )where y ̸= Fail[再訪]

M (A, x) = (Fail, x, g)
applyRule(A, x, M ) −−−−−−→ (MisMatch, x, M [(A, x) 7→ (MisMatch, x, True)])[検出](A, xyz) ∈/ M0(R(A), xyz, M0 [(A, xy) 7→ (Fail, xy, False)]) −−→ (x′ , yz, M1 )M1 (A, xyz) = (MisMatch, xyz, True)(A, xyz, M1 [(A, xyz) 7→ (x′ , yz, False)]) −−−−−→ (x′ y ′ , z, M2 )evalgrowLR

applyRule(A, xyz, M0 ) −−−−−−→ (x′ y ′ , z, M2 [(A, xyz) 7→ (x′ y ′ , z, False)])(A, xy) ∈/ M0(R(A), xy, M0 [(A, xy) 7→ (Fail, xy, False)]) −−→ (x′ , y, M1 )evalapplyRule(A, xy, M0 ) −−−−−−→ (x′ , y, M1 [(A, xy) 7→ (x′ , y, False)])(A, x) ∈/ M0[左再帰発生][左再帰なし]eval(R(A), x, M0 [(A, x) 7→ (Fail, x, False)]) −−→ (MisMatch, x, M1 )applyRule(A, x, M0 ) −−−−−−→ (MisMatch, x, M1 )

図8

[失敗]

applyRule

関係 −−−−−−−−→ の定義

evalGrow(R(A), xy, xy, M0 , {A}) −−−−−−→ (MisMatch, xy, M1 , L1 )

M1 (A, xy) = (x′ , y, g)

growLR(A, xy, M0 ) −−−−−→ (x′ , y, M1 )(R(A), xyz, xyz, M0 , {A}) −−−−−−→ (x′ , yz, M1 , L1 )evalGrow

M1 (A, xyz) = ((xy)′ , z, g)

growLR(A, xyz, M0 ) −−−−−→ ((xy)′ , z, M1 )(R(A), xyz, xyz, M0 , {A}) −−−−−−→ (x′ , yz, M1 , L1 )evalGrow[停止 1][停止 2]

growLR(A, xyz, M1 [(A, xyz) 7→ (x′ , yz, g)]) −−−−−→ ((xy)′ , z, M2 )growLR(A, xyz, M0 ) −−−−−→ ((xy)′ , z, M2 )図9growLR

関係 −−−−−−→ の定義

意味論との等価性の証明などが挙げられる．

参 考 文 献[1] Ford, B.: Packrat parsing: simple, powerful, lazy,linear time, functional pearl, ACM SIGPLAN Notices, Vol. 37, No. 9(2002), pp. 36–47.
[2] Ford, B.: Parsing expression grammars: arecognition-based syntactic foundation, Proceedingsof the 31st ACM SIGPLAN-SIGACT symposiumon Principles of programming languages, 2004,
pp. 111–122.
[3] Masaki, U. and Atusi, M.: Packrat Parsers
Can Support Multiple Left-recursive Calls at theSame Position, Journal of Information Processing,Vol. 29(2021), pp. 174–187.
[4] Medeiros, S., Mascarenhas, F., and Ierusalimschy,
R.: Left recursion in parsing expression grammars,
Science of Computer Programming, Vol. 96(2014),
pp. 177–190.
[5] Warth, A., Douglass, J. R., and Millstein, T.:
Packrat parsers can support left recursion, Proceedings of the 2008 ACM SIGPLAN symposium
on Partial evaluation and semantics-based program
manipulation, 2008, pp. 103–110.
[6] 後藤勇太, 白田佳章, 木山真人, 芦原評, ほか: 更新検知を用いて左再帰に対応する Packrat Parser の実装,
情報処理学会論文誌プログラミング (PRO), Vol. 4,
No. 3(2011), pp. 84–93.

[継続]evalGrow(ε, x, y, M, L) −−−−−−→ (ε, x, M, L)
evalGrow(a, ax, y, M, L) −−−−−−→ (a, x, M, L)
evalGrow(a, bx, y, M, L) −−−−−−→ (MisMatch, bx, M, L)[終端記号 (成功)]

where a ̸= bevalGrow(a, ε, y, M, L) −−−−−−→ (MisMatch, ε, M, L)(e1 , x1 x2 y, z, M0 , L0 ) −−−−−−→ (x′1 , x2 y, M1 , L1 )[空文字列][終端記号 (失敗 1)][終端記号 (失敗 2)](e2 , x2 y, z, M1 , L1 ) −−−−−−→ (x′2 , y, M2 , L2 )evalGrow

evalGrow(e1 e2 , x1 x2 y, z, M0 , L0 ) −−−−−−→ (x′1 x′2 , y, M2 , L2 )evalGrow[連接 (成功)]

evalGrow(e1 , x, y, M0 , L0 ) −−−−−−→ (MisMatch, x, M1 , L1 )

[連接 (失敗 1)]

evalGrow(e1 e2 , x, y, M0 , L0 ) −−−−−−→ (MisMatch, x, M1 , L1 )(e1 , xy, z, M0 , L0 ) −−−−−−→ (x′ , y, M1 , L1 )evalGrow

evalGrow(e2 , y, z, M1 , L1 ) −−−−−−→ (MisMatch, y, M2 , L2 )evalGrow(e1 e2 , xy, z, M0 , L0 ) −−−−−−→ (MisMatch, xy, M2 , L2 )(e1 , xy, z, M0 , L0 ) −−−−−−→ (x′ , y, M1 , L1 )

[連接 (失敗 2)]

evalGrow[選択 1](e1 /e2 , xy, z, M0 , L0 ) −−−−−−→ (x′ , y, M1 , L1 )evalGrow(e2 , xy, z, M1 , L1 ) −−−−−−→ (x′ , y, M2 , L2 )evalGrow

evalGrow(e1 , xy, z, M0 , L0 ) −−−−−−→ (MisMatch, xy, M1 , L1 )(e1 /e2 , xy, z, M0 , L0 ) −−−−−−→ (x′ , y, M2 , L2 )evalGrow

evalGrow

evalGrow(e1 , x, z, M0 , L0 ) −−−−−−→ (MisMatch, x, M1 , L1 )(e2 , x, z, M1 , L1 ) −−−−−−→ (MisMatch, x, M2 , L2 )evalGrow(e1 /e2 , x, z, M0 , L0 ) −−−−−−→ (MisMatch, x, M2 , L2 )(e, xy, z, M0 , L0 ) −−−−−−→ (x′ , y, M1 , L1 )evalGrow

evalGrow(!e, xy, z, M0 , L0 ) −−−−−−→ (MisMatch, xy, M1 , L1 )[否定的先読み 1]

evalGrow(e, x, z, M0 , L0 ) −−−−−−→ (MisMatch, x, M1 , L1 )evalGrow(!e, x, z, M0 , L0 ) −−−−−−→ (ε, x, M1 , L1 )

図 10

[選択 2]

evalGrow

関係 −−−−−−−→ の定義 1[否定的先読み 2][選択 (失敗)]

applyRuleGrow(A, xy, xy, M0 , L0 ) −−−−−−−−−−→ (x′ , y, M1 , L1 )

A∈
/ L0

(A, xy, xy, M0 , L0 ) −−−−−−→ (A[x′ ], y, M1 , L1 )evalGrowA∈/ L0[非終端記号 (探索 1)]

applyRuleGrow(A, y, y, M0 , L0 ) −−−−−−−−−−→ (MisMatch, y, M1 , L1 )evalGrow(A, y, y, M0 , L0 ) −−−−−−→ (MisMatch, y, M1 , L1 )A ∈ L0applyRule(A, xy, M0 ) −−−−−−→ (x′ , y, M1 )(A, xy, xy, M0 , L0 ) −−−−−−→ (A[x′ ], y, M1 , L0 )evalGrow

A ∈ L0[非終端記号 (探索 2)][非終端記号 (参照 1)]

applyRule(A, x, M0 ) −−−−−−→ (MisMatch, x, M1 )evalGrow(A, x, x, M0 , L0 ) −−−−−−→ (MisMatch, x, M1 , L0 )[非終端記号 (参照 2)]applyRule

applyRule(A, xy, M0 ) −−−−−−→ (x′ , y, M1 )(A, xy, z, M0 , L0 ) −−−−−−→ (A[x′ ], y, M1 , L0 )evalGrowwhere z ̸= xy[非終端記号 (参照 3)]

applyRule

applyRule(A, x, M0 ) −−−−−−→ (MisMatch, x, M1 )evalGrow(A, x, z, M0 , L0 ) −−−−−−→ (MisMatch, x, M1 , L0 )図 11

where z ̸= x

[非終端記号 (参照 4)]

evalGrow

関係 −−−−−−−→ の定義 2(R(A), xyz, w, M0 , L0 ∪ {A}) −−−−−−→ (x′ y ′ , z, M1 , L1 )evalGrow

M1 (A, xyz) = (x′ , yz, g)

applyRuleGrow(A, xyz, w, M0 , L0 ) −−−−−−−−−−→ (x′ y ′ , z, M1 [(A, xyz) 7→ (x′ y ′ , z, g)], L1 )(R(A), xyz, w, M0 , L0 ∪ {A}) −−−−−−→ (x′ , yz, M1 , L1 )evalGrow

M1 (A, xyz) = (x′ y ′ , z, g)

applyRuleGrow(A, xyz, w, M0 , L0 ) −−−−−−−−−−→ (x′ y ′ , z, M1 , L1 )evalGrow(R(A), xy, w, M0 , L0 ∪ {A}) −−−−−−→ (MisMatch, xy, M1 , L1 )applyRuleGrow

applyRuleGrow

関係 −−−−−−−−−−−−→ の定義[メモ表の更新][延長失敗]

M1 (A, xy) = (x′ , y, g)(A, xy, w, M0 , L0 ) −−−−−−−−−−→ (x′ , y, M1 , L1 )図 12

where y ̸= ε

[解析失敗]