Parser - Syntactic parsing of sentence
[Syntactic tools level]

Implementation of the syntactic parsing algorithm (former cyk module). More...

Data Structures
struct	InterpretationIterator
	Syntactic interpretation iterator. More...
Enumerations
enum	ParsingMode { ALL_SOLUTIONS = 0, ONE_BEST }
	Syntactic parsing process mode. More...
Functions
gboolean	equal (const Probability x, const Probability y, const double limit)
InterpretationIterator *	interpretationIteratorCreate (const ParsingChart *chart, const unsigned int row, const unsigned int column, const gboolean only_top_nt)
void	interpretationIteratorFree (InterpretationIterator **iterator)
ParsingChart *	parse (const char *sentence, const Grammar *grammar, const ParsingChartInitConfig *init_config, const ParsingMode parsing_mode)
gboolean	interpretationIteratorGetNext (InterpretationIterator *iterator, ParsingResult *output)
gboolean	interpretationIteratorGetNextMPP (InterpretationIterator *iterator, ParsingResult *output)
void	interpretationIteratorGoToFirst (InterpretationIterator *iterator)
void	interpretationIteratorGoToFirstMPP (InterpretationIterator *iterator)
void	parsingChartGetMostProbableInterpretation (const ParsingChart *parsing_chart, const unsigned int row, const unsigned int column, const gboolean only_top_nt, ParsingResult *output)
Variables
void(*[ParsingMode parsing_mode])	parsingChartAutoFill (ParsingChart *chart, const unsigned int row, const unsigned int column, const unsigned int max_column)
void(*[ParsingMode parsing_mode])	parsingChartApplyParsing (ParsingChart *chart)
void(*	parsingChartApplyParsing [])(ParsingChart *)

---

Detailed Description

Implementation of the syntactic parsing algorithm (former cyk module).

SlpTK Library 0.6.0

Required header

<parser.h>

Author:

Jean-Cédric Chappelier (creation on 11.04.1997)

Antonin Merçay (revision on 01.02.2005)

Date:

2 March 2005

Version:

0.6.0

---

Enumeration Type Documentation

enum ParsingMode

Syntactic parsing process mode.

See also:

parsingChartApplyParsing() parsingChartAutoFill() parse()

Enumerator:

ALL_SOLUTIONS	Functioning mode where all possible syntactic interpretations are extracted
ONE_BEST	Functioning mode where only the most probable syntactic interpretation is extracted (faster processing)

---

Function Documentation

gboolean equal	(	const Probability	x,
		const Probability	y,
		const double	limit
	)

Test if the difference between two Probability values is less than a chosen limit

Parameters:

[in]	x	The first value to compare
[in]	y	The second value to compare
[in]	limit	The maximal absolute difference allowed to declare equality

Returns:

TRUE if the values are though equal, FALSE otherwise

See also:

Grammar::equality_ratio

Former(s) function(s):

equal

InterpretationIterator * interpretationIteratorCreate	(	const ParsingChart *	chart,
		const unsigned int	row,
		const unsigned int	column,
		const gboolean	only_top_nt
	)

Instanciate and initialize a syntactic interpretation iterator (constructor)

Parameters:

[in]	chart	The source parsing chart
[in]	row	The starting row of the interpretations to consider (1 to size)
[in]	column	The starting column of the interpretations to consider (1 to size - row + 1)
[in]	only_top_nt	Set if only interpretations that begin with the higher level non-terminal must be taken into account

Returns:

The new interpretation iterator instance

See also:

interpretationIteratorFree()

void interpretationIteratorFree

(

InterpretationIterator **

iterator

)

Free the memory allocated to a syntactic interpretation iterator (destructor)

Parameters:

[in]

iterator

The interpretation iterator to free

See also:

interpretationIteratorCreate()

gboolean interpretationIteratorGetNext	(	InterpretationIterator *	iterator,
		ParsingResult *	output
	)

Get all the syntactical interpretations using a dedicated iterator

Parameters:

[in]	iterator	The interpretation iterator
[in]	output	The structure where to output interpretations

Returns:

TRUE if it remains interpretations to get after function completion, FALSE otherwise

See also:

interpretationIteratorGoToFirst() interpretationIteratorCreate()

Former(s) function(s):

Parcours_Cyk_Iteratif

gboolean interpretationIteratorGetNextMPP	(	InterpretationIterator *	iterator,
		ParsingResult *	output
	)

Function equivalent to interpretationIteratorGetNext, but only for trees with an equal probability to the most probable parse

Parameters:

[in]	iterator	The interpretation iterator
[in]	output	The structure where to output interpretations

Returns:

TRUE if it remains interpretations to get after function completion, FALSE otherwise

See also:

interpretationIteratorGoToFirstMPP() interpretationIteratorCreate()

Former(s) function(s):

Print_MPP_Iteratively

void interpretationIteratorGoToFirst

(

InterpretationIterator *

iterator

)

Reinitialize an interpretation iterator in such a that the next interpretationIteratorGetNext call will return the first available interpretation

Parameters:

[in]

iterator

The interpretation iterator to initialize

See also:

interpretationIteratorGetNext()

Former(s) function(s):

RaZ_Parcours_Cyk_Iteratif

void interpretationIteratorGoToFirstMPP

(

InterpretationIterator *

iterator

)

Function equivalent to interpretationIteratorGoToFirst, but only for trees with an equal probability to the most probable parse.

Remarks:

iterator->exploration_list->current_derivation is initialized to the first interpretation with the maximum probability.

Parameters:

[in]

iterator

The interpretation iterator to initialize

See also:

interpretationIteratorGetNextMPP()

Former(s) function(s):

Init_Cyk_For_MPP

ParsingChart * parse	(	const char *	sentence,
		const Grammar *	grammar,
		const ParsingChartInitConfig *	init_config,
		const ParsingMode	parsing_mode
	)

Perform a syntactic analysis of a sentence using a given grammar

Remarks:

For correct parsing, the top level non-terminal (Grammar::top_level_nt) of the provided grammar must have the smallest assigned internal integral code

Parameters:

[in]	sentence	The sentence to parse
[in]	grammar	The grammar to use
[in]	init_config	The chart initialization configuration to use. If this parameter is set to NULL, DEFAULT_PARSINGCHART_INIT_CONFIG is used
[in]	parsing_mode	The parsing mode

Returns:

A resulting parsing chart

Former(s) function(s):

Analyse_Syntaxique & Analyse_Syntaxique_Type

void parsingChartGetMostProbableInterpretation	(	const ParsingChart *	parsing_chart,
		const unsigned int	row,
		const unsigned int	column,
		const gboolean	only_top_nt,
		ParsingResult *	output
	)

Extract the most probable interpretation stored in parsing chart cell

Parameters:

[in]	parsing_chart	The considered parsing chart
[in]	row	The chart cell row index (from 1 to size)
[in]	column	The chart cell column index (from 1 to size - row + 1)
[in]	only_top_nt	A flag indicating if only interpretations starting with the higher level non-terminal are taken into account (TRUE), or if all interpretations are considered (FALSE)
[out]	output	The result where to output

See also:

interpretationIteratorGetNext() interpretationIteratorGoToFirst()

Former(s) function(s):

Extrait_Plus_Probable

---

Variable Documentation

void(* parsingChartApplyParsing[])(ParsingChart *)

Apply the parsing algorithm to a chart already lexically initialized

Remarks:

This function array is indexed by the ParsingMode used

Parameters:

[in]

chart

The parsing chart to treat

See also:

parse()

void(*[ParsingMode parsing_mode]) parsingChartApplyParsing(ParsingChart *chart)

Apply the parsing algorithm to a chart already lexically initialized

Remarks:

This function array is indexed by the ParsingMode used

Parameters:

[in]

chart

The parsing chart to treat

See also:

parse()

void(*[ParsingMode parsing_mode]) parsingChartAutoFill(ParsingChart *chart, const unsigned int row, const unsigned int column, const unsigned int max_column)

Automatically fill a parsing chart cell using the parsing algorithm. Identify elements stored in the cell that can lead to other elements using X -> Y like rules

Remarks:

This function array is indexed by the ParsingMode used

Parameters:

[in]	chart	The considered parsing chart
[in]	row	The row index of the chart cell to fill
[in]	column	The column index of the chart cell to fill
[in]	max_column	The maximal considered column index

---