/* cfp_parser - the SELVA bootom-up parser for an arbitrary context-free grammar. */
/* Last edited on 2015-04-02 03:22:06 by stolfilocal */

#define PROG_NAME "cfp_parser"
#define PROG_VERSION "1.0"
#define PROG_USAGE \
  PROG_NAME " GRAMMAR.red PHRASE.phr > CHART.chr"

/* Must define _GNU_SOURCE in order to get {asprintf} */
#define _GNU_SOURCE

#include <cfp_types.h>

#include <affirm.h>
#include <js.h>
#include <nget.h>
#include <fget.h>
#include <filefmt.h>

#include <stdlib.h>
#include <stdio.h>

/* PROTOTYPES */

Grammar_t *cfp_read_Grammar(FILE *rd);
/*
  File format: the first line must be standard header "begin grammar
  (format of ...)"; see "filefmt.h".
  
  Then come three lines of the form "symbols = {NS}", "rules = {NR}",
  and "axiom = {X}" where {X} is in the range {1..NS}.
  
  Then come {NS} symbol lines, of the form "{S}: {name}" where {S} is
  the symbol number in the range {1..NS}, in order, and {name} is
  either a token without any embedded blanks or '#'.
  
  Then come {NR} rule lines of the form "{ir}: {H} {L} {R} {cmt}" where
  {ir} is a rule number, in {1..NR}; {H}, {L}, and {R} are symbol
  numbers in the range {1..NS}; and {cmt} is either empty or "#"
  followed by any string. The {L} field may also be 0, denoting a
  unary rule.
  
  The standard footer "end grammar" indicates the end of the input.

  Comment lines and/or blank lines are allowed after the header,
  before the footer, and just before the symbol and rule data
  sections. */

Phrase_t *cfp_read_Phrase(FILE *rd, int NS);
/*
  File format: the first line must be standard header "begin phrase
  (format of ...)"; see "filefmt.h".
  
  Then come two lines of the form "nodes = {NN}" and "arcs = {NA}".
  
  Then come {NA} arc lines of the form "{IA}: {O} {D} {S} {VAL}
  {CMT}". Here {IA} is the arc number, ranging over {1..NA}, in order;
  {O,D} are node numbers in the range {1..NN}; {S} is a symbol name,
  as in the grammar's symbol table; {VAL} is either a token without
  embedded blanks or '#'; and {CMT} is either empty or "#" followed by
  any string.
  
  The standard footer "end phrase" indicates the end of the input.

  Comment lines and/or blank lines are allowed after the header,
  before the footer, and just before the arc data section. */
  
int main(int argc, char **argv);
Chart_t *cfp_parse(Phrase_t *P, Grammar_t *G);
Grammar_t *cfp_new_Grammar(int NS, int NR);
Phrase_t *cfp_new_Phrase(int NN, int NA);
Chart_t *cfp_new_Chart(int NN);
int cfp_triang_index(PNodeId_t i, PNodeId_t j);
void cfp_set_Chart(Chart_t *C, GSymbId_t S, PNodeId_t i, PNodeId_t j, CSymb_t *n);
CSymb_t *cfp_get_Chart(Chart_t *C, GSymbId_t S, PNodeId_t i, PNodeId_t j);
CSymb_t *cfp_new_CSymb(GSymbId_t S, bool_t term, void *info);
CRule_t *cfp_new_CRule(GRuleId_t irule, PNodeId_t cut, CSymb_t *Ln, CSymb_t *Rn, CRule_t *next);
void cfp_add_CRule
  ( Chart_t *C,
    GRuleId_t irule, 
    GSymbId_t H, 
    GSymbId_t L, 
    GSymbId_t R, 
    CSymb_t *Ln, 
    CSymb_t *Rn, 
    PNodeId_t ini, 
    PNodeId_t cut, 
    PNodeId_t fin
  );
void cfp_init_Chart(Chart_t *C, Phrase_t *P);
void cfp_write_Chart(FILE *wr, Chart_t *C, Phrase_t *P, Grammar_t *G);
void cfp_arg_error(char *msg);
void cfp_file_error(char *where, int loc, char *msg);
char *cfp_plot_span(PNodeId_t i, PNodeId_t j, int NN);

cfp_lookup_symbol(Grammar_t *G, char *name);
/* 
  Finds in {G} the number {S} of the symbol with given {name}.
  Returns {NOSYMB} if not found. */

char *cfp_read_symbol_name(FILE *rd);
/* 
  Skips blanks then reads zero or more nonblank chars, up to (but not
  including) EOF or the first blank char. Returns a pointer to newly
  allocated area with the string and a terminating '\0'. */

char *cfp_read_arc_name(FILE *rd);
/* 
  Skips blanks then reads zero or more nonblank chars, up to (but not
  including) EOF or the first blank char. Returns a pointer to the 
  string and a terminating '\0'.  The string is newly allocated unless
  it is "-". */

bool_t cfp_skip_comment(FILE *rd);
/* 
  Skips blanks until a newline ('\012') or a '#' character. If the
  latter, skips any additional characters until the newline. Consumes
  the newline. Returns TRUE normally, FALSE if syntax error. */

void cfp_skip_comment_lines(FILE *rd);
/* 
  Reads zero or more lines that are either wholly blank or contain '#'
  as their first non-blank character. Also skips any leading spaces of
  the first non-comment line found. */
   
/* IMPLEMENTATIONS */

/* 
  PARSING
  
  Parsing means building a chart that represents all possible
  parse trees of a given phrase {P} according to a given 
  grammar {G}.
  
  The chart under construction is divided into two sections,
  the /complete/ entries and the /incomplete/ ones (the /agenda/).
  
  Um nó {n} da agenda ainda pode ter {T(n)} incompleto, e podem ser
  usados em {CRule_t}s ainda não criados. No primeiro caso, eles podem
  vir a ganhar novos {CRule_t}s filhos.
  
  Para um nó completo {n} {T(n)} já está completo, e nenhum descendente de
  {n} será alterado.
*/

Chart_t *cfp_parse(Phrase_t *P, Grammar_t *G)
  {
    Chart_t *C = cfp_new_Chart(P->NN);
    /* Agenda: */
    PNodeId_t jA, iA;
    /* The chart consists of all entries {i,j,S} of {C} with {j<jA},
      or {j=jA} and {i>iA}, or {j=jA}, {i=iA}, and {S>pA.S}.
      The remaining nodes in {C} constitute the agenda.
    */
    cfp_init_Chart(C, P);
    for (jA = 2; jA <= C->NN; jA++)
      for (iA = jA-1; iA >= 1; iA--)
        { /* Get bucket {iA,jA} from chart: */
          CSymb_t *nA = C->ent[cfp_triang_index(iA,jA)];
          while (nA != NULL)
            { /* Scan entries of chart bucket {iA,jA}, in order of decreasing symbol id: */
              GSymbId_t N = nA->symb;
              /* Neste ponto {T(nA)} está completo, {org(nA)=i, dst(nA)=j}. */

              /* Process all unary rules {H --> N}: */
              GRuleId_t irule = G->firstU[N]; /* A unary rule which uses {N} as the {right} part. */
              while (irule != NORULE)
                { /* Rule number {irule} uses {N} as the {right} part. */ 
                  GRule_t *gr = &(G->rule[irule]);
                  GSymbId_t H = gr->H, L = gr->L, R = gr->R;
                  affirm(R == N, "R symb mismatch");
                  affirm(L == NOSYMB, "L used in unary rule");
                  cfp_add_CRule(C, irule, H,NOSYMB,N, NULL,nA, iA,0,jA);
                  irule = gr->nextR;
                }

              /* Process all binary rules {H --> L N} such that {L} occurs ending at {iA}: */
              PNodeId_t k; /* Candidate starting point of {L}. */
              for (k = iA-1; k >= 1; k--)
                { /* !!! Should merge the lists {G->firstR[N]} and {C->ent[k,iA]} !!! */
                  GRuleId_t irule = G->firstR[N]; /* First rule which uses {N} as the {right} part. */
                  while (irule != NORULE)
                    { /* Rule number {irule} uses {N} as the {right} part. */ 
                      GRule_t *gr = &(G->rule[irule]);
                      GSymbId_t H = gr->H, L = gr->L, R = gr->R;
                      affirm(R == N, "R symb mismatch");
                      affirm (L != NOSYMB, "null L in binary rule");
                      /* Neste ponto {cfp_get_Chart(L,k,iA)} está completa (i.e. no chart)! */
                      CSymb_t *p = cfp_get_Chart(C, L,k,iA);
                      if (p != NULL)
                        { cfp_add_CRule(C, irule, H,L,N, p,nA, k,iA,jA); }
                      irule = gr->nextR;
                    }
                }

              nA = nA->next;
            }
        }

    return C;
  }

void cfp_init_Chart(Chart_t *C, Phrase_t *P)
  {
    PArcId_t iarc;
    for (iarc = 1; iarc <= P->NA; iarc++)
      { 
        PArc_t *arc = P->arc[iarc]; 
        GSymbId_t S = arc->symb;
        CSymb_t *n = cfp_new_CSymb(S,TRUE,(void*)arc);
        cfp_set_Chart(C, S, arc->org, arc->dst, n);
      }
  }

void cfp_add_CRule
  ( Chart_t *C,
    GRuleId_t irule, 
    GSymbId_t H, 
    GSymbId_t L, 
    GSymbId_t R, 
    CSymb_t *Ln, 
    CSymb_t *Rn, 
    PNodeId_t ini, 
    PNodeId_t cut,
    PNodeId_t fin
  )
  {
    CSymb_t *m = cfp_get_Chart(C, H,ini,fin);
    if (m == NULL)
      { m = cfp_new_CSymb(H,FALSE,NULL);
        cfp_set_Chart(C, H,ini,fin, m);
        /* This new node should end up automatically in the agenda part of the chart. */
      }
    CRule_t *cr = cfp_new_CRule(irule, cut, Ln, Rn, (CRule_t *)m->info);
    m->info = (void *)cr;
  }

CSymb_t *cfp_new_CSymb(GSymbId_t S, bool_t term, void *info)
  {
    CSymb_t *n = (CSymb_t *)notnull(malloc(sizeof(CSymb_t)), "no mem");
    n->symb = S; n->term = term; n->info = info; n->next = NULL;
    return n;
  }

CRule_t *cfp_new_CRule(GRuleId_t irule, PNodeId_t cut, CSymb_t *Ln, CSymb_t *Rn, CRule_t *next)
  {
    CRule_t *cr = (CRule_t *)notnull(malloc(sizeof(CRule_t)), "no mem");
    cr->irule = irule; 
    cr->cut = cut;
    cr->Ln = Ln;
    cr->Rn = Rn;
    cr->next = next;
    return cr;
  }

CSymb_t *cfp_get_Chart(Chart_t *C, GSymbId_t S, PNodeId_t i, PNodeId_t j)
  {
    CSymb_t *p = C->ent[cfp_triang_index(i,j)];
    while ((p != NULL) && (p->symb > S)) { p = p->next; }
    if ((p == NULL) || (p->symb != S))
      { return NULL; }
    else
      { return p; }
  }

void cfp_set_Chart(Chart_t *C, GSymbId_t S, PNodeId_t i, PNodeId_t j, CSymb_t *n)
  {
    CSymb_t **anext = &(C->ent[cfp_triang_index(i,j)]);
    CSymb_t *p = *anext;
    while ((p != NULL) && (p->symb > S)) { anext = &(p->next); p = *anext; }
    if (p != NULL) { affirm(p->symb != S, "dup symbol"); }
    affirm(n->next == NULL, "next not null");
    n->next = p;
    (*anext) = n;
  }

int cfp_triang_index(PNodeId_t i, PNodeId_t j)
  {
    return (j-1)*(j-2)/2+(j-i-1);
  }

int main(int argc, char **argv)
  {
    if (argc != 3) { cfp_arg_error("bad args"); }
    char *nameG = argv[1]; /* Name of grammar file. */
    char *nameP = argv[2]; /* Name of phrase file. */
    
    FILE *fG = open_read(nameG);
    Grammar_t *G = cfp_read_Grammar(fG);

    FILE *fP = open_read(nameP);
    Phrase_t *P = cfp_read_Phrase(fP, G->NS);

    Chart_t *C = cfp_parse(P, G);

    cfp_write_Chart(stdout, C, P, G);
    fflush(stdout);
    return 0;
  }

#define GrammarVersion "2004-11-01" 

Grammar_t *cfp_read_Grammar(FILE *rd)
  {
    Grammar_t *G;

    /* Read header "begin grammar (format of YYYY-MM-DD)" */
    filefmt_read_header(rd, "grammar", GrammarVersion);
    cfp_skip_comment_lines(rd);

    /* Read number of symbols and number of rules. */ 
    int NS = nget_int(rd, "symbols"); fget_eol(rd);
    int NR = nget_int(rd, "rules"); fget_eol(rd);

    /* Create grammar and initialize its tables: */
    G = cfp_new_Grammar(NS, NR);
    
    /* Read axiom symbol: */
    int X = nget_int(rd, "axiom"); fget_eol(rd);
    if ((X < 1) || (X > NS)) { cfp_file_error(NULL, NORULE, "bad axiom"); }
    G->axiom = X;

    /* Read symbol data: */
    cfp_skip_comment_lines(rd);
    GSymbId_t S;
    for (S = 1; S <= NS; S++)
      { 
        int N = fget_int(rd);
        if (! fget_skip_blanks_and_test_char(rd, ':')) { cfp_file_error("symbol", S, "missing ':'"); }
        if (N != S) { cfp_file_error("symbol", S, "seq error"); }
        
        char *name = cfp_read_symbol_name(rd);

        /* Skip comments and end-of-line: */
        if (! cfp_skip_comment(rd)) { cfp_file_error("symbol", S, "bad comment"); } 
        fget_eol(rd);

        /* Store symb name in grammar: */
        G->sname[S] = name;
     }

    /* Read rule data: */
    cfp_skip_comment_lines(rd);
    GRuleId_t irule;
    for (irule = 1; irule <= NR; irule++)
      { 
        int jrule = fget_int(rd);
        if (! fget_skip_blanks_and_test_char(rd, ':')) { cfp_file_error("rule", irule, "missing ':'"); }
        if (jrule != irule) { cfp_file_error("rule", irule, "seq error"); }
        
        int H = fget_int(rd);
        if ((H < 1) || (H > NS)) { cfp_file_error("rule", irule, "bad H field"); }

        int L = fget_int(rd);
        if ((L < 0) || (L > NS)) { cfp_file_error("rule", irule, "bad L field"); }

        int R = fget_int(rd);
        if ((R < 1) || (R > NS)) { cfp_file_error("rule", irule, "bad R field"); }

        /* Skip comments and end-of-line: */
        if (! cfp_skip_comment(rd)) { cfp_file_error("rule", irule, "bad comment"); } 
        fget_eol(rd);

        /* Store rule in grammar: */
        if (L == 0)
          { /* Unary rule - prepend to the {firstU} list. */
            L = NOSYMB; /* Just in case {NOSYMB} is not zero... */
            if (R <= H) { cfp_file_error("rule", irule, "H >= R in unary rule"); }
            G->rule[irule] = (GRule_t){H,NOSYMB,R,G->firstU[R]};
            G->firstU[R] = irule;
          }
        else
          { /* Binary rule - insert in the {firstR} list, sorting by {L}: */
            GRuleId_t this = G->firstR[R], prev = NORULE;
            while ((this != NORULE) || (G->rule[this].L > L)) 
              { prev = this; this = G->rule[this].nextR; }
            G->rule[irule] = (GRule_t){H,L,R,this};
            if (prev == NORULE)
              { G->firstR[R] = irule; }
            else
              { G->rule[prev].nextR = irule; }
          }
      }

    /* Read footer "end grammar" */
    cfp_skip_comment_lines(rd);
    filefmt_read_footer(rd, "grammar");
    
    return G;
  }

#define PhraseVersion "2004-11-01" 

Phrase_t *cfp_read_Phrase(FILE *rd, int NS)
  {
    Phrase_t *P;

    /* Read header "begin phrase (format of YYYY-MM-DD)" */
    filefmt_read_header(rd, "phrase", PhraseVersion);
    cfp_skip_comment_lines(rd);

    /* Read number of nodes and arcs. */ 
    int NN = nget_int(rd, "nodes"); fget_eol(rd);
    int NA = nget_int(rd, "arcs"); fget_eol(rd);

    /* Create phrase: */
    P = cfp_new_Phrase(NN, NA);

    /* Read arcs: */
    cfp_skip_comment_lines(rd);
    PArcId_t iarc;
    for (iarc = 1; iarc <= NA; iarc++)
      { 
        int jarc = fget_int(rd);
        if (! fget_skip_blanks_and_test_char(rd, ':')) { cfp_file_error("arc", iarc, "missing ':'"); }
        if (jarc != iarc) { cfp_file_error("arc", iarc, "seq error"); }
        
        PNodeId_t org = fget_int(rd);
        if ((org < 0) || (org > NN)) { cfp_file_error("arc", iarc, "bad org field"); }

        PNodeId_t dst = fget_int(rd);
        if ((dst < 1) || (dst > NN)) { cfp_file_error("arc", iarc, "bad dst field"); }

        if (org >= dst) { cfp_file_error("arc", iarc, "backwards arc"); }

        char *Sname = cfp_read_symbol_name(rd);
        GSymbId_t S = cfp_lookup_symbol(G, Sname);
        if (S == NOSYMB) { cfp_file_error("arc", iarc, "unknown symbol"); }
        free(name);

        char *Aname = cfp_read_arc_name(rd);

        /* Skip comments and end-of-line: */
        if (! cfp_skip_comment(rd)) { cfp_file_error("arc", iarc, "bad comment"); } 
        fget_eol(rd);

        /* Store arc in phrase: */
        PArc_t *a = (PArc_t *)notnull(malloc(sizeof(PArc_t)), "no mem");
        (*a) = (PArc_t){S,org,dst,Aname};
        P->arc[iarc] = a;
      }

    /* Read footer "end phrase" */
    cfp_skip_comment_lines(rd);
    filefmt_read_footer(rd, "phrase");
    
    return P;
  }
  
char *cfp_read_symbol_name(FILE *rd)
  {
    return fget_string(rd);
  }

GSymbId_t cfp_lookup_symbol(Grammar_t *G, char *name)
  { GSymbId_t S;
    for (S = 1; S <= NS; S++)
      { char *Sn = G->sname.el[S];
        if (strcmp(name,Sn) == 0) { return S; }
      } 
    return NOSYMB;
  }

char *cfp_read_arc_name(FILE *rd)
  {
    if (fget_skip_and_test_char(rd, '-'))
      { return "-"; }
    else
      { return fget_string(rd); }
  }

void cfp_skip_comment_lines(FILE *rd)
  {
    while(1)
      { fget_skip_spaces(rd);
        if (fget_test_char(rd, '#'))
          { ungetc('#', rd);
            if (! cfp_skip_comment(rd))  
              { cfp_file_error(NULL, NORULE, "bad comment"); }
            fget_eol(rd);
          }
        else if (fget_test_char(rd, '\012'))
          { /* OK, continue */ }
        else 
          { return; }
      }
  }

bool_t cfp_skip_comment(FILE *rd)
  { int c;
    do 
      { c = fgetc(rd); }
    while ((c=='\000') || (c==' ') || (c=='\011'));
    if (c == EOF) { return FALSE; }
    if (c == '#')
      { do 
          { c = fgetc(rd); }
        while ((c != '\012') && (c != EOF));
        if (c == EOF) { return FALSE; }
      }
    ungetc(c, rd);
    return (c == '\012');
  }
    
  
void cfp_file_error(char *where, int loc, char *msg)
  {
    fprintf(stderr, "data file error:");
    if (where != NULL) { fprintf(stderr, " %s %d:", where, loc); }
    fprintf(stderr, " ** %s\n", msg);
    exit(1);
  }
  
void cfp_arg_error(char *msg)
  {
    fprintf(stderr, "** %s: %s", PROG_NAME, msg);
    fprintf(stderr, "usage: %s\n", PROG_USAGE);
    exit(1);
  }
  
Grammar_t *cfp_new_Grammar(int NS, int NR)
  {
    Grammar_t *G = (Grammar_t *)notnull(malloc(sizeof(Grammar_t)), "no mem");
    G->NS = NS;
    G->NR = NR;
    G->axiom = NOSYMB;
    G->rule = (GRule_t *)notnull(malloc((NR+1)*sizeof(GRule_t)), "no mem");
    G->sname = (char **)notnull(malloc((NS+1)*sizeof(char *)), "no mem");
    G->firstR = (GRuleId_t *)notnull(malloc((NS+1)*sizeof(GRuleId_t)), "no mem");
    G->firstU = (GRuleId_t *)notnull(malloc((NS+1)*sizeof(GRuleId_t)), "no mem");

    /* Initialize the rule table, just in case: */
    GRuleId_t irule; 
    for (irule = 0; irule <= NR; irule++) 
      { G->rule[irule] = (GRule_t){NOSYMB, NOSYMB, NOSYMB, NORULE}; }

    /* Initialize the symbol-indexed arrays: */
    GSymbId_t S; 
    for (S = 0; S <= NS; S++) 
      { G->firstU[S] = NORULE; 
        G->firstR[S] = NORULE;
        G->sname[S] = NULL;
      }
    return G;
  }
  
Phrase_t *cfp_new_Phrase(int NN, int NA)
  {
    Phrase_t *P = (Phrase_t *)notnull(malloc(sizeof(Phrase_t)), "no mem");
    P->NN = NN;
    P->NA = NA;
    P->arc = (PArc_t **)notnull(malloc((NA+1)*sizeof(PArc_t *)), "no mem");
    return P;
  }
  
Chart_t *cfp_new_Chart(int NN)
  {
    Chart_t *C = (Chart_t *)notnull(malloc(sizeof(Chart_t)), "no mem");
    C->NN = NN;
    C->ent = (CSymb_t **)notnull(malloc(NN*(NN-1)/2*sizeof(CSymb_t *)), "no mem");

    /* Initialize the triangular array: */
    PNodeId_t i,j;
    for (i = 1; i <= NN; i++)
      { for (j = i+1; j <= NN; j++)
        { int ix = cfp_triang_index(i,j);
          C->ent[ix] = NULL; 
        }
      }

    return C;
  }

void cfp_write_Chart(FILE *wr, Chart_t *C, Phrase_t *P, Grammar_t *G)
  {
    PNodeId_t i,j;
    affirm(C->NN == P->NN, "P/C NN mismatch");
    for (i = 1; i <= C->NN; i++)
      { for (j = C->NN; j >= i+1; j--)
          { 
            /* Get bucket {i,j} from chart: */
            CSymb_t *n = C->ent[cfp_triang_index(i,j)];
            if (n != NULL)
              { char *txspan = cfp_plot_span(i,j, C->NN);
                while (n != NULL)
                  { /* Scan entries of chart bucket {i,j}, in order of decreasing symbol id: */
                    GSymbId_t N = n->symb;
                    if (n->term)
                      { /* Instance of a terminal symbol. */
                        PArc_t *a = (PArc_t *)n->info;
                        affirm(a->symb == N, "term symb mismatch");
                        char *txrule = NULL;
                        char *txrule = jsprintf("  s%d --> «%d..%d»", N, a->org, a->dst);
                        fprintf(wr, "%-25s", txrule);
                        fprintf(wr, " %3d %3d %s", i, j, txspan);
                        fprintf(wr, " %s --> «%s»", G->sname[N], a->aname);
                        fprintf(wr, "\n");
                        free(txrule);
                      }
                    else
                      { /* Instances of grammar rules */
                        CRule_t *cr = (CRule_t *)n->info;
                        affirm(cr != NULL, "CSymb_t with zero rules");
                        while (cr != NULL)
                          { 
                            GRule_t *gr = &(G->rule[cr->irule]);
                            PNodeId_t cut = cr->cut;
                            char *txrule = NULL;
                            affirm (gr->H == N, "H symb mismatch");
                            if (gr->L == NOSYMB) 
                              { /* Instance of a unary rule. */
                                char *txrule = jsprintf("  s%d --> s%d", N, gr->R);
                                affirm(cut == NONODE, "nonzero cut in unary rule");
                                affirm (cr->Ln == NULL, "non-null L node in unary rule");
                                fprintf(wr, "%-25s", txrule);
                                fprintf(wr, " %3d %3d %s", i, j, txspan);
                                fprintf(wr, " %s --> %s", G->sname[N], G->sname[gr->R]);
                              }
                            else
                              { /* Instance of a binary rule. */
                                char *txrule = jsprintf("  s%d --> s%d [%d] s%d", N, gr->L, cr->cut, gr->R);
                                affirm ((i <= cut) && (cut <= j), "bad cut");
                                affirm (cr->Ln->symb == gr->L, "L symb mismatch");
                                fprintf(wr, "%-25s", txrule);
                                fprintf(wr, " %3d %3d %s", i, j, txspan);
                                fprintf(wr, " %s --> %s %s", G->sname[N], G->sname[gr->L], G->sname[gr->R]);
                              }
                            affirm (cr->Rn->symb ==  gr->R, "R symb mismatch");
                            
                            fprintf(wr, "\n");
                            free(txrule);
                            cr = cr->next;
                          }
                      }
                    n = n->next;
                  }
                /* fprintf(wr, "\n"); */
             }
           }
      }
  }
  
char *cfp_plot_span(PNodeId_t i, PNodeId_t j, int NN)
  {
    affirm(i > 0, "bad i");
    affirm(j > i, "bad span");
    /* Includes an initial '|', {NN} plot positions, another '|', and a '\000'. */
    char *plot = (char *)notnull(malloc((NN+3)*sizeof(char)), "no mem");
    int k;
    for (k = 0; k <= NN; k++) { plot[k] = ' '; }
    plot[0] = '|';
    plot[NN+1] = '|';
    plot[i] = '+';
    for (k = i+1; k <= j-1; k++) { plot[k] = '-'; }
    plot[j] = '+';
    plot[NN+2] = '\000';
    return plot;
  }