dk.brics.servletvalidator.grammar
Class Grammar

java.lang.Object
  dk.brics.servletvalidator.grammar.Grammar

public class Grammar
extends Object

A context free grammar is a quadtuple (V, Σ, S, P), where

• V is the non terminal alphabet
• Σ is the terminal alphabet (in this version Σ is the full Unicode alphabet
• V ∩ Ε = Ø
• S ⊆ V is the set of all start nonterminals
• U is the combined alphabet V ∪ Ε
• P is a finite set of productions on the form A → θ, where A ∈ V and θ ∈ U*

We write αAω ⇒ αθω when A → θ ∈ P and α,ω ∈ U*. Furthermore we will use ⇒⁺ to denote the transitive closure and ⇒^* to denote the reflexive transitive closure

Constructor Summary

Grammar(dk.brics.automaton.Automaton a)

Grammar(dk.brics.automaton.Automaton a, boolean lenient)

Grammar(FlowGraph f, String methodName, boolean lenient)

Grammar(NonTerminal n)

Method Summary

void	apply(GrammarEntityVisitor v) Applies the visitor to the grammar.
Set<Terminal>	getEpsilon() Gets the set Ε of all terminals from the grammar.
Map<NonTerminal,List<Production>>	getP() The map from all nonterminals to their productions P.
Set<NonTerminal>	getS() Returns the set of start non terminals S
Set<AlphabetSymbol>	getU() Gets the set of all terminals and non terminal.
Set<NonTerminal>	getV() Gets the set of all nonterminals.
void	reduce() Removes nodes in the graph by removing all nonterminals with only one production using.
void	simplify() Removes epsilon productions from the language using EpsilonRemovalVisitor, then removes unit productions using UnitProductionRemovalVisitor, finally removes useless productions using UselessProductionRemovalVisitor

Methods inherited from class java.lang.Object

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

Constructor Detail

Grammar

public Grammar(dk.brics.automaton.Automaton a)

Grammar

public Grammar(dk.brics.automaton.Automaton a,
               boolean lenient)

Grammar

public Grammar(FlowGraph f,
               String methodName,
               boolean lenient)

Grammar

public Grammar(NonTerminal n)

Method Detail

apply

public void apply(GrammarEntityVisitor v)

Applies the visitor to the grammar. The visitor is allowed to change the grammar.

Parameters:

v - the visitor to apply

getEpsilon

public Set<Terminal> getEpsilon()

Gets the set Ε of all terminals from the grammar. Changing this set does not affect the grammar

Returns:

the Ε set

getP

public Map<NonTerminal,List<Production>> getP()

The map from all nonterminals to their productions P. Changing the map itself will not change the grammer, but changing the production set will.

Returns:

getS

public Set<NonTerminal> getS()

Returns the set of start non terminals S

Returns:

getU

public Set<AlphabetSymbol> getU()

Gets the set of all terminals and non terminal. Changing this set does not affect the grammar

Returns:

the V set

getV

public Set<NonTerminal> getV()

Gets the set of all nonterminals. Changing this set will now affect the grammar itself, but changing the nonterminals in the set will.

Returns:

the set of all nonterminal.

reduce

public void reduce()

Removes nodes in the graph by removing all nonterminals with only one production using. See SingleProductionNonTerminalRemovalVisitor

simplify

public void simplify()

Removes epsilon productions from the language using EpsilonRemovalVisitor, then removes unit productions using UnitProductionRemovalVisitor, finally removes useless productions using UselessProductionRemovalVisitor