Syntactic Analysis

A poor mans analysis

Christian Gram Kalhauge

What is Syntactic Analysis?
What can we Pattern Match on?
How do we Match Patterns in Practice?

Questions

What are the limitations of a syntactic analysis?
When is syntactic analysis a good tool?
Trick Question: Is Java a regular language, context free or recursive enumerable?

What is Syntactic Analysis? (§1)

Pattern Matching on the structure of the program.

The Levels of Syntax (§1.1)

The levels of syntactic matches can range from matching the bits, to matching the final compiled bytecode.

Preventing AND and OR

fn (int a, b, c) { 
  return a && b || c;  # Might be a mistake
}

fn (int a, b, c) { 
  return (a && b) || c;  # Ah, never mind.
}

Goal of Syntactic Analysis (§1.2)

No bad warnings (false negatives).
Complete is better than Sound.

Program analysis design should aim for a false-positive rate no higher than 15–20%.
— Christakis and Bird

When forced to choose between more bugs or fewer false positives, [developers] typically choose the latter.
— Christakis and Bird

What can we Pattern Match on? (§2)

The set of programs matched by a pattern is called a Language.

A Language — Formally Speaking (§2.1)

Language

A language $L$ over the alphabet $Σ$ , is a subset of all words $w \in Σ *$ from the alphabet $L \subseteq Σ *$ .

$L_{h a l t} = {p | p terminates, p \in L_{J a v a}}$

Sound: $S A_{h a l t} (p) ⟹ p \in L_{h a l t}$
Complete: $p \in L_{h a l t} ⟹ S A_{h a l t} (p)$

Production Rules and Grammars (§2.2)

Grammar

A grammar $G$ is a quadruple $(N, Σ, \to, S)$ , where $N$ is a set of non-terminals ( $A$ , $B$ , $C$ ), $Σ$ is the alphabet, $\to$ is a set of production rules, and $S$ is the start symbol.

The language of the grammar is:

L_{G} = {w | w \in Σ *, S \to^{*} w}

Where $\to^{*}$ means applying the rules in $\to$ until no non-terminal is left.

Generate $((a b) b)$

Consider the grammar $({S, X}, {a, b, (,)}, \to, S)$ , where $\to$ is defined like this:

\begin{matrix} S & \to^{1} (S X) \\ S & \to^{2} a \\ X & \to^{3} b \end{matrix}

It can generate the following word in the language $S \to^{1} (S X) \to^{3} (S b) \to^{1} ((S X) b) \to^{2} ((a X) b) \to^{3} ((a b) b)$

Some languages actually work like this, think about LaTeX and the C macro system.

What Types of Languages Exist? (§2.3)

Chomsky hierarchy

The Chomsky hierarchy, with production rules.

How do we Match Patterns in Practice? (§3)

Regular: Regular Expressions
Context-Free: Grammars and Parsers
Context Sensitive: Matching Patterns in Trees
Recursive Enumerable: Bespoke

Regular: Regular Expressions (§3.1)

\begin{matrix} e & := & ϵ & – an empty string \\ | & a & – symbol \\ | & e_{1} e_{2} & – a concatenation \\ | & e_{1} + e_{2} & – an alternative \\ | & e_{1} * & – a Kleene star \end{matrix}

The grammar for defining regular expressions.

$\begin{matrix} [[ϵ]] & = {ϵ} \\ [[a]] & = {a} \\ [[e_{1} e_{2}]] & = {u w | u \in [[A]], w \in [[B]]} \\ [[e_{1} + e_{2}]] & = [[A]] \cup [[B]] \\ [[e_{1} *]] & =^{†} {ϵ} \cup {u w | u \in [[e_{1}]], w \in [[e_{1} *]]} \end{matrix}$ where $†$ is the smallest solution to the equation.

The denotational semantics for regular expressions

Getting Started (§3.1.1)

https://regex101.com/

Context-Free: Grammars and Parsers (§3.2)

Write a Grammar in Backus Naur form.
Parse the unstructured text into an CST.
...
Profit

Using `Tree-Sitter` (§3.2.1)

https://tree-sitter.github.io/tree-sitter/playground

Lambda Calculus

\begin{matrix} e := & λ x . e & – abstraction \\ | & e_{1} e_{2} & – application \\ | & x & – variable \\ | & (e) \end{matrix}

{
  rules: {
    source_file: $ => $._exp,
    _exp: $ => choice($.abs, $.app, $.var, $._parens),
    abs: $ => prec.right(seq('λ', $.var, '.', $._exp)),
    app: $ => prec.left(seq($._exp, $._exp)),
    var: $ => /[a-zA-Z]+/,
    _parens: $ => choice("(", $._exp, ")"),
  }
}

Context Sensitive: Matching Patterns in Trees (§3.3)

public class Simple {
  public static int assertFalse() {
    assert False;
  }
  public static int divideByZero() {
    return 1 / 0;
  }
}

Folds: General Matching of Patterns in Trees (§3.3.1)

$𝚏𝚘𝚕𝚍 : ((x, a) + ⊥ \to a) \to [a] \to a$
$𝚌𝚊𝚝𝚊 : (f a \to a) \to F \to a$

Tree Traversals (§3.3.2)

Pre- (red), In- (green), and Post-order (blue) traversal of tree. source

def traverse(item: ts.Tree) -> Iterator[ts.Node]:
    cursor = item.walk()
    godeeper = True
    while True:
        node = cursor.node
        if godeeper:
            yield node # Pre or Post
            if not cursor.goto_first_child():
                godeeper = False
        elif cursor.goto_next_sibling():
            godeeper = True
        elif cursor.goto_parent():
            yield node # Pre or Post
            godeeper = False
        else:
            break

Recursive Enumerable: Bespoke (§3.4)

Linters (SpotBugs and EsLint)
No good system, yet...
LLMs to the rescue