# How does a TeX engine read and render the input stream?

I am new to TeX programming and I have not finished reading the TeXBook yet. I need at a glance tutorial about how a TeX engine reads, processes, and produces its output.

My mental model as a newbie when considering any black box receiving an input stream and producing an output stream is as follows.

The black box

1. takes a chunk of characters of a constant length,
2. processes the taken chunk of characters,
3. save the processed chunk in a file,
4. does 1, 2, 3 until all input stream of characters gets processed.

Does a TeX engine use the chunk-by-chunk processing mechanism? Or does it do multiple processing from start to finish as follows?

A TeX engine

1. scans all input stream (in an input file) from start to finish,
2. does the first expansion.
3. repeat 1 followed by 2 for the nth expansion until no more expansion possible.
4. saves the rendered output to a file, for example, in PDF format.

The answer of this question really helps me to learn plain TeX faster than reading the TeXBook.

## Edit 1 (Sept 9, 2014)

Rather than spawning a new related question, I think it is better to just edit this question.

It is still hard for me to digest the algorithm how TeX engine works without an example. That is why here I provide a simple example.

The comments unit * are intentionally added to ease referencing.

% unit A
\def\aa[#1]{a's value: #1}
\def\bb{[Hi!]}
\def\cc{\bb}
\def\dd{\cc}

% unit B
\expandafter\expandafter\expandafter\expandafter
\expandafter\expandafter
\expandafter
\aa\dd

% unit C
\expandafter\expandafter
\expandafter
\aa\cc

% unit D
\expandafter
\aa\bb

\bye


Could you elaborate your answer using this example? The points I want to know:

1. How TeX know when to proceed to the next unit.
2. Is it my understanding correct that scanning starts from top to bottom, proceed to the next unit once after the previous unit has been completely expanded and executed? I mean when processing unit B to complete its expansion and execution, the remaining units (C and D) are untouched.
-
I don't know why, but I'm confident it's linear. Just given the time in which TeX was written… –  Sean Allred Feb 3 at 5:26
@SeanAllred: I think it is neither exponential nor sinusoidal as well. –  In PSTricks we trust Feb 3 at 5:39
@Werner When you say "Read the TeX Book. Remember that there is major disconnect between what is read and what is processed," Are you referring to the TeX engine or the poor reader trying to plow through the TeX Book? –  Steven B. Segletes Feb 3 at 11:43
"I am new to TeX programming..." I don't believe you ;-) –  Henri Menke Feb 5 at 13:02
Any new answers will be reviewed in one or two days. Please be patient. :-) –  In PSTricks we trust Sep 9 at 8:43

TeX has three modes of operation: (1) Converting the input stream to tokens, (2) expanding the token, (3) executing a complete command (made up of tokens).

In more detail, it first prepares one line of input by stripping off the EOL (OS dependent) and all spaces from the end of the line (usually also tab characters). Then it adds its own endline character (the value of \endlinechar, normally ctrl-M).

It then reads the line one character at a time until it obtains a complete token (generally a single character or a control sequence). This token is passed to stage (2) the macro expansion engine, which expands it (if it can be) or asks for more tokens from stage (1) (if needed for the expansion process) or passes it along to stage (3), the execution process. This process either executes the command, or asks for more tokens from stage (2), which may then have to ask for more tokens from stage (1).

The tokenizing stage converts most characters to a token consisting of a character-code/category-code pair. Since the execution engine is capable of assigning new category codes to a character, it can influence the behavior of stage (1).

One slight complication is the existence of an endline character within a line. TeX considers that the end and ignores the rest of the line. Also a comment character (normally %) causes the rest of the line to be ignored, including the endline character.

Note that tokenization happens within a line (you cannot start a macro token on one line and finish it on the next), but expansion -- step (2) -- can request more tokens and that can continue over to the next line.

I don't know whether you can put this process under either of your two schemes. The "chunks" are either lines or tokens, neither of which have constant length, so the first description is out. And certainly TeX doesn't read a whole file at once (except perhaps it may move it from disk to an input buffer for efficiency).

As for outputting the results: TeX sends it a page at a time to the output. It evaluates whether a full page has been obtained after each paragraph has been processed. When it breaks paragraphs into lines (along with hyphenation and margin justifying), it operates on an entire paragraph at a time.

-
you might elaborate on what happens if a line ends with % -- that obscures the eol. (i honestly don't remember whether it then pulls in the next line, or proceeds to tokenize, remembering that tokenization can't finish until the continuation (next) line is added in.) –  barbara beeton Feb 3 at 13:41
Tokenization does finish before the next line in that case, but expansion cannot always finish. I will add a remark about % in a bit. –  Dan Feb 3 at 20:09
This can't be true: "It then reads the line one character at a time until it obtains a complete token". Otherwise, if both \somemacrox and \somemacro were defined, \somemacrox would also expand to \somemacro + x at the end, which isn't the case. –  1010011010 Sep 9 at 7:24
@1010011010 I've tried to cover that in my answer: to build a control word, TeX keeps reading chars until it finds one that is not a 'letter' (but doesn't tokenize it at this stage). Whatever was found before the non-letter is the control word. –  Joseph Wright Sep 9 at 8:02
@1010011010 Exactly what Joseph says: TeX looks ahead to check that the control sequence is complete. A bit like REGEX context ;) –  tohecz Sep 9 at 12:55

This is more about a comment rather than an answer, but it doesn't fit.

I recently came up to a problem with \expandafters and tried to easily understand how it works, so I'll tell here my “process” (altough it's not really well tested).

The thing is, how can you “know” what happens with many expandafters? Well, here's my process. I do anotate with a number after the macros the number of expansions that happens.

The process is “relatively simple”, you remove rectangular columns of \expandafters, see the resultant expansion (and add the number to indicate it). Then you remove the “first column” of \expandafters and start again :)

### Unit D

\expandafter
\aa
\bb


No block to remove, just see that the results expands \bb once before leaving \aa and executing it. So

\aa
\bb1


### Unit C

\expandafter\expandafter
\expandafter\aa
\cc


Remove the block of expandafters (1 column by 2 rows) and add a number, and then remove the whole block (which just happens to be a single column, so all is gone):

\expandafter
\aa
\cc1


which, by the way explained above, ends as

\aa
\cc2


### Unit B

\expandafter\expandafter
\expandafter\expandafter
\expandafter\expandafter
\expandafter\aa
\dd


First level: after seeing the block (1 columns, 4 rows), you see that \dd is expanded, so remove one column (and add then numbers) so:

\expandafter
\expandafter
\expandafter
\aa
\dd1


Same job again, reorganize to see better:

\expandafter\expandafter
\expandafter\aa
\dd1


and, you end with

\expandafter
\aa
\dd2


which leaves at the end

\aa
\dd3


\dd expanded three times before \aa is executed.

This is a famous one by Knuth. In this case, it's not the number of expansions, but the order of expansions. So here the numbers means order:

\def\z{M}
\def\Z{C}
\def\a{\z er}
\def\b{ry }
\def\c{\Z hr}
\def\d{ist}
\def\e{mas}

\expandafter\expandafter
\expandafter\expandafter
\expandafter\expandafter
\expandafter\a
\expandafter\expandafter
\expandafter\b
\expandafter\c
\d
\e


after the first line of expandafters go

\expandafter
\expandafter
\expandafter
\a
\expandafter
\b
\c
\d1
\e


then (reorganizing)

\expandafter\expandafter
\expandafter\a
\expandafter\b
\c
\d1
\e

\expandafter\a
\b
\c2
\d1
\e


and finally

\a4
\b3
\c2
\d1
\e


So, first \d, then, \c, \b, \a (\e is never touched by the expandafters).

-

All processes were explained in detail by Josef Wright and Dan. Maybe only \expandafter should be explained more.

The expansion of \expandafter <token1><token2> does:

• save <token1> to TBRA (= "To Be Read Again queue").
• expand <token2> (i.e replace it to "expanded material", if is not expandable then "expanded material" = <token2>)
• return to reading of TBRA + "expanded material" (in this order) and process expansion again.

This routine can be run recursively. Note that the TBRA:

• is queue FIFO, no stack,
• is nonempty only at the innermost recursion level of the \expandafter routine,
• is emptied when it is read (of course).

Note, that the contents of TBRA is shown during special TeX errors (but specially not for this type of TBRA from \expandafters).

I'll explain our unit B from this point of view. The token processor creates a queue of tokens (without lines structure) and the symbols below these tokens means:

• TBRA = the token is saved to the TBRA,
• EX = the token is expanded (ie. it is removed during expansion).

\expandafter\expandafter\expandafter\expandafter\expandafter\expandafter\expandafter\aa\dd
EX          TBRA         EX          TBRA        EX          TBRA       EX       TBRA EX

expanded material=  \cc
TBRA= \expandafter\expandafter\expandafter\aa

TBRA + expanded material: \expandafter\expandafter\expandafter\aa\cc
EX         TBRA         EX       TBRA EX

expanded material=  \bb
TBRA=  \expandafter\aa

TBRA + expanded material= \expandafer\aa\bb
EX       TBRA EX

expanded material=  [Hi!]

TBRA + expanded material:  \aa [Hi!]
EX

expanded material:  a's value: Hi!   (TBRA is empty now)


The whole input queue is formed from TBRA + "expanded material" + "input from file". The "expanded material" may be changed during expansion and only the "input from file" is the subject of the actual tokenization by token processor.

From my point of view, there are four level of processors

• input processor: reads lines, as defined in OS, does encoding conversion, outputs line-buffers independent on OS by removing EOL and white spaces before EOL and adding \endlinechar.
• token processor: reads line-buffers from input processor and creates the queue of tokens (without any segmentation to lines). The token processor behavior is another story.
• expand processor: does expansion of expandable tokens and outputs the unexpandable tokens.
• main processors: executes unexpandable primitive commands and its well defined parameters or execute character token as "print it". But this is more complicated, it depends on context and it is another story too.

First, the main processor starts. It is hungry (it is stomach from TeXbook's terminology), so it asks to the first unexpandable token from expand processor. It has no data at this moment on its input side, so it asks to the token from expand processor. The token processor has no prepared line-buffer, so it asks to the first one to the input processor. The input processor reads one line from input file. Each level of processors stores at its input side only minimal amount of data in order to comply with its superior processor. The assignment to the internal TeX registers, setting meanings of control sequences etc. are done at main processor level and the changing of these values can do influence of behavior of another processors (\endlinechar, \catcode, \def etc.).

-

Taking the example (following the edit), I'll start giving a very detailed view of the first couple of lines then move on a bit more rapidly. Dan has noted the fact that there is a bit of processing to normalise 'lines': I'm going to assume we can move on to the char-by-char reading of each line.

The bottom line here is that TeX reads the input from the beginning, working one char at a time to do tokenization. (Line-by-line stuff is as already noted needed to normalise line ends but isn't normally a concern at the 'TeX end'.) Each token is then processed further as appropriate.

## Unit A

The first line starts with a %, which TeX reads and tokenizes as a comment char. That means that it skips the rest of the line.

The second line starts with \, which is the escape char. TeX therefore keeps reading to find a control sequence: either a single non-letter or one or more 'letter' characters. That's actually done one at a time, but again let's skip to the result: a token called \def. (This is followed by a \, which is left alone for the moment: at this stage what's important is that it's not a letter so terminates the formation of a control word.) TeX now looks up a definition for \def to see what to do: it might be expandable, it might be executable, it might be an implicit char (with say \let\foo=a), or of course it might be undefined. In this case, it's a primitive that is executed. The \def primitive needs to be followed by a token to be defined, possibly an parameter text and then a replacement text. TeX therefore needs to find these, which means more tokenization.

The first thing after \def is \ as already noted. This starts a control word, so TeX once again builds one up a character at a time: it finds \aa terminated by [. So \def will define a macro called \aa. TeX now tokenizes [ and as isn't a start-group token, is becomes the first char of a parameter text. TeX works along, tokenizing #, 1 and ] similarly before it comes to {. This is a start-group token, so the parameter text is complete and is [#1]. Thus \aa will be defined such that it must be followed by a [ (catcode 12), then a variable part (#1) then a ] (catcode 12). TeX is now constructing the replacement text for \aa. It's seen the { and now starts tokenizing the content. There is a brace-matching requirement here, so we have to remember that each token TeX reads might be } or equivalent, but that no expansion is going on. Thus \aa ends up with replacement text a's value: #1 where #1 is a place-holder for whatever comes between the [ and ] required when \aa is used.

After the } is a space (end-of-line converted to a space by TeX). As we are in vertical mode, the space does nothing and so we can move on. The remaining definition lines can be analysed in the same way: each is read a char at a time with tokenization, execution, etc., but that is hopefully clear and pretty tedious to write out!

After the line defining \dd there is a blank line, which TeX converts to a token called \par which is inserted and executed (I'm assuming there has been no code before the first line here: \par could also be a macro to be expanded). We are in vertical mode so the \par primitive (which I'm assuming) doesn't do anything significant.

## Unit B

Unit B starts again with a comment line: I'll skip that one and future comment lines. TeX then finds a \ again and after a bit of work has the token \expandafter which it looks up. This is an expandable token which causes TeX to skip over the next token and to (try to) expand the following one. To do that, TeX obviously has to find the next two tokens, which is does: both turn out to be \expandafter. At this stage life gets a little more fun. As the new token to be dealt with is also expandable, the process continues. You have a chain:

\expandafter\expandafter\expandafter\expandafter
\expandafter\expandafter
\expandafter
\aa\dd


which is you read it carefully results in TeX getting from that very first \expandafter to \dd. Now, \dd is a macro with no parameters but with a replacement text, and so TeX does exactly one expansion, replacing \dd by \cc and effectively giving us

\expandafter\expandafter\expandafter\aa\cc


(follow the expansion carefully to see this!).

(Note: in the above I've ignored the line endings. TeX has converted line ends to spaces, s mentioned earlier, and after control words TeX skips spaces. Thus they don't 'count' for working out what the next token is.)

TeX has already tokenized the above as part of the first \expandafter chain, so there is no question about tokens here. We have another \expandafter, so the same process is repeated, this time finding \cc which again is a macro so is replaced, giving us effectively

\expandafter\aa\bb


There is still an \expandafter, so yet again a replacement takes place to give

\aa[Hi]


TeX now has to expand \aa, but this time there is a parameter text to allow for. Thus TeX matches up the input with the requirements: there is a [ with catcode 12, there is 'some stuff' (Hi!) then there is a ] with catcode 12. TeX now inserts the replacement text for \aa with #1 replaced by Hi!, so we have

a's value: Hi!


The letter a is just a letter: reading it forces TeX to switch to horizontal mode. TeX then inserts the \everypar token parameter, which is empty here, then starts collecting material to build a paragraph. As everything is now 'text', nothing 'new' happens until we get to the empty line. This inserts a \par token, which again is the primitive. As we are in horizontal mode this will start the paragraph-building algorithm. That's a topic on it's own: for the moment, we can I hope take it that TeX builds a paragraph inserting various skips, checks that the paragraph will fit on the current page without breaking, and as it does adds it to the 'current page' material. It doesn't add it to the PDF/DVI yet.

## Units C and D

These are very similar to unit A. Exactly the same analysis applies except there are fewer rounds of expansion. As I've noted above, each time \expandafter is expanded we can view the input as 'rewritten' and 'simplified' as that is basically what does happen. As such, other than being less complex there is nothing new to say here.

## Last line

The last instruction here is bye. This is a tidy-up operation which finishes off the run. In particular, it will ensure that any material for the 'current page' is actually shipped out before finalising the DVI/PDF file. Thus with the short demo here this is the only place where any \shipout will occur. The plain TeX output routine is quite simple, but it does add for example a page number to the current page. Thus \bye is again probably best analysed on its own.

-