Re: Opinions about "epsilon" Symbols in Parse Trees

First of all, I want to thank you for your interest and your prompt reply.


I'm not sure if I correctly understand your point.


In the example I stated only the <Identifier part> is optional. Also,
it is not an implied alternative. It is an explicit statement and any
program somehow must deal with it. Apparently, in a program, such the
one I'm trying to write, every single step must be specified
explicitly.


With regard to the notation, I don't see why it is a bad choice.


I chose the syntactic notation used in ISO/IEC 9075 (SQL/Framework)
which is an extended version of BNF. (Unfortunately, after a
copy-paste the ellipses, were converted automatically to dots but the
conversion was consistent throughout the document).


Actually, the program is a Lexical Analyzer modified to keep also
syntactical information. The reason this parser doesn't represent
"epsilon" symbols is exactly that when it reads a terminal it makes at
once all possible movements and proceeds with the next token.


That is the reason and not the notation. If I restrict the notation
the problem is still there.


Further, the extended notation can result to packed Parse
Trees. Correct me if I make any mistake, in the example below a list
of length n is represented in the first case by 2*n nodes in the Parse
Tree whereas in the second case (can) by n+1 nodes.


(1) <list> ::= <list element>
                                  | <list> <list element>


(2) <list> ::= <list element> ...


Once again thank you.


Evangelos Drikos


Hans-Peter Diettrich wrote:
> Evangelos Drikos wrote:
>
>
>>The e-free Syntax Rule:
>>"<Identifier> ::= <Latin Letter> [ { <Latin Letter> | <digit> } . ] "
>>can be restated as:
>>
>><Identifier> ::= <Identifier start> <Identifier part>
>><Identifier start> ::= <Latin Letter>
>><Identifier part> ::= { <Latin Letter> | <digit> | NONE } .
>>/* where X-Mozilla-Status: 0009*/
>
>
> Isn't NONE an implied alternative for the whole loop, in case of zero
> occurences?
>
> I suspect that you choose a bad grammar syntax for your purpose, pure
> BNF might be a more appropriate choice.

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