Objectives

$$ To describe a language using Context$-$Free Grammar $($CFG$)$

$$ To describe an Abstract Syntax Tree $($AST$)$ for a small language.

$$ To contrast an Abstract Syntax Tree from a Concrete Syntax Tree $($CST$)$

$$ To demonstrate how Abstract Syntax Tree$$s can be used my compilers to identify and

describe syntactical errors.

Requirements:

$1.$ Create a Context$-$Free Grammar

Consider the following operations from boolean relational operators:

Less Than $<$ Less Than or Equal

to

$<=$

Greater than $>$ Greater Than or

Equal to

$>=$

Equal to $==$ Not Equal $!=$

Using the following as a basis, create a context$-$free grammar for the boolean

expressions.

$1.$ S $->$ S $??$ S

$2.$ S $->$ S $??$ S

$3.$ S $->$ S $??$ S

$4.$ S $->$ S $??$ S

$5.$ S $->$ S $??$ S

$6.$ S $->$ S $??$ S

$7.$ S $->$ numerical negative infinity to positive infinity

Replace the $??$s with your answer.

$2.$ Create a Concrete Syntax Tree

Along with your solution from question $1,$ add the following to include mathematical

operations in your CFG$.$

$1.$ S $->$ S $+$ S

$2.$ S $->$ S $$ S

$3.$ S $->$ S $*$ S

$4.$ S $->$ S $/$ S

$5.$ S $->($S$)$

Use this CFG to create a concrete syntax tree for the following expression:

$(9+1/5)<=(9*3/6+1)$

$3.$ Convert to Abstract Syntax Tree

Using your Concrete Syntax Tree from question $2,$ create an equivalent abstract syntax

tree.

$4.$ Explain the error in terms of an AST

Consider the following boolean expression: $(1*9-)<40$

With the subtraction operation having no value to subtract from the $9,$ this is a clear

syntax error.

Draw the Abstract Syntax Tree as far as you can, and stop when you can go no further.

Explain how this process of creating the AST demonstrates how it can leads to better

descriptions of syntax errors.

Abstract Syntax Tree

Explanation of error finding