CODEWITHSUNDEEP
grammarcontext-free-grammarbnfebnf
Garrett Jennings
Garrett Jennings

Reputation: 21

Is this conversion from BNF to EBNF correct?

As context, my textbook uses this style for EBNF:

Text

Sebesta, Robert W. Concepts of Programming Languages 11th ed., Pearson, 2016, 150.

The problem: Convert the following BNF rule with three RHSs to an EBNF rule with a single RHS.

Note: Conversion to EBNF should remove all explicit recursion and yield a single RHS EBNF rule.

A ⟶ B + A | B – A | B

My solution:

A ⟶ B [ (+ | –) A ]

My professor tells me:

"First, you should use { } instead of [ ], Second, according to the BNF rule, <"term"> is B." (He is referring the the style guide posted above)

Is he correct? I assume so but have read other EBNF styles and wonder if I am entitled to credit.

Upvotes: 0

Views: 2349

Answers (1)

rici
rici

Reputation: 241911

You were clearly asked to remove explicit recursion and your proposed solution doesn't do that; A is still defined in terms of itself. So independent of naming issues, you failed to do the requested conversion and your prof is correct to mark you down for it. The correct solution for the problem as presented, ignoring the names of non-terminals, is A ⟶ B { (+ | –) B }, using indefinite repetition ({…}) instead of optionality ([…]). With this solution, the right-hand side of the production for A only references B, so there is no recursion (at least, in this particular production).

Now, for naming: clearly, your textbook's EBNF style is to use angle brackets around the non-terminal names. That's a common style, and many would say that it is more readable than using single capital letters which mean nothing to a human reader. Now, I suppose your prof thinks you should have changed the name of B to <term> on the basis that that is the "textbook" name for the non-terminal representing the operand of an additive operator. The original BNF you were asked to convert does show the two additive operators. However, it makes them right-associative, which is definitely non-standard. So you might be able to construct an argument that there's no reason to assume that these operators are additive and that their operands should be called "terms" [Note 1]. But even on that basis, you should have used some name written in lower-case letters and surrounded in angle brackets. To me, that's minor compared with the first issue, but your prof may have their own criteria.

In summary, I'm afraid I have to say that I don't believe you are entitled to credit for that solution.

Notes

  1. If you had actually come up with that explanation, your prof might have been justified in suggesting a change of major to Law.

Upvotes: 1

Related Questions