🏗️ ΘρϵηΠατπ🚧 (under construction)

Syntax
The syntax of a programming language is the set of rules that define what allowed expressions of a programming language can look like.
Grammar
A grammar is a formal description of how to generate expresions

An example of a grammar that generates arithmetic operations is specified as follows:

Grammar for Arithmetic
We define the grammer for artimetic operations as: 
            &ltexpr> = NUMBER
                       | '(' &ltexpr> &ltexpr> &ltexpr> ')'

            &ltop>   =  '+' | '-' | '*' | '/'

The left hand side of equations in our grammar are called non-terminal symbols, which means that we can generate valid strings in this language's syntax by using the rules defined by the grammer to produce strings that do not contain non-terminal symbols.

Terminal symbols in the above example include

NUMBER
which represents any numeric literal and anything surrounded by single quotes is also terminal (Note that we won't include the single quotes while substituting). The vertical bar symbols indicates the separation of different options for substitution, for example &ltop> can be any one of 
+, -, *, /
. Note that our grammar is recursive

Ironically we speak of formality, but we define our grammar meta syntax using the english language, if it was specified using another syntax then we'd require infinitely many syntax.

Syntactically Valid
We say that a string is syntactically valid iff it can be generated by the language's grammar
Syntactically Valid Arithmetic
Show that 1, 2, are valid
Syntactic Abiguity
We say that a grammar is ambiguous iff it generates a string expression for which there are two or more distinct ASTs
Ambiguous String Expression
A string expression is ambiguous with respect to a grammar if that grammar generates two or more distinct AST's for the string expression.
Ambiguous If Then Grammar
Prove that the following grammar is ambiguous 
                &ltstmt> = &ltprint-stmt> | &ltif-stmt>
                &ltif-stmt> = if &ltboolean-expr> then &ltstmt>
                              | if &ltboolean-expr> then &ltstmt> else &ltstmt>

Note that we can fix the above grammar by introducing delimiters like this:

        &ltstmt> = &ltprint-stmt> | &ltif-stmt>
        &ltif-stmt> = if &ltboolean-expr> then &ltstmt> fi
                      | if &ltboolean-expr> then &ltstmt> else &ltstmt> fi