-- This package is used for the representation of context-free
--   grammars.  It provides a type for symbols (including both
--   terminals and nonterminals) and a type for grammars.
--   It also provides a type for lists of symbols, and for
--   lists of lists of symbols.

-- Grammars are assumed to have no epsilon rules, and no
--   left recursion.

-- This package does not reclaim storage.


with TEXT_IO;
with LINK;

package grammar is


-- publicly accessible types

-- can any of this be private??
-- if so, should document symbol constructor
--  and that symbols are equal iff strings are

subtype string3 is string(1..3);
type symbol is new string(1..3);
type symbolptr is access symbol;

type ruleptr is private;
type grammarptr is private;

package SYMBOLLIST is new LINK(symbolptr);
use SYMBOLLIST;

package YIELDS is new LINK(SYMBOLLIST.listptr);
use YIELDS;



-- procedures & functions


-- prints the symbol pointed to by s to standard output

procedure put(s:symbolptr); 



-- creates and returns a grammar with a given start symbol s,
--   with no other nonterminals, and with no rules.

function make_grammar(s:symbolptr) return grammarptr;



-- add a given symbol s to a given grammar g

procedure add_nonterminal(g:grammarptr; s:symbolptr);



-- add the rule to the grammar g whose LHS is the symbol lhs
--   and whose RHS contains only the symbol rhs1

procedure add_rule(g:grammarptr; lhs,rhs1:symbolptr);



-- add the rule to the grammar g whose LHS is the symbol lhs
--   and whose RHS contains the symbols rhs1 and rhs2
--   in that order.


procedure add_rule(g:grammarptr; lhs,rhs1,rhs2:symbolptr);


-- add the rule to the grammar g whose LHS is the symbol lhs
--   and whose RHS contains the symbols rhs1, rhs2, and rhs3
--   in that order.

procedure add_rule(g:grammarptr; lhs,rhs1,rhs2,rhs3:symbolptr);



-- Creates and returns a list of those strings of length n
--   that can be generated from the nonterminal symbol s 
--   of the grammar g.
-- No check is necessarily made whether s is a nonterminal
--   symbol of g.  In this case, the result returned may be arbitrary.
-- This function may be slow for large n or large grammars.

function get_yields(s:symbolptr; g:grammarptr; n:integer) return YIELDS.listptr;



-- print a list l0 of lists of symbols to standard output.

procedure traverse_yields(l0:YIELDS.listptr);



private
  type rule;
  type ruleptr is access rule;
  type grammar;
  type grammarptr is access grammar;


end grammar;