Chapter 1 exercises¶

You build two things this chapter:

The Pebble lexer (E1–E5): the hand-written, on-demand lexer that every later chapter's pebblec runs first. The contract is the Lexer class in pebble/include/pebble/Lex/Lexer.h (constructor plus Token lex()), the token model is Token.h, and the behavior is the lexical grammar of the Pebble specification §3 with the dump format of §14.1. Your code goes anywhere under pebble/lib/Lex/src/ (switch lexer); it starts with a Lexer.cpp whose lex() stops with TODO(ch01): E1-E5 ….
The comparison lab (L1–L7): one regex front end with four matching back ends, three minimizers and ★ a generated table-driven Pebble lexer. It is specified in full in labs/ch01-regex/SPEC.md; the last section of this page orders the work.

./course test 1                                              # builds, then runs every ch01 test
ctest --preset linux -L '^ch01$' -R 'PebbleLexer' --output-on-failure   # the lexer only (macOS: --preset macos)
build/linux/bin/ch01-lexdump tests/ch01/Inputs/fib.pbl       # your tokens, values and diagnostics
build/linux/bin/pebblec --emit=tokens tests/ch01/Inputs/fib.pbl         # the official §14.1 dump

Provided: the token kinds and their names and spellings (tok::getTokenName, tok::getSpelling, tok::isKeyword, and tok::getKeywordKind, a linear scan you may use or replace), printToken, lexFile (which calls your lex() until eof), the SourceManager and DiagnosticEngine, the ch01-lexdump tool, and the corpus tests/ch01/Inputs/*.pbl with golden dumps *.tokens. The goldens were produced by the reference lexer and checked against an independent Python lexer (tools/course/lib/pebble_lex.py) on every corpus file and 3000 random inputs.

Before you start, every ch01.PebbleLexer.* test and ch01.lit fail with TODO(ch01): E1-E5: implement the Pebble lexer (Lexer::lex). The tests are grouped by exercise in tests/ch01/unit/LexerTest.cpp, so you can work through them in order.

Stuck? Work through the hints in order. The reference solution is in solutions/pebble/lib/Lex/ (one possible design); only look at it after you pass the tests, or after an honest hour.

E1 · The loop: whitespace, identifiers, keywords, punctuators, eof¶

Contract: Token Lexer::lex() · Spec: §3.1, §3.2, §3.6 · Tests: ch01.PebbleLexer.EmptyFileIsJustEof, EofForever, KeywordsAndIdentifiers, EveryKeywordRoundTrips, EveryPunctuatorAlone, LocationsAreLineAndByteColumn · Lessons: 1.5 (Algorithm 1.5.6), 1.8

Each call skips whitespace (space, tab, \r, \n), then returns one token: an identifier [A-Za-z_][A-Za-z0-9_]* or one of the 21 keywords, or an operator or punctuator. At the end of the buffer it returns eof with an empty spelling at the end offset, and keeps returning it on every later call.

Requirements: Kind, Loc (the first byte of the spelling) and Spelling (a string_view into the source buffer, never a copy) are set on every token. Keywords are case-sensitive (While is an identifier). Locations are line and byte column, both 1-based; the SourceManager computes them from the offset, so you only need the right offset.

Hint 1 — where to start

Cur points at the next byte and BufferEnd at a NUL one past the last byte. Write a small makeToken(Kind, Start) that sets the location from Start, the spelling from [Start, Cur), and returns. Then the main loop is a switch on *Cur (Lesson 1.5 §2, Algorithm 1.5.6). Do not use the NUL at BufferEnd as the end-of-file test: a NUL byte can appear inside a file (E5).

Hint 2 — the key idea

Scan the whole identifier first, then decide whether it is a keyword: one lookup on the finished spelling, not a keyword check per character. Any of Lesson 1.8's methods works; the reference switches on the length first (Algorithm 1.8.8), because Pebble's keywords have lengths 2 to 8 and at most 6 share a length.

Hint 3 — a design sketch

A switch (*Cur) with one case group for identifier starts, one for digits (E3), one for " (E3–E4), one for / (comment or slash/slashequal), and one case per punctuator first character. EveryPunctuatorAlone walks every token kind with a fixed spelling, so a missing punctuator shows up by name. The most common bug: returning eof once and then reading past BufferEnd on the next call (EofForever).

Done when: the six E1 tests pass.

E2 · Maximal munch¶

Spec: §3.6 (the maximal-munch rule and its examples) · Tests: ch01.PebbleLexer.MaximalMunchFromTheSpec, MaximalMunchMore, FloatNeedsDigitsOnBothSides; lit munch.test, all-tokens.test · Lesson: 1.6 (Definition 1.6.2, Algorithm 1.6.5)

Every operator is the longest punctuator spelling that starts at the current byte: a<<=b is << = (Pebble has no <<=), p-->q is - ->, ... is .. ., x&-1 is the wrapping operator &-. Numbers obey the same rule with one extra condition: a . belongs to a float only if a digit follows it, so 1..2 is 1 .. 2, 1. is 1 ., and 1.e5 is 1 . e5.

Requirements: no backing up by more than one byte anywhere in the Pebble lexer: the only case where the longest candidate fails is 1. followed by a non-digit, and one byte of lookahead (Cur[1]) decides it without consuming (Proposition 1.6.8 is why this is enough).

Hint 1 — where to start

List the punctuators by first character (§3.6): for each first character, which second characters extend it, and does any three-character token exist? Write each case as "consume one byte, then look at the next".

Hint 2 — the key idea

Maximal munch on a fixed set of spellings is a trie walk (Lesson 1.8, Definition 1.8.3) that stops at the last accepting node. Because every prefix of a Pebble punctuator is itself a punctuator, the last accepting node is always the deepest node you reach: no backup is needed.

Hint 3 — a design sketch

A tiny helper bool consumeIf(char C) that advances Cur when *Cur == C makes each case two or three lines: case '&': if (consumeIf('&')) return make(ampamp); if (consumeIf('+')) …. For .: .. wins over . always; a digit before . goes to the number scanner (E3), which looks at Cur[1] before it takes the ..

Done when: the E2 tests and munch.test pass.

E3 · Literals and their values¶

Spec: §3.3, §3.4, §3.5 (escapes) · Tests: ch01.PebbleLexer.IntegerValues, IntegerErrors, FloatValues, StringEscapes, StringKeepsUTF8, EscapeErrors, StringAtEof; lit numbers.test, err-numbers.test, err-escapes.test, err-eof-string.test · Lesson: 1.5

Integers are decimal, 0x hex or 0b binary, with _ separators after the first digit; floats are decimal digits . digits with an optional exponent, or digits with an exponent. Strings are "…" with the escapes \n \t \r \\ \" \' \0 \u{h…} (1–6 hex digits, a Unicode scalar value: not a surrogate, at most 10FFFF). Fill IntValue, FloatValue (correctly rounded) and StringValue (escapes decoded, delimiters removed).

Requirements (errors and recovery):

A digit run is scanned maximally as [0-9A-Za-z_]* after the first digit (plus .digits and an exponent for floats), then validated. An invalid run (12ab, 0x, 0x_1, 0b2, 1e, 0X1F) is one int_literal token with E0106 at its first byte; an integer above $2^{64}-1$ is one token with E0105. Values of bad literals are unspecified.
9223372036854775808 ($2^{63}$) is a valid token: the lexer does not know about unary minus (Sema checks the range).
A float too large for a double is inf, not an error (§3.4).
A bad escape reports E0104 at the backslash and is skipped (\u{…} through its } when there is one); the string continues and remains one token.
A string that reaches the end of the file reports E0102 at the opening quote and ends there. A string that reaches a line break reports E0108 at the line break with a note "string started here" at the opening quote, and ends before the line break (E0108 is also for interpolated strings, E4).

Hint 1 — where to start

Numbers: scan the maximal run first, then decide (prefix? which digits are legal? a . followed by a digit? an exponent?). Errors then come out naturally, one per literal, and the token covers the whole run, which is what IntegerErrors checks. Strings: scan to the closing quote, decoding escapes into StringValue as you go.

Hint 2 — the key idea

Do not convert floats yourself: correct rounding (FloatValues compares bit-exactly, including subnormals) is hard. Strip the _ separators and call a correctly rounding library routine; llvm::StringRef::getAsDouble is one (portable, unlike std::from_chars for double on older standard libraries). For integers, accumulate in uint64_t and detect overflow before multiplying (__builtin_mul_overflow or a comparison with (UINT64_MAX - d) / base).

Hint 3 — a design sketch

lexNumber(Start), lexString(Start), lexEscape(Out) as separate functions (or files). \u{…} encodes its code point as UTF-8 into StringValue (1–4 bytes, Lesson 1.9 Definition 1.9.2). Put the string scanning in a function that returns "why it stopped" (closing quote, \(, line break, end of file): E4 reuses it for the pieces of an interpolated string.

Done when: the E3 tests and the four lit tests pass.

E4 · Modes: nested comments and string interpolation¶

Spec: §3.1 (nested block comments), §3.5 (interpolation, the string_head/string_middle/string_tail table) · Tests: ch01.PebbleLexer.NestedCommentsAreTrivia, UnterminatedComment, InterpolationTableFromTheSpec, InterpolationValues, NestedInterpolation, ParenOutsideInterpolationIsPunctuation, UnterminatedInterpolation, StringErrorsRecoverAtLineBreak; lit comments.test, interpolation.test, err-comment.test, err-interp.test, err-newline.test, fib.test · Lesson: 1.7 (Definition 1.7.2, Algorithm 1.7.7, Theorem 1.7.13)

/* … */ comments nest (/* a /* b */ c */ is one comment), and // runs to the end of the line; both are trivia. In a string, \( starts an interpolation: the lexer returns the text so far as string_head (spelling "a\(), then ordinary tokens, until the ) that matches the \(; that ) resumes the string, which continues as string_middle ()b\() or ends as string_tail ()b"). Interpolations nest, and parentheses inside them are ordinary punctuation.

Requirements: use the InterpolationDepth stack of Lexer.h: push 0 at \(; ( increments the top; ) with a non-zero top decrements it and is r_paren; ) with top 0 pops and resumes the string. A ) with an empty stack is r_paren. Errors:

an unterminated comment reports E0103 at its /* and ends at the end of the file (the comment's bytes are trivia of eof);
the end of the file inside an interpolation reports E0107 at the end (once, however deep) and clears the stack;
a line break inside a string piece reports E0108 (as in E3), ends the piece there, and pops the interpolation that piece belonged to, so lexing continues in the enclosing mode: "a\(x)b⏎z gives string_head, x, string_tail (spelling )b), then z.

Hint 1 — where to start

Nested comments first: a depth counter inside the comment scanner (Lesson 1.1, Corollary 1.1.17 says why no regular expression can do it). Then interpolation without nesting, then nesting. NestedInterpolation has a string inside an interpolation inside a string; trace it on paper with the stack before you run it.

Hint 2 — the key idea

The only place the stack changes what a byte means is ). At ) you are either in normal mode (it is punctuation) or it closes an interpolation (you are back in the middle of a string). So the E3 string scanner needs two entry points: after " (start of a literal or head) and after the closing ) (start of a middle or tail); both use the same loop and return which delimiter ended the piece. The piece kind is then a 2 × 2 table: (started at " or )) × (ended at " or \().

Hint 3 — a design sketch

lexStringPiece(Start, StartedAtQuote) returns the token; on \( it pushes 0 and returns string_head or string_middle. In the ( and ) cases of the main switch, look at InterpolationDepth. The bug the tests catch most: forgetting that a " inside an interpolation starts a new string whose own \( pushes again ("o \("i \(d) e")"); and popping on E0108 in the wrong place, which makes the next line lex as a string.

Done when: the E4 tests and six lit tests pass (fib.test is a whole program).

E5 · Invalid input, UTF-8 and lossless trivia¶

Spec: §3 (source text is UTF-8; identifiers are ASCII) · Tests: ch01.PebbleLexer.InvalidCharactersRecover, NulByteIsNotEndOfFile, NonASCIIIdentifier, NonASCIINonIdentifierIsOneUnknownToken, InvalidUTF8, CommentsMayHoldAnyBytes, TriviaCounts, CorpusIsLossless, CorpusCoversEveryTokenKind, RandomInputsAreLosslessAndTerminate; lit err-chars.test, utf8.test, err-utf8.test, pebblec-*.test · Lessons: 1.9 (Definitions 1.9.3–1.9.5, Algorithm 1.9.8), 1.10 (Definition 1.10.1, Algorithm 1.10.6)

The lexer never stops early and never loses a byte.

Requirements:

Trivia. LeadingTrivia is the number of whitespace and comment bytes between the previous token (or the start of the file) and this token; eof carries the trailing trivia. Concatenating trivia and spelling of every token, eof included, gives back the file exactly (Definition 1.10.1).
Invalid ASCII. A byte that starts no token (@, #, $, `, \, NUL, other control characters) is one unknown token with E0101 at it. A NUL byte is not the end of the file.
UTF-8. Outside comments, the lexer decodes UTF-8 strictly (Table 3-7 of the Unicode standard: no overlongs, no surrogates, nothing above U+10FFFF). Each maximal subpart of an ill-formed sequence (Definition 1.9.4) reports E0109 with the byte in hex; outside strings it becomes one unknown token, inside a string it is dropped from StringValue and the string continues. Comments may contain any bytes.
Non-ASCII characters. A well-formed non-ASCII character that is XID_Start (or, after an identifier's first byte, XID_Continue) is swallowed into the identifier with E0110 at the character (recovery: café is one identifier, one error). Any other non-ASCII character is one unknown token with E0101. The UAX #31 tables are generated for you in the reference solution; you may copy solutions/pebble/lib/Lex/src/XIDTables.inc and its generator, or write your own from the Unicode Character Database (Algorithm 1.9.9).
Termination. Every non-eof token has a non-empty spelling, so the number of tokens is at most the file size plus one.

Hint 1 — where to start

Count trivia by remembering where the skipping began: Start = Cur before the whitespace/comment loop, and LeadingTrivia = TokenStart - Start. Then make the default: case of your switch handle every byte you do not recognize, with one branch for bytes ≥ 0x80 (decode) and one for the rest (E0101).

Hint 2 — the key idea

Write the decoder once, as "decode one scalar at Cur, or tell me the length of the maximal subpart that is ill-formed" (Algorithm 1.9.8), and use it in three places: the default: case, the identifier loop (to see whether a non-ASCII character continues the identifier) and the string scanner. The random test (RandomInputsAreLosslessAndTerminate) combines every error with every mode switch; it fails on the first non-lossless or non-terminating input and prints it.

Hint 3 — a design sketch

decodeUTF8(Ptr, End) -> {CodePoint, Length, Valid}; isXIDStart(CP), isXIDContinue(CP) as binary searches over sorted ranges. In the identifier loop, the ASCII test comes first (fast path), and only a byte ≥ 0x80 calls the decoder. The bug the tests catch most: an unterminated comment or string whose bytes are neither in a token nor in trivia (the concatenation comes out short), and the diagnostic for a UTF-8 error inside a string reported at the string's start instead of at the byte.

Done when: every ch01.PebbleLexer.* test and ch01.lit pass, and pebblec --emit=tokens prints the golden dump for every error-free corpus file.

Lab · One regex engine, four back ends¶

Spec: labs/ch01-regex/SPEC.md (requirements R1–R9, the contract include/regexlab/Regex.h, the pattern syntax and what every test checks) · Your code: labs/ch01-regex/src/ (switch regex) · Tests: ch01.Regex*, ch01.MinDFA.*, ch01.TableLexer.*, ch01.lab.bench-smoke

Step	What	Lessons	Tests
L1	pattern parser and Thompson's construction	1.1	`RegexSyntax.*`
L2	Pike VM (Thompson's NFA simulation)	1.2	`RegexEngines.`, `RegexRandom.`, `RegexPathological.*`
L3	subset construction and the DFA matcher	1.2	the same, with `Backend::DFA`
L4	Brzozowski derivatives, memoized	1.3	the same, with `Backend::Derivative`
L5	minimal DFA size: Hopcroft; ★ Moore and Brzozowski	1.4	`MinDFA.*`
L6 ★	lazy DFA with a bounded cache	1.2	`RegexLazyDFA.*`; run `ch01-regexbench`
L7 ★	generated table-driven lexer, priority and maximal munch	1.5, 1.6	`TableLexer.*` (needs E1–E5)

The spec's milestones give the order, the measurement table to fill in, and three levels of hints. Until you reach L6, your eager DFA can stand in for Backend::LazyDFA. The stub messages name the step each failing test belongs to: TODO(ch01): L1-L4 …, L5 …, L7 (star) ….

Done when: ./course test 1 passes (the ★ tests included, or knowingly skipped), and you have filled in the measurement table of the spec and compared it with the comparison tables of Lessons 1.2 and 1.5.