سؤال

Without the use of parentheses and only considering addition, subtraction, multiplication, and division, the following context-free grammar describing these simple arithmetic operations is incorrect, right, because it is right-associative rather than left-associative?

 - E -> T | T + E | T - E
 - T -> int | int * T | int / T

A correct grammar would be:

 - E -> T | E + T | E - T
 - T -> int | T * int | T / int

Is this reasoning correct?

هل كانت مفيدة؟

المحلول

"Correct" is whatever you define it to be. The "traditional" meaning for non-associative operators that is taught in grammar school is left-associative, so in that sense the left recursive grammar is "correct" while the right recursive grammar is not, but that's a pretty circular defintion.

In addition, your left-recirsive grammar needs E -> T added to be correct (as is, it does not describe any finite strings)

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى StackOverflow
scroll top