-- This program creates and tests context-free grammars.
-- The tests involve generating all possible strings in
--   the grammar of a given length.
-- The functions that manipulate the grammar do not
--   necessarily reclaim storage, and do not
--   use the most efficient possible algorithm, so
--   they may be unsuitable for large grammars or
--   large string lengths.


with TEXT_IO; use TEXT_IO;
with GRAMMAR; use GRAMMAR;


procedure A5 is

package INT_IO is new INTEGER_IO(INTEGER); use INT_IO;


-- grammars to be tested
g0,g1,g2:grammarptr;

-- it's convenient to give names to symbols
s,np,vp,pp,det,n,v,p:symbolptr;
x,y,e,t,f,lt,gt,plus,times:symbolptr;

-- an output pointer to the lists of strings of
--   the desired length
l0:YIELDS.listptr;



begin


  -- This is a grammar for a fragment of English
  -- The rules are:
  --   S -> NP VP
  --  NP -> Det N  |  Det N PP
  --  PP -> P NP
  --  VP -> V      |  V NP     |  V PP
  --
  -- Note that the lexical categories P, V, N, and Det
  --   are treated as terminal symbols

  s :=  new symbol'("s  ");
  np := new symbol'("np ");
  vp := new symbol'("vp ");
  pp := new symbol'("pp ");
  det :=new symbol'("det");
  n :=  new symbol'("n  ");
  v :=  new symbol'("v  ");
  p :=  new symbol'("p  ");

  g0 := make_grammar(s);
  add_Nonterminal(g0,np);
  add_Nonterminal(g0,vp);
  add_Nonterminal(g0,pp);
  add_rule(g0,s,np,vp);
  add_rule(g0,np,det,n);
  add_rule(g0,np,det,n,pp);
  add_rule(g0,pp,p,np);
  add_rule(g0,vp,v);
  add_rule(g0,vp,v,np);
  add_rule(g0,vp,v,pp);
  add_rule(g0,vp,v,np,pp);

  l0 := get_yields(s,g0,3);
  traverse_yields(l0);
  new_line;

  l0:= get_yields(s,g0,4);
  traverse_yields(l0);
  new_line;

  l0:= get_yields(s,g0,5);
  traverse_yields(l0);
  new_line;

  l0:= get_yields(s,g0,6);
  traverse_yields(l0);
  new_line;

  l0:= get_yields(s,g0,7);
  traverse_yields(l0);
  new_line;

  l0:= get_yields(vp,g0,6);
  traverse_yields(l0);
  new_line;

  l0:= get_yields(s,g0,8);
  traverse_yields(l0);
  new_line;



  -- This is a simple grammar with rules
  --    S -> x | x S S

  -- Note that the symbol s is already defined

  x :=  new symbol'("x  ");

  g1 := make_grammar(s);
  add_rule(g1,s,x,s,s);
  add_rule(g1,s,x);

  l0:=get_yields(s,g1,3);
  traverse_yields(l0);
  new_line;

  l0:=get_yields(s,g1,5);
  traverse_yields(l0);
  new_line;

  l0:=get_yields(s,g1,6);
  traverse_yields(l0);
  new_line;

  l0:=get_yields(s,g1,7);
  traverse_yields(l0);
  new_line;

  l0:= get_yields(vp,g1,6);
  traverse_yields(l0);
  new_line;



  -- This is a grammar for simple algebraic expressions.
  -- Its rules are
  --   E -> T | T + E
  --   T -> F | F * T
  --   F -> x | y | < E >

  -- Note that the symbol x is already defined.

  y :=  new symbol'("y  ");
  e :=  new symbol'("e  ");
  t :=  new symbol'("t  ");
  f :=  new symbol'("f  ");
  lt := new symbol'("<  ");
  gt := new symbol'(">  ");
  plus := new symbol'("+  ");
  times := new symbol'("*  ");

  g2 := make_grammar(e);
  add_nonterminal(g2,t);
  add_nonterminal(g2,f);
  add_rule(g2,e,t);
  add_rule(g2,e,t,plus,e);
  add_rule(g2,t,f);
  add_rule(g2,t,f,times,t);
  add_rule(g2,f,x);
  add_rule(g2,f,y);
  add_rule(g2,f,lt,e,gt);

  l0:=get_yields(e,g2,1);
  traverse_yields(l0);
  new_line;

  l0:=get_yields(e,g2,3);
  traverse_yields(l0);
  new_line;

  l0:=get_yields(e,g2,4);
  traverse_yields(l0);
  new_line;

  l0:=get_yields(e,g2,5);
  traverse_yields(l0);
  new_line;

  put(YIELDS.length(l0));
  new_line;


end A5;