TeX言語のトークンと値、字句解析から展開と実行まで

2件の返信

ここ最近TeX言語を実装しているので、TeX言語の仕組みについて得られた筆者の理解を吐き出しておく。

目次

TeXを真面目に勉強したければ結局はThe TeXbookやTeX by Topicを読む必要があるし、この記事も読者がこれらの文献を読むことを前提に書いている。しかし、この記事ではTeX処理系についてこれらの本とは異なる視点から書いたつもりである。また、筆者の書いているTeX処理系 YuruMath はこの記事に書いた理解に基づいて作られているので、YuruMathのコードを読みたい人はこの記事を読んでおくと良いだろう。

この記事ではTeXのプログラミング言語としての側面に焦点を当て、組版に関する部分は一切扱わない。

定義

いくつかの集合（データ型）を定義しておく。ここでの記法は独自のもので、一般には他所では通じない。用語の使い方も独自のものが多いと思うが、もしここで使ったものよりもふさわしい用語があれば筆者に教えて欲しい。

トークンと値の定義

カテゴリーコード \(\mathsf{CatCode}\) は、TeXの字句解析においてソースコードに書かれた文字に割り当てられる、0から15までの整数である。例えば、カテゴリーコード0が割り当てられた文字は、制御綴(コントロールシークエンス)の始まりを表す（通常はバックスラッシュ \ がカテゴリーコード0を持つ）。カテゴリーコードは整数だが、ここではわかりやすい別名（\(0=\mathsf{Escape}\), \(1=\mathsf{BeginGroup}\), …）をつけておく。字句解析の結果に出現するカテゴリーコードは（アクティブ文字を除くと）10通りであり、ここではそれを \(\mathsf{TCatCode}\) と呼ぶことにする。

\[\begin{aligned}
\mathsf{CatCode}:=&\{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15\} \\
=&\{\mathsf{Escape},\mathsf{BeginGroup},\mathsf{EndGroup},\mathsf{MathShift},\\
&\quad\mathsf{AlignmentTab},\mathsf{EndLine},\mathsf{Parameter},\mathsf{Superscript},\\
&\quad\mathsf{Subscript},\mathsf{Ignored},\mathsf{Space},\mathsf{Letter},\\
&\quad\mathsf{Other},\mathsf{Active},\mathsf{Comment},\mathsf{Invalid}\}, \\
\mathsf{TCatCode}:=&\{\mathsf{BeginGroup},\mathsf{EndGroup},\mathsf{MathShift},\mathsf{AlignmentTab},\\
&\quad\mathsf{Parameter},\mathsf{Superscript},\mathsf{Subscript},\mathsf{Space},\\
&\quad\mathsf{Letter},\mathsf{Other}\}
\end{aligned}\]

TeX言語におけるコマンド名 \(\mathsf{CommandName}\) としては、制御綴(コントロールシークエンス)と呼ばれる0文字以上の文字列、またはアクティブ文字と呼ばれる1文字を使うことができる。制御綴は、名前を四角で囲ったものによって表すことにする（例えば、\foo という文字列を字句解析して得られる制御綴は \(\fbox{foo}\) と書く）。アクティブ文字は、右下に添字として 13 を置くことで表すことにする。

\[\begin{aligned}
\mathsf{CommandName}:=&\{\text{control sequence}\}\cup\{\text{active char}\}\\
=&\{\fbox{foo},\fbox{bar},\fbox{relax},\ldots\}\cup\{\mathtt{a}_{13},\mathtt{b}_{13},\ldots,\verb|~|_{13},\ldots\}
\end{aligned}\]

LaTeXの初期状態のカテゴリーコードではチルダ文字 ~ のみがアクティブ文字だが、ここで定義する集合には任意の文字がアクティブ文字としてコマンド名に含まれる。

字句解析の結果生み出されるトークン \(\mathsf{Token}\) は、コマンド名か、「文字とカテゴリーコードの組」のいずれかである。後者として現れるカテゴリーコードは10通りである。「文字とカテゴリーコードの組」は、文字の右下にカテゴリーコードの数字を置くことで表すことにする。

\[\begin{aligned}
\mathsf{Token}:=&\mathsf{CommandName}\cup\{x_\mathit{cc}\mid x\in\mathsf{Char},\mathit{cc}\in\mathsf{TCatCode}\}\\
=&\mathsf{CommandName}\cup\{\mathtt{a}_{11},\mathtt{b}_{11},\ldots,\mathtt{a}_{12},\ldots,\mathtt{=}_{12},\ldots\}
\end{aligned}\]

展開可能な値 \(\mathsf{EValue}\) とは、展開可能プリミティブ \(\mathsf{EPrim}\) とマクロ \(\mathsf{Macro}\) の和集合である。展開可能プリミティブはTeX処理系によって定まる有限集合で、おなじみ \expandafter や \romannumeral, \csname 等はこれに属する。マクロは、 \def で定義できるやつである。展開可能プリミティブは、先頭にバックスラッシュをつけた名前で表す。

\[\begin{aligned}
\mathsf{EValue}:=&\mathsf{EPrim}\cup\mathsf{Macro}\\
=&\{\mathtt{\backslash expandafter},\mathtt{\backslash romannumeral},\mathtt{\backslash csname},\ldots\}\\
&\cup\mathsf{Macro}
\end{aligned}\]

展開可能プリミティブの部分集合として、ブール値による条件分岐 \(\mathsf{BooleanConditional}\subset\mathsf{EPrim}\) がある。\if や \ifx, \ifnum 等がこれに属する。

展開不能な値 \(\mathsf{NValue}\) とは、展開不能プリミティブ \(\mathsf{NPrim}\) とカテゴリーコード付きの文字、\chardefされたもの \(\mathsf{Chardef\text{-}ed}\)、\mathchardefされたもの \(\mathsf{Mathchardef\text{-}ed}\)、\countレジスター \(\mathsf{CountReg}\)、\dimenレジスター \(\mathsf{DimenReg}\)、その他多数の和集合である。展開可能プリミティブも先頭にバックスラッシュをつけた名前で表す。

\[\begin{aligned}
\mathsf{NValue}:=&\mathsf{NPrim}\cup\{x_\mathit{cc}\mid x\in\mathsf{Char},\mathit{cc}\in\mathsf{TCatCode}\}\\
&\quad\cup\mathsf{Chardef\text{-}ed}\cup\mathsf{Mathchardef\text{-}ed}\cup\cdots\\
&\quad\cup\mathsf{CountReg}\cup\mathsf{DimenReg}\cup\cdots
\end{aligned}\]

展開不能プリミティブはTeX処理系によって定まる有限集合で、例としては、 \relax, \def, \let, \chardef, \count, \endcsname などがある。\def 自体はマクロではないのと同様に、 \chardef 命令自体は「\chardefされたもの」ではなく「展開不能プリミティブ」の範疇に入る。また、「\countレジスター」は「\countdefされたもの」のことであり、 \count 自体は「展開不能プリミティブ」である。

（TeX by Topicでは \endcsname が〈expandable command〉つまり展開可能となっているが、筆者の考えではこれは展開不能に分類しておいた方が良い）

「カテゴリーコード付きの文字」を値として持つトークンは、文献によっては「暗黙の文字トークン（implicit character token）」と呼ばれるが、ここではその呼び方はしない。

展開可能な値と展開不能な値の和集合を、値 \(\mathsf{Value}\) と呼ぶ。便宜的に、未定義 \(\mathsf{undefined}\) も値として含めておく。

\[\mathsf{Value}=\mathsf{EValue}\cup\mathsf{NValue}\cup\{\mathsf{undefined}\}\]

（要検討：「値」よりも「コマンド」の方が良いか？）

（追記：\(\mathsf{undefined}\) も「展開するとエラーを出す展開可能コマンド」として扱った方がいいかもしれない）

展開不能な値のうち幾つかは、内部整数 \(\mathsf{InternalInteger}\), 内部長さ \(\mathsf{InternalDimension}\), 内部グルー \(\mathsf{InternalGlue}\), 内部数式グルー \(\mathsf{InternalMuGlue}\) である。例えば\countレジスターや整数パラメーター、\chardefされたものは内部整数である。カテゴリーコード付きの文字（\(\mathtt{7}_{12}\) など）は内部整数ではない。

\[\begin{gathered}
\mathsf{InternalInteger},\mathsf{InternalDimension},\mathsf{InternalGlue},\mathsf{InternalMuGlue}\subset\mathsf{NValue},\\
\mathsf{CountReg},\mathsf{Chardef\text{-}ed},\ldots\subset\mathsf{InternalInteger}
\end{gathered}
\]

処理系の状態

TeX処理系は状態を持つ。

ローカルな状態 \(\mathsf{LocalState}\) は「コマンド名が表す値」 \(\mathsf{definition}\colon\mathsf{CommandName}\rightarrow\mathsf{Value}\), カテゴリーコード \(\mathsf{catcode}\colon\mathsf{Char}\rightarrow\mathsf{CatCode}\), その他各種コード \(\mathsf{lccode}\colon\mathsf{Char}\rightarrow\mathsf{Int}\), …, 各種パラメーター \(\mathsf{endlinechar}\colon\mathsf{Int}\), … などからなるレコードである。このほか、グループの種類 \(\mathsf{groupType}\colon\{\mathsf{braces},\mathsf{begingroup\text{-}endgroup},\mathsf{math},\mathsf{left\text{-}right}\}\) も持つ。

\[\begin{aligned}
\mathsf{LocalState}:=&(\mathsf{definition}\colon\mathsf{CommandName}\rightarrow\mathsf{Value}, \\
&\quad\mathsf{catcode}\colon\mathsf{Char}\rightarrow\mathsf{CatCode}, \mathsf{lccode}\colon\mathsf{Char}\rightarrow\mathsf{Int},\ldots\\
&\quad\mathsf{endlinechar}\colon\mathsf{Int},\ldots\\
&\quad\mathsf{groupType}\colon\{\mathsf{braces},\mathsf{begingroup\text{-}endgroup},\mathsf{math},\mathsf{left\text{-}right}\})
\end{aligned}\]

ローカルな状態というのは、グループの終わり（ } や \endgroup）によって巻き戻される状態である。

トークンの値とは、コマンド名に対しては写像 \(\mathsf{definition}\) による値であり、カテゴリーコード付きの文字に対してはそれ自体を展開不能な値とみなしたものである。

展開可能なトークンとは、その値が展開可能な値（\(\mathsf{EValue}\) の元）であるようなトークンのことであり、展開不能なトークンとは、その値が展開不能な値（\(\mathsf{NValue}\) の元）であるようなトークンのことである。（TODO: 未定義なやつはどうする？）

状態 \(\mathsf{State}\) は、字句解析器・展開器の状態 \(\mathsf{expansionState}\colon\mathsf{ExpansionState}\) と、ローカルな状態のスタック、現在のモード \(\mathsf{mode}\colon\{\ldots\}\) からなるレコードである。

\[\begin{aligned}
\mathsf{State}:=&(\mathsf{expansionState}\colon\mathsf{ExpansionState},\\
&\quad\mathsf{localStates}\colon\mathsf{Stack}(\mathsf{LocalState}),\\
&\quad\mathsf{mode}\colon\{\mathsf{Vertical},\mathsf{InternalVertical},\mathsf{Horizontal},\\
&\qquad\mathsf{RestrictedHorizontal},\mathsf{Math},\mathsf{DisplayMath}\})
\end{aligned}\]

現在のローカルな状態といったら、スタック \(\mathsf{localStates}\) の先頭（一番上）にあるものを指す。また、断らない限り、トークンの値や展開可能性は現在のローカルな状態におけるそれを指す。

展開器の状態 \(\mathsf{ExpansionState}\) は、字句解析器の状態 \(\mathsf{tokState}\colon\mathsf{TokState}\) および先読み済みのトークン列 \(\mathsf{pendingToken}\colon\mathsf{Stack}(\mathsf{Token})\), 条件分岐のスタック \(\mathsf{condStack}\colon\mathsf{Stack}(\{\mathsf{Test},\mathsf{Then},\mathsf{Else},\mathsf{IfCase}\})\) からなるレコードである。

\[\begin{aligned}
\mathsf{ExpansionState}:=&(\mathsf{tokState}\colon\mathsf{TokState},\\
&\quad\mathsf{pendingToken}\colon\mathsf{Stack}(\mathsf{Token}),\\
&\quad\mathsf{condStack}\colon\mathsf{Stack}(\{\mathsf{Test},\mathsf{Then},\mathsf{Else},\mathsf{IfCase}\}))
\end{aligned}\]

字句解析器の状態については詳しい説明はしない。（TODO: \inputについて検討する）

字句解析

展開器における先読み済みのトークン列が空となった場合、次のトークンを取得するために字句解析が行われる。TeXの字句解析は実行前に行われるのではなく、必要に応じて引き起こされるものである。

「ローカルな状態」に含まれるパラメーターのうち、字句解析は \(\mathsf{catcode}\) と \(\mathsf{endlinechar}\) に依存する。同じ入力文字列であっても「ローカルな状態」によって字句解析の結果が変わりうるため、字句解析は、展開器が次のトークンを必要としたタイミングで行われる。

詳しいことは省略するが、字句解析によってトークン（\(\mathsf{Token}\) の元）が生み出され、展開器に渡される。

展開

コマンドの実行や引数の解釈で「次のコマンド」や「次の展開不能トークン／値」が必要になった場合、必要に応じて展開が行われる。展開は勝手に起こるのではなく、誰かによって引き起こされるものである。

先読み済みのトークン列が空でない場合は、そこからトークンを取ってきて処理対象とする。先読み済みのトークン列が空の場合は、字句解析器を動かしてトークンを読み取る。（この段階のまだ展開処理をしていないトークンを、未展開トークンと呼ぶことにする）

処理対象のトークン \(t\) は、コマンド名か「文字とカテゴリーコードの組」である。前者の場合は、現在のローカルな状態における「コマンド名が表す値」 \(\mathsf{definition}\) の \(t\) に対応する値を \(v\) とおく。

\(v\) が展開不能な値 \(v\in\mathsf{NValue}\) ならば展開は終了（あるいは、元のトークン \(t\) 自体が展開結果）である。\(v\) が展開可能な値 \(v\in\mathsf{EValue}\) ならば展開を行う。

展開可能な値 \(v\in\mathsf{EValue}\) は、展開結果としてトークン列を生成する。つまり、状態を変化させる部分写像 \(\mathsf{expand}\colon\mathsf{EValue}\times\mathsf{State}\rightarrow\mathsf{List}(\mathsf{Token})\times\mathsf{State}\) が定まっている（展開時にエラーが起きる可能性があるので、部分写像である）。

展開においては、基本的には展開器の状態 \(\mathsf{ExpansionState}\) のみが変化するが、一部の展開可能プリミティブ（具体的には \csname）はそれ以外の状態も変化させうる。（このようなプリミティブは古典的には \csname だけだったが、LuaTeXでの展開可能プリミティブ \directlua を使うと任意の状態が変化しうる。なお、pdfTeXには乱数を取得展開可能プリミティブがあるが、これは乱数生成器の状態も展開器の状態に含めることで説明できそうな気がする）

普通に展開する状況では、展開結果として得られたトークン列は「先読み済みのトークン列」の先頭に積む。

展開不能なトークン・値が必要な場合は繰り返し展開を行い、先頭に展開不能トークンが現れるまで頑張る。場合によってはここで無限ループに陥る。

例：\string は1個の未展開トークン \(t_1\) を読み取り、 \(t_1\) を文字列化したトークン列を返す。擬似コード：

expand(\string) = do
  t1 <- nextToken()
  if t1 is a control sequence then
    name <- (t1 の名前)
    (\escapechar を参照しつつ name の先頭にエスケープ文字を付加する)
    (TODO: name == "" の場合は \csname\endcsname が返るようにする)
    return (stringToTokenList name)
  else
    (t1 は文字トークン c であるとする)
    return (stringToTokenList [ c ])
(stringToTokenList は文字列をトークン列に変換する関数である)

例：\number は整数を読み取り、それを10進数として文字列化したものをトークン列として返す。擬似コード：

expand(\number) = do
  x <- readInt()
  return stringToTokenList(toString(x))

例： \expandafter は2個の未展開トークン \(t_1\), \(t_2\) を読み取り、 \(t_1\) および「\(t_2\) を1回展開した結果のトークン列」からなる列を展開結果とする。擬似コード：

expand(\expandafter) = do
  t1 <- nextToken()
  t2 <- nextToken()
  t2' <- expand(definition(t2))
  return [t1] ++ t2'

条件分岐

条件分岐に関わるコマンド（\ifﾅﾝﾄｶ, \ifcase, \or, \else, \fi）については解説が必要である。

\ifﾅﾝﾄｶ は適宜引数を読み取り、条件の真偽（あるいは \ifcase の場合は整数値）を判定する。この際、引数を読み取る前に \(\mathsf{condStack}\) の先頭に値 \(\mathsf{Test}\) を積んでおく。

条件が真なら、 \(\mathsf{condStack}\) の先頭の値 \(\mathsf{Test}\) を \(\mathsf{Then}\) に置き換え、空のトークン列を展開結果として返す。

条件が偽なら、続くトークン列から（展開せずに） \else または \fi または \or を値としてもつトークンを探す。この際、対応の取れた \ifﾅﾝﾄｶ .. \else .. \fi はカウントしない。

  • \else が見つかった場合は \(\mathsf{condStack}\) の先頭の値 \(\mathsf{Test}\) を \(\mathsf{Else}\) に置き換え、空のトークン列を展開結果として返す。
  • \fi が見つかった場合は \(\mathsf{condStack}\) の先頭の値 \(\mathsf{Test}\) を取り除き、空のトークン列を展開結果として返す。
  • \or が見つかった場合は Extra \or. のエラーを出す。

\ifcase の場合は、整数値によって \or をスキップしたりする（詳細は略）。

例： \iftrue Foo \else Bar \fi の先頭の \iftrue を1回展開した結果は Foo \else Bar \fi である。e-TeXであればこれは \message{\unexpanded\expandafter{\iftrue Foo \else Bar \fi}} によって確かめられる。

つまり、条件が真の \ifﾅﾝﾄｶ を展開した時点では、後続のトークン列に \else や \fi が残ったままである。

次は \else の展開を見てみよう。\else の展開が起こるということは、対応する \ifﾅﾝﾄｶ は「真」と判断されたはずである。\(\mathsf{condStack}\) の先頭の値を確認し、それが \(\mathsf{Then}\) 以外であれば Extra \else. のエラーを出す。

\(\mathsf{condStack}\) の先頭の値が \(\mathsf{Then}\) であれば、続くトークン列から（展開せずに） \fi を値としてもつトークンを探す。この際、対応の取れた \ifﾅﾝﾄｶ .. \else .. \fi はカウントしない。

  • \fi が見つかった場合は \(\mathsf{condStack}\) の先頭の値 \(\mathsf{Then}\) を取り除き、空のトークン列を展開結果として返す。

\fi の展開では、\(\mathsf{condStack}\) の先頭の値を取り除いて空のトークン列を返す。

完全展開と\edef

通常は完全展開と言ったら展開不能トークンが現れるまで頑張るものだが、一部の展開可能な値は \edefの文脈（\edef の他に \message, \expanded 等）で異なる挙動を示す。

具体的にはe-TeXの\protectedなマクロと \unexpanded で、前者は\edefの文脈では展開されない。後者は引数のトークン列を展開せずそのまま返す。

（\noexpandについては後で説明する）

実行

展開の結果として展開不能な値（\(\mathsf{NValue}\) の元）が得られたら、次はそれを実行する。

代入・演算

\let, \def, \chardef, \count 等は代入コマンドである。\advance 等も代入コマンドの一種である。

\let はコマンド名 \(n\) を読み取り、省略可能なイコールの後の未展開トークンの値 \(v\in\mathsf{Value}\) を \(n\) に関連づける： \(\mathsf{definition}(n)\leftarrow v\)

\def はコマンド名 \(n\) とマクロの定義（パラメーターの指定・展開後のトークン列）を読み取り、構築されたマクロを \(n\) に関連づける。

代入がグローバルな場合は、 \(\mathsf{localStates}\) の先頭だけではなく、スタック全てについて同じ代入操作を行う。\advance の場合は「同じ演算操作を」ではなく「演算結果の代入を」スタック全てについて行う。

ということはグループの深いところでのグローバルな代入操作に時間がかかりそうだが、伝統的なTeX処理系は save stack というものを使っていて、グループが深いからといってグローバルな代入操作の時間が長くなるということはないらしい。ちなみに筆者のYuruMathでは素朴にスタック全てについて代入操作を行っているのでグループが深くなるとグローバルな代入操作が遅くなると思われる。LuaTeXについては自分で調べてくれ。

グループ

カテゴリーコードが \(\mathsf{BeginGroup}\) の文字 \(x_{1}\) や \begingroup は新たなグループを作る。つまり、 \(\mathsf{localStates}\) の先頭の値を複製し、それをスタック先頭に積む。この際、 \(\mathsf{groupType}\) は適宜設定される。

（LaTeXのように \(\fbox{bgroup}\) の値を \(\mathtt{\{}_{1}\) と定義すると、トークンそのものではなく値を参照する状況で \(\fbox{bgroup}\) が { の代わりになる。つまり \(\fbox{bgroup}\) はグループを作る用途には使えるがマクロ引数をくるむのには使えない）

ちなみに、{ .. } と \begingroup .. \endgroup は「状態」に関しては同じように振舞うが、数式モードでは組版結果が変わりうる。

\uppercaseと\lowercase

これらのコマンドはトークン列を読み取り、大文字小文字の変換を行なった上で「先読み済みのトークン列」にそれを戻す。

これらは、展開可能なコマンド以外では数少ない、「先読み済みのトークン列」を直接操作するコマンドである。（このようなコマンドとしては他には数式モードでの math active char がある）

組版のためのリスト構築

他の多数のコマンドは、組版に関するものである。詳しくは扱わない。

次回予告

この記事に書いた描像はTeXを理解するとっかかりとしては良いのだが、実は微妙に不完全である。（筆者のやる気が急速に減退しない限り）次回はその辺（\(\mathsf{Token}\) のより正確な定義, \noexpand, 挿入された\relax）を扱う。

ちなみに、今月（6月）は筆者の誕生月であり、筆者のほしい物リストはほしい物リスト／ほしい本リストである。

このエントリーをはてなブックマークに追加

「TeX言語のトークンと値、字句解析から展開と実行まで」への2件のフィードバック

  1. ピンバック: TeX言語のトークンと値 その2：noexpandと、挿入されたrelax | 雑記帳

  2. ピンバック: 2022年振り返りと来年に向けて | 雑記帳

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です