Hi Doug,
thanks for your interest. In the syntax that I want to specify, "baa" should succeed. Remember that each of the symbols must appear at least once, not once only. I think this makes it a combination rather than a permutation:
<
http://en.wikipedia.org/wiki/Combination>
What I want to state is that
Pre: #a = 0 ^ #b = 0 ^ #c = 0 ^ ... ^ #z = 0
Parse
Post: #a > 0 ^ #b > 0 ^ #c > 0 ^ … ^ #z > 0
I think you can sort of specify a permutation, but only by, in essence, listing all the permutations. In the original email I suggested this:
mandatoryParts = ( A B C | A C B | B C A | B A C | C A B | C B A ) { a | b | c } .
A = a {a} .
B = b {b} .
C = c {c} .
...
But if you have to list all the permutations, like enumerating a very large set, it kind of defeats the purpose. It should be possible to define a comprehensive specification.
B
From: BlackBox [mailto:BLACKBOX{([at]})nowhere.xy
Sent: 16 February 2012 21:18
To: BLACKBOX{([at]})nowhere.xy
Subject: Re: [BLACKBOX] EBNF question
Bob,
Ok, got it.
You want to specify that any permutation of a set of symbols is accepted for a production.
There are n! (n factorial) permutations of n things. So bear with me as I walk through the
thoughts on this.
How would one write a parser to say yay, or nay to a string of symbols as a permutation?
Suppose our hypothetical notation states a permutation production as
x = P(a, b, c)
So there is a set S = {a, b, c} that our parser must keep track of. There is also another set
E={} which is the examined symbols so far in the parse.
Let's say our input is I=bca then the parser would need to read '"b" and firstly determine if it
is in the set S. It then needs to determine it that symbol has been previously examined for
this specific production so it check "b" against E. It is not there so all is well we hence progress
as
E S I
{} {abc} bca
{b} {abc} ca
{bc} {abc} a
{bca} {abc}
and the parse succeeds. If the input were "baa" or "bxc" the parse would fail.
The problem is that there is a 'state' E which is changing as the production is processed.
But surely EBNF has complex states so what is the difference? If the input is "a...a" where
there are n-2 symbols between the "a"s for our set S of n symbols then the parse path has
to look back n-1 symbols to determine if it has seen the last "a" before. So, do any of the
EBNF constructs look back to previously encountered symbols?
O = [a] (optional)
S = {a} (zero or more)
F = a b (followed by)
A = a | b (alternatives)
L = "string" (literal)
G = (a) (grouping)
I don't see any of those rules looking back. The parse certainly can 'backtrack' to an earlier state if it fails but the failure does
not seem to be dependent upon the symbols in the parse path.
So, tentatively, I conclude that no, you can't do a permutation in EBNF.
I am not happy with that since a more formal specification is warranted.
(the reason for my interest is that I am in the process or writing a parser for arbitrary EBNF
grammars)
-Doug
On 2/15/2012 11:36 PM, Bob Walkden wrote:
From: BlackBox [mailto:BLACKBOX{([at]})nowhere.xy
Danforth
Sent: 16 February 2012 01:53
To: BLACKBOX{([at]})nowhere.xy
Subject: Re: [BLACKBOX] EBNF question
On 2/15/2012 3:23 PM, Bob Walkden wrote:
I can't write
mandatoryParts = { a {a} | b {b} | c {c} | ... | z {z} } .
Bob,
Why not just write
mandatoryParts = ( a {a} | b {b} | c {c} | ... | z {z} ) .
Just parenthesize the list. That would allow any order to occur and
one of the options must be chosen.
Thanks, but that would mean only one of them is mandatory. I am trying to
state that each of them is mandatory, in any order.
B
----
To unsubscribe, send a message with body "SIGNOFF BLACKBOX" to LISTSERV{([at]})nowhere.xy
---- To unsubscribe, send a message with body "SIGNOFF BLACKBOX" to LISTSERV{([at]})nowhere.xy---- To unsubscribe, send a message with body "SIGNOFF BLACKBOX" to LISTSERV{([at]})nowhere.xy
Received on Fri Feb 17 2012 - 00:46:08 UTC