Re: best grammar for handling optional symbols?

Johannes <jaluber@gmail.com>
Sun, 17 Aug 2008 13:16:57 -0700 (PDT)

          From comp.compilers

Related articles
best grammar for handling optional symbols? jmichae3@yahoo.com (2008-08-15)
Re: best grammar for handling optional symbols? max@gustavus.edu (Max Hailperin) (2008-08-16)
Re: best grammar for handling optional symbols? jaluber@gmail.com (Johannes) (2008-08-17)
Re: best grammar for handling optional symbols? jmichae3@yahoo.com (2008-08-18)
Re: best grammar for handling optional symbols? cfc@shell01.TheWorld.com (Chris F Clark) (2008-08-19)
| List of all articles for this month |

From: Johannes <jaluber@gmail.com>
Newsgroups: comp.compilers
Date: Sun, 17 Aug 2008 13:16:57 -0700 (PDT)
Organization: Compilers Central
References: 08-08-021 08-08-022
Keywords: parse
Posted-Date: 17 Aug 2008 16:33:17 EDT

On Aug 16, 2:22 pm, Max Hailperin <m...@gustavus.edu> wrote:>
> John's sugestion is particularly apt if the options can appear in any
> order -- which I suspect is the case. In that case, you have far more
> than 2^18 fully-expanded possibilities -- not that you would want to
> write even 2^18 productions. Moreover, there is no nice trick of BNF
> or EBNF that would come to your rescue.


Well, theoretically one could write a program to generate the output
but I think with 2^18 alternatives no one is going to read that file
anyway.


> Your approach using <a> to represent an optional <code40>, defined
> using <nullsymbol> (or some other notation for the empty string) would
> work OK for 18 options, which need to appear in a fixed order if used.
> It would be mildly clutzy, since you'd need 18 new nonterminals like
> your <a>. (I'd name them <optionalCode40> and so forth.)
>
> If you are fortunate enough to use EBNF, but again have a required
> fixed order, the clutziness would go away. You could just write the
> 18 options out with each in brackets or followed by a question mark,
> and life would be good. Or to adopt John's phrase, you would have
> kept your grammar manageable.
>
> But nothing like that is possible if the order is variable. In that
> case, even if you are writing for humans, your best bet is to escape
> from the BNF or EBNF into some more general means of communication --
> which for a human, might well be a natural-language explanation.


In other grammars I have seen the preferred method to deal with this
situation is to write something like this:


rule: modifier+;


modifier: A | B;


One has to check afterwards though, if a modifier is never repeated
(also add a note in the grammar). I actually would choose this
solution even for a fixed order, as one can provide a better error
message if you provide the input in the wrong order.


Johannes


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.