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 developer's intention, but later levels give us more structure, making the analysis more robust and easier to write.

We can start by analyzing 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 are 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 converts the AST into 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 compiled to Bytecode, now the style from the original language is gone, and only pure functionality is left.

While every step down the ladder 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 completeness (rejecting no good programs). 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 sequences of symbols from the alphabet. If a string is in a language, we refer to it as a word.

The goal is to automatically 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 running forever.

We can describe every programming analysis problem as a 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: ${\mathrm{S}\mathrm{A}}_{halt}(p)⟹p\in L_{halt}$

• Complete: $p\in L_{halt}⟹{\mathrm{S}\mathrm{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 because we will keep applying the production rules, rewriting strings that look like $\alpha$ into $\beta$ until there are no non-terminals left. Any string in a language is called a word. If 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 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 have type 3 languages. The type 3 language category is the most restrictive, and contains all languages definable by regular expressions. In practice, this only allows for repeats of small languages and cannot match nested parentheses. 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 parentheses. 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 parentheses:

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, arises when we want to match items nested within other items.

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

Parsers are often generated automatically from grammars, and 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 defined by a set of productions (as 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 use 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, ")"),
  }
}

$ jpamb -vv analyse syntaxer-treesitter

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

divide_q = tree_sitter.Query(
    JAVA_LANGUAGE,
    """
(binary_expression
operator: "/"
) @divide
""",
)

divide_found = any(
    capture_name == "divide"
    for capture_name, _ in tree_sitter.QueryCursor(divide_q).captures(body).items()
)

if div_found:
    log.debug("Found divide")
    print("divide by zero;found")
else:
    log.debug("No divide")
    print("divide by zero;not-found")

for q in jpamb.QUERIES:
    if q != "assertion error" and q != "divide by zero":
        print(f"{q};skip")

$ jpamb -vv analyse --filter Simple syntactic-treesitter

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

• Tree traversal - Wikipedia

In practice, general recursion is often expensive in terms of speed and memory; luckily, all recursions can be made into iterative traversals by mimicking the stack manually. When we traverse, we differentiate between pre - and post-orders, i.e ., do we match 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. LLMs, due to their fixed input window, can only recognize regular languages; however, in practice, they tend to do well on simple analysis tasks because of their ability to recognize common patterns.