Skip to content
Tutorials Center
My learning

Topics

Lesson 121 of 135 ยท Projects

Project: Lexical Analyzer and Bracket Checker

Build a tokenizer for a small programming language in C: keyword table, numbers, strings, operators and error tokens, then a stack-based checker for balanced brackets.

Every compiler, interpreter, syntax highlighter and code formatter starts the same way. Before it can understand a program, it has to turn a long string of characters into a list of tokens: while, (, total, <=, 10. This first step is called lexical analysis, and the program that does it is a lexer (or scanner, or tokenizer). It is small enough to write in an afternoon, and it uses nearly everything you know about strings, structs, enums and pointers.

In the second half you will use the lexer for something practical: a bracket checker that reports unbalanced (, [ and { with line and column, using a stack. The project builds on strings, character classification, enums, structures, stacks and reading input.

Stage 1: the tokenizer

The language. The lexer reads a tiny C-like language with six keywords (else, if, int, print, return, while), identifiers, whole numbers, double-quoted strings, operators (+ - * / % = == != < > <= >= && || !) and punctuation (( ) { } [ ] ; ,). Whitespace separates tokens, and // starts a comment that runs to the end of the line. Neither whitespace nor comments produce tokens.

A token is a kind, a text and a position. struct Token stores the kind (an enum), the text (up to 31 characters), and the line and column where it started. Positions are what turn "syntax error" into "syntax error at 5:12", and they are cheap to track: a small function advance is the only code that moves through the source, and it counts lines and columns as it goes. Having one such function means the bookkeeping cannot be forgotten in some branch.

One function, one token. next_token skips whitespace and comments, looks at the first character, and decides what kind of token starts here:

  • a letter or underscore starts a word: read letters, digits and underscores, then check the keyword table. If the word is in the table it is a keyword, otherwise an identifier;
  • a digit starts a number: read all digits;
  • a double quote starts a string: read up to the closing quote;
  • anything else is an operator or punctuation character, or an error.

Looking up keywords. The keywords are in a small array sorted alphabetically, and bsearch from <stdlib.h> finds a word in it. For six keywords a plain loop would be fine, but the sorted table scales to fifty with no code change (keeping it sorted is the only rule). Do the lookup after reading the whole word: iffy and printer are identifiers even though they start with keywords.

The longest match wins. For <=, the lexer must not return < and then =. So before accepting a one-character operator, it checks the table of two-character operators. This rule is called maximal munch, and every real lexer follows it.

Errors are tokens. What should happen at 2fast, at a lone &, or at a string that is never closed? A lexer that stops at the first problem makes the user fix and re-run, one error at a time. This one produces a token of kind TK_ERROR with a message, consumes the offending characters, and carries on, so one pass reports every problem. For 2fast, the number is followed directly by a letter, so the lexer swallows the whole word and calls it a malformed number, rather than splitting it into 2 and fast. An unterminated string stops at the end of the line.

Never read past the end. peek_at(lx, 1) looks one character ahead, which is safe only if the current character is not the string terminator. The code checks the current character first every time. Reading one byte beyond a string's '\0' is the kind of bug that works for months and then does not.

C Stage 1: turn source text into tokens

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Find the first line of the output: int is a keyword at 1:1, total is an identifier at 1:5, and the comment on line 1 disappears. On line 2, <= is one operator. At the end, the three problems are reported together: 2fast, the lone &, and the unclosed string. The string error runs to the end of the line, so its text (shown without the opening quote) swallows the ); too.

Stage 2: a stack-based bracket checker

Why counting is not enough. The obvious bracket check keeps three counters. It accepts ([)], which has one of each opener and closer but is not nested correctly. Brackets must close in the reverse order they were opened, which is exactly how a stack behaves: the most recent opener must be the first to be closed. So the algorithm is:

  1. on an opener, push it (with its position);
  2. on a closer, pop; if the stack was empty, the closer is unexpected, and if the popped opener is the wrong kind, report a mismatch;
  3. at the end, anything left on the stack is unclosed.

The stack is a plain array of struct Frame (the opener and where it was) plus a top counter, in the style of the stack lesson. Its size is fixed at 64. Deeper nesting is reported as an error instead of overflowing.

Why run the lexer first. A checker that scans raw characters gets confused by print("("); and by // don't close this ): the brackets inside strings and comments do not count. Because the lexer already skips comments and wraps strings into single tokens, the checker only ever sees real brackets. This is the main reason programs use a tokenizer instead of looking at characters directly. Each step handles one concern.

Messages that help. Each report gives line and column for both ends of a problem. For a mismatch, "} at 3:1 does not match ( opened at 1:4" tells the programmer both places to look. The checker also reports lexer errors, since a stray character might be the reason a bracket seems missing.

Test data first, then your own. The demo checks five built-in sources that cover each case (balanced, mismatched, unexpected closer, brackets only in strings and comments, unclosed) and then checks whatever arrives on standard input. The input is read with a single fread into a buffer, and the buffer is terminated with '\0' by hand, because fread does not do that.

C Stage 2: check brackets in several sources

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Test 4 is the one that shows why the lexer comes first. A checker that looks at raw characters would see a second ( inside the string and a stray ] in the comment, and report two problems that do not exist; the token-based checker sees one real pair. In the final test, the { is opened while ( of the if is still open, so the } at the end closes the { correctly, and the ( of the if is reported as never closed, with the position where it was opened.

Ideas for going further

  • Token list. Store tokens in a dynamic array (see dynamic arrays) so that a parser can look ahead.
  • A parser. Write a function that evaluates 1 + 2 * (3 + 4) from the token stream with recursive descent: one function per precedence level.
  • Syntax coloring. Print the source again with ANSI colors per token kind, which is exactly what an editor does.
  • More tokens. Add floating-point numbers, 'c' character literals, escape sequences in strings (\"), and /* ... */ comments, and think about what each one does to next_token.
  • Hash-table keywords. Replace the sorted table with a hash table from the hashing lesson and compare.
  • Statistics. Count tokens by kind and print a table, the beginning of a code-metrics tool.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does a lexer produce?

    A lexer turns characters into tokens. Building a tree from those tokens is the parser's job, and generating code comes later still.
  2. 2. Why does the lexer check the table of two-character operators before accepting a single-character one?

    This is the longest-match (maximal munch) rule. Checking the longer operators first makes sure a longer valid token is never split.
  3. 3. Why does the keyword lookup happen after the whole word is read?

    Only the complete word decides what it is. Looking at a prefix would turn iffy into the keyword if plus y.
  4. 4. A checker has three counters and accepts a source when each opener count equals its closer count. Which input fools it?

    ([)] has one of each pair, but the brackets close in the wrong order. A stack notices that ) arrives while [ is on top.
  5. 5. Why are brackets inside strings and comments not reported by the checker?

    Separating the work means each stage solves one problem. The checker works on tokens and cannot be confused by text that is not code.

Summary

  • A lexer converts characters into tokens (kind, text, position); every compiler, interpreter and highlighter begins with one.
  • Keep all position tracking in a single advance function, and never read past the string terminator when you look ahead.
  • Decide the token kind from its first character; follow the longest-match rule; look keywords up (bsearch on a sorted table) only after reading the whole word.
  • Report problems as error tokens and keep going, so one run lists all of them.
  • Balanced brackets need a stack, not counters: push openers with their position, pop on closers, and report leftovers at the end.
  • Running the lexer first means strings and comments cannot confuse later stages.

Next: the 2048 project, a puzzle game with a grid, sliding tiles and screen redraw.