Master

Parsing nested text

Text that nests, like brackets or an expression, is parsed by recursion that mirrors the grammar. Each rule is a small function, and the nesting drives the calls.

What you will see

About 3 min of reading

Quick check

Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.

Try It

Parse nested text with recursion.

Bracket depth.

def depth(s, i): best = 0 d = 0 while i < len(s): if s[i] == "[": d += 1 elif s[i] == "]": d -= 1 best = max(best, d) i += 1 return best print(depth("[[[]]]", 0))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Parse a number.

def num(s, i): d = 0 while i < len(s) and s[i].isdigit(): d = d * 10 + int(s[i]) i += 1 return d, i print(num("12x", 0))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

(12, 2)

Group a paren.

def group(s, i): assert s[i] == "(" return i + 1 print(group("(7)", 0))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Sum a bracketed list.

def parse(s, i): total = 0 while i < len(s) and s[i] != "]": if s[i] == "[": v, i = parse(s, i + 1) total += v elif s[i].isdigit(): total += int(s[i]) i += 1 else: i += 1 return total, i + 1 val, _ = parse("[1[2]]", 0) print(val)

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Put it in order

Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.

Data Flow

Nested text is parsed by recursive descent: one function per grammar rule, each returning the next position, so nesting drives the calls.

1 read a token

↓

2 rule calls sub-rule

↓

3 return next position

↓

4 nesting drives depth

Line by line

Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.

def depth(s, i): sets nothing on screen

best = 0 sets nothing on screen

d = 0 sets nothing on screen

while i < len(s): sets nothing on screen

if s[i] == "[": sets nothing on screen

d += 1 sets nothing on screen

elif s[i] == "]": sets nothing on screen

d -= 1 sets nothing on screen

best = max(best, d) sets nothing on screen

i += 1 sets nothing on screen

return best sets nothing on screen

print(depth("[[[]]]", 0)) 3

Why this works

Mirror the grammar

One small function per rule, each returning the next position, turns nested text into a recursion that follows the structure.

Deep text is deep calls

A parser built on recursion inherits the depth limit. Very deep input needs an iterative parser or a raised limit.

Examples

Match brackets

def depth(s, i):
    best = 0
    d = 0
    while i < len(s):
        if s[i] == "[":
            d += 1
        elif s[i] == "]":
            d -= 1
        best = max(best, d)
        i += 1
    return best
print(depth("[[[]]]", 0))

A counter tracks how deep the brackets go. That depth is the nesting.

Recursive descent

def expr(s, i):
    val, i = num(s, i)
    return val, i
def num(s, i):
    d = 0
    while i < len(s) and s[i].isdigit():
        d = d * 10 + int(s[i])
        i += 1
    return d, i
print(expr("42", 0))

Each grammar rule is a function that returns the next position. Rules call rules.

Group rule recurses

def group(s, i):
    assert s[i] == "("
    val, i = expr(s, i + 1)
    assert s[i] == ")"
    return val, i + 1
def num(s, i):
    d = 0
    while i < len(s) and s[i].isdigit():
        d = d * 10 + int(s[i])
        i += 1
    return d, i
def expr(s, i):
    if s[i] == "(":
        return group(s, i)
    return num(s, i)
print(group("(7)", 0))

A group calls expr again. The parentheses drive the recursion.

Sum a bracketed list

def parse(s, i):
    total = 0
    while i < len(s) and s[i] != "]":
        if s[i] == "[":
            v, i = parse(s, i + 1)
            total += v
        elif s[i].isdigit():
            total += int(s[i])
            i += 1
        else:
            i += 1
    return total, i + 1
val, _ = parse("[1[2]]", 0)
print(val)

A nested bracket calls parse again. The grammar and the calls match.

Return the position

def num(s, i):
    d = 0
    while i < len(s) and s[i].isdigit():
        d = d * 10 + int(s[i])
        i += 1
    return d, i
print(num("12x", 0))

A rule returns the value and where it stopped. Passing the index along is how the parse advances.

Grammar is the plan

def expr(s, i):
    return num(s, i)
def num(s, i):
    d = 0
    while i < len(s) and s[i].isdigit():
        d = d * 10 + int(s[i])
        i += 1
    return d, i
print(expr("9", 0))

Write one function per grammar rule. The structure of the code is the grammar.

Fail fast on bad input

def group(s, i):
    if i >= len(s) or s[i] != "(":
        return None
    return i + 1
g = group("(x)", 0)
print(g is not None)

A rule checks the token it expects and fails if absent. Errors stop the parse early.

Nesting equals depth

def depth(s, i):
    best = 0
    d = 0
    while i < len(s):
        if s[i] == "[":
            d += 1
        elif s[i] == "]":
            d -= 1
        best = max(best, d)
        i += 1
    return best
print(depth("[[[", 0))

Deeply nested text means deep calls. Parsing a huge nest can hit the recursion limit.

Words this lesson uses

Each one is defined here on this site. Open the entry for the full definition and the other words it points at.

← When recursion is too deep

Previous Lesson

When recursion is too deep