CODEWITHSUNDEEP
expressiongrammaroperator-precedence
Meghan
Meghan

Reputation: 305

how to find which operator has highest precedence in a grammar

I have an exam just the day after tomorrow. Please help me with this question and explain me the answer so that i could do all questions of this level in my exam.

Grammar is

E-> E/X | X
X-> T-X | X*T | T
T-> T+F | F
F-> (E) | id

id stands for identifier.

Q1 : Above grammar is used to generate all valid arithmetic expressions in a hypothetical language in which 

a. / associates from the left
b. * associative from the left
c. + associative from the left
d. all of these

Q 2 : Above grammar is used to generate all valid arithmetic expressions in a hypothetical language in which

a.  + has the highest precedence
b.  * has the highest precedence
c.  - has the highest precedence
d.  / has the highest precedence

Upvotes: 2

Views: 1539

Answers (1)

akshat sinha
akshat sinha

Reputation: 41

let's put the level at each statements

E-> E/X | X....................1(root)
X-> T-X | X*T | T..............2
T-> T+F | F....................3
F-> (E) | id...................4

Precedence

op which is in the max level has the max precedence so id, (, ) has highest precedence folowed by + then -,* then /

so + has the highest precedence as per option

Associativity

Note A->Ax is left recursive and A-xA is right recursive grammer Now 

E-> E/X  is left recursive so / is left associated
X-> T-X is right recursive so - is right associated
X->  X*T is left recursive so / is left associated
T-> T+F | F is left recursive so / is left associated

so ans of Q1 is d :)

Upvotes: 3

Related Questions