On Wed, September 16, 2009 16:32, Akim Demaille wrote:
>>> It would be nice to extend the *.output file with various metrics
>>> about the grammar.
>>
>> Agreed.
>
> Will add this to TODO.
About this metrics feature: there is a patched bison version
with a metrics option added. it is at "Ambiguity detection in GNU Bison"
http://www.lsv.ens-cachan.fr/~schmitz/software
there are some test grammars and documentation and cannot
test this feature because the bison-2.3a+ambiguity.tar.bz2
does not compile for some reason.
the source for metrics is in metrics.c
/*
Copyright (C) 2006
Laboratoire I3S, Université de Nice-Sophia Antipolis & CNRS.
This file is part of Bison, the GNU Compiler Compiler.
Bison is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.
Bison is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with Bison; see the file COPYING. If not, write to
the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
Boston, MA 02110-1301, USA. */
/**
* \file metrics.c
* \brief Grammar metrics computations.
*/
#include <config.h>
#include "system.h"
#include <math.h>
#include "gram.h"
#include "derives.h"
#include "metrics.h"
#include "sets.h"
/** Returns the McCabe complexity of the grammar. In a bison grammar,
this boils down to counting the number of alternance signs \c
|.
\pre #derives_counts was computed. */
inline static unsigned int
mcc (void)
{
unsigned int i, ret = 0;
for (i = 0; i < nvars; i++)
ret += (derives_counts[i])? derives_counts[i] - 1: 0;
return ret;
}
/** Compute the number of LR(1) positions.
\pre #derives has been computed.
\pre #follow_tokens has been computed. */
inline static unsigned int
lr1_npositions (void)
{
unsigned int i, j, ret = 0;
for (i = 0; i < nvars; i++)
{
unsigned int f = bitset_count (follow_tokens[i]);
ret += 2 * f;
for (j = 0; derives[i][j]; j++)
ret += f * (rule_rhs_length (derives[i][j]) + 1);
}
return ret;
}
inline void
grammar_metrics (FILE *out)
{
unsigned int nlr1 = lr1_npositions ();
double npairs = (double)nlr1 * (double)(nlr1 + 1) * 2;
fprintf (out, "Grammar metrics.\n");
fprintf (out, "\tsize |G|:\t\t%u\n", nritems);
fprintf (out, "\tterminals |T|:\t\t%u\n", ntokens);
fprintf (out, "\tnonterminals |N|:\t%u\n", nvars);
fprintf (out, "\tvocabulary |V|:\t\t%u\n", nsyms);
fprintf (out, "\tproductions |P|:\t%u\n", nrules);
fprintf (out, "\tnorm ||G||:\t\t%.2f\n", nritems * log (nsyms) / M_LN2);
fprintf (out, "\tMcCabe complexity MCC:\t%u\n", mcc ());
fprintf (out, "\taverage rhs length AVS:\t%.2f\n",
(double)nritems / (double)nrules);
fprintf (out, "\tLR(1) positions:\t%u\n", nlr1);
fprintf (out, "\tmax LR(1) pairs:\t%.3e\n", npairs);
fprintf (out, "\n");
}
