Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

In class, we considered (part of) an attribute grammar for arithmetic expressions. A more complete LL(1) grammar for arithmetic expressions is the following: S E

In class, we considered (part of) an attribute grammar for arithmetic expressions. A more complete LL(1) grammar for arithmetic expressions is the following:

S E$

E TE0 E0 ATE0

E0 "

T FT0

T0 MFT0

T0 "

F id

F num

F ( E )

A+

A-

M *

M /

The attribute grammar we discussed in class calculated the value of a given expression. In this question, you are to solve the same problem, but you should take a different approach:

  • Instead of directly computing the value of the expression, you are to generate C code that computes the value of the expression at runtime. Specifically, if you run the parser generated from the grammar annotated with your action routines, the parser should print C code to evaluate the parsed expression to stdout.
  • You are to use action routines written in C to generate this C code.

The code you generate has access to a stack of doubles that can be manipulated using the following two functions:

  • A function void push(double) that pushes a double onto a global stack holding values of type double.
  • A function double pop() that removes the topmost entry from the global stack of doubles and returns it.

The code you generate should place the final result of evaluating the arithmetic expression into a variable result of type double.

As an example, with the help of the global stack of doubles, the expression 3 + (4 + x) / y can be evaluated as follows:

double tmp1, tmp2, result; push(3);

push(4);

push(x);

tmp2 = pop();

tmp1 = pop();

push(tmp1 + tmp2);

push(y);

tmp2 = pop();

tmp1 = pop();

push(tmp1 / tmp2);

tmp2 = pop();

tmp1 = pop();

push(tmp1 + tmp2);

result = pop();

This (or equivalent code) is what your parser should print on stdout when run on the expression 3 + (4 + x) / y. To be perfectly clear, the action routines you attach to the productions in the grammar should be C code that prints the above code when parsing the expression 3 + (4 + x) / x. The action routines themselves should not contain this code. (They cant, because the action routines dont change depending on the arithmetic expression we parse, but the generated C code must change

with the parsed arithmetic expression.)

Your code should assume that the scanner annotates every terminal with the following information:

  • For a number literal num, a string num.val that is a valid string representation of the floating point value of the number literal.
  • For an identifier id, a string id.name that holds the name of the C variable this identifier refers to.

In your action routines, refer to the different symbols in a production by their position in the production, as is common in parser generators that use action routines. The left-hand side of the production is symbol $0. The symbols on the right-hand side are numbered from 1, left to right. You are allowed to associate attributes with symbols in the grammar. For example, it may be helpful to annotate each M or A with an attribute op that stores the operator it represents as a string. Youd achieve this using:

A+{ $0.op = "+"; }

To illustrate your task a little more clearly, here is one possible (somewhat convoluted) set of action routines that would generate C code to print the parsed expression instead of evaluating it:

  1. E$

E TE0

E0 ATE0 {printf("printf(\"%s\");", $1.op);}

E0

  1. FT0

T0 MFT0 {printf("printf(\"%s\");", $1.op);}

T0

F id {printf("printf(\"%s\");", $1.name);}

F num {printf("printf(\"%s\");", $1.val);}

F ({printf("printf(\"(\");");} E ){printf("printf(\")\");");}

A+{$0.op = "+";}

A{$0.op = "-";}

M {$0.op = "*";}

M /{$0.op = "/";}

When parsing the expression 3 + (4 + x) / y using this annotated grammar, the output printed to stdout would be

printf("3");

printf("+");

printf("(");

printf("4");

printf("+");

printf("x");

printf(")");

printf("/");

printf("y");

which is C code that prints the original expression. The action routines you provide is to print C code that evaluates the expression instead of printing the expression.

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image_2

Step: 3

blur-text-image_3

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Refactoring Databases Evolutionary Database Design

Authors: Scott Ambler, Pramod Sadalage

1st Edition

0321774515, 978-0321774514

More Books

Students also viewed these Databases questions

Question

Briefly explain the various types of leadership ?

Answered: 1 week ago

Question

Explain the need for and importance of co-ordination?

Answered: 1 week ago

Question

Explain the contribution of Peter F. Drucker to Management .

Answered: 1 week ago

Question

What is meant by organisational theory ?

Answered: 1 week ago