読者です 読者をやめる 読者になる 読者になる

LISP on TeXを作る(パーサ編)

TeX

LISP on TeXネタを全部消費して,新たなるTeX芸へ向かうためのソリューションその2.今回はパーサ編.要はS式を解釈して前回のデータ構造編で説明したデータへ変換するマクロがどのように構成されているかを示す.これから説明するマクロは,lisp-read.styにそのほとんどが記述されている.

はじめに

実装説明に入る前に,パーサ全体にかかる注意事項を述べておく.まず,LISP on TeXの文法はLL1であるので,字句解析と構文解析をごちゃ混ぜにした実装になっている.また,一部のマクロを除き,パーサのマクロは

\def\controlsequence#1#2{....}

の形で定義されている.#1は制御綴りで,#2は現在解析中の先頭文字である.これらのマクロは,#1の中身を\cs,パースの結果得られたデータ構造を\@tlabel@xxx{hoge}とすると

\cs\@tlabel@xxx{hoge}

と展開される.ちょうど\csを継続としたCPSで記述されていると思えばいい.このようなまどろっこしい構造にしているのは,こちらのほうがTeXの資源消費を減らせるからである.実は,入力全体をマクロに保存しておき,一文字ずつ取ってくるという構造にしていた時期もあるのだが,それだと大量のLISP on TeXコードを投入したときにエラーを吐くことわかり,急遽この構造にした経緯がある*1

対象とするLISP on TeXの文法をそろそろ明示しないといけないので,READMEから文法を抜粋しておく.

   ::=  
            |  
            |  
            | 
            | 
            | 
            | 
            | 
            | 
    ::= (+) | ( . )
     ::= :[TeX's integer]
  ::= '[TeX's tokens]'
  ::= [a control sequence]
    ::= /t | /f
     ::= ()
::= +{::}
 ::= [TeX's tokens]
  ::= [TeX's tokens]
    ::= @[TeX's skip]
   ::= ![TeX's dimen]

は非終端記号,|は選択,+は非終端記号の長さ1以上の列である.[comment]は終端記号のうち,TeX側に依存するので言及をようにしていないことを示す. ::= ... でその非終端記号における規則が導入される.以上の説明に出現しない記号はすべて終端記号である.

コード解説

型による分岐部分

パーサの起点は\@lispreadで定義は,次のようになっている.

\def\@lispread#1#2{\begingroup\@lispread@main#1#2}

\begingroupでローカルな定義を漏れ出さないようにして\@lispread@mainを呼び出すだけである.\@lispread@mainは次で示される.

\def\@lispread@main#1#2{% Define \@@next, the continuation. 
  \if\noexpand#2(% [Branch 1] CONS cell or NIL
    \def\@@next{\@lispread@cell#1}%
  \else\ifcat\noexpand#2\relax% [Branch 2] A control sequence or a control symbol 
    \ifx#2\@end@lispread % [Branch 2-1] EOI
      \def\@@next{\endgroup#1\@tlabel@exception{!Found End of Input!}}%
    \else
      \def\@@next{\@lispread@symbol#1#2}% [Branch 2-2] Symbol
    \fi
  \else\if\noexpand#2'% [Branch 3] String
      \def\@@next{\@lispread@string#1}%
  \else\if\noexpand#2/% [Branch 4] Boolean
    \def\@@next{\@lispread@bool#1}%
  \else\if\noexpand#2:% [Branch 5] Integer
    \def\@@next{\@lispread@int#1}%
  \else\if\noexpand#2!% [Branch 6] Dimension 
    \def\@@next{\@lispread@dimen#1}%
  \else\if\noexpand#2@% [Branch 7] Skip
    \def\@@next{\@lispread@skip#1}%
  \else\if\noexpand#2+% [Branch 8] call a Reader Module 
    \def\@@next{\@lispread@module#1}%
  \else % Otherwise -- parse error
    \errmessage{LISP on teX [read]: no such type start with \noexpand#2}%
  \fi\fi\fi\fi\fi\fi\fi\fi
  \@@next}

この部分では,先頭の1文字を見て次に呼び出すべきマクロを\@@nextに収める.LISP on TeXでは,先頭の1文字を見るだけで型をほぼ識別できるようにデザインしているため,このようマクロで動く.分岐パターンは次のとおりである.

  • 「(」CONSセルもしくはnil
  • 「\cs」シンボル*2.\ifcatで判断しているので,実際はカテゴリーコード13の文字もシンボルとみなされる.
  • 「'」文字列.
  • 「/」ブール値.
  • 「:」整数.
  • 「!」ディメンジョン.
  • 「@」スキップ.
  • 「+」パーサの拡張機能パーサモジュール)の呼び出し

ここからは,(順不同で)これらのパターンそれぞれに対応したマクロを見ていく.

シンボル,文字列,ブール値

シンボル(文法上は)を読み込むマクロ\@lispread@symbolは,次のように定義されている.

\def\@lispread@symbol#1#2{%
  \endgroup#1\@tlabel@symbol{#2}}

まぁ,簡単.先の\@lispread@mainによって,#2にはシンボルとなるトークンが与えられていることがわかっているので,単にシンボル型のデータ\@tlabel@symbol{#2}を作って継続である#1に渡すだけである.ここで,\@lispreadで\begingroupしているので\endgroupを忘れてはいけない.

文字列()やブール値()もほぼ同様で,次のようなコードになっている.

%% String
\def\@lispread@string#1#2'{%
  \endgroup#1\@tlabel@string{#2}}
%% Boolean
\def\@lispread@bool#1#2{%
  \endgroup#1\@tlabel@bool{#2}}

なお,文字列には「'」を含められないことがこのコードからわかる*3.また,ブール値は「/t」もしくは「/f」なはずだが,ここではそのチェックを入れていない.よって,不正な値(例:「/a」)でもパーサは受理してしまう.この辺りも改善の余地がある.

整数,ディメンジョン,スキップ

TeXの数値や長さに関連するこれらのパーサは,TeXの読み込み処理を利用するようにできている.要は,

を実施しているだけである.コードを示す.

%% Integer
\newcount\@cnt@lispread@int
\def\@lispread@int#1{%
  \gdef\@lispread@int@callback{\@lispread@int@main#1}%
  \afterassignment\@lispread@int@callback
  \global\@cnt@lispread@int}
\def\@lispread@int@main#1{%
  \endgroup\expandafter#1\expandafter\@tlabel@int\expandafter{\the\@cnt@lispread@int}}
%% Skip
\newskip\@cnt@lispread@skip
\def\@lispread@skip#1{%
  \gdef\@lispread@skip@callback{\@lispread@skip@main#1}%
  \afterassignment\@lispread@skip@callback
  \global\@cnt@lispread@skip}
\def\@lispread@skip@main#1{%
  \endgroup\expandafter#1\expandafter\@tlabel@skip\expandafter{\the\@cnt@lispread@skip}}
%% Dimen
\newdimen\@cnt@lispread@dimen
\def\@lispread@dimen#1{%
  \gdef\@lispread@dimen@callback{\@lispread@dimen@main#1}%
  \afterassignment\@lispread@dimen@callback
  \global\@cnt@lispread@dimen}
\def\@lispread@dimen@main#1{%
  \endgroup\expandafter#1\expandafter\@tlabel@dimen\expandafter{\the\@cnt@lispread@dimen}}

ほら簡単.\@cnt@lispread@int,\@cnt@lispread@skip,および\@cnt@lispread@dimenがレジスタで,それぞれへの代入を\@lisp@read@intの末尾で行うようなコードになっている.LISP on TeXの流れに戻る処理は,\afterassignmentでTeXの代入処理をフックすることで実現されている*4

CONSセルおよびnil

CONSセルとnilの処理が実は一番難しい.先にコードを示す.

%% CONS cell or NIL
\def\@lispread@cell#1#2{%
  \if\noexpand#2)% [Branch 1] NIL
    \def\@@next{\endgroup#1\@tlabel@nil{}}%
  \else % Otherwise CONS cell
    \def\@@next{\@lispread@cell@car#1#2}%
  \fi\@@next}
%% first part of CONS cell : read CAR
\def\@lispread@cell@car#1{%
  \def\@lispread@car@reg##1##2{%
    \def\@reg@lispread@car{##1{##2}}%
    \@lispread@cell@dot#1}%
  \@lispread\@lispread@car@reg}
\def\@lispread@cell@dot#1#2{%
  \if\noexpand#2.%
    \def\@@next{%
      \def\@lispread@cell@fincheck####1####2{%
        \def\@reg@lispread@cdr{####1{####2}}%
        \@lispread@fin#1}%
    \@lispread\@lispread@cell@fincheck}% kokonaosu
  \else
    \def\@@next{\@lispread@cell@cdr#1(#2}%
  \fi\@@next}
\def\@lispread@cell@cdr#1{%
  \def\@lispread@cdr@reg##1##2{%
    \expandafter\@read@malloc\expandafter\@reg@tmp\@reg@lispread@car##1{##2}%
    \expandafter\endgroup\expandafter#1\@reg@tmp}%
  \@lispread\@lispread@cdr@reg}
\def\@lispread@fin#1#2{%
  \if\noexpand#2)%
    \def\@@next{%
      \expandafter\expandafter\expandafter\@read@malloc
      \expandafter\expandafter\expandafter\@reg@tmp
      \expandafter\@reg@lispread@car\@reg@lispread@cdr
      \expandafter\endgroup\expandafter#1\@reg@tmp}%
  \else
    \def\@@next{\errmessage{LISP on teX [read]: missing )}}%
  \fi\@@next}
\def\@read@malloc#1#2#3#4#5{%
  \expandafter\gdef\csname car\the\@malloc\endcsname{#2{#3}}%
  \expandafter\gdef\csname cdr\the\@malloc\endcsname{#4{#5}}%
  \expandafter\@@read@malloc\expandafter#1\csname car\the\@malloc\endcsname\csname cdr\the\@malloc\endcsname}
\def\@@read@malloc#1#2{\expandafter\@@@read@malloc\expandafter#1\expandafter#2}
\def\@@@read@malloc#1#2#3{%
  \global\advance\@malloc1
  \def#1{\@tlabel@cons{#2#3}}}

\@lispread@cellではまず,入力の先頭文字が「)」であるか否かを確認する.「)」であればそれはnilなので,継続に「\@tlabel@nil{}」を引き渡して処理を終了する.そうでなければ,それはCONSセルなので,CARを構成するために\@lispread@cell@carを呼び出す.

\@lispread@cell@carでは継続を表すマクロ\@lispread@cdr@regを生成し,再帰的にパーサを呼び出す.\@lispread@cdr@regの表す継続は,「\@reg@lispread@carにパース結果を保存して『.』の有無を調べる処理にこれまでの継続を渡して呼び出す」である.

CAR部分の読み込みが終わると,「.」の有無を調べる処理\@lispread@cell@dotが起動される*5.これは,入力の先頭が「.」であるときは「CDR部分を読み込み,『)』で終端しているかを調べる」とい継続を生成し,パーサを再帰的に呼び出す.そうでない時はリスト表記なので,コード上は「(hoge fuga...)」の形をしているはずである.これは「(hoge . (fuga...))」の省略形であるから,入力の先頭に「(」を付加してから再帰的にパーサを呼び出す*6.このときに渡される継続は,「ここで渡された継続に対応するCONSセルを渡す」である.

\@lispread@finが,先の前者の呼び出しに対する継続,すなわち「『)』で終端しているかの確認とそれまでの継続の呼び出し」に当たる部分である.これは,単に\ifで「)」と入力の先頭を比較して,正しければ「CONSセルを継続に渡す処理」を実行するだけである.

\@read@mallocが\@lispread@cell@dotの後者(「.」が入力の先頭でなかったとき)と\@lispread@finで使っている「CONSセルを作る処理」である.#1に制御綴りをとり,CAR(#2{#3})とCDR(#4{#5})を\carXXと\cdrXXにグローバルに代入して#1を

\@tlabel@cons{\carXX\cdrXX}

に定義する.XXは数値で,\@mallocによりすべてのCONSセルに対して一意の値を振るようにしている.ちょうどXXがメモリアドレスのように振る舞うので,その数値を元にGCを作ることが可能である*7

パーサモジュール

ここが,前回のデータ構造編で言及していた,パーサへのフック機構になっている.まずはコードを示す.

%% Reader Module
\def\@lispread@module#1#2{%
  \@lispread@module@main\@register@lispread@module#2\@@end
  \endgroup
  \expandafter#1\@register@lispread@module}
\def\@lispread@module@main#1#2::#3\@@end{\csname @mod@read@#2\endcsname#1{#3}}

パーサモジュールの呼び出しは,「+{modname::value}」の形をしている.モジュール名fooは,パーサモジュールとして

\@mod@read@foo#1#2

というマクロを定義しておく.\@mod@read@fooは#1に制御綴りを,#2にモジュール呼び出し時のvalueの部分のトークン列を取り,#1をLISP on TeXのデータ構造の要件を満たすトークン列になるように定義する.\@lispread@moduleは,\@mod@read@fooを展開して得られたオブジェクトを継続に引き渡す.

文法上示されていない固定小数点数型は,実はこれを使って実現している.

(評価器編へ続く)*8

*1:keno_ssさんの報告により気がついた.多謝

*2:ただし,入力の終わりに使用される\@end@lispreadは使用できない.

*3:入れるように定義を変更してもいいのだけれど,割りと面倒くさいので放置してた.

*4:TeXは様々な処理をフックするための機構が標準で用意されているよくわからない言語である.参考

*5:ここ直すというコメントが入っているが,なにが問題なのか忘れてしまった.そんなに重要な問題では無いと思うのだが……←プロジェクト管理大事.最近Redmineを試してみている.

*6:入力の末尾に「)」をつけなくても,括弧の対応は正しく取られることに注意する.

*7:実際は,これらのアロケーション機構とともに変更が必要だったり,そもそもポインタをたどることに対応する処理がTeXで実現しづらいので,very hardな実装になるが……

*8:何時頃になるか名言はできないが……