Re: Opinions about "epsilon" Symbols in Parse Trees

eDrikos <drikosv@otenet.gr>
13 Jun 2005 10:55:29 -0400

          From comp.compilers

Related articles
Opinions about "epsilon" Symbols in Parse Trees drikosv@otenet.gr (Evangelos Drikos) (2005-06-09)
Re: Opinions about "epsilon" Symbols in Parse Trees schmitz@i3s.unice.fr (Sylvain Schmitz) (2005-06-10)
Re: Opinions about "epsilon" Symbols in Parse Trees DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2005-06-10)
Re: Opinions about "epsilon" Symbols in Parse Trees mefrill@yandex.ru (mefrill) (2005-06-12)
Re: Opinions about "epsilon" Symbols in Parse Trees news4e71@yahoo.com (0x4e71) (2005-06-12)
Re: Opinions about "epsilon" Symbols in Parse Trees DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2005-06-12)
Re: Opinions about "epsilon" Symbols in Parse Trees drikosv@otenet.gr (eDrikos) (2005-06-13)
| List of all articles for this month |

From: eDrikos <drikosv@otenet.gr>
Newsgroups: comp.compilers
Date: 13 Jun 2005 10:55:29 -0400
Organization: An OTEnet S.A. customer
References: 05-06-052 05-06-072
Keywords: parse
Posted-Date: 13 Jun 2005 10:55:29 EDT

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.


Post a followup to this message

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