2. Lexical analysis

The indentation levels of consecutive lines are used to generate INDENT andDEDENT tokens, using a stack, as follows.

Before the first line of the file is read, a single zero is pushed on the stack;this will never be popped off again. The numbers pushed on the stack willalways be strictly increasing from bottom to top. At the beginning of eachlogical line, the line’s indentation level is compared to the top of the stack.If it is equal, nothing happens. If it is larger, it is pushed on the stack, andone INDENT token is generated. If it is smaller, it must be one of thenumbers occurring on the stack; all numbers on the stack that are larger arepopped off, and for each number popped off a DEDENT token is generated. At theend of the file, a DEDENT token is generated for each number remaining on thestack that is larger than zero.

Here is an example of a correctly (though confusingly) indented piece of Pythoncode:

def perm(l):        # Compute the list of all permutations of l    if len(l) <= 1:                  return [l]    r = []    for i in range(len(l)):             s = l[:i] + l[i+1:]             p = perm(s)             for x in p:              r.append(l[i:i+1] + x)    return r