Concrete and Abstract Syntax

The Distinction

Concrete Syntax

Concrete syntax is how expressions are written as text strings by programmers. It includes:

• Parentheses for grouping
• Operator precedence
• Associativity rules
• Whitespace and formatting

Abstract Syntax

Abstract syntax is the “essential structure” of an expression, typically represented as a tree. It captures:

• The operators and operands
• The hierarchical structure
• No need for parentheses or precedence

Example: Arithmetic Expressions

Concrete Syntax

The string "1 + 2 * 3" has a specific meaning due to precedence (* binds tighter than +).

Different strings can have the same meaning:

• "1 + 2 * 3"
• "1+(2*3)"
• "1 + ( 2 * 3 )"

Abstract Syntax Tree

All three concrete strings map to the same abstract syntax tree:

    +
   / \
  1   *
     / \
    2   3

Parsing

Definition

Parsing is the process of converting concrete syntax (a string) to abstract syntax (a tree).

Grammar Rules

Expressions can be defined by grammar rules:

E ::= E + T | T
T ::= T * F | F
F ::= n | ( E )

This grammar enforces precedence: E handles addition, T handles multiplication.

Ambiguity

A grammar is ambiguous if some string has multiple parse trees.

This is usually undesirable: the meaning should be unique.

Abstract Syntax Trees for Regular Expressions

Constructors

For regular expressions over alphabet $\Sigma$:

Constructor	Notation	Meaning
Null	$\varepsilon$	Empty string
Never	$\emptyset$	No strings
Symbol	$a$ for $a \in \Sigma$	Single symbol
Union	$R_1	R_2$
Concat	$R_1 R_2$	Sequencing
Star	$R^*$	Kleene closure

Tree Representation

The regex a(b|c)* has AST:

    Concat
    /    \
   a     Star
          |
         Union
         /  \
        b    c

Parsing Regular Expressions

Precedence

From highest to lowest:

1. Star (*): binds tightest
2. Concatenation (implicit): next
3. Union (|): binds loosest

Associativity

• Star: postfix, right-associative
• Concat: implicit, left-associative
• Union: left-associative (usually)

Example

ab|c*d parses as (ab)|((c*)d):

        Union
       /    \
    Concat  Concat
    /   \   /   \
   a     b Star  d
            |
            c

The Parsing Relation

Definition

Define a relation _ parsesTo _ between strings and ASTs.

Rules

Atoms: $\frac{}{\text{"}\varepsilon\text{" parsesTo Null}} \qquad \frac{}{\text{"}\emptyset\text{" parsesTo Never}} \qquad \frac{}{a \text{ parsesTo Sym}_a}$

Compound: $\frac{s_1 \text{ parsesTo } R_1 \quad s_2 \text{ parsesTo } R_2}{s_1 | s_2 \text{ parsesTo Union}(R_1, R_2)}$

Similar for Concat and Star.

Pretty Printing

Definition

Pretty printing is the inverse of parsing: converting an AST to a readable string.

Challenge

The string should be:

• Unambiguous
• Readable (minimal parentheses)

Algorithm

Add parentheses only when necessary based on precedence.

If child’s precedence is lower than parent’s, parenthesize the child.

---

Summary

• Concrete syntax: the textual representation
• Abstract syntax: the tree structure (AST)
• Parsing: concrete to abstract
• Pretty printing: abstract to concrete
• Precedence resolves ambiguity in concrete syntax