0

Can someone please assist me with the following question.

Write a BNF rule to parse into

C -> E
C -> E && E
C -> E && E && E

so that C generates as many E && E as needed and enforces left association.

Is the following correct?

C -> C && E | E

It should force left association because of the left recursion and make as many && E's it wants to because of the recursion.

2
  • 3
    This is not BNF. There's no indication of terminals or nonterminals. It uses a notation that I've never seen and it looks like you aren't parsing anything, but trying to invent a generative grammar.
    – msw
    Commented Oct 16, 2014 at 1:44
  • 1
    @msw Given that BNF is only a notation for context-free grammars which are indeed generative grammar (cf wikipedia), the OP is not too far from the mark.
    – babou
    Commented Oct 16, 2014 at 16:47

2 Answers 2

2

Apart from some formatting issues (-> doesn't exist in formal BNF), your rule is correct. Written in proper BNF syntax and using quotes around literals, it would be

C ::= C '&&' E | E

The left-recursion indeed creates a parse tree for a left-associative operator.

0

What you present in your question is a context-free (CF) grammar, omitting details about terminal (which symbols are in the generated text) and non-terminals (which symbols are used only to be rewritten (expanded), and the initial symbol (which non-terminal you start with).

BNF (Backus-Naur Form) is a specific syntax (syntactic style) for presenting CF grammars, so that this missing information is visible just by looking at the rules.

So, written in BNF your grammar would look like this:

<C> ::= <C> "&&" <E> | <E>

The <> are for non-terminals and the "" are for terminals.

But actually it is only a grammar fragment. This is also clearly true of the first given definition, though it is not explicit.

The reason is that E is clearly intended to be a non-terminal that can derive further in other expression, such as (I am guessing an example) x == y. But the rules for that are missing.

Other than that syntax issue, you are quite correct with your answer, as Bart van Ingen Schenau already told you.

It is very possible that your instructor does not distinguish BNF and CF grammar. Many people do not. The name CF grammar is more used by theoreticians, while BNF is a common, 50 years old, notation used by many practitioners for computer input ... and much less for casual work because it is longer to write.

1
  • downvote ... so what?
    – babou
    Commented Oct 16, 2014 at 23:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.