Lexical analysis

Why it exists

The parser should deal with words of the language (an identifier, a number, the keyword while), not with individual characters. The lexical analyser (scanner, lexer) reads the character stream and delivers one token at a time on demand. Separating it from the parser keeps both simple: white space and comments are removed in one place, the patterns of tokens are regular and can be recognised by a fast finite automaton, and the parser's grammar can be written over tokens. It also isolates machine and character-set details.

Prerequisites

You need the first phase of the compiler from phases of a compiler, and regular expressions, because the pattern of every token class is a regular expression (see regular expressions).

Precise definitions

Token. A pair $\langle \text{token name}, \text{attribute value} \rangle$ such as $\langle \text{id}, \text{pointer to symbol table entry} \rangle$ or $\langle \text{num}, 60 \rangle$. The name is the abstract symbol the parser uses; the attribute is extra information for later phases. Operators and keywords usually need no attribute.

Lexeme. The actual character sequence in the source that matches a token's pattern, for example rate or 60.

Pattern. The rule describing the set of lexemes of a token, normally a regular expression.

Regular definitions name the parts: for C-like identifiers

$\text{letter} = [A\text{-}Za\text{-}z\_],\qquad \text{digit} = [0\text{-}9],\qquad \text{id} = \text{letter}\,(\text{letter}\mid\text{digit})^{*}.$

An unsigned number: $\text{digits}\,(\,.\,\text{digits})?\,(E\,(+\mid -)?\,\text{digits})?$.

The two rules that decide ambiguity. When several patterns could match at the current position, the scanner uses

1. Longest match (maximal munch): take the longest prefix of the remaining input that matches any pattern. So <= is one token, not < followed by =, and a+++b is read as a, ++, +, b.
2. Rule priority: if two patterns match the same longest lexeme, the one listed first wins. That is how the lexeme if becomes the keyword and not an identifier, as long as the keyword rule is listed before the identifier rule. A common implementation instead matches an identifier and then looks the lexeme up in a table of reserved words.

The longest match is a greedy local rule: it never backs off to make the rest parse. In C, x = y+++z; always gives y ++ + z, even where another split could be valid.

What the scanner removes or keeps. White space (blanks, tabs, newlines), comments and, in C, the result of preprocessing are discarded. A string literal (including spaces or // inside the quotes) is one token. Newlines matter in some languages (Python, Fortran) and are then tokens.

Recognising tokens. The patterns are combined into one automaton: each regular expression becomes an NFA, the NFAs are joined, the result is converted to a DFA and minimised (regex to automata, DFA). The scanner runs the DFA; every accepting state is tagged with a token name. The scanner remembers the last accepting state passed and, when the DFA gets stuck, backs up to it, which is exactly the longest-match rule. Tools such as Lex and Flex generate this scanner from a list of pattern action rules.

Input buffering. Reading one character at a time from disk is slow, so the scanner uses a buffer pair: two halves of $N$ characters each, with a lexemeBegin pointer and a forward pointer. Characters are read a block at a time into one half while the other is scanned. A sentinel (an end-of-file character at the end of each half) lets the scanner test for the end of a buffer only when it reads a sentinel, not at every character. The lookahead after a lexeme (to decide whether < is the start of <=) is the reason a pointer can run ahead of the lexeme.

Symbol table. When the scanner finds an identifier lexeme it looks it up in the symbol table (entering it if new) and returns the token with a pointer to the entry, so that later phases attach type, scope and address to it.

Lexical errors. The scanner reports only things it can see locally: an illegal character, an unterminated string or comment, a malformed number. It cannot detect a missing semicolon or an undeclared name. Recovery is usually panic mode (delete characters until a token can be formed) or inserting, deleting, replacing or transposing a single character.

What a lexer cannot do. Its patterns are regular, so it cannot check anything that needs counting or nesting, such as balanced parentheses or matching begin and end: that is the parser's job (a context-free grammar, see phases). It also does not know which names are declared.

How it works

Two small machines, run on lexemes. The first accepts identifiers. State ID is accepting; any letter, digit or underscore keeps it there; a digit in the start state leads to the dead state, because an identifier cannot begin with a digit.

The second shows the longest-match rule for relational operators. After < the scanner is in an accepting state (LT) but an edge on = exists, so it continues; it ends in LE with no outgoing edge, so the token is <=.

The following C program is a complete scanner for a small part of C (identifiers, numbers, strings, operators, punctuation). Its next_token function returns the length of the longest token at a position, which is the longest-match rule written directly. Keywords come out as id here because the program does not look names up in a reserved-word table; a real scanner would label if and else as keywords.

#include <ctype.h>
#include <stdio.h>
#include <string.h>
 
static const char *OPS3[] = {"<<=", ">>=", "...", NULL};
static const char *OPS2[] = {"++", "--", "<<", ">>", "<=", ">=", "==", "!=", "&&", "||", "+=", "-=", "*=", "/=", "->", NULL};
 
static int starts_with_any(const char *s, const char **list, size_t n) {
    for (int i = 0; list[i] != NULL; i++)
        if (strlen(list[i]) == n && strncmp(s, list[i], n) == 0) return 1;
    return 0;
}
 
/* length of the longest token that starts at s (maximal munch); *kind names the token class */
static size_t next_token(const char *s, const char **kind) {
    size_t n = 0;
    if (isalpha((unsigned char)s[0]) || s[0] == '_') {
        while (isalnum((unsigned char)s[n]) || s[n] == '_') n++;
        *kind = "id";
    } else if (isdigit((unsigned char)s[0])) {
        if (s[0] == '0' && (s[1] == 'x' || s[1] == 'X')) {
            n = 2;
            while (isxdigit((unsigned char)s[n])) n++;
        } else {
            while (isdigit((unsigned char)s[n])) n++;
            if (s[n] == '.') {
                n++;
                while (isdigit((unsigned char)s[n])) n++;
            }
            if ((s[n] == 'e' || s[n] == 'E') &&
                (isdigit((unsigned char)s[n + 1]) || ((s[n + 1] == '-' || s[n + 1] == '+') && isdigit((unsigned char)s[n + 2])))) {
                n += 2;
                while (isdigit((unsigned char)s[n])) n++;
            }
        }
        while (s[n] != '\0' && strchr("fFlLuU", s[n]) != NULL) n++;
        *kind = "num";
    } else if (s[0] == '"') {
        n = 1;
        while (s[n] != '\0' && s[n] != '"') n += (s[n] == '\\' && s[n + 1] != '\0') ? 2 : 1;
        if (s[n] == '"') n++;
        *kind = "str";
    } else if (starts_with_any(s, OPS3, 3)) {
        n = 3;
        *kind = "op";
    } else if (starts_with_any(s, OPS2, 2)) {
        n = 2;
        *kind = "op";
    } else {
        n = 1;
        *kind = strchr("(){}[];,", s[0]) != NULL ? "punct" : "op";
    }
    return n;
}
 
static void scan(const char *src) {
    int count = 0;
    printf("%s\n ", src);
    for (const char *p = src; *p != '\0';) {
        if (isspace((unsigned char)*p)) {
            p++;
            continue;
        }
        const char *kind;
        size_t n = next_token(p, &kind);
        printf(" <%s %.*s>", kind, (int)n, p);
        p += n;
        count++;
    }
    printf("\n  %d tokens\n", count);
}
 
int main(void) {
    scan("a = b+++c;");
    scan("a+++++b;");
    scan("x = 3.14e-2f + 0x1F;");
    scan("printf(\"i = %d, &i = %x\", i, &i);");
    scan("if (a <= b) c = a; else c = b;");
    return 0;
}

a = b+++c;
  <id a> <op => <id b> <op ++> <op +> <id c> <punct ;>
  7 tokens
a+++++b;
  <id a> <op ++> <op ++> <op +> <id b> <punct ;>
  6 tokens
x = 3.14e-2f + 0x1F;
  <id x> <op => <num 3.14e-2f> <op +> <num 0x1F> <punct ;>
  6 tokens
printf("i = %d, &i = %x", i, &i);
  <id printf> <punct (> <str "i = %d, &i = %x"> <punct ,> <id i> <punct ,> <op &> <id i> <punct )> <punct ;>
  10 tokens
if (a <= b) c = a; else c = b;
  <id if> <punct (> <id a> <op <=> <id b> <punct )> <id c> <op => <id a> <punct ;> <id else> <id c> <op => <id b> <punct ;>
  15 tokens

Worked examples

Cheat box

Traps and GATE patterns

Connections

The scanner is the first phase in the phases of a compiler. Its patterns are regular expressions, turned into a DFA by the conversions. The tokens it produces are the terminals of the grammar used by the parser (LL(1) parsing and LR parsing).

PYQs

A lexical analyzer uses the following token
definitions
letter → [A – Z a - z]
digit → [0 - 9]
id → letter (letter | digit)*
number → digit +
ws → (blank | tab | newline) +

For the string given below,
            x1 23mm  78 y  7z  zz5  14A  8H   AaYcD

the number of tokens (excluding ws) that will be
produced by the lexical analyzer is __________.
(answer in integer)

A lexical analyzer uses the following patterns to
recognize three tokens T1, T2, and T3 over the
alphabet {a,b,c}.

T1 : a?(b|c)*a

T2 : b?(a|c)*b

T3 : c?(b|a)*c

Note that 'x?' means 0 or 1 occurrence of the symbol
x. Note also that the analyzer outputs the token that
matches the longest possible prefix. If the string
bbaacabc is processed by the analyzer, which one of
the following is the sequence of tokens it outputs?

In a compiler, keywords of a language are recognized
during:-

The lexical analysis for a modern computer language
such as Java needs the power of which one of the
following machine models in a necessary and
sufficient sense?

Consider line number 3 of the following C- program.
                  int main ( ) {                           /*Line 1 */
                  int I, N;
/*Line 2 */
                  fro (I = 0, I < N, I++);         /*Line 3 */
                     }

Identify the compiler's response about this line while
creating the object-module

Consider the following C statements:
             char *str1 = "Hello; /* Statement S1 */
             char *str2 = "Hello;"; /* Statement S2 */
              int *str3 = "Hello"; /* Statement S3 */

Which of the following options is/are correct?

Self-check

Revision card

References