Re: BNF grammar interpretation (Simon)
29 Apr 2004 11:59:15 -0400

          From comp.compilers

Related articles
BNF grammar interpretation (valentin tihomirov) (2004-04-03)
Re: BNF grammar interpretation (2004-04-29)
| List of all articles for this month |

From: (Simon)
Newsgroups: comp.compilers
Date: 29 Apr 2004 11:59:15 -0400
References: 04-04-021
Keywords: parse
Posted-Date: 29 Apr 2004 11:59:15 EDT

"valentin tihomirov" <> wrote in message

> A ::= '(''plus' X Y')'
> 'plus' determines type of the expression, identifier is a terminal (string
> token) and X and Y are imperative (non-optional). I was trying to make a
> universal parser traveling through the tree and generating events to
> translator. As far as I've seen the imperative sub-expressions in edif
> grammar are usually defined like this:
> X ::= ( identifier | M | N )
> M ::= '(''m' identifier ')'
> N ::= '(''n' identifier ')'
> As you see, the X selects one expression, whether terminal or M or N. This
> conforms to the highr-level A expression that requires only one imperative
> sub-expression. I could not find expressions like:
> X ::= { identifier | M }
> But what is the way to parse it if the above declaration is encountered; the
> {} braces mean optional expression in BNF? This looks like a paradox
> (conflict) of declarations. X-element becomes optional as opposed to
> A-parent element expectations.

The curly braces {S} means "0 or more occurences of S".
Optional would be [S] - more exactly "0 or 1 occurence of S".

Also note that this is EBNF (Extended), though you can rewrite a BNF
grammar to give the same meaning, it's just shortcuts.

If you want to rewrite
      X ::= { identifier | M }
so that there must be at least one occurence, try
      X ::= identifier | M { identifier | M }

or in the simpler, BNF form, write
      X ::= identifier | M |( identifier | M ) X
This left-recursion might give you problems later on, if so you can
rewrite further or augment your grammar with extra rules.

> [2] The second paradox is similar to the first one.
> A ::= ( identifier [X] [Y] )
> X ::= (identifier | B)
> Y ::= (identifier | C)
> Here, expression A has 3 sub-expressions. The first child is simple terminal
> identifier, second is optional X element followed by optional Y expression.
> If X is optinal, how do I know that identifier returned by lexer at X
> position is X element rather than Y?

Yes that is possible... its equivalent to having separate rules for A
            A ::= (identifier | identifier X | identifier Y | identifier X

how this is handled depends on the parser... you can tell because the
parser would eventually reach a B or a C. The tokens should have
something to identify them, though, so your rule shouldnt be a problem

hope this helps,


Post a followup to this message

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