I would put some of your restrictions in the syntax and some in the semantics. I can work this up on Coco if you desire.
mandatory = { a {a} | b {b} | c {c} } . (*A legal production in your grammar is legal in this production.*)
MODULE PrivMandatory;
CONST
a_sy = 1;
b_sy = 2;
c_sy = 3;
errorNr = 200;
VAR
mandatorySym : SET;
PROCEDURE Doit;
VAR
ch : CHAR;
BEGIN
WHILE moreTokens DO
CASE ch OF
'A' : INCL( mandatorySym, a_sy);
| 'B' : INCL( mandatorySym, b_sy);
| 'C' : INCL( mandatorySym, c_sy);
END;
END;
ASSERT ( {a_sy,b_sy,c_sy} * mandatorySym = {a_sy,b_sy,c_sy}, errorNr)
END Doit;
END PrivMandatory.
On Thu, Feb 16, 2012 at 5:46 PM, Bob Walkden <bob{([at]})nowhere.xy
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--
Aubrey McIntosh, Ph.D.
1502 Devon Circle
Austin TX 78723-1814
http://home.grandecom.net/~amcintosh/aubrey/Search/
512-348-7401
---- To unsubscribe, send a message with body "SIGNOFF BLACKBOX" to LISTSERV{([at]})nowhere.xy
Received on Fri Feb 17 2012 - 01:18:04 UTC