PythonでLanguage Implementation Patternsのパーサと戯れる 序

前２回の記事でも書いたとおり、Language Implementation Patternsのはじめの方をPythonで実装している。

具体的にはPackrat Parsingまで、本に出てくるクラスベースな実装ではなく、lookaheadやbacktrackの機能はトークンストリームの方に持たせた上で相互再帰関数の集まりとして実装してみた。ちなみにPython3.10の新機能であるStructural Pattern Matchingを多用している。

パースする言語はまず簡単なリストからはじめて：

list     : '[' elements ']';
elements : element (',' element)*;
element  : ('a'..'z' | 'A'..'Z')+;

リストのネスト：

list     : '[' elements ']';
elements : element (',' element)*;
element  : NAME | list;
NAME : ('a'..'z' | 'A'..'Z')+;

変数間の代入：

list     : '[' elements ']';
elements : element (',' element)*;
element  : NAME | assign | list;
assign : NAME '=' NAME;
NAME : ('a'..'z' | 'A'..'Z')+;

そしてリスト間の代入：

list     : '[' elements ']';
elements : element (',' element)*;
element  : NAME | assign | list | list_assign;
assign : NAME '=' NAME;
list_assign : list '=' list;
NAME : ('a'..'z' | 'A'..'Z')+;

へと拡張していく。

流れとしては：

• lexerとPeekableストリームオブジェクト
• 簡単なリスト言語の非再帰的なパーサ
• ネストしたリストのLL(1)再帰的パーサ
• 変数間代入のLL(2)再帰的パーサ
• Backtrackableストリームオブジェクトとリスト間代入のBacktrackパーサ
• Backtrack実行時間効率化のためのPackratパーサ
• Packratのキャッシュクリアとメモリ効率化

これらを個別の記事で解説していく。