Constrained Dynamic Parser - Revision history

imported>Pascal: /* Typos */

2010-02-15T13:21:50Z

Typos

imported>Mathieu: /* Main Objects */

2010-02-13T23:19:11Z

Main Objects

← Older revision		Revision as of 23:19, 13 February 2010
Line 385:		Line 385:
	;{{class\|expressionListParser}}: inherits from {{class\|Parser }}. Its {{ident\|parse}} function implements a list of expression as used in the extension set expression.		;{{class\|expressionListParser}}: inherits from {{class\|Parser }}. Its {{ident\|parse}} function implements a list of expression as used in the extension set expression.

	;{{class\|infixParser}}: inherits from {{class\|LedParser}}. Its {{ident\|led}}		;{{class\|infixParser}}: inherits from {{class\|LedParser}}. Its {{ident\|led}} function implements something like (pseudocode):
	function implements something like (pseudocode):
	<blockquote><code><pre>		<blockquote><code><pre>
	led(AST left, Symbol value):		led(AST left, Symbol value):
Line 402:		Line 401:
	{{TODO\|each parser should be passed a context to allow rewriting of bound identifiers on the AST being constructed. A special rewriting should be done for comprehension sets and alike, because the bouns variables are not known before the parsing of the actual expression}}		{{TODO\|each parser should be passed a context to allow rewriting of bound identifiers on the AST being constructed. A special rewriting should be done for comprehension sets and alike, because the bouns variables are not known before the parsing of the actual expression}}

	;{{class\|atomicParser}}: inherits from {{class\|NudParser}}. Its {{ident\|nud}}		;{{class\|atomicParser}}: inherits from {{class\|NudParser}}. Its {{ident\|nud}} function implements something like (pseudocode):
	function implements something like (pseudocode):
	<blockquote><code><pre>		<blockquote><code><pre>
	nud(Symbol value):		nud(Symbol value):
Line 410:		Line 408:
	</pre></code></blockquote>		</pre></code></blockquote>

	;{{class\|postfixParser}}: inherits from {{class\|LedParser}}. Its {{ident\|led}}		;{{class\|postfixParser}}: inherits from {{class\|LedParser}}. Its {{ident\|led}} function implements something like (pseudocode):
	function implements something like (pseudocode):
	<blockquote><code><pre>		<blockquote><code><pre>
	led(AST left, Symbol value):		led(AST left, Symbol value):
Line 422:		Line 419:
	</pre></code></blockquote>		</pre></code></blockquote>

	;{{class\|prefixParser}}: inherits from {{class\|NudParser}}. Its {{ident\|nud}}		;{{class\|prefixParser}}: inherits from {{class\|NudParser}}. Its {{ident\|nud}} function implements something like (pseudocode):
	function implements something like (pseudocode):
	<blockquote><code><pre>		<blockquote><code><pre>
	nud(Symbol value):		nud(Symbol value):
Line 434:		Line 430:
	</pre></code></blockquote>		</pre></code></blockquote>

	;{{class\|functionalPostfixParser}}: inherits from {{class\|LedParser}}. It has a supplementary {{ident\|close_symbol}} attribute, and its {{ident\|led}} function implements something like (pseudocode):		;{{class\|functionalPostfixParser}}: inherits from {{class\|LedParser}}. It has a supplementary {ident\|close_symbol}} attribute, and its {{ident\|led}} function implements something like (pseudocode):
	<blockquote><code><pre>		<blockquote><code><pre>
	led(AST left, Symbol value):		led(AST left, Symbol value):

imported>Mathieu: /* Main Objects */

2010-02-13T23:18:08Z

Main Objects

← Older revision		Revision as of 23:18, 13 February 2010
Line 277:		Line 277:

	;{{class\|Tokenizer}} {{ident\|tokenizer}}: which provides the {{class\|SymbolParser}} associated to the next lexem of the formula being parsed.		;{{class\|Tokenizer}} {{ident\|tokenizer}}: which provides the {{class\|SymbolParser}} associated to the next lexem of the formula being parsed.
	: {{TODO\|shall be a singleton ? ~~Define how is it use by Parser object~~}}		: {{TODO\|shall be a singleton ? }}

	;{{class\|SymbolParser}}: a Parser for a specific symbol. It should at least have the following attributes:		;{{class\|SymbolParser}}: a Parser for a specific symbol. It should at least have the following attributes:

imported>Mathieu: l

2010-02-13T23:17:43Z

← Older revision		Revision as of 23:17, 13 February 2010
Line 256:		Line 256:
	We will try to explain how the parser manage to build an AST from the input ''2 * 3 + a''.		We will try to explain how the parser manage to build an AST from the input ''2 * 3 + a''.

	''MainParser'' will ~~try to apply~~ the ''nud'' function of the parser associated		Firstly, ''MainParser'' will call the ''nud'' function of the parser associated
	to the ''literal'' symbol valued with '2', which simply return an AST node		to the ''literal'' symbol valued with '2', which simply return an AST node
	''(literal 2)''. ''MainParser'' will then ~~passed~~ this AST to the ''led''		''(literal 2)''.

			''MainParser'' will then passe this AST to the ''led''
	function of the parser associated to the '*' operator, which will use it for		function of the parser associated to the '*' operator, which will use it for
	its left child and will then call ''MainParser'' to recognize its right term.		its left child and will then call ''MainParser'' to recognize its right term.

	This new call to ''MainParser'' will in turn build the AST node ''(literal 3)''		This new call to ''MainParser'' will in turn build the AST node ''(literal 3)''
	and then will return, because precedences ~~won~~'t allow to build a ''('+'		and then will return, because of precedences between the current AST being build ('*') and the next lexem ('+') which don't allow to build a ''('+' (literal 3) (name a))'' sub-expression.
	(literal 3) (name a))'' sub-expression.

	The initial ''MainParser'' call now get the following left term: ''('*'		The initial ''MainParser'' call now get the following left term: ''('*' (literal 2) (literal 3))'' and then call the ''led'' function associated to the
	(literal 2) (literal 3))'' and then call the ''led'' function associated to the		'+' operator, which will in turn call ''MainParser'' which will return the simple
	'+' operator, which will ~~then~~ call ''MainParser'' which will return the simple
	AST ''(ident a)'' and build the resulting AST: ''('+' ('*' (literal 2) (literal		AST ''(ident a)'' and build the resulting AST: ''('+' ('*' (literal 2) (literal
	3)) (name a) )''.		3)) (name a) )''.

imported>Mathieu: /* Parsing an Example */

2010-02-13T23:14:00Z

Parsing an Example

← Older revision		Revision as of 23:14, 13 February 2010
Line 254:		Line 254:

	==== Parsing an Example ====		==== Parsing an Example ====
	We will try to explain how the parser manage to build an AST from the input ''2		We will try to explain how the parser manage to build an AST from the input ''2 * 3 + a''.
	* 3 + a''.

	''MainParser'' will try to apply the ''nud'' function of the parser associated		''MainParser'' will try to apply the ''nud'' function of the parser associated

imported>Mathieu: /* Limitations */

2010-02-13T23:13:45Z

Limitations

← Older revision		Revision as of 23:13, 13 February 2010
Line 237:		Line 237:
	: It would certainly be a good idea to implement a user interface to test the grammar, so that an extension designer has a way to ensure that he agrees with the parser on the semantic of his extension (or at least on the AST obtained by using it). For example, the representation of the syntax tree returned by <tt>Formula.getSyntaxTree</tt> could be compared to an expected entered string.		: It would certainly be a good idea to implement a user interface to test the grammar, so that an extension designer has a way to ensure that he agrees with the parser on the semantic of his extension (or at least on the AST obtained by using it). For example, the representation of the syntax tree returned by <tt>Formula.getSyntaxTree</tt> could be compared to an expected entered string.

	== Limitations ==		=== Limitations ===
	In a first implementation, we do not want to support several alternative for one symbol (using backtracking -- see [[#Some Difficulties\|here before]]). As a side effect, it won't be possible to define new ''lambda like'', ''union like'' and ''sets like'' terms, or terms that use one of the following symbol: λ, ⋂, ⋃ or ∣		In a first implementation, we do not want to support several alternative for one symbol (using backtracking -- see [[#Some Difficulties\|here before]]). As a side effect, it won't be possible to define new ''lambda like'', ''union like'' and ''sets like'' terms, or terms that use one of the following symbol: λ, ⋂, ⋃ or ∣

imported>Mathieu: /* Some Existing Extensible Languages */

2010-02-13T23:06:19Z

Some Existing Extensible Languages

← Older revision		Revision as of 23:06, 13 February 2010
Line 70:		Line 70:
	* [http://itcentre.tvu.ac.uk/~clark/xmf.html XMF] whose implementation seems not be describes in details.		* [http://itcentre.tvu.ac.uk/~clark/xmf.html XMF] whose implementation seems not be describes in details.
	* [http://xlr.sourceforge.net/index.html XLR: Extensible Language and Runtime], which looks like a ''Pratt'' parser according to the [http://xlr.svn.sourceforge.net/viewvc/xlr/trunk/xl2/xlr/parser.cpp?revision=805&view=markup sources].		* [http://xlr.sourceforge.net/index.html XLR: Extensible Language and Runtime], which looks like a ''Pratt'' parser according to the [http://xlr.svn.sourceforge.net/viewvc/xlr/trunk/xl2/xlr/parser.cpp?revision=805&view=markup sources].
	* [http://www.pi-programming.org/What.html <math>\pi</math>] whose implementation ~~seems~~ not be ~~describes~~ in details (but source code is available).		* [http://www.pi-programming.org/What.html <math>\pi</math>] whose implementation does not seem to be described in details (but source code is available).
	* Prolog and its operator declarations; see, e.g., [http://scholar.google.com/scholar?q=%22The+simple+and+powerful+yfx+operator+precedence+parser.%22 2007 paper].		* Prolog and its operator declarations; see, e.g., [http://scholar.google.com/scholar?q=%22The+simple+and+powerful+yfx+operator+precedence+parser.%22 2007 paper].


	== Design Proposal ==		== Design Proposal ==

imported>Mathieu: Most TODO done

2010-02-13T23:05:45Z

Most TODO done

Show changes

imported>Mathieu: /* Limitations */

2010-02-13T22:48:26Z

Limitations

← Older revision		Revision as of 22:48, 13 February 2010
Line 66:		Line 66:
	:* [http://javascript.crockford.com/tdop/tdop.html ''Pratt'' parsing in javascript]		:* [http://javascript.crockford.com/tdop/tdop.html ''Pratt'' parsing in javascript]
	Note that a ''pratt'' parser is essentially a parser for expressions (where		Note that a ''pratt'' parser is essentially a parser for expressions (where
	~~== Limitations ==~~
	In a first implementation, we do not want to support several alternative for one symbol (using backtracking -- see [[#Some Difficulties\|below]]). As a side effect, it won't be possible to define new ''lambda like'', ''union like'' and ''sets like'' terms, or terms that use one of the following symbol: λ, ⋂, ⋃ or ∣
	~~expression parts are themselves expressions)... But it may be tweaked to limit~~
	~~the accepted sub-expressions or to enforce some non-expression parts inside an~~
	~~expression. More on that hereafter.~~

	=== Some Existing Extensible Languages ===		=== Some Existing Extensible Languages ===
Line 78:		Line 73:
	* [http://www.pi-programming.org/What.html <math>\pi</math>] whose implementation seems not be describes in details (but source code is available).		* [http://www.pi-programming.org/What.html <math>\pi</math>] whose implementation seems not be describes in details (but source code is available).
	* Prolog and its operator declarations; see, e.g., [http://scholar.google.com/scholar?q=%22The+simple+and+powerful+yfx+operator+precedence+parser.%22 2007 paper].		* Prolog and its operator declarations; see, e.g., [http://scholar.google.com/scholar?q=%22The+simple+and+powerful+yfx+operator+precedence+parser.%22 2007 paper].

			== Limitations ==
			In a first implementation, we do not want to support several alternative for one symbol (using backtracking -- see [[#Some Difficulties\|below]]). As a side effect, it won't be possible to define new ''lambda like'', ''union like'' and ''sets like'' terms, or terms that use one of the following symbol: λ, ⋂, ⋃ or ∣
			expression parts are themselves expressions)... But it may be tweaked to limit
			the accepted sub-expressions or to enforce some non-expression parts inside an
			expression. More on that hereafter.

	== Design Proposal ==		== Design Proposal ==

imported>Mathieu at 22:47, 13 February 2010

2010-02-13T22:47:51Z

Show changes

← Older revision		Revision as of 23:18, 13 February 2010
Line 277:		Line 277:

	;{{class\|Tokenizer}} {{ident\|tokenizer}}: which provides the {{class\|SymbolParser}} associated to the next lexem of the formula being parsed.		;{{class\|Tokenizer}} {{ident\|tokenizer}}: which provides the {{class\|SymbolParser}} associated to the next lexem of the formula being parsed.
	: {{TODO\|shall be a singleton ? ~~Define how is it use by Parser object~~}}		: {{TODO\|shall be a singleton ? }}

	;{{class\|SymbolParser}}: a Parser for a specific symbol. It should at least have the following attributes:		;{{class\|SymbolParser}}: a Parser for a specific symbol. It should at least have the following attributes: