Parsing and Pretty Printing Regular Expressions

Parsing: String to AST

The Problem

Given a concrete string like a|b*c, produce the abstract syntax tree.

Precedence Resolution

The string a|b*c should parse as $a|(b*c)$, not $(a|b)*c$.

This is implemented by a parsing relation with precedence levels.

Parsing Relation

Levels

Define parsing at different precedence levels:

• parseUnion: handles |
• parseConcat: handles concatenation
• parseStar: handles *
• parseAtom: handles atoms and parentheses

Grammar (Simplified)

Union  ::= Concat ('|' Concat)*
Concat ::= Star+
Star   ::= Atom '*'*
Atom   ::= ε | ∅ | symbol | '(' Union ')'

Rules for Parsing

Atoms: $\frac{}{\text{parseAtom}(a, \text{Sym}_a)} \quad \frac{}{\text{parseAtom}(\varepsilon, \text{Null})} \quad \frac{\text{parseUnion}(s, R)}{\text{parseAtom}((s), R)}$

Star: $\frac{\text{parseAtom}(s, R)}{\text{parseStar}(s, R)} \quad \frac{\text{parseStar}(s, R)}{\text{parseStar}(s*, \text{Star}(R))}$

Concatenation: $\frac{\text{parseStar}(s, R)}{\text{parseConcat}(s, R)} \quad \frac{\text{parseConcat}(s_1, R_1) \quad \text{parseStar}(s_2, R_2)}{\text{parseConcat}(s_1 s_2, \text{Concat}(R_1, R_2))}$

Union: $\frac{\text{parseConcat}(s, R)}{\text{parseUnion}(s, R)} \quad \frac{\text{parseUnion}(s_1, R_1) \quad \text{parseConcat}(s_2, R_2)}{\text{parseUnion}(s_1|s_2, \text{Union}(R_1, R_2))}$

Example Parse

String: a|b*

1. Parse as Union
2. Left part: a parses as Sym$_a$
3. Right part: b*
   • b parses as Sym$_b$
   • b* parses as Star(Sym$_b$)
4. Result: Union(Sym$_a$, Star(Sym$_b$))

    Union
    /   \
   a    Star
         |
         b

Parentheses Disambiguate

With Parentheses

(a|b)*c parses as:

    Concat
    /    \
  Star    c
    |
  Union
  /   \
 a     b

Without Parentheses

a|b*c parses as a|(b*c):

    Union
    /   \
   a   Concat
        /   \
      Star   c
        |
        b

Pretty Printing: AST to String

The Problem

Given an AST, produce a readable concrete string.

Strategy

1. Recursively convert subtrees to strings
2. Add parentheses when child has lower precedence than parent
3. Minimize parentheses for readability

Precedence Table

Constructor	Precedence
Star	3 (highest)
Concat	2
Union	1 (lowest)

Rules

$\text{pprint}(R, p) = \text{pretty print } R \text{ at precedence level } p$

Add parentheses if $p > \text{prec}(R)$.

Atoms: Never need parentheses around themselves.

Star: $\text{pprint}(R^*, p) = \text{pprint}(R, 3) + *$

Concat: $\text{pprint}(RS, p) = \text{pprint}(R, 2) + \text{pprint}(S, 2)$, parenthesise if $p > 2$.

Union: $\text{pprint}(R|S, p) = \text{pprint}(R, 1) + | + \text{pprint}(S, 1)$, parenthesise if $p > 1$.

Example Pretty Prints

Simple

• $\text{pprint}(a) = a$
• $\text{pprint}(a^*) = a*$
• $\text{pprint}(ab) = ab$
• $\text{pprint}(a|b) = a|b$

With Parentheses

• $\text{pprint}((a|b)^*) = (a|b)*$ (union under star needs parens)
• $\text{pprint}(a^*b^*) = a*b*$ (no parens needed)
• $\text{pprint}((a|b)(c|d)) = (a|b)(c|d)$ (unions in concat need parens)

Round-Trip Property

Parsing then Pretty Printing

For any string $s$ that parses to AST $R$:

$\text{parse}(s) = R \Rightarrow \text{pprint}(R) = s'$

where $s'$ is semantically equivalent and may be $s$ or a normalised form.

Pretty Printing then Parsing

For any AST $R$:

$\text{parse}(\text{pprint}(R)) = R$

The pretty-printed string should re-parse to the same AST.

---

Summary

• Parsing converts concrete strings to abstract syntax trees
• Precedence determines how strings are structured into trees
• Pretty printing converts ASTs back to readable strings
• Parentheses are added only when necessary for correctness