6.6. Grammar.   

These graphs can be used to express the grammar of the language. 


A GRAMMAR is a finite set of productions which contain terminal

or non-terminal strings.

A production is of the form:
<A>::=1|2|3|.....
where A is non empty string of non-terminals and i's are strings, possibly empty, of terminal or non- terminal symbols.
If i can be changed directly into then is directly derived from .
A derivation is a sequence of elements
1.....n
such that <i>::=<i-1>. 0 < i <= n. 

If there is at least one step in a derivation n >= 1 then

n is eventually derived from 0.


If n >= 0, i.e. perhaps no steps in derivation then n is derived from 0.

A sentential form is one of these strings which is derived from the start or sentence symbol.
<program>::= program id ( id ) ; block .

A sentence is a sentential form which only contains terminal symbols. 


 import local.units.sdsu.io.*;

 public class Hello

 {

     public static void main(String argv[])

     {

        Format.print(System.out,"Hello\n");

     }

 }

      The wombat eats the fish.


      Term         symbol   use        Meaning

Directly derived     =>    0=>n    in one step

eventually derived   =>+   0=>+n   in one or more steps

    derived          =>*   0=>*n   zero or more steps

sentential form            S =>*n

Now we can create a syntax graph for any BNF input. 

In fact, programs exist which churn out a "front end"

or syntax checker for a particular language.

YACC is a compiler Compiler.  Context free grammar is

used to produce a C or Fortran program which contains

routines to analyse the syntax of language.  YACC can

handle ambiguous structures.  Uses user defined precedence.

The syntax graph can be used to create, as follows, the code necessary to parse the language. 

   Although for following, we have two rules:

       (1)  First symbol(each branch)i = First symbol(each branch)j  i  !=  j

       (2)  If we can traverse a graph without getting a new symbol,

                    we must "know" what symbols may follow.