REBOL 3 Concepts: Parsing: Recursive Rules

Pending Revision

This document was written for R2 and has yet to be revised for R3.

Here is an example of rule set that parses mathematical expressions and gives a precedence (a priority) to the math operators used:

expr:    [term ["+" | "-"] expr | term]
term:    [factor ["*" | "/"] term | factor]
factor:  [primary "**" factor | primary]
primary: [some digit | "(" expr ")"]
digit:   charset "0123456789"

Now we can parse many types of math expressions. The following examples return true, indicating that the expressions were valid:

probe parse "1 + 2 * ( 3 - 2 ) / 4" expr
true

probe parse "4/5+3**2-(5*6+1)" expr
true

Notice in the examples that some of the rules refer to themselves. For instance, the expr rule includes expr. This is a useful technique for defining repeating sequences and combinations. The rule is recursive --it refers to itself.

When using recursive rules, care is required to prevent endless recursion. For instance:

expr: [expr ["+" | "-"] term]

creates an infinite loop because the first thing expr does is use expr again.