CS374: Principles of Programming Languages - The Lexer (100 Points)

Purpose, Task, and Criteria

Purpose: To turn the class tokenizer into the first permanent component of your language pipeline: a reusable Lexer with a stable peek/advance/expect interface that the Parser and the team project import unchanged.

Task: Specify an ordered token grammar. Build a reusable Lexer component with peek/advance/expect, string escapes, and a configurable token specification, either hand-rolled in Python or in the generator-toolchain direction (Flex or PLY). Then add positioned error reporting and a full test suite.

Criteria: I assess your work on a correctly ordered token spec, an idempotent side-effect-free Lexer interface, and precise error reporting with a full test suite, weighted 30/40/30 across the three parts. The rubric applies the same way to whichever direction you choose. The full breakdown is in the rubric below.

Assignment Goals

The goals of this assignment are:
  1. To specify a complete token grammar for the project language using ordered regular-expression rules
  2. To harden the class tokenizer into a reusable Lexer component with peek, advance, and expect interface methods
  3. To implement string literals with escape sequences and JSON-configurable token specifications
  4. To report lexical errors with precise line and column positions and support both fail-fast and collect-all error modes
  5. To deliver a fully tested component that the parser assignment and team project will import unchanged

Background Reading and References

Please refer to the following readings and examples offering templates to help get you started:

The Assignment

This assignment turns the class tokenizer into a component: the first permanent piece of your language pipeline. A component is a module that other code imports and uses without changing it. The Parser assignment imports your Lexer unchanged, and your team project ships it. Every design decision you make here carries forward, so document your interface carefully. Build in the scaffolded steps below, and test after each step before you move on.

Part 0: Before You Start (Tokens and Scanning, 10 points)

Do this part first, before you write any lexer code. It takes about twenty minutes on paper.

A scanner (the program that splits source text into tokens) is easy to write for input that behaves and interesting to write for input that does not. The awkward cases below are the ones this assignment turns on, so form an opinion about them before you implement anything.

  1. Hand-tokenize the line x = 12 + foo(3) into a token stream. Give each token a type and a value. Then predict what your scanner should do with 12foo, and with = = versus ==.
  2. Write the regular expressions your lexer would use for three token classes. Identify one pair whose patterns overlap. Which rule wins, and why does order matter?

Bring your answer for 12foo: one token, two tokens, or an error. Bring it even if you are not confident. Disagreement about these cases is the point, and Part 1’s ordered TOKEN_SPEC is where your answer becomes a design decision you have to live with.

Choose Your Direction

This is one assignment with one deliverable and one rubric. You build it in one of two directions:

  • Hand-rolled lexer (the core direction). Build the Lexer yourself in Python on top of the re module, following Parts 1-3 below. Most students take this direction, and the step-by-step scaffolding assumes it.
  • Generator-toolchain lexer (Flex or PLY). Build the same component with a lexer generator: Flex (for C) or PLY (for Python). These tools produce the scanners inside major compilers. This direction replaces the vehicle of Parts 1 and 2 (the TOKEN_SPEC list, the tokenize generator, and the hand-written class internals) with a generator specification. The interface contract, Part 3’s error, position, and test requirements, the deliverable structure, and the rubric all apply the same way. See The Generator-Toolchain Direction below for the full mapping.

In either direction you submit a token specification, a working lexer component behind the peek/advance/expect contract, and positioned errors with a full test suite. Both directions are graded on the same 30/40/30 rubric.

Getting Started

Environment and Setup

You need Python 3.10 or newer (python --version; record the version in your readme) and only the standard library (re, json, dataclasses). This assignment grows the class tokenizer, or the finditer mini lexer you built in the Regex assignment, into a component. Start from whichever of those you trust more. Create the deliverable files up front:

lexer.py             # the Lexer module
token_spec.json      # default token specification (Step 2d)
token_spec_alt.json  # alternate dialect (Step 2d)
test_lexer.py        # the test suite

Your First 30 Minutes

  1. Define the Token dataclass from Step 1b.
  2. Write a TOKEN_SPEC with just six rules: WHITESPACE, LET, IDENT, EQ, INT, SEMICOLON.
  3. Write the tokenize generator from Step 1c and run it on the worked example:
for tok in tokenize("let x = 42;"):
    print(tok)

Compare your output against the six-token listing in Step 1c, including line and column numbers. Then feed it lets x = 42; and confirm that lets comes out as a single IDENT. If it comes out as LET + IDENT("s"), your keyword pattern is missing its boundary check. It is far better to learn that now with six rules than later with twenty-nine.

Suggested Pacing

See the course schedule for the assigned and due dates. Your starting point is the mini lexer you built in the Regex Workshop lab and grew in the Regex assignment. This assignment turns it into a permanent pipeline component. The Finite Automata Simulators lab runs alongside the start of this window. It is short by design, so plan its two to three hours into your week:

Checkpoint You should have
On assignment Token dataclass and a six-rule tokenize generator working (grown from your mini lexer)
Checkpoint 1 Parts 1-2a: full TOKEN_SPEC passing all maximal-munch cases, and the core Lexer class with peek/advance/expect working
Checkpoint 2 Parts 2b-2c: string escapes and JSON configuration (both dialects)
Due date Part 3 error modes with precise positions and the full test suite complete; readme written; ZIP assembled and submitted

Part 1: Token Specification (27 points)

Why Order Matters

A lexer built on regular expressions applies its rules in order and uses maximal munch: at each position, it matches the longest string it can. Two rules produce bugs if you order them wrong:

  • If IDENT appears before IF, then if will be tokenized as an identifier named "if".
  • If LT (<) appears before LE (<=), then <= will be tokenized as LT followed by EQ.

The correct ordering is keywords before identifiers, and longer operators before their prefixes.

Step 1a: Define the TOKEN_SPEC

Define a TOKEN_SPEC list of (token_name, regex_pattern) pairs. It must cover, at minimum, every token type in the table below. Write every pattern as a raw string (r"...").

| Token Name | Example Lexemes | Notes | |————|—————-|——-| | COMMENT | # this is a comment | Match to end of line; to be skipped | | WHITESPACE | ` , \t, \n | Skip; track newlines for line counting | | STRING | “hello”, “a\nb” | Double-quoted; see Part 3 for escapes | | FLOAT | 3.14, -0.5 | Must appear before INT | | INT | 42, 0 | Non-negative; sign handled by unary minus | | IF | if | Must appear before IDENT | | ELSE | else | Must appear before IDENT | | WHILE | while | Must appear before IDENT | | LET | let | Must appear before IDENT | | PRINT | print | Must appear before IDENT | | TRUE | true | Must appear before IDENT | | FALSE | false | Must appear before IDENT | | AND | and | Must appear before IDENT; used by the Parser's and_expr | | OR | or | Must appear before IDENT; used by the Parser's or_expr | | NOT | not | Must appear before IDENT; used by the Parser's not_expr | | FUN | fun | Must appear before IDENT; used by function definitions | | IDENT | foo, my_var, x1 | Letter or underscore, then letters/digits/underscores | | LE | <= | Must appear before LT | | GE | >= | Must appear before GT | | EQEQ | == | Must appear before EQ | | NEQ | != | Must appear before BANG | | BANG | ! | Logical negation; must appear after NEQ | | ARROW | -> | Return-type annotation; must appear before MINUS | | EQ | = | Assignment | | LT | < | | | GT | > | | | PLUS | + | | | MINUS | - | | | STAR | * | | | SLASH | / | | | LPAREN | ( | | | RPAREN | ) | | | LBRACE | { | | | RBRACE | } | | | SEMICOLON | ; | | | COLON | : | Type annotations, e.g. let x: Num = 42; | | COMMA | ,` | Parameter and argument lists |

Maximal-munch test cases you must pass: iffy -> IDENT("iffy") (not IF + IDENT("ffy")); <= -> LE (not LT + EQ); == -> EQEQ (not two EQs); whiles -> IDENT("whiles"); notable -> IDENT("notable") (not NOT + IDENT("able")); -> -> ARROW (not MINUS + GT); != -> NEQ (not BANG + EQ).

Step 1b: Token Dataclass

Define a Token dataclass (or namedtuple) with four fields: type (string), value (string, the raw lexeme), line (int), and col (int). The EOF token has type "EOF", value "", and the line and column of the last character consumed.

Step 1c: Baseline Tokenize Generator

Write a tokenize(source: str) -> Iterator[Token] generator. At the current position, it tries the TOKEN_SPEC rules with re.match, skips WHITESPACE and COMMENT tokens, and advances the position by the match length. Verify it against the provided test programs before you wrap it in a class.

Worked example, source "let x = 42;":

Token(LET,       "let", line=1, col=1)
Token(IDENT,     "x",   line=1, col=5)
Token(EQ,        "=",   line=1, col=7)
Token(INT,       "42",  line=1, col=9)
Token(SEMICOLON, ";",   line=1, col=11)
Token(EOF,       "",    line=1, col=12)

Step 1d: Lexing Theory Questions (in your readme)

Answer three written questions from the Tokens and Scanning session. They are graded within Part 1’s rubric row.

  1. Maximal munch, precisely. Your spec tokenizes <== as LE then EQ, not LT then EQEQ, and not three single-character tokens. State the two rules (longest match, then rule order) that force this outcome. Then give one input where the two rules would disagree about the result if you applied them in the other priority.
  2. Why keywords aren’t the lexer’s problem twice. iffy must lex as one IDENT, never IF + IDENT("fy"). Explain the two different mechanisms that can enforce this: rule ordering with boundary-aware patterns, versus lexing as an identifier and then reclassifying against a keyword table. Name one cost of each.
  3. The division of labor. let 42 = x; lexes without a single error. In one sentence per stage, state why the lexer must accept it and which later pipeline stage rejects it. Then say what this tells you about what a token stream does and does not promise.

Part 2: Lexer Class Implementation (36 points)

The Interface Contract

The parser will use exactly three methods:

Method Behavior
peek() -> Token Return the next token without consuming it. Idempotent: calling it ten times in a row must return the same token.
advance() -> Token Consume and return the next token. After calling advance, the next peek/advance returns the token after the one just returned.
expect(token_type: str) -> Token If the next token matches token_type, consume and return it. Otherwise raise LexError with the expected type, found type, and position.

At end of input, both peek and advance return the EOF token repeatedly. They never raise StopIteration or return None.

Step 2a: Implement the Lexer Class

class Lexer:
    def __init__(self, source: str, config_path: str = None):
        ...  # load config if provided, build token stream, initialize lookahead buffer

    def peek(self) -> Token: ...
    def advance(self) -> Token: ...
    def expect(self, token_type: str) -> Token: ...

Use an internal buffer that holds one token (the lookahead). When the buffer is empty, pull the next token from your generator and fill it. peek returns the buffer contents without clearing the buffer. advance returns the buffer contents and clears the buffer.

Step 2b: Verify Two Consumption Patterns

Show that a peek-driven loop and an advance-driven loop produce identical token streams:

# Pattern A: peek-driven
tokens_a = []
while lexer_a.peek().type != "EOF":
    tokens_a.append(lexer_a.advance())

# Pattern B: advance-driven
tokens_b = []
tok = lexer_b.advance()
while tok.type != "EOF":
    tokens_b.append(tok)
    tok = lexer_b.advance()

assert tokens_a == tokens_b, "Consumption patterns disagree!"

Step 2c: String Literals with Escapes

Extend the STRING pattern (or handle strings as a special case) to support these escape sequences:

Escape sequence Decoded value
\" double-quote character
\\ backslash
\n newline (ASCII 10)
\t tab (ASCII 9)

Store both the raw lexeme (e.g., "a\nb" with a backslash-n) and the decoded value (with a real newline) in the Token. An unterminated string is one that reaches end-of-line or end-of-file without a closing ". It must raise a LexError that points at the opening quote’s position, not at the end of input.

Worked example:

source: "hello\nworld"
raw lexeme:    "hello\nworld"   (14 chars including quotes)
decoded value: hello           (with a real newline between)
               world

Step 2d: JSON Configuration

Move TOKEN_SPEC to a JSON file with this structure:

{
  "comment_char": "#",
  "tokens": [
    ["COMMENT",    "#[^\n]*"],
    ["WHITESPACE", "[ \t\n]+"],
    ["STRING",     "\"(?:[^\"\\\\]|\\\\.)*\""],
    ...
  ]
}

Load and validate the config when Lexer.__init__ runs. Every pattern must compile: catch re.error and raise LexError with the offending pattern. Then show that the spec is configurable. Write a second JSON spec in which the comment character is // and the assignment operator is :=, and show the same Lexer class tokenizing a short program in that dialect.

Part 3: Error Handling, Positions, and Test Suite (27 points)

Step 3a: Precise Error Positions

Every LexError must include:

  • The line number (1-indexed) of the offending character
  • The column number (1-indexed) of the offending character
  • The offending text itself (the unrecognized character or the unterminated string lexeme)

Example message format: LexError at line 3, col 7: unexpected character '@'

Track the line number by counting the \n characters you consume. Track the column by resetting it to 1 after each newline.

Step 3b: Two Error Modes

Implement two modes, chosen at construction time with error_mode="fail_fast" (the default) or error_mode="collect_all":

  • fail_fast: raise LexError on the first unrecognized character.
  • collect_all: skip each unrecognized character and record its error, finish tokenizing, then raise a single LexErrorList that holds all the errors. The programmer sees every mistake in one pass instead of fixing them one at a time.

Step 3c: Test Suite

Build test_lexer.py with at least the test cases below. Each test must assert the token types in order and, for selected tokens, the value, line, and col.

Token type coverage (one test per type):

  • INT, FLOAT, STRING (with escape), IDENT, IF, ELSE, WHILE, LET, PRINT, TRUE, FALSE
  • All operators: PLUS, MINUS, STAR, SLASH, EQ, EQEQ, NEQ, LT, LE, GT, GE, LPAREN, RPAREN, LBRACE, RBRACE, SEMICOLON

Maximal-munch cases:

  • iffy -> single IDENT, not IF + IDENT
  • whiles -> single IDENT
  • <= -> LE, not LT + EQ
  • == -> EQEQ, not EQ + EQ
  • != -> NEQ, not two tokens

String escape cases:

  • "no escapes" -> value equals no escapes
  • "tab\there" -> value contains a real tab
  • "line\nbreak" -> value contains a real newline
  • "quote\"end" -> value contains a double-quote

Deliberate error programs (five required):

  1. A program with @: expect LexError at line 1, col ...
  2. An unterminated string "hello: expect LexError at the opening quote
  3. A program with $ in the middle: check position is mid-program, not line 1
  4. A collect-all run with two errors: verify both are reported
  5. A program with a valid token immediately after an error: verify recovery in collect-all mode

The Generator-Toolchain Direction (Flex or PLY)

In this direction, you build the same component with a lexer generator instead of a hand-rolled re loop. The generator does the maximal-munch machinery for you. Your job shifts to three things: write the rule specification correctly, wrap the generated scanner behind the interface contract, and prove the same properties with the same tests. The three parts above map onto this direction as follows.

Part 1 equivalent: the rule specification

Write a Flex .l file (or a PLY tokens/t_* module) that covers the full token table from Step 1a. The ordering discipline is the same. Generators resolve ties by rule order (Flex) or by function definition order and pattern length (PLY), so the same bugs await you if keywords trail IDENT or < precedes <=. Your specification must handle:

  • Numeric literals: integers and floats ([0-9]+\.[0-9]* and [0-9]*\.[0-9]+), with FLOAT tried before INT.
  • String literals in double quotes with \", \\, \n, \t escape sequences, decoded at scan time (in Flex, store the decoded string via strdup; in PLY, set t.value to the decoded text while keeping the raw lexeme available).
  • Identifiers vs. keywords: match [a-zA-Z_][a-zA-Z0-9_]* and check a keyword table, returning the keyword’s own token type for if, else, while, let, print, true, false. This is the generator idiom for “keywords before IDENT.” Your readme must explain why the keyword-table approach and the rule-ordering approach are equivalent.
  • Multi-character operators: <=, >=, ==, != as single tokens, listed so they win over their single-character prefixes.
  • Comments and whitespace: # to end of line, skipped; whitespace skipped with newlines counted (%option yylineno in Flex; track t.lexer.lineno in PLY).

The pass criteria are the same maximal-munch cases from Step 1a: iffy -> IDENT, whiles -> IDENT, <= -> LE, == -> EQEQ.

Part 2 equivalent: the component wrapper

The generated scanner hands you a next-token function: yylex() in Flex, lexer.token() in PLY. Your deliverable is still a component with the interface contract. Wrap the generated scanner in a Lexer class (PLY) or a small driver module (Flex) that exposes peek, advance, and expect with exactly the behaviors in the table above: an idempotent peek, EOF tokens forever at end of input, and a located LexError from expect on mismatch. Show the same two consumption patterns from Step 2b agreeing. In place of Step 2d’s JSON configuration, provide a second rule specification that implements the alternate dialect (// comments, := assignment), and show the same wrapper driving both. This meets the configurability requirement using the tools’ own configuration medium.

Part 3 applies unchanged

This direction requires precise line and column positions on every error, the fail-fast and collect-all modes, and the full test suite of Step 3c (token type coverage, maximal-munch cases, string escapes, and the five deliberate error programs), exactly as written. (In Flex, collect-all means your error rule records the offense and continues scanning rather than exiting.)

Where the toolchain goes next

Flex is one half of a pair. Its companion parser generator, Bison (or PLY’s yacc module), turns a context-free grammar with precedence declarations into an LALR parser. That half is deliberately out of scope here. It is the natural continuation of this direction, and the Parser assignment offers a matching generator-toolchain direction where your Flex/PLY scanner feeds a Bison/PLY grammar. Choosing the generator direction now sets you up well for that one, but the two choices are independent: you choose a direction assignment by assignment.

Deliverables

Submit a ZIP containing:

  • lexer.py: the Lexer module (importable with no side effects)
  • token_spec.json: the default token specification
  • token_spec_alt.json: the alternate dialect specification (// comments, := assignment)
  • test_lexer.py: the test suite with documented test cases
  • test_output.txt: the output of running python test_lexer.py (all tests passing)
  • readme.md: approximately one page documenting the Lexer interface for the parser author (future you), including the TOKEN_SPEC ordering rationale and the two error modes

List your Python version (python --version) so that I can reproduce your results.

Generator-toolchain direction: the deliverable structure is identical with the vehicle swapped. Submit the .l file (plus a Makefile that builds the scanner from scratch) or the PLY lexer module in place of the hand-rolled internals; the default and alternate-dialect rule specifications in place of the two JSON files; the wrapper exposing peek/advance/expect; the same test suite and test_output.txt; and a readme that also records your toolchain versions (flex --version, or your PLY version) and explains the keyword-table idiom.

Grading Breakdown

Component Points
Part 0: Tokens and Scanning 10
Part 1: Token Specification 27
Part 2: Lexer Class Implementation 36
Part 3: Error Handling and Test Suite 27
Total 100

Reflection Prompts

  • Which scanning rule (maximal munch or priority) caused you a real bug, and how did your tests catch it?
  • Which direction did you choose, and what did that choice make easier or harder than you expected? If you took the generator toolchain: what did Flex or PLY do for you that you would otherwise have written by hand, and what did it hide that you had to recover?
  • What about your lexer would you change if your language used significant indentation like Python?
  • The expect method was designed for the parser’s benefit. Explain why the parser needs expect rather than just calling advance and checking the type afterward.
  • If collaboration with a buddy was permitted, did you work with a buddy on this assignment? If so, who? If not, do you certify that this submission represents your own original work? Please identify any and all portions of your submission that were not originally written by you.
  • AI disclosure: list any generative-AI tools you used, for what, and how you verified the results (or state ‘none’).
  • Approximately how many hours it took you to finish this assignment (I will not judge you for this at all; I am simply using it to gauge if the assignments are too easy or hard)?

Submission

In your submission, please include answers to any questions asked on the assignment page, as well as the questions listed below, in your README file. If you wrote code as part of this assignment, please describe your design, approach, and implementation in a separate document prepared using a word processor or typesetting program such as LaTeX. This document should include specific instructions on how to build and run your code, and a description of each code module or function that you created suitable for re-use by a colleague. In your README, please include answers to the following questions:
  • Describe what you did, how you did it, what challenges you encountered, and how you solved them.
  • Please answer any questions found throughout the narrative of this assignment.
  • If collaboration with a buddy was permitted, did you work with a buddy on this assignment? If so, who? If not, do you certify that this submission represents your own original work?
  • Please identify any and all portions of your submission that were not originally written by you (for example, code originally written by your buddy, or anything taken or adapted from a non-classroom resource). It is always OK to use your textbook and instructor notes; however, you are certifying that any portions not designated as coming from an outside person or source are your own original work.
  • Approximately how many hours it took you to finish this assignment (I will not judge you for this at all...I am simply using it to gauge if the assignments are too easy or hard)?
  • Your overall impression of the assignment. Did you love it, hate it, or were you neutral? One word answers are fine, but if you have any suggestions for the future let me know.
  • Using the grading specifications on this page, discuss briefly the grade you would give yourself and why. Discuss each item in the grading specification.
  • Any other concerns that you have. For instance, if you have a bug that you were unable to solve but you made progress, write that here. The more you articulate the problem the more partial credit you will receive (it is fine to leave this blank).

Assignment Rubric

Description Pre-Emerging (< 50%) Beginning (50%) Progressing (85%) Proficient (100%)
Part 0: Before You Start - Tokens and Scanning (10%) The line is not tokenized and no token-class patterns are written The line is tokenized but tokens carry no types, or the awkward cases are not addressed The line is hand-tokenized with types and values and three patterns are written, but no overlapping pair is identified, or the 12foo and == cases are answered without reasoning x = 12 + foo(3) is hand-tokenized with a type and value per token; 12foo and = = versus == are each answered with a defended position; three token-class patterns are written and one overlapping pair is identified with a statement of which rule wins and why order matters
Token Specification (Goal 1: specify a complete token grammar using ordered regular-expression rules) (27%) Fewer than half the token types in the specification table are defined, or the patterns are so incorrect that the lexer cannot tokenize even simple programs Most token types are defined but several patterns are wrong (e.g., keywords not prioritized over identifiers, or operators missing from the spec) All required token types are defined with correct patterns, but the specification has a minor ordering or coverage gap (e.g., multi-character operators not listed before single-character ones) Every token type in the specification table is defined in the correct priority order (keywords before IDENT, multi-character operators before their single-character prefixes, whitespace and comments skipped), showing command of ordered regular-expression rules; the spec is externalized in a loadable JSON file (or, in the generator-toolchain direction, expressed as an ordered Flex/PLY rule specification); and the lexing theory questions (Step 1d) are answered with mechanism-level reasoning about maximal munch, keyword handling, and the lexer/parser division of labor
Lexer Implementation (Goal 2: harden the tokenizer into a reusable Lexer component with peek, advance, and expect) (36%) The Lexer class does not exist or the peek/advance interface is fundamentally broken The Lexer class exists with peek and advance, but one or both are incorrect (e.g., peek consumes input, or advance skips tokens) peek and advance work correctly for most inputs, but edge cases fail (e.g., repeated peek calls return different tokens, or EOF is not handled gracefully) The Lexer class implements peek, advance, and expect correctly; peek is idempotent, both return an EOF token at end of input, and expect raises a located LexError on mismatch, showing that the component is ready to be imported unchanged by the parser; the lexer has no side effects at import time
Error Handling, Positions, and Test Suite (Goals 3-5: escape sequences, precise error positions, collect-all mode, and a fully tested deliverable) (27%) Lexical errors crash Python with an unhandled exception, positions are absent, and no test suite exists Errors are caught and reported, but positions are missing or incorrect, and the test suite covers only a handful of token types Errors include line and column and the test suite covers most token types, but error recovery (collect-all mode) is missing or incorrect, and escape sequences are not fully tested Every error includes line, column, and the offending text; collect-all mode gathers every error in a single pass without stopping; string-literal escape sequences are fully implemented; and the test suite covers all token types, all escape sequences, all maximal-munch cases, and at least five deliberate error programs with expected messages verified, showing a deliverable that the team project can import unchanged

Please refer to the Style Guide for code quality examples and guidelines.