The LaTeX lexer lemma
Every list of LaTeX tokens (tokOK
) reads back from its rendering: lex (render ts) = some ts. The proof goes token by token: each token reads back from its spelling
whatever follows it, as long as what follows does not extend it (Sep
), and the
renderer writes a space exactly where a following token would extend the previous
one.
Characters
Balanced raw text
JSON strings
Numbers
def spOK : List Char → Bool
A spelling skipSp
stops at: its first character is not white space and not \,
or it is \ followed by something other than a spacing command.
def clash : List Char → List Char → Bool
Two spellings differ within the first one’s length.
theorem sciExp_pre (P Y : List Char) (h1 : spOK P = true) (h2 : clash "\\times".toList P = true) :
sciExp (P ++ Y) = none
No scientific tail after a spelling that skipSp
stops at and that is not \times.
theorem sciExp_none {Z : List Char} (h : dropP "\\times".toList (skipSp Z) = none) : sciExp Z = none
No scientific tail where \times does not come first.
theorem sciExp_tail (e : Int) (X : List Char) :
sciExp (timesTen ++ (Number.printInt e ++ '}' :: X)) = some (e, X)
The printed scientific tail reads back as its exponent.
def NumSep (X : List Char) : Prop
What may follow a number: nothing that extends it, and not a scientific tail.
theorem lexSigned_num (n : JNum) (hn : n.WF) (X : List Char)
(h : lexNum sciExp (numChars n ++ X) = some (.num n, X)) :
lexSigned sciExp (numChars n ++ X) = some (.num n, X)
A number token reads back with its sign: a printed - starts a negative number.
Character classes
theorem letter_facts {c : Char} (h : isLetter c = true) :
isDig c = false ∧ c ≠ '\\' ∧ c ≠ '"' ∧ c ≠ '-' ∧ c ≠ ' ' ∧ c ≠ '\n' ∧ c ≠ '\t' ∧ c ≠ '\r' ∧
c ≠ ';' ∧ c ≠ ':' ∧ c ≠ '!'
A letter is none of the characters the lexer dispatches on.
Greek names
Tokens
def kwOK : Kw → Bool
LaTeX keywords: the ones with a LaTeX spelling, except \times, which the printer
writes only before a bracket (TN
: after a number, \times 10^{…} would be its
scientific tail).
def Sep (t : Tok) (X : List Char) : Prop
What may follow the spelling of t: nothing that extends it.
Spaces
One token
\times
theorem sciExp_times (S W : List Char) (hS : S = [] ∨ S = [' '])
(hW : (∃ r, W = '[' :: r) ∨ (∃ r, W = '&' :: r) ∨ (∃ r, W = '\\' :: '\\' :: r)) :
sciExp (tokChars (.kw .times) ++ (S ++ W)) = none
\times before a bracket, & or a row break, with or without a space: no 10
follows it, so it is no scientific tail.
Token lists
def TN : List Tok → Prop
A \times is followed by nothing, the bracket of a region’s next bound pair, & or
a row break: never by a number, so no number before it reads \times 10^{…} as its
scientific tail.
def TokL (ts : List Tok) : Prop
The tokens of the lexer lemma: LaTeX tokens, and \times where TN
allows it.
theorem TN_sep (k : Kw) (hk : k = .amp ∨ k = .nl) (b : List Tok) (hb : TN b) : TN (.kw k :: b)
& or a row break in front of a list.
theorem TN_app_sep (k : Kw) (hk : k = .amp ∨ k = .nl) : ∀ (a b : List Tok), TN a → TN b →
TN (a ++ .kw k :: b)
A list, then & or a row break and another.
theorem lexOne_tokL (t : Tok) (ht : tokOK t ∨ t = .kw .times) (X : List Char) (hX : Sep t X) :
lexOne (tokChars t ++ X) = some (t, X)
One token of a TokL
list, at the front of the input.
theorem lex_render (ts : List Tok) (h : TokL ts) : lex (render ts) = some ts
The LaTeX lexer lemma: a list of LaTeX tokens reads back from its rendering.