org.stekikun.dolmen.unparam

Class Expansion

java.lang.Object

org.stekikun.dolmen.unparam.Expansion

public final class Expansion
extends Object

This class deals with the process of expanding a parametric grammar into a ground one by generating all ground instances of rules from (monomorphic) public entry points.

Checking that the grammar is finitely expandable

This is potentially non-terminating if the rules interact in such a way that larger and larger instances keep being generated. The method checkExpandability(PGrammar) checks whether the expansion of a grammar is guaranteed to terminate or not, and throws a Expansion.PGrammarNotExpandable exception in the latter case.

It proceeds by building the _expansion flow graph_ of the grammar, representing how the formal parameters of a rule can contribute to effective parameters of other generic rules in the productions. Such contributions are safe if the the formal appears directly as the effective parameter, or dangerous if it appears deep in some rule expression.

The strongly-connected components of the expansion flow graph are then computed and the grammar is deemed safe for expansion if no SCC contains a dangerous flow edge. Indeed, when dangerous edges are only found linking different SCCs, there is no risk of an ever-growing cycle of rule instantiations occurring.

NB: The expandability of the grammar is checked without taking into account the actual rules that can be reached from the grammar's entry points. In other words, a grammar is only deemed expandable if it can be finitely expanded from any ground instantiation of its rules.

Expanding the parametric grammar

Expanding a parametric grammar starts from the public rules of the grammar, which cannot be parametric, and works its way down to generate all the necessary ground instances that appear in production items. When generating a ground instance of some parametric rule, the various extents (arguments, return type, semantic actions in production items) must also be instantiated. Namely, the holes which act as placeholders in parametric extents are replaced with the return type of the effective instances or terminals that stand for the corresponding formal parameter.

Author:

Stéphane Lescuyer

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	Expansion.PGrammarNotExpandable Exception thrown when checkExpandability(PGrammar) finds a potentially dangerous cycle preventing the expansion of a grammar.

Method Summary

Modifier and Type	Method and Description
static void	checkExpandability(PGrammar grammar) Checks that the given parametric grammar can be expanded in a finite fashion.
static Grammar	of(PGrammar pgrammar) This performs the expansion (aka monomorphization) of the parametric grammar pgrammar, which must have been checked to be expandable beforehand.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

checkExpandability

public static void checkExpandability(PGrammar grammar)
                               throws Expansion.PGrammarNotExpandable

Checks that the given parametric grammar can be expanded in a finite fashion. Note that the check does not take the actual entry points of the grammar into account. In particular, the grammar may fail this check because of some rules which are declared and yet actually unused in the grammar.

Parameters:

grammar -

Throws:

Expansion.PGrammarNotExpandable - if expanding this grammar may not terminate

of

public static Grammar of(PGrammar pgrammar)

This performs the expansion (aka monomorphization) of the parametric grammar pgrammar, which must have been checked to be expandable beforehand.

The result is a non-parametric Grammar whose public entry points are the same as pgrammar and must parse the same language.

Parameters:

pgrammar -

Returns:

the result of expanding pgrammar

Throws:

Grammar.IllFormedException - if the expanded grammar happens to be ill-formed