Loading page…
Master the fundamental concepts of lexical analysis through this focused micro-challenge.
You have read the whole brief, and the concepts above stay free on every task. Writing and running the code needs a plan.
Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.
Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.
How it worksA deterministic finite automaton (DFA) is a state machine that reads input symbols and transitions between states. Lex/Flex compiles regex patterns into DFAs; hand-written lexers implement the same logic implicitly. GCC's cpp and Clang's character classifier tables are DFAs in disguise.
Each state represents progress in recognizing a pattern. From state S0, digit goes to S_NUMBER; letter goes to S_IDENT; / might go to S_DIV or S_COMMENT if next char is /. Accept states emit tokens; trap states report errors.
cLoading…
Production compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.
You will build an explicit DFA transition table and use it to drive token recognition. This exercise requires encoding lexer states as integers, defining transitions for digits, letters, and operators, and emitting tokens when accept states are reached.
Recognise integer and floating-point literals with a table-driven DFA, and print the path the automaton takes so every transition is visible.
One candidate literal per line (no spaces inside). Blank lines are ignored.
Classify each character into one of five classes: digit 0-9, sign + -, dot ., exp e E, other (anything else). Use exactly these nine states, named as shown:
| State | Meaning (what has been read so far) | Accepts as |
|---|---|---|
START | nothing yet | - |
SIGN | a leading + or - | - |
INT | optional sign, then one or more digits | INT |
DOT | optional sign, then a . with no digits before it | - |
POINT | digits followed by . (like 2.) | FLOAT |
FRAC | at least one digit after the . | FLOAT |
EXP | a mantissa followed by e/E | - |
EXP_SIGN | … then + or - | - |
EXP_INT | … then one or more exponent digits | FLOAT |
A leading sign is only allowed at the very start, and one more is allowed right after e/E. An exponent needs a mantissa with at least one digit (INT, POINT or FRAC), so .e5 is rejected. Any transition not implied by the table is missing, and a missing transition rejects the input immediately.
One line per input, starting with the input itself and the states visited, beginning with START:
cLoading…
REJECT at N 'c': there is no transition for character c at 1-based position N. The trace lists the states reached before it.REJECT at end: the input was consumed but the final state is not accepting.Finish with accepted=A rejected=R.
Input:
cLoading…
Output:
cLoading…
next_state[state][char_class], with a sentinel for "no transition". No per-character if chains.Hidden tests include 2., .5, +.5e+10, ., -, 1e5.0, 12a, and uppercase E.