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:

<expr> = NUMBER | '(' <expr> <expr> <expr> ')' <op> = '+' | '-' | '*' | '/'

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

NUMBERwhich 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 <op> 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

<stmt> = <print-stmt> | <if-stmt> <if-stmt> = if <boolean-expr> then <stmt> | if <boolean-expr> then <stmt> else <stmt>

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

<stmt> = <print-stmt> | <if-stmt> <if-stmt> = if <boolean-expr> then <stmt> fi | if <boolean-expr> then <stmt> else <stmt> fi