number of reductions is nothing but the number of non-leaves in the parse tree ...

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+11 votes

Consider the syntax directed translation scheme (SDTS) given in the following. Assume attribute evaluation with bottom-up parsing, i.e., attributes are evaluated immediately after a reduction.

E$\rightarrow $ E$_{1}$ * T {E.val = E$_{1}$.val * T.val}

E$\rightarrow $ T {E.val = T.val}

T$\rightarrow $ F - T$_{1}$ {T.val = F.val - T$_{1}$.val}

T$\rightarrow$ F {T.val = F.val}

F$\rightarrow$2 {F.val = 2}

F$\rightarrow$4 {F.val = 4}

- Using this SDTS, construct a parse tree for the expression $4 - 2 - 4 * 2$ and also compute its $E.val$.
- It is required to compute the total number of reductions performed to parse a given input. Using synthesized attributes only, modify the SDTS given, without changing the grammar, to find $E.red$, the number of reductions performed while reducing an input to $E$.

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,871 questions

47,533 answers

146,046 comments

62,299 users