Archon::Utilities::CFG Class Reference

Context free grammars. More...

#include <archon/util/cfg.H>

Collaboration diagram for Archon::Utilities::CFG:

[legend]List of all members.

Public Member Functions
	CFG (const Actor *a=0)
	~CFG ()
int	getNumberOfTerminals () const
int	getNumberOfRules () const
const Rule &	getRule (int i) const
int	defineTerminal (string name)
int	defineNonterminal (string name)
void	addProd (int nontermIndex, const vector< Symbol > &)
void	addProd (int nontermIndex, Symbol=nil(), Symbol=nil(), Symbol=nil(), Symbol=nil(), Symbol=nil(), Symbol=nil(), Symbol=nil(), Symbol=nil())
string	printTerminal (int index) const
string	printNonterminal (int index) const
string	printProduction (int rule, int production) const
string	printItem (const Item &) const
string	print (int width=0) const
void	introduceNewStartSymbol ()
void	eliminateEpsilonProductions ()
	CURRENTLY DOES NOT REWRITE ACTIONS PROPERLY!!!!!
void	eliminateCycles ()
	CURRENTLY DOES NOT REWRITE ACTIONS PROPERLY!!!!!
void	eliminateMidRuleActions ()
	Rewrite.
Static Public Member Functions
static const Symbol &	nil ()
static Symbol	term (int terminalIndex)
	Make a terminal symbol from a terminal index.
static Symbol	nont (int nonterminalIndex)
	Make a nonterminal symbol from a nonterminal index.
static Symbol	act (int methodIndex, int arg1=-2, int arg2=-2, int arg3=-2, int arg4=-2, int arg5=-2, int arg6=-2, int arg7=-2)
	Make an action symbol from a method index and argument references.
static Symbol	null ()
	Special action that return the null reference.
static Symbol	copy (int arg)
	Special action that copies attributes.
static Symbol	concat (int arg1, int arg2)
	Special action that concattenates strings.
Classes
struct	Actor
class	FirstSets
class	FollowSets
struct	Item
class	Production
class	Rule
struct	Symbol

---

Detailed Description

Context free grammars.

The start symbol is always the left hand side of the first rule.

Still to be done: Conversion to Chomsky Normal Form http://www.wikipedia.com/wiki/Chomsky+Normal+Form http://muldoon.cipic.ucdavis.edu/~jchen007/UCD/ECS120/Notes/LectureNotes11.pdf

Definition at line 49 of file cfg.H.

---

Member Function Documentation

CFG::Symbol Archon::Utilities::CFG::act (  int  methodIndex, int  arg1 = -2, int  arg2 = -2, int  arg3 = -2, int  arg4 = -2, int  arg5 = -2, int  arg6 = -2, int  arg7 = -2 )  [static]

Make an action symbol from a method index and argument references. An argument reference of zero refers to the symbol imediately preceeding this action. A value of 1 refers to the symbol before that one and so on. A value of -1 indicates that a null argument should be passed to the method. A value of -2 is skipped and does not count as an argument. Definition at line 300 of file cfg.C. Referenced by concat(), copy(), eliminateEpsilonProductions(), null(), and Archon::X3D::VRML::Parser::Parser().

void Archon::Utilities::CFG::eliminateCycles (   )

CURRENTLY DOES NOT REWRITE ACTIONS PROPERLY!!!!! Convert the grammar into an equivalent cycle-free grammar. A grammar is cycle free if it has no cycles at all. A grammar has a cycle if for some non-terminal A there is a possible derivation A =>+ A. That is, a derivation from A to itself in one or more steps. Elimination procedure: To simplify things we will start this operation by deriving an epsilon-free grammar. From such a garmmar it is reasonably simple to find and eliminate cycles. In the search for cycles we only need to considder productions that have no terminal symbols and have exactly one non-terminal on the right side. A cycle in an unambiguous epsilon-free grammar always has the form: A0 -> A1 A1 -> A2 An-1 -> An An -> A0 That is, the right sides consist of nothing but one non-terminal. One could imagine a cycle where one or more of the involved productions had semantic actions in them, but in that case the grammar would be ambiguous. If any such cycle exists in the grammar this method will report failure. To eliminate the cycle shown above from an epsilon-free grammar we need only to choose an Ai among the cyclic non-terminals then remove the production Ai-1 -> Ai or An -> A0 if i = 0 and then fix all productions that are not part of the cycle by replacing any occurance of Aj by Ai where 0 <= j <= n and j != i. What about productions like A2 -> A1 or A2 -> B and B -> A3? A cycle may never contain a non-terminal twice. Definition at line 590 of file cfg.C. References eliminateCyclesVisit(), eliminateEpsilonProductions(), Archon::Utilities::CFG::Symbol::index, nont(), printProductionRightSide(), Archon::Utilities::CFG::Rule::productions, rules, Archon::Utilities::CFG::Production::symbols, and Archon::Utilities::CFG::Symbol::type.

void Archon::Utilities::CFG::eliminateEpsilonProductions (   )

CURRENTLY DOES NOT REWRITE ACTIONS PROPERLY!!!!! Convert the grammar into an equivalent epsilon-free grammar. We say that a grammar is epsilon-free if either it has no epsilon productions or there is exactly one epsilon production for the start symbol and then the start symbol does not appear on the right side of any production. The new grammar will accept exactly the same language and the sequence of semantic actions that are to be evaluated for any given derivation will not be changed. This operation may introduce a new start symbol. This operation may leave the grammar with non-terminals that cannot produce anything, so you might want to run the 'eliminateDeadNonTerminals' method afterwards. This operation also may leave the grammar with duplicate productions, so you also might want to run the 'eliminateDuplicateProductions' method afterwards. Ambiguous nullability: This operation will fail if any non-terminal has ambiguous nullability, that is if there among the ways to derive null from the non-terminal are some that result in different sequences of actions to be performed. An example would be: A -> B | C B -> {action1} | b C -> {action2} | c Note that both B nad C have epsilon productions but with different actions associated to them. Definition at line 530 of file cfg.C. References act(), addProd(), Archon::Utilities::CFG::Symbol::index, introduceNewStartSymbol(), Archon::Utilities::CFG::Rule::productions, Archon::Utilities::CFG::Production::symbols, and Archon::Utilities::CFG::Symbol::type. Referenced by eliminateCycles().

void Archon::Utilities::CFG::eliminateMidRuleActions (   )

Rewrite. A -> B C f(1) D E g(2, 5) F G h(3, 8) to A -> B C M D E N F G h(3, 8) M -> f(-1) N -> g(-3, 0) Definition at line 654 of file cfg.C. References addProd(), Archon::Utilities::CFG::Symbol::args, defineNonterminal(), Archon::Utilities::CFG::Symbol::index, Archon::Utilities::CFG::Rule::productions, Archon::Utilities::CFG::Production::symbols, and Archon::Utilities::CFG::Symbol::type. Referenced by Archon::Utilities::LrParserBase::LrParserBase().

string Archon::Utilities::CFG::printTerminal (  int  index  )  const

Parameters: index  A negative value will be interpreted as the imaginary EOI terminal. Definition at line 375 of file cfg.C. References Archon::Utilities::Text::toUpperCase(). Referenced by Archon::Utilities::ClrParser::ClrParser(), Archon::Utilities::CFG::FollowSets::print(), Archon::Utilities::CFG::FirstSets::print(), Archon::Utilities::AutomatonSymbolPrinter::printSymbol(), and Archon::Utilities::SlrParser::SlrParser().

---

The documentation for this class was generated from the following files:

• archon/util/cfg.H
• archon/util/cfg.C

---