CPSC 3520 - DAY 3
JANUARY 18, 2018

================================================================================

BASIS OF FORMAL GRAMMAR
-----------------------

	1. Set of Productions
	2. Terminals
	3. Non-terminals
	4. Starting symbol that starts from non-terminals

Chomsky Hierarchy
-----------------

	T0 Grammar has no constraints (you can do anything you want)
	T1 Context-sensitive aa_iB -> aB_iB, replacements involving the 
	empty string are treated as a special case.
	T2 Context-Free Grammar (CFG) a_1 = S_1 (a_1 must be a single
	nonterminal)

To figure out the language of a grammar:

	Is it an element of the language of the grammar?
	Use the production starting with S
	Is it comprised solely of terminals?

S -> AB
S -> C
A -> C
A -> a
B -> b
B -> c
C -> d

One way to do it:

S
AB
aB
ac

Another way to do it:

S
AB
Ac
ac

Still another way:

S
C
d

ac satisfies the constraints
d satisfies the constraints

Because there is a derivation, it is an element of the language of the grammar.


Derivation (or Parse) Tree
--------------------------

A derivation or parse tree, T, has the following characteristics:

	1. The root of T is the starting symbol S E V_N
	2. Leaf nodes of T are terminals E V_T
	3. Interior nodes are non-terminals
	4. The children of any non-leaf node represent the right hand side
	(RHS) of some production in P, where the parent node represents the
	corresponding LHS of the production.

		
		S
	       / \
	     A    B
	     |    |
	     C    c
	     |
	     d


		
		S
	       / \
	     A    B
	     |    |
	     C    c
	     |
	     d

***If there were two different derivation trees, then the grammar would be
ambiguous***

A grammar is ambiguous if any string in L(G)^a has two or more distinct
derivation trees.

Classic Examples of Ambiguity
-----------------------------

Classic examples of potential ambiguity in programming languages include:

	-Strings employing binary mathematical operators.  For example,
	what is the underlying structure of:

			a = b + c * a

	Of course, specification of operator precedence together with
	syntax specification may eliminate this problem ex. PEMDAS

	The use of nested if-then-(optional)-else constructs.  This is a major
	source of potential ambiguity, hence the syntax specification is 
	usually augmented with a description of the corresponding
	interpretation algorithm.