Syntactic analysis is the process of checking whether a program is syntactically correct.

The compilation process consists of:

1. Lexical analysis: programs decomposed into tokens
2. Parsing: tokens checked to ensure they form a word in the prog. language

Parsing

A parser reads a sequence of tokens and builds a parse tree (or derivation tree), outputting an abstract syntax tree.

A parse tree shows the step-by-step process of building the AST.

Abstract Syntax

Abstract Syntax describes the syntax trees, to which semantics is associated.

Link to original

Top-Down parsing: Recursive descent parsing (RDP)

In top-down parsing, (starting from the start symbol) search for a rule that rewrites the non-terminals to yield terminals consistent with the input.

There are two problems with RDP:

• left recursion
• repeated terminal checking

A grammar is suitable for RDP if, wherever there is a choice, the parser can select the correct alternative by looking at the current symbol. If this is not the case, we end up backtracking a lot which is inefficient (each token is examined several times). We can make it less expensive by left factoring the grammar: expand rules to expose the common part and factor it out.

Left recursion can cause an RDP to get stuck in an infinite loop. A grammar is left-recursive if it has a non-terminal $A$ such that there is a derivation $A\to A\alpha$ for some string $\alpha$.

To eliminate left recursion from any rule, we can apply the following substitution:

We can also run into infinite loops if the grammar is indirectly left-recursive. $\begin{array}{rl}⟨A⟩& \to ⟨B⟩\alpha |\beta \\ ⟨B⟩& \to ⟨A⟩\gamma |\delta \end{array}$

We can rewrite indirect left-recursion as an equivalent direct left-recursion by using the substitution rule below: (and then eliminate left-recursion as before) $\begin{array}{r}⟨A⟩\to (⟨A⟩\gamma |\delta )\alpha |\beta \\ \text{is equivalent to}\\ ⟨A⟩\to ⟨A⟩(\gamma \alpha )|\delta \alpha |\beta \end{array}$

Example RDP 1

Let’s say we have the grammar:

stat -> begin statlist
      | S
statlist -> end
          | stat ; statlist

Assume that the input is derived from start symbol stat, examine each alternative rule for stat. Compare first unmatched token with first symbol on RHS of each alternative rule for stat. If a matching production is found, use it to rewrite stat. Repeat, using next input token to determine the rule used for next non-terminal. If no match, try a rule that begins with a non-terminal, e.g. stat;statlist.

Example RDP 2

Given the following definition: $\begin{array}{rl}⟨S⟩& \to c⟨R⟩b\\ ⟨R⟩& \to a|ra\end{array}$ Use top-down parsing to determine if crab is valid.

Example of left factoring

Given the grammar:

stmt -> while exp do stmt | assign | call
assign -> ident = exp
call -> ident ( arglist )

Expand assign and call: stmt -> ... | ident = exp | ident ( arglist )

And then factor out ident:

stmt -> ... | ident rest
rest -> = exp | ( arglist )

Example of left recursion

Given the definition: $\begin{array}{rl}⟨T⟩& \to ⟨T⟩\times ⟨D⟩|⟨D⟩\\ ⟨D⟩& \to [0-9]\end{array}$ The parse tree ends up infinitely recursing:

Example of indirect left recusion

Bottom-up parsing: Shift-reduce parsing

In bottom-up parsing, we start from the input and compare it against right-hand side of the rules, to find where a string can be replaced by a non-terminal. Parsing succeeds when the whole input has been replaced by the start symbol of the grammar.

Shift-reduce is hard to do by hand but it’s efficient since we don’t have to rewrite the grammar.

A parser generator generates a parser from a given grammar.

1. Generate a push-down automata to recognise language (shift and reduce transitions)
2. Generate code in a chosen language

Example

Lexical Analysis

A lexer reads a string and converts it to a sequence of tokens. In practice it also removes white-space / tabs, comments, has some limited error detection / correction, and can do macro expansion.

Skipping slides 12-18

A regular expression $r$ denotes a language $L(r)$. (set of acceptable words) Formulation rules for regular expressions over alphabet $\mathcal{X}$:

• $ϵ$ denotes $\{ϵ\}$
• $a$ denotes $\{a\}$ for any symbol $a\in \mathcal{X}$
• Suppose $r$ and $s$ are regular expressions:
  • $(r)|(s)$ denotes $L(s)\cup L(s)$; sometimes written as $(r)+(s)$
  • $(r)?$ denotes $(r)|ϵ$
  • $(r)(s)$ denotes $L(r)L(s)$
  • $(r{)}^{\ast }$ denotes $L(r{)}^{\ast }$, i.e. $ϵ|r|rr|\dots$
  • $(r{)}^{+}$ abbreviates $(r)(r{)}^{\ast }$ Conventions: drop unnecessary parentheses, all operators are left-associative, precedence is $\ast$ then concatenation then $|$, and use abbreviations incl. character classes e.g. $[a-z]$.

A regular definition, over an alphabet $\mathcal{X}$, is a sequence of definitions: $\begin{array}{rl}⟨d_0⟩& \to r_0\\ ⟨d_1⟩& \to r_1\\ & \dots \\ ⟨d_n⟩& \to r_n\end{array}$ Where each $d_i$ is a distinct name and each $r_i$ is a regular expression over $\mathcal{X}\cup \{d_0,\dots ,d_{i-1}\}$. Symbols in $\mathcal{X}$ are called terminals. $\{d_0,\dots ,d_n\}$ are called non-terminals.

Example

$\begin{array}{rl}⟨digit⟩& \to 0|1|\dots |9\\ ⟨digits⟩& \to ⟨digit⟩⟨digit{⟩}^{\ast }\\ ⟨fraction⟩& \to .⟨digits⟩|ϵ\\ ⟨number⟩& \to ⟨digits⟩⟨fraction⟩\end{array}$