Consider the grammar defined by the following production rules, with two…
2014
Consider the grammar defined by the following production rules, with two operators ∗ and
\(S\:\to\:T∗P \\ T\:\to\:U\mid T∗U \\ P\:\to\:Q+P\mid Q \\ Q\:\to Id \\ U\:\to Id\)
Which one of the following is TRUE?
- A.
+ is left associative, while ∗ is right associative
- B.
+ is right associative, while ∗ is left associative
- C.
Both + and ∗ are right associative
- D.
Both + and ∗ are left associative
Attempted by 128 students.
Show answer & explanation
Correct answer: B
Answer: + is right associative, while ∗ is left associative.
Reason: Associativity follows from whether a production is left- or right-recursive.
+ (plus): The production P -> Q + P is right-recursive, so + is right-associative. Example: Id + Id + Id is parsed as Id + (Id + Id).
∗ (star): The production T -> T ∗ U is left-recursive, so ∗ is left-associative. Example: Id ∗ Id ∗ Id is parsed as (Id ∗ Id) ∗ Id.
Note: The top-level production S -> T ∗ P does not change these associativity conclusions; associativity is determined by the recursive shape of T and P.
A video solution is available for this question — log in and enroll to watch it.