0
$\begingroup$

I'm reading https://ilyasergey.net/CS4212/_static/lectures/PLDI-Week-07-more-parsing.pdf

On page 11, there's the definition of Sum Grammar:

S -> E + S | E
E -> number | (S)

Just wondering if this grammar same as follows:

S -> number | (S+S) 
$\endgroup$
2
  • 1
    $\begingroup$ will your grammar be able to generate $num + num + num...+ num$? $\endgroup$ Commented Dec 26, 2022 at 4:27
  • $\begingroup$ @ArunMadhav Awesome thanks, please make it as an answer, I will accept it. $\endgroup$
    – pvd
    Commented Dec 26, 2022 at 4:34

1 Answer 1

1
$\begingroup$

In modified grammar:

  1. We cannot generate $number + number + number....+ number$, as every operation will have a parenthesis associated with it.

  2. Redundant parenthesis: $number + number$, we will have to describe it as $(number + number)$ here the parenthesis are redundant.

If you modify the grammar to:

$S\rightarrow S+S$ $|(S)|$ $number$

It will solve both the issues mentioned and generate the same language as Sum Grammar but it's an ambiguous grammar and doesn't have the properties of Sum grammar(right-to-left associativity)

$\endgroup$

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.