Syntactic Analysis

The Levels of Syntax §1.1

When matching syntax it is important to match at the right level of abstraction. Initial levels contain more of the developers intention, but later levels gives us more structure, making the analysis more robust and easier to write.

We can start by analysing the text directly, this allows us to extract information about the white-space of the program. However, if we don't think that the white-space is important for the analysis, we can look at the tokens instead. The tokens is a list of elements matched by the parser to group patterns like integer literals 1232 and 232, so that they appear the same to the parser.

The parser converts the list of tokens into a Concrete Syntax Tree. A CST is the collection of all the tokens of the program, but placed in a tree like structure. For example 10 + (5 + 3) is turned into a tree like (parenthesis (+ 10 (parenthesis (+ 5 3)))) instead. This deals with precedence and other headaches we don't want to think about. E.g ., is 10 + 3 * 5 equal to 10 + (3 * 5) or (10 + 3) * 5?

In contrast to CST, Abstract Syntax Tree does not have to follow directly from the structure of the text. This allows the AST to remove seemingly unimportant information from the tree. E.g ., parenthesis: (( 10 )) and ( 10 ) are both stored as 10.

The compiler then coverts the AST into a some kind of Intermediate Representation, this can be the LLVM-IR, ClangIR, or RTL. At this level, a lot of work has been done by the compiler to disambiguate references (making all variables fully qualified) and optimize some cases. x + 2 + 4 might now be mypackage.Class.x + 6, which makes some kinds of analysis easier.

Finally the IR is complied to Bytecode, now the style from the original language is gone, and only pure functionality is left.

While every step down the latter makes it easier to write analyses, we lose a little of the context and intention of the developer.

Goal of Syntactic Analysis §1.2

Since a syntactic analysis can never be sound (accepting only good programs), we often have to aim for complete (rejecting no good program). This is in line with a study by Christakis (2016), that shows that most developers would rather have an unsound analysis than too many warnings. Here are two quotes from the findings:

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

A Language — Formally Speaking §2.1

In Computer Science, we refer to a language as a set of a sequence of symbols from the alphabet. If a string is in language we refer to it as a word.

The goal is automatically to figure out if a given word is in the language or not. We differentiate between Recognizers and Deciders. A decider, is a machine (or Automaton), which can determine if a string is in a language or not. A recognizer does the same thing, but is allowed to never give an answer. Essentially run forever.

We can describe every programming analysis problem as sub-language problem: For example, the language of all terminating java programs can be described like so:

$$L_{halt}=\{p|p\mathrm{\text{terminates}},p\in L_{Java}\}$$

It is also because of language theory, that we use sound and complete for static analyses as we do. In fact, we can see a static analysis as a decider for a sublanguage.

• Sound: $S{A}_{halt}(p)⟹p\in L_{halt}$

• Complete: $p\in L_{halt}⟹S{A}_{halt}(p)$

Production Rules and Grammars §2.2

In practice we define languages using Grammars. A grammar is a collection of production rules of the form $\alpha \to \beta$, where $\alpha ,\beta$ are sequences of symbols (represented by $a$, $b$, and $c$) and nonterminals (represented by $A$, $B$, and $C$). They are called non-terminals as we will keep applying the production rules, rewriting the string that look like $\alpha$ into $\beta$ until there no non-terminals left. Any string in a language is called a word, and the language is a programming language we call it a program.

We can now see if a word $w$ is in a language by generating all possible words in the language, and then checking if $w$ is in that set. This algorithm, clearly can run forever, so more efficient solutions are needed.

This is best illustrated by an example.

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

What Types of Languages Exist? §2.3

Since syntactic analysis is simply matching strings, which languages can we efficiently match? This is where the Chomsky hierarchy comes in.

It separates languages into four categories of decreasing expressive power. On the top of the hierarchy, we type 3 languages. The type 3 language category is the most restrictive, and contain all languages definable by regular expressions. In practice, this only allows for repeats of small languages and cannot match nested parenthesis. Figuring out if a string is in a type 3 language is decidable.

In a type 2 language we can have words defined by nesting. This is very useful if you want nested parenthesis. This language is the basis of the syntax of most programming languages (except C: typedef I'm looking at you!). Type 2 languages can be recognized using a push down automaton.

In a type 1 language, we can define our language recursively, but we are also allowed to give context to the recursion. For example checking a program to see if a variable is in scope, is context sensitive because it depends on the declarations and how nested we are in the curly parenthesis:

int hello(int x) { 
  // Context { x , y }
  int y; 
  { 
    int z; 
    // Context { x , y, z} is z in scope? Yes
  }
  // Context { x , y} is z in scope? No
}

Finally, we have type 0 languages, is a set of words which can be recognized by a Turing machine. One example is all programs that terminate.

Regular: Regular Expressions §3.1

To match regular languages we can use regular expressions, they are extremely useful, common, and very fast (They can be recognized in $O(n)$):

The programs from this language can be executed to form sets of accepted words. We can easily define the meaning of the language using denotational semantics. Denotational semantics just means, giving an mathematical object meaning by mapping it to one we already know about.

In practice, this language is extended quite heavily to be able to easily write better matches. You can explore different flavors of the language and how it matches on https://regex101.com/. Here | is often used instead of +, and + is used to indicate one or more matches: $ee*=e^{+}$.

r"public\W+static\W+(?P<retype>void)\W+(?P<mname>\w*)()\W*{(?P<code>[^}]*)}"

Context-Free: Grammars and Parsers §3.2

At this point it should be clear that using regular expressions for matching a Context Free language is a bad idea. The problem of course happens when we want to match items nested within other items.

Instead we want to use a Parser. A parser is a structured program which goal is to take in a stream of tokens and turn them into a CST.

Parsers are often generated automatically from grammars, and the grammars are often written in what is known as Backus-Naur form. In programming language theory, this is the primary way to define the syntax of a programming language.

It is created by a set of productions (like with our grammar), but we allow each production to have multiple matches, separated by |: $A:=abc|B|x*$ and B := a. The BNF is often extended with syntax for many $\cdot *$ and some ${\cdot }^{+}$. Furthermore, we often uses first-match semantics where we match on the first production we can. This makes the language deterministically context-free, which changes the complexity of parsing a program from $O(n^3)$ to $O(n)$.

There are many categories of parsers, and to learn more about them you should take the 02247 Compilers course.

{
  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, ")"),
  }
}

$ uv run solutions/syntaxer.py 'jpamb.cases.Simple.assertPositive:(I)V'

(method_declaration name: 
      ((identifier) @method-name (#eq? @method-name "assertBoolean"))
      body: (_) @body
    ) @method

(binary_expression
  operator: "/"
) @expr

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

Context Sensitive: Matching Patterns in Trees §3.3

One big limitation of Tree-sitter queries is that they do not currently support nested queries, and we need those if we want to match patterns with context.

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

In this case you have to write your own.

Tree Traversals §3.3.2

• https://en.wikipedia.org/wiki/Tree_traversal

In practice, is general recursion often expensive in terms of speed and memory, luckily all recursions can be made into iterative traversals by mimicking the stack yourself. When we traverse we differentiate between pre and post orders. I.e., do we match for patterns on the way down or on the way up.

In our case, we can use the built-in Tree-sitter cursor to traverse the tree.

Pre or Post-order?

Consider the following traversal of the tree, which of the yield points yield a postorder and which yield a preorder?

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

To match languages beyond Context-Insensitive languages, there exist some tools, but it becomes harder and harder to match full languages efficiently. In this case you have to write bespoke analyses in your favorite language.

Almost all syntactic static analyses or linters falls into this category. Here are some examples:

• https://spotbugs.github.io

• https://eslint.org

There is still interesting work in building an easy and intuitive system for pattern match normal programming constructs with recent work like Rafnsson (2020) and Tomasdottir (2020).

Another approach is to use LLMs. An LLM due to its fixed input window, can only recognize regular languages, however in practice, they tend to do well on simple analysis tasks because of its ability to recognize common patterns.