DailyRNG
Login
Basic

A grammar as rules that decide shape

Tokens have a name but no structure. The structure comes from rules, and the rules are written once and read by the parser.

What you will see

refuse. The rule never answers, and refusing it at start is the catch.

About 1 min of reading

Try It

Write rules and refuse a bad one

1

Write two rules

printf 'expr = term plus expr\nterm = number\n' > /tmp/g.txt; cat /tmp/g.txt

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

What it prints
Two lines. The lines name what may follow, which is the shape.
2

Write the nesting

printf 'expr = lparen expr rparen\n' >> /tmp/g.txt; wc -l < /tmp/g.txt

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

What it prints
3. A rule naming expr is what makes nesting possible.
3

Refuse a rule that consumes nothing

printf 'bad = bad\n' | awk '{print ($1==$2) ? "refuse" : "ok"}'

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

What it prints
refuse. The rule never answers, and refusing it at start is the catch.

Data Flow

Rules to a decision about shape
1 The rules are written once
↓
2 The parser reads the rules
↓
3 A rule that consumes nothing is refused at start
↓
4 Precedence is written in the rules
Why this works
Why the rules are separate from the parser

A change to the language is a change to the rules. A change that is a file is a change that cannot break the parser.

The one rule that must be refused

A rule that can call itself with no text consumed. That rule never answers, and never answering is caught at start.

Examples

A rule is a name and a shape

The shape says what may follow. What may follow is a set, and a set is small enough to write.

Recursion is allowed

A rule may name itself. Naming itself is what makes nesting possible, and nesting is the thing a loop cannot do.

Precedence is a rule choice

The rules decide the order. The order is not remembered by the reader, it is written in the rules.

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.

← Tokens as a language with a shape
Previous Lesson
Tokens as a language with a shape
Next Lesson
A tree as the meaning
A tree as the meaning →