$1$ Introduction to Parsing

In this assignment, we will be building a parser that is capable of identifying whether a com$-$

puter program is valid and syntactically correct. How do we differentiate between the following

syntactically correct expression

$7+(b**3)$

and the incorrect expression

$7**b3?$

All expressions follow a context free grammar, which is a set of rules that can be used to derive

strings. The set of all strings a grammar produces is called the language of the grammar. Consider

the following grammar that is capable of producing all arithmetic expressions using additions,

multiplications and brackets to enforce order of operations.

$ST|T+S$

$TI|I**S|(S)$

$Iid|$ num

The symbols $S,T$ and I are non$-$terminals, while,$+**,($ and $)$ are terminal symbols. The symbols

id and num are placeholders to indicate identifiers and numeric constants respectively, which can

also be expressed as production rules in the grammar. But we will consider these as terminal

symbols. A production rule replaces a non$-$terminal symbol with symbols that it derives. So the

rule $ST+S$ replaces $S$ with the string $T+S.$ The first non$-$terminal symbol is the start symbol.

A derivation is a set of production rules applied from the start symbol where each non$-$terminal

is replaced with its production. A valid arithmetic expression is the set of all strings of terminal

symbols that can be derived from the start symbol $S.$ For example, the expression num num