Reflect on what you have learned in this unit, and compose a reflection paper about your chosen career path (firefighter) and how psychology can benefit your career. You will address the following as

Programming Languages Concepts

CMPSC 461

Homework 1

Due May 24, 2019 at 11:59 pm

Problems:

Given the following attribute grammar:

Production Semantic Rules

E  str 100 str.pos=3;

E.val=str.val+4

str  str1 B str1.pos=str.pos+1;

B.pos=str.pos;

str.val=str1.val+B.val

str  B B.pos=str.pos;

str.val=B.val

B  0 B.val=0

B  1 B.val=2^B.pos

What does this grammar do? What does it compute if any?
Show the annotated parse tree for the input “100100”. Make sure to show all dependences between the evaluation of the attributes in this parse tree.

Consider the following grammar:

E  ( ) | ( E ) | E E

What does this grammar do?
Is the grammar ambiguous?
Modify the grammar so to obtain an unambiguous grammar generating the same language.
Show that the new grammar is not ambiguous.

Consider the following grammar representing the addition two expressions expr and any number n, where n can be an integer or FP (floating points with decimal point).
1. 1. expr  expr + S | S
  2. S  n.n | n

Write an attribute grammar to determine the type of each S and expr. Show the annotated parse tree of 3.1 + 2

Write an unambiguous grammar that generates all strings of a’s and b’s containing an even number of b’s. Using your grammar, give a right-most derivation of the string

b a a b a a a b b and show the parse tree.

The set of formulas can be defined as follows:
1. 1. An atomic formula is a formula
  2. if "X" and "Y" are formulas, then also "not X", "X and Y", "X or Y", and "X implies Y" are formulas
  3. If "X" is a formula and "a" is an identifier, then also "exists a. X" and "forall a. X" are formulas

These properties must hold:

The precedence order is as follows:
1. not
2. and
3. or
4. implies
5. exists, forall
"and" and "or" are left-associative, "implies" is right-associative.
Formulas can be preceded by an arbitrary number of negations (i.e. "not not X", "not not not X", etc. are allowed)

Examples of the strings in the languages:

forall x. forall y. exists z. X or B implies C

Not A

forall x. A or B not C

Give an unambiguous CFG generating the language above and satisfying all properties. You may assume given productions for generating identifiers and atomic formulas starting from the non-terminals ID(can be any of the alphabet)and ATOM(can be any atomic formula) respectively.

Honor code: “I pledge on my honor that I have not given or received any inappropriate help on this assignment”