Description

  Context-free grammars: definitions, manipulations, etc.

See also: General parsing of context-free grammars

Author: Juan-Antonio Fernandez-Madrigal. http://jafma.net

Date: 2018-2019

Copyright: Copyright (c), Individual contributors, see AUTHORS file. This program is free for non-commercial uses. For the rest, contact the AUTHORS. Please include a mention in your programs to the main developer and the web page of the library.

Collaboration diagram for Context-Free Grammars:

Classes
class	elementa::parsing::CFGrammar
	A context-free grammar. More...

class	elementa::parsing::Szer_CFGrammarSpec
	Serializations of CFGrammars specified in a certain textual language. More...

Class Documentation

◆ elementa::parsing::CFGrammar

class elementa::parsing::CFGrammar

A context-free grammar.

This class maintains the grammar in an efficient representation (using integers for element identifiers) but it can also hold string names associated to the grammar elements. Both can be maintained separately and each one used independently.

It also can categorize elements (terminals and non-terminals) in different groups, which can be useful for parsing.

Efficiency of O(1) in many consults is achieved at the cost of increasing memory use (a bunch of bytes per grammar element -terminals, non-terminals and rules- are stored), which is reasonable for human-readable grammar sizes.

Note: - This class is not thread-safe.

Definition at line 70 of file cfgrammars.h.

Collaboration diagram for elementa::parsing::CFGrammar:

[legend]

Static Public Member Functions
Class methods
static bool	isNonTerminal (CodeElement c) noexcept
	Return TRUE if C is a valid non-terminal code for any grammar. More...

static bool	isTerminal (CodeElement c, bool extended=false) noexcept
	Return TRUE if C is a valid terminal code for any grammar. More...

static void	checkRule (const Rule &r)
	Check that the rule R is well constructed for any possible grammar. More...

static bool	isRuleHeader (const Rule &r, CodeElement left, CodeElement firstright)
	Check whether R has LEFT at its left and FIRSTRIGHT at its first right. More...

static bool	hasRuleFirstRight (const Rule &r, CodeElement firstright)
	Check whether the given rule has as first right-side element FIRSTRIGHT. More...

Public Member Functions
Constructors
	CFGrammar (void)
	Default constructor: empty grammar. More...

	CFGrammar (const CFGrammar &)=delete

	CFGrammar (CFGrammar &&)=delete

CFGrammar &	operator= (const CFGrammar &)=delete

CFGrammar &	operator= (CFGrammar &&)=delete

virtual	~CFGrammar (void)=default
	Destructor.

General consulting methods
size_t	sizeTerminals (void) const noexcept
	Return the number of terminals in the grammar. More...

size_t	sizeNonTerminals (void) const noexcept
	Return the number of non-terminals in the grammar. More...

bool	existsTerminal (CodeElement c) const
	Return TRUE if the given code is of a registered terminal. More...

bool	existsNonTerminal (CodeElement c) const
	Return TRUE if the given code is of a registered non-terminal. More...

size_t	sizeTerminals (int cat) const
	Return the number of terminals in a category. More...

size_t	sizeNonTerminals (int cat) const
	Return the number of non-terminals in a category. More...

bool	existsTerminalCategory (int cat) const
	Return FALSE if the given terminal category does not exists in the gr. More...

bool	existsNonTerminalCategory (int cat) const
	Return FALSE if the given non-terminal category does not exists in gr. More...

bool	existsTerminalCatID (const CatId &catid) const
	Return FALSE if the given terminal cat/id does not exists in the gr. More...

bool	existsNonTerminalCatID (const CatId &catid) const
	Return FALSE if the given non-terminal cat/id does not exists in gr. More...

CodeElement	codeOfTerminal (const CatId &catid) const
	Return the code corresponding to the given category and index of a term. More...

CodeElement	codeOfNonTerminal (const CatId &catid) const
	Return the code corresponding to the given category/index of a non-term. More...

CatId	catidOfTerminal (CodeElement c) const
	Return the catid corresponding to a given terminal element. More...

CatId	catidOfNonTerminal (CodeElement c) const
	Return the catid corresponding to a given non-terminal element. More...

int	catOfTerminal (CodeElement c) const
	Return the category only corresponding to a given terminal element. More...

int	catOfNonTerminal (CodeElement c) const
	Return the category only corresponding to a given non-terminal element. More...

const RHSs &	rightsOf (CodeElement n) const
	Return a reference to all the rules associated to a non-terminal N. More...

CodeElement	starting (void) const
	Return the code for the non-terminal that is the starting symbol. More...

std::string	nameOfTerminal (CodeElement c) const
	Return a copy of the name associated to the terminal C. More...

std::string	nameOfNonTerminal (CodeElement c) const
	Return a copy of the name associated to the non-terminal C. More...

Iterating methods
RuleIterator	begin (void) const
	Return an iterator to the first rule in the grammar. More...

RuleIterator	end (void) const
	Return an iterator past the last rule in the grammar. More...

elementa::base::IotaView< CodeElement >	terminalRange (void) const noexcept
	Return an IotaView to iterate on the current terminals. More...

elementa::base::IotaView< CodeElement >	nonTerminalRange (void) const noexcept
	Return an IotaView to iterate on the current non-terminals. More...

elementa::base::IotaView< int >	terminalCatRange (void) const noexcept
	Return an IotaView to iterate on the current terminal categories. More...

elementa::base::IotaView< int >	nonTerminalCatRange (void) const noexcept
	Return an IotaView to iterate on the current non-terminal categories. More...

elementa::base::IotaView< int >	terminalCatIDRange (int cat) const
	Return an IotaView to iterate on the current ids of a terminal category. More...

elementa::base::IotaView< int >	nonTerminalCatIDRange (int cat) const
	Return an IotaView to iterate on the current ids of a non-terminal cat. More...

Element searching methods
CodeElement	findNonTerminal (const std::string &name) const
	Return the code for non-terminal called NAME,or kCodeEmpty if not found. More...

CodeElement	findTerminal (const std::string &name) const
	Return the code for a terminal called NAME, or kCodeEmpty if not found. More...

Conversion to string methods
std::string	to_string (const SetOfElements &soe) const
	Return a string with the given set of alements (their names).

std::string	to_string (const MapOfElements &moe) const
	Return a string with the given map of elements.

std::string	to_string (const RHS &rhs) const
	Return a string with the sequence of elements in the given rhs.

std::string	to_string (const Rule &r) const
	Return a string with the given rule expressed with its names.

std::string	to_string (const LL1Table t) const
	Return a string representation of an LL(1) table.

Modifying methods
void	clear (void)
	Delete all the current content of the grammar.

CodeElement	addTerminal ()
	Register a new termninal. More...

CodeElement	addNonTerminal ()
	Register a new non-terminal. More...

void	addRule (const Rule &r)
	Add a new rule for a non-terminal. More...

void	assignName (CodeElement c, const std::string &name)
	Assign a name to an element. More...

int	newTerminalCategory (void)
	Create a new category where the next terminals will be placed. More...

int	newNonTerminalCategory (void)
	Create a new category where the next non-terminals will be placed. More...

Procedures (it is recommended to use checkIntegrity() first)
void	checkIntegrity (bool withnames=true) const
	Check that the content of the grammar is properly filled. More...

bool	directlyLeftRecursive (Rule &r) const
	Check direct left-recursivity in the grammar. More...

bool	leftRecursive (CodeElement &rec) const
	Check any left-recursivity, direct or not. More...

void	calculateFirsts (MapOfElements &firsts) const
	Fill FIRSTS with the first sets of all non-terminals in the grammar. More...

void	firstOfRHS (const RHS &rhs, const MapOfElements &firsts, SetOfElements &f) const
	Fill F with the first set of the entire RHS, according to FIRSTS. More...

void	calculateFollows (const MapOfElements &firsts, MapOfElements &follows, std::string *trace=nullptr) const
	Fill FOLLOWS with the follow sets of all non-terminals in the grammar. More...

void	firstFirstConflicts (const MapOfElements &firsts, SetOfElements &nts) const
	Fill in NTS with the non-terminals that cause first-first conflicts. More...

void	firstFollowConflicts (const MapOfElements &firsts, const MapOfElements &follows, MapOfElements &nts) const
	Fill in NTS with the terminals shared in firsts and follows of non-term. More...

bool	isLL1 (const MapOfElements &firsts, const MapOfElements &follows, SetOfElements &fifi, MapOfElements &fifo) const
	Return TRUE if the grammar is LL(1). More...

void	fillLL1Table (const MapOfElements &firsts, const MapOfElements &follows, LL1Table &table) const
	Try to fill TABLE with the parsing table of the grammar. More...

Types, consts, etc.
using	CodeElement = TokenId
	Unique code of an element of the grammar, either terminal or non-term. More...

using	SetOfElements = std::set< CodeElement >
	Set of elements. More...

using	MapOfElements = std::map< CodeElement, SetOfElements >
	Set of elements associated to another element. More...

using	VectorOfElements = std::vector< CodeElement >
	Vector of elements. More...

using	RHS = VectorOfElements
	The right-hand side of a rule of the grammar. More...

using	RHSs = std::vector< RHS >
	A number of RHS (usually for the same left hand side non-terminal). More...

using	MapOfRules = std::map< CodeElement, RHSs >
	A mapping from left-side non-terminals to vectors of right sides. More...

using	Rule = std::pair< CodeElement, RHS >
	A rule in the grammar (only one alternative for the left side). More...

using	LL1Table = std::map< LL1TableIndex, RuleIterator >
	An LL(1) parsing table (sparse). More...

static const CodeElement	kCodeEmpty
	Code of the "empty" element. More...

static const CodeElement	kCodeEnd
	Code of the "end of source" el. More...

static const std::string	kEmptyName
	A name for the "empty" element. More...

static const std::string	kEndName
	A name for the "end of source" elem. More...

Member Typedef Documentation

◆ CodeElement

using elementa::parsing::CFGrammar::CodeElement = TokenId

Unique code of an element of the grammar, either terminal or non-term.

Terminals: in the range [-2, -inf). Non-terms: in the range [1 , +inf). The values 0 and -1 are reserved: 0 is "empty" and -1 is "end of source".

Note: - This type is asserted in compile time to be integral and signed, and equal to TokenId.

Definition at line 97 of file cfgrammars.h.

◆ SetOfElements

using elementa::parsing::CFGrammar::SetOfElements = std::set<CodeElement>

Set of elements.

Definition at line 100 of file cfgrammars.h.

◆ MapOfElements

using elementa::parsing::CFGrammar::MapOfElements = std::map<CodeElement,SetOfElements>

Set of elements associated to another element.

Definition at line 103 of file cfgrammars.h.

◆ VectorOfElements

using elementa::parsing::CFGrammar::VectorOfElements = std::vector<CodeElement>

Vector of elements.

Definition at line 106 of file cfgrammars.h.

◆ RHS

using elementa::parsing::CFGrammar::RHS = VectorOfElements

The right-hand side of a rule of the grammar.

It may be empty. It contains the right hand side of just one rule.

Definition at line 110 of file cfgrammars.h.

◆ RHSs

using elementa::parsing::CFGrammar::RHSs = std::vector<RHS>

A number of RHS (usually for the same left hand side non-terminal).

Definition at line 113 of file cfgrammars.h.

◆ MapOfRules

using elementa::parsing::CFGrammar::MapOfRules = std::map<CodeElement, RHSs>

A mapping from left-side non-terminals to vectors of right sides.

Definition at line 116 of file cfgrammars.h.

◆ Rule

using elementa::parsing::CFGrammar::Rule = std::pair<CodeElement,RHS>

A rule in the grammar (only one alternative for the left side).

Definition at line 119 of file cfgrammars.h.

◆ LL1Table

using elementa::parsing::CFGrammar::LL1Table = std::map<LL1TableIndex,RuleIterator>

An LL(1) parsing table (sparse).

Definition at line 287 of file cfgrammars.h.

Constructor & Destructor Documentation

◆ CFGrammar()

elementa::parsing::CFGrammar::CFGrammar ( void )

inline

Default constructor: empty grammar.

Definition at line 340 of file cfgrammars.h.

References clear().

Member Function Documentation

◆ isNonTerminal()

static bool elementa::parsing::CFGrammar::isNonTerminal ( CodeElement c )

inlinestaticnoexcept

Return TRUE if C is a valid non-terminal code for any grammar.

Definition at line 304 of file cfgrammars.h.

References kCodeEmpty.

Referenced by elementa::parsing::CFGrammar::LL1TableIndex::LL1TableIndex(), and existsNonTerminal().

◆ isTerminal()

static bool elementa::parsing::CFGrammar::isTerminal	(	CodeElement	c,
		bool	extended = `false`
	)

inlinestaticnoexcept

Return TRUE if C is a valid terminal code for any grammar.

Parameters

extended indicates whether to consider the special codes 'empty' and 'end' as terminals or not.

Definition at line 310 of file cfgrammars.h.

References kCodeEmpty, and kCodeEnd.

Referenced by elementa::parsing::CFGrammar::LL1TableIndex::LL1TableIndex(), and existsTerminal().

◆ checkRule()

static void elementa::parsing::CFGrammar::checkRule ( const Rule & r )

static

Check that the rule R is well constructed for any possible grammar.

If not ok, throw an std::invalid_argument exception. It does not check whether the rule is correct if inserted in the grammar (e.g., not repeated w.r.t. other rule).

◆ isRuleHeader()

static bool elementa::parsing::CFGrammar::isRuleHeader	(	const Rule &	r,
		CodeElement	left,
		CodeElement	firstright
	)

static

Check whether R has LEFT at its left and FIRSTRIGHT at its first right.

Return TRUE if that is the case. FIRSTRIGHT may be kCodeEmpty to indicate empty right side. This method is useful in some grammars, e.g., LL(1), where the left plus the first right may be enough to identify a rule completely.

◆ hasRuleFirstRight()

static bool elementa::parsing::CFGrammar::hasRuleFirstRight	(	const Rule &	r,
		CodeElement	firstright
	)

static

Check whether the given rule has as first right-side element FIRSTRIGHT.

Return TRUE if that is the case. FIRSTRIGHT may be kCodeEmpty to indicate empty right side.

◆ sizeTerminals() [1/2]

size_t elementa::parsing::CFGrammar::sizeTerminals ( void ) const

inlinenoexcept

Return the number of terminals in the grammar.

Definition at line 357 of file cfgrammars.h.

References kCodeEnd.

Referenced by nonTerminalRange().

◆ sizeNonTerminals() [1/2]

size_t elementa::parsing::CFGrammar::sizeNonTerminals ( void ) const

inlinenoexcept

Return the number of non-terminals in the grammar.

Definition at line 361 of file cfgrammars.h.

References kCodeEmpty.

Referenced by terminalRange().

◆ existsTerminal()

bool elementa::parsing::CFGrammar::existsTerminal ( CodeElement c ) const

inline

Return TRUE if the given code is of a registered terminal.

This is O(1). Throw if C is not a proper terminal code.

Definition at line 366 of file cfgrammars.h.

References isTerminal().

Referenced by catidOfTerminal(), and catOfTerminal().

◆ existsNonTerminal()

bool elementa::parsing::CFGrammar::existsNonTerminal ( CodeElement c ) const

inline

Return TRUE if the given code is of a registered non-terminal.

This is O(1). Throw if C is not a proper non-terminal code.

Definition at line 371 of file cfgrammars.h.

References isNonTerminal().

Referenced by catidOfNonTerminal(), and catOfNonTerminal().

◆ sizeTerminals() [2/2]

size_t elementa::parsing::CFGrammar::sizeTerminals ( int cat ) const

inline

Return the number of terminals in a category.

Definition at line 375 of file cfgrammars.h.

References ELE_CODE_INVARG, and existsTerminalCategory().

◆ sizeNonTerminals() [2/2]

size_t elementa::parsing::CFGrammar::sizeNonTerminals ( int cat ) const

inline

Return the number of non-terminals in a category.

Definition at line 381 of file cfgrammars.h.

References ELE_CODE_INVARG, and existsTerminalCategory().

◆ existsTerminalCategory()

bool elementa::parsing::CFGrammar::existsTerminalCategory ( int cat ) const

inline

Return FALSE if the given terminal category does not exists in the gr.

The first possible valid category is 0. This is O(1).

See also: newTerminalCategory, terminalCatRange.

Definition at line 389 of file cfgrammars.h.

Referenced by existsNonTerminalCatID(), existsTerminalCatID(), sizeNonTerminals(), sizeTerminals(), and terminalCatIDRange().

◆ existsNonTerminalCategory()

bool elementa::parsing::CFGrammar::existsNonTerminalCategory ( int cat ) const

inline

Return FALSE if the given non-terminal category does not exists in gr.

The first possible valid category is 0. This is O(1).

See also: newNonTerminalCategory, nonTerminalCatRange.

Definition at line 396 of file cfgrammars.h.

Referenced by nonTerminalCatIDRange().

◆ existsTerminalCatID()

bool elementa::parsing::CFGrammar::existsTerminalCatID ( const CatId & catid ) const

inline

Return FALSE if the given terminal cat/id does not exists in the gr.

The first possible valid ID is 0. This is O(1).

See also: newTerminalCategory, terminalCatIDRange.

Definition at line 403 of file cfgrammars.h.

References existsTerminalCategory().

Referenced by codeOfTerminal().

◆ existsNonTerminalCatID()

bool elementa::parsing::CFGrammar::existsNonTerminalCatID ( const CatId & catid ) const

inline

Return FALSE if the given non-terminal cat/id does not exists in gr.

The first possible valid ID is 0. This is O(1).

See also: newNonTerminalCategory, nonTerminalCatIDRange.

Definition at line 411 of file cfgrammars.h.

References existsTerminalCategory().

Referenced by codeOfNonTerminal().

◆ codeOfTerminal()

CodeElement elementa::parsing::CFGrammar::codeOfTerminal ( const CatId & catid ) const

inline

Return the code corresponding to the given category and index of a term.

Throw if catid is invalid. This is O(1).

Definition at line 418 of file cfgrammars.h.

References ELE_CODE_PLACE, and existsTerminalCatID().

◆ codeOfNonTerminal()

CodeElement elementa::parsing::CFGrammar::codeOfNonTerminal ( const CatId & catid ) const

inline

Return the code corresponding to the given category/index of a non-term.

Throw if catid is invalid. This is O(1).

Definition at line 425 of file cfgrammars.h.

References ELE_CODE_PLACE, and existsNonTerminalCatID().

◆ catidOfTerminal()

CatId elementa::parsing::CFGrammar::catidOfTerminal ( CodeElement c ) const

inline

Return the catid corresponding to a given terminal element.

Throw if c is invalid. This is O(1).

Definition at line 432 of file cfgrammars.h.

References ELE_CODE_PLACE, and existsTerminal().

◆ catidOfNonTerminal()

CatId elementa::parsing::CFGrammar::catidOfNonTerminal ( CodeElement c ) const

inline

Return the catid corresponding to a given non-terminal element.

Throw if c is invalid. This is O(1).

Definition at line 439 of file cfgrammars.h.

References ELE_CODE_PLACE, and existsNonTerminal().

◆ catOfTerminal()

int elementa::parsing::CFGrammar::catOfTerminal ( CodeElement c ) const

inline

Return the category only corresponding to a given terminal element.

Throw if c is invalid. This is O(1).

Definition at line 447 of file cfgrammars.h.

References ELE_CODE_PLACE, and existsTerminal().

◆ catOfNonTerminal()

int elementa::parsing::CFGrammar::catOfNonTerminal ( CodeElement c ) const

inline

Return the category only corresponding to a given non-terminal element.

Throw if c is invalid. This is O(1).

Definition at line 454 of file cfgrammars.h.

References ELE_CODE_PLACE, and existsNonTerminal().

◆ rightsOf()

const RHSs & elementa::parsing::CFGrammar::rightsOf ( CodeElement n ) const

Return a reference to all the rules associated to a non-terminal N.

This is O(log(m)), being M the number of non-terminals in the grammar. Throw if N is not a non-terminal of if it has no rules in the grammar.

◆ starting()

CodeElement elementa::parsing::CFGrammar::starting ( void ) const

Return the code for the non-terminal that is the starting symbol.

The first non-terminal added to the grammar is considered the starting non-terminal. This method is O(1). This method throws if there are no non-terminals.

◆ nameOfTerminal()

std::string elementa::parsing::CFGrammar::nameOfTerminal ( CodeElement c ) const

Return a copy of the name associated to the terminal C.

If the code has no known name, return a name automatically created at this time for it. If the element is not in the grammar or is not a terminal, throws. This method is O(1).

◆ nameOfNonTerminal()

std::string elementa::parsing::CFGrammar::nameOfNonTerminal ( CodeElement c ) const

Return a copy of the name associated to the non-terminal C.

If the code has no known name, return a name automatically created at this time for it. If the element is not in the grammar or is not a non-terminal, throws. This method is O(1).

◆ begin()

RuleIterator elementa::parsing::CFGrammar::begin ( void ) const

inline

Return an iterator to the first rule in the grammar.

Definition at line 491 of file cfgrammars.h.

◆ end()

RuleIterator elementa::parsing::CFGrammar::end ( void ) const

inline

Return an iterator past the last rule in the grammar.

Definition at line 494 of file cfgrammars.h.

◆ terminalRange()

elementa::base::IotaView< CodeElement > elementa::parsing::CFGrammar::terminalRange ( void ) const

inlinenoexcept

Return an IotaView to iterate on the current terminals.

See also: IotaView.

Definition at line 498 of file cfgrammars.h.

References kCodeEnd, and sizeNonTerminals().

◆ nonTerminalRange()

elementa::base::IotaView< CodeElement > elementa::parsing::CFGrammar::nonTerminalRange ( void ) const

inlinenoexcept

Return an IotaView to iterate on the current non-terminals.

See also: IotaView.

Definition at line 505 of file cfgrammars.h.

References kCodeEmpty, and sizeTerminals().

◆ terminalCatRange()

elementa::base::IotaView< int > elementa::parsing::CFGrammar::terminalCatRange ( void ) const

inlinenoexcept

Return an IotaView to iterate on the current terminal categories.

See also: IotaView, newTerminalCategory.

Definition at line 513 of file cfgrammars.h.

◆ nonTerminalCatRange()

elementa::base::IotaView< int > elementa::parsing::CFGrammar::nonTerminalCatRange ( void ) const

inlinenoexcept

Return an IotaView to iterate on the current non-terminal categories.

See also: IotaView, newNonTerminalCategory.

Definition at line 519 of file cfgrammars.h.

◆ terminalCatIDRange()

elementa::base::IotaView< int > elementa::parsing::CFGrammar::terminalCatIDRange ( int cat ) const

inline

Return an IotaView to iterate on the current ids of a terminal category.

See also: IotaView, newTerminalCategory.

Definition at line 525 of file cfgrammars.h.

References ELE_CODE_PLACE, and existsTerminalCategory().

◆ nonTerminalCatIDRange()

elementa::base::IotaView< int > elementa::parsing::CFGrammar::nonTerminalCatIDRange ( int cat ) const

inline

Return an IotaView to iterate on the current ids of a non-terminal cat.

See also: IotaView, newNonTerminalCategory.

Definition at line 533 of file cfgrammars.h.

References ELE_CODE_PLACE, and existsNonTerminalCategory().

◆ findNonTerminal()

CodeElement elementa::parsing::CFGrammar::findNonTerminal ( const std::string & name ) const

Return the code for non-terminal called NAME,or kCodeEmpty if not found.

This is O(log(m)), being M the number of non-terminals in the grammar that have a name. This method does not work with automatically-generated element names. If the name is found but associated to a terminal, an exception is thrown.

◆ findTerminal()

CodeElement elementa::parsing::CFGrammar::findTerminal ( const std::string & name ) const

Return the code for a terminal called NAME, or kCodeEmpty if not found.

This is O(log(m)), being M the number of terminals in the grammar that have a name. This method does not work with automatically-generated element names. If the name is found but associated to a non-terminal, an exception is thrown.

◆ addTerminal()

CodeElement elementa::parsing::CFGrammar::addTerminal ( )

Register a new termninal.

This is O(1).

◆ addNonTerminal()

CodeElement elementa::parsing::CFGrammar::addNonTerminal ( )

Register a new non-terminal.

This is O(1).

Note: - The first non-terminal added to the grammar is considered the starting non-terminal.

◆ addRule()

void elementa::parsing::CFGrammar::addRule ( const Rule & r )

Add a new rule for a non-terminal.

If there are some more rules for the same non-terminal already, this one is merged (if it is the same as another one, an error is thrown). This is O( R*r + log(n) ), being R the number of rules in the grammar, 'r' the length of the right side of the input argument and N the number of non-terminals in the grammar.

◆ assignName()

void elementa::parsing::CFGrammar::assignName	(	CodeElement	c,
		const std::string &	name
	)

Assign a name to an element.

If the element does not appear yet in the grammar, throws. This is O(log(m)), being M the number of elements of the same kind (terminals or non-terminals) in the grammar.

◆ newTerminalCategory()

int elementa::parsing::CFGrammar::newTerminalCategory ( void )

Create a new category where the next terminals will be placed.

Return the new category created. A category is just an integer value to grouping terminals. While this method is not called, all terminals are assigned the same category, starting at 0. If adding a new category would leave the previous one empty, throws.

◆ newNonTerminalCategory()

int elementa::parsing::CFGrammar::newNonTerminalCategory ( void )

Create a new category where the next non-terminals will be placed.

Return the new category created. A category is just an integer value to grouping non-terminals. While this method is not called, all non-terminals are assigned the same category, starting at 0. If adding a new category would leave the previous one empty, throws.

◆ checkIntegrity()

void elementa::parsing::CFGrammar::checkIntegrity ( bool withnames = true ) const

Check that the content of the grammar is properly filled.

If WITHNAMES == TRUE also check integrity of the names. If some error is detected, an elementa::base::invalid_state error is thrown.

◆ directlyLeftRecursive()

bool elementa::parsing::CFGrammar::directlyLeftRecursive ( Rule & r ) const

Check direct left-recursivity in the grammar.

Check whether there is some rule(s) of the form A : A... and, if there is any, return TRUE and copy into R first one that is found.

◆ leftRecursive()

bool elementa::parsing::CFGrammar::leftRecursive ( CodeElement & rec ) const

Check any left-recursivity, direct or not.

If it is left-recursive, return TRUE and fill REC with the first non- terminal that produces left-recursivity.

◆ calculateFirsts()

void elementa::parsing::CFGrammar::calculateFirsts ( MapOfElements & firsts ) const

Fill FIRSTS with the first sets of all non-terminals in the grammar.

FIRST(c) == set of elements of the grammar that will be produced in the first place when derived from C, including kEmptyCode and kEndCode. This method does not calculate firsts of terminals since the first set of a terminal is just the same terminal.

◆ firstOfRHS()

void elementa::parsing::CFGrammar::firstOfRHS	(	const RHS &	rhs,
		const MapOfElements &	firsts,
		SetOfElements &	f
	)		const

Fill F with the first set of the entire RHS, according to FIRSTS.

You must call previously calculateFirsts().

◆ calculateFollows()

void elementa::parsing::CFGrammar::calculateFollows	(	const MapOfElements &	firsts,
		MapOfElements &	follows,
		std::string *	trace = `nullptr`
	)		const

Fill FOLLOWS with the follow sets of all non-terminals in the grammar.

FOLLOWS(c) == set of elements of the grammar that will be produced after any derivation of C. This method needs a previous calculation of first sets. If TRACE != nullptr, clears TRACE and fills it with a trace of how each follow set has been calculated. This is handy for debugging grammars when there are fi-fo conflicts, since each line in TRACE indicates a reason why a terminal is in the follow set of some non-terminal.

◆ firstFirstConflicts()

void elementa::parsing::CFGrammar::firstFirstConflicts	(	const MapOfElements &	firsts,
		SetOfElements &	nts
	)		const

Fill in NTS with the non-terminals that cause first-first conflicts.

A first-first conflict happens when a non-terminal has alternatives that begins with the same terminal according to the given FIRST set. It is an indication of left recursivity in the grammar.

◆ firstFollowConflicts()

void elementa::parsing::CFGrammar::firstFollowConflicts	(	const MapOfElements &	firsts,
		const MapOfElements &	follows,
		MapOfElements &	nts
	)		const

Fill in NTS with the terminals shared in firsts and follows of non-term.

Each index in NTS will be a non-terminal, while its second part will be the set of terminals that appear both in the first and follow sets of it. A first-follow conflict happens when a non-terminal has some alternative production that yields empty and its follow set and its first set has a non- empty intersection (when not considering the empty code element), meaning, for example, that a LL(1) grammar does not suffice to recognize that language, since longer look-ahead would be required. For instance:

    \code
    S -> a A b;
    A -> b a A | empty; // parser LL(1) cannot know, after encountering 
                        // 'b', whether it should take A -> empty or
                        // A -> b a A. The FiFo conflict rises for A.
    \endcode

◆ isLL1()

bool elementa::parsing::CFGrammar::isLL1	(	const MapOfElements &	firsts,
		const MapOfElements &	follows,
		SetOfElements &	fifi,
		MapOfElements &	fifo
	)		const

Return TRUE if the grammar is LL(1).

A grammar is LL(1) iff there is no first-first or first-follow conflicts. This method calculates the first-first conflicts into FIFI and the first-follow conflicts into FIFO.

◆ fillLL1Table()

void elementa::parsing::CFGrammar::fillLL1Table	(	const MapOfElements &	firsts,
		const MapOfElements &	follows,
		LL1Table &	table
	)		const

Try to fill TABLE with the parsing table of the grammar.

The parsing table contains, for a given non-terminal and a given terminal, the rule that should be applied during parsing that non-terminal when the next input terminal is the corresponding one. If there is more than one rule for some pair (non-terminal,terminal) in the table, this method throws (then the grammar is not LL(1): see isLL1()). Those pairs that do not have any rule are not filled -they should be considered parsing errors during parsing-.

Member Data Documentation

◆ kCodeEmpty

const CodeElement elementa::parsing::CFGrammar::kCodeEmpty

static

Code of the "empty" element.

Definition at line 289 of file cfgrammars.h.

Referenced by isNonTerminal(), isTerminal(), nonTerminalRange(), and sizeNonTerminals().

◆ kCodeEnd

const CodeElement elementa::parsing::CFGrammar::kCodeEnd

static

Code of the "end of source" el.

Definition at line 291 of file cfgrammars.h.

Referenced by elementa::parsing::CFGrammar::LL1TableIndex::LL1TableIndex(), isTerminal(), sizeTerminals(), and terminalRange().

◆ kEmptyName

const std::string elementa::parsing::CFGrammar::kEmptyName

static

A name for the "empty" element.

Definition at line 293 of file cfgrammars.h.

◆ kEndName

const std::string elementa::parsing::CFGrammar::kEndName

static

A name for the "end of source" elem.

Definition at line 295 of file cfgrammars.h.

◆ elementa::parsing::Szer_CFGrammarSpec

class elementa::parsing::Szer_CFGrammarSpec

Serializations of CFGrammars specified in a certain textual language.

This serializer deals with grammars specified in a text composed exclusively of three elements: words without separators (spc, tabs, nline, etc.), separators (spc, tabs, etc.) and comments (both multiline and uniline C-style comments, without nesting in multiline comments).

Separators are, as in most languages, ignored.

Every word must be separated from the next (if it is not the last one) and from the previous (if it is not the first one) by some separator(s).

These words must form the grammar according to the following example (terminals must be written in uppercase entirely and non-terminals in lowercase entirely; both must follow the rules of standard identifiers):

\code

Terminals:  // optional section (if omitted, all terms are in one category)
{
    { TERM1 TERM2 } // the first category of terminals; ids from 0 on.
    { TERM3 } // the second category ... items separated with separators
}

Non-terminals: // optional section (if omitted, all non-terms in one cat.)
{
    { nonterm1 } // first category of non-terminals ...
}

Rules: // mandatory section
{

    nonterm1 : TERM1 nonterm2 | TERM2 TERM3 nonterm2 | ; // spaces around |
    nonterm2 : TERM3 | ; // notice space before ';'
    // Rest of rules of the grammar...
}

\endcode

Empty alternatives to rules can be at any point in the declaration of a rule, but can only happen once in a rule.

More than one rule for a given non-terminal can be written separately (and in any order): they will be collected and merged appropriately by the de-serializer.

The non-terminal in the left-hand side of the first rule in the text will be considered the starting non-terminal in the grammar.

Definition at line 816 of file cfgrammars.h.

Inheritance diagram for elementa::parsing::Szer_CFGrammarSpec:

[legend]

Collaboration diagram for elementa::parsing::Szer_CFGrammarSpec:

[legend]

Public Types
using	SType = CFGrammar
	To access the Sble type parameter of this type. More...

using	RDeserType = CFGrammar
	To access the ReturnDeserType type parameter of this type. More...

using	RSerType = CFGrammar
	To access the ReturnSerType type parameter of this type. More...

Static Public Attributes
static const std::string	kTermsSect
	Keyword to enter the terminals section. More...

static const std::string	kNonTermsSect
	Keyword to enter the non-terminals section. More...

static const std::string	kRulesSect
	Keyword to enter the rules section. More...

static const std::string	kOpenSect
	Keyword to open any section. More...

static const std::string	kCloseSect
	Keyword to close any section. More...

static const std::string	kOpenCat
	Keyword to open any category list. More...

static const std::string	kCloseCat
	Keyword to close any category list. More...

static const std::string	kSideSep
	Text separator of left and right hand side in a default-serialized rule. More...

static const std::string	kRHSSep
	Text separator between alternatives in a default-serialized rule. More...

static const std::string	kRuleEndMark
	Text ending mark of a rule in a default-serialized rule. More...

Public Member Functions
void	ser (elementa::base::OutSerCh &chout, const CFGrammar &cfg)
	Serialize.

void	deser (elementa::base::InSerCh &chin, CFGrammar &cfg)
	Deserialize.

virtual void	ser (OutSerCh &chout, const CFGrammar &obj)
	Serializes an object, writing the resulting chars into CHOUT. More...

virtual void	deser (InSerCh &chin, CFGrammar &obj)
	Deserializes an object from a sequence of chars in CHIN. More...

Member Typedef Documentation

◆ SType

using elementa::base::Serializer< CFGrammar , void , void >::SType = CFGrammar

inherited

To access the Sble type parameter of this type.

Definition at line 193 of file serializers.h.

◆ RDeserType

using elementa::base::Serializer< CFGrammar , void , void >::RDeserType = CFGrammar

inherited

To access the ReturnDeserType type parameter of this type.

Definition at line 196 of file serializers.h.

◆ RSerType

using elementa::base::Serializer< CFGrammar , void , void >::RSerType = CFGrammar

inherited

To access the ReturnSerType type parameter of this type.

Definition at line 199 of file serializers.h.

Member Function Documentation

◆ ser()

virtual void elementa::base::Serializer< CFGrammar , void , void >::ser	(	OutSerCh &	chout,
		const CFGrammar &	obj
	)

inlinevirtualinherited

Serializes an object, writing the resulting chars into CHOUT.

Must throw if any error during serialization, including channel errors (in that case, the channel can be left in the state it was when the error occurred).

Definition at line 206 of file serializers.h.

◆ deser()

virtual void elementa::base::Serializer< CFGrammar , void , void >::deser	(	InSerCh &	chin,
		CFGrammar &	obj
	)

inlinevirtualinherited

Deserializes an object from a sequence of chars in CHIN.

Must change the content of OBJ with the result. Throw if any error during serialization, including channel errors (in that case, the channel and the object are left in the state they were at the moment of the error).

Definition at line 214 of file serializers.h.

Member Data Documentation

◆ kTermsSect

const std::string elementa::parsing::Szer_CFGrammarSpec::kTermsSect

static

Keyword to enter the terminals section.

Definition at line 869 of file cfgrammars.h.

◆ kNonTermsSect

const std::string elementa::parsing::Szer_CFGrammarSpec::kNonTermsSect

static

Keyword to enter the non-terminals section.

Definition at line 872 of file cfgrammars.h.

◆ kRulesSect

const std::string elementa::parsing::Szer_CFGrammarSpec::kRulesSect

static

Keyword to enter the rules section.

Definition at line 875 of file cfgrammars.h.

◆ kOpenSect

const std::string elementa::parsing::Szer_CFGrammarSpec::kOpenSect

static

Keyword to open any section.

Definition at line 878 of file cfgrammars.h.

◆ kCloseSect

const std::string elementa::parsing::Szer_CFGrammarSpec::kCloseSect

static

Keyword to close any section.

Definition at line 881 of file cfgrammars.h.

◆ kOpenCat

const std::string elementa::parsing::Szer_CFGrammarSpec::kOpenCat

static

Keyword to open any category list.

Definition at line 884 of file cfgrammars.h.

◆ kCloseCat

const std::string elementa::parsing::Szer_CFGrammarSpec::kCloseCat

static

Keyword to close any category list.

Definition at line 887 of file cfgrammars.h.

◆ kSideSep

const std::string elementa::parsing::Szer_CFGrammarSpec::kSideSep

static

Text separator of left and right hand side in a default-serialized rule.

Definition at line 890 of file cfgrammars.h.

◆ kRHSSep

const std::string elementa::parsing::Szer_CFGrammarSpec::kRHSSep

static

Text separator between alternatives in a default-serialized rule.

Definition at line 893 of file cfgrammars.h.

◆ kRuleEndMark

const std::string elementa::parsing::Szer_CFGrammarSpec::kRuleEndMark

static

Text ending mark of a rule in a default-serialized rule.

Definition at line 896 of file cfgrammars.h.

Description

Classes

Class Documentation

◆ elementa::parsing::CFGrammar

Static Public Member Functions

Public Member Functions

Types, consts, etc.

Member Typedef Documentation

◆ CodeElement

◆ SetOfElements

◆ MapOfElements

◆ VectorOfElements

◆ RHS

◆ RHSs

◆ MapOfRules

◆ Rule

◆ LL1Table

Constructor & Destructor Documentation

◆ CFGrammar()

Member Function Documentation

◆ isNonTerminal()

◆ isTerminal()

◆ checkRule()

◆ isRuleHeader()

◆ hasRuleFirstRight()

◆ sizeTerminals() [1/2]

◆ sizeNonTerminals() [1/2]

◆ existsTerminal()

◆ existsNonTerminal()

◆ sizeTerminals() [2/2]

◆ sizeNonTerminals() [2/2]

◆ existsTerminalCategory()

◆ existsNonTerminalCategory()

◆ existsTerminalCatID()

◆ existsNonTerminalCatID()

◆ codeOfTerminal()

◆ codeOfNonTerminal()

◆ catidOfTerminal()

◆ catidOfNonTerminal()

◆ catOfTerminal()

◆ catOfNonTerminal()

◆ rightsOf()

◆ starting()

◆ nameOfTerminal()

◆ nameOfNonTerminal()

◆ begin()

◆ end()

◆ terminalRange()

◆ nonTerminalRange()

◆ terminalCatRange()

◆ nonTerminalCatRange()

◆ terminalCatIDRange()

◆ nonTerminalCatIDRange()

◆ findNonTerminal()

◆ findTerminal()

◆ addTerminal()

◆ addNonTerminal()

◆ addRule()

◆ assignName()

◆ newTerminalCategory()

◆ newNonTerminalCategory()

◆ checkIntegrity()

◆ directlyLeftRecursive()

◆ leftRecursive()

◆ calculateFirsts()

◆ firstOfRHS()

◆ calculateFollows()

◆ firstFirstConflicts()

◆ firstFollowConflicts()

◆ isLL1()

◆ fillLL1Table()

Member Data Documentation

◆ kCodeEmpty

◆ kCodeEnd

◆ kEmptyName

◆ kEndName

◆ elementa::parsing::Szer_CFGrammarSpec

Public Types

Static Public Attributes

Public Member Functions