0

I would like to know if one of the two following equivalent grammars (since they can produce the same rules) is preferred (and why).
For instance the second grammar is more concise but is it a good thing that in the second form the rule b can produce εor such rules should be avoided.

G1:

a => X b Y
   | X Y

b => c b
   | c

G2:

a => X b Y

b => c b
   |
2
  • 2
    I can't tell you which is preferred, but from seeing a lot of practical grammars (such as the grammars for C++, Java, and the like), they almost exclusively use the first as it's easier to see all productions and find which is causing an issue when attempting to debug it. Practically they all get compiled down to the same code using a parser generator so it's up to you which you find more visually appealing.
    – Thatguypat
    Oct 6 '16 at 15:44
  • Fundamentally, they are equivalent. If the engine processing them does not make a difference either (which is implementation specific), then it boils down to a matter of taste.
    – dagnelies
    Oct 6 '16 at 17:30
2

That depends on what the grammar is used for.

If it's meant to be read by humans (e.g. as a part of a programming language specification), then use whatever is easier to understand. That is likely going to be as close to the way users think about the syntax of the language as possible.

If it's meant to be used by a parser generator, then the usual approach to writing code applies:

  1. The most important thing is to make the grammar correct. For example, some parser generators don't accept all CFGs, but only a subset of them.
  2. Second, your grammar should be easy to understand. This is effectively the same as for grammars aimed exclusively at humans above.
  3. Last, if the parser is too slow, use whichever option is more efficient with the parser generator you're using.

If you're using the grammar for some other purpose, or if there are additional considerations (e.g. if you're extending an existing grammar, consistency with the old grammar might be important), choose based on them.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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