Date : 16 October 2014

Name : Desy Kurniasih

NIM : 1801429903

Class : LM01

Lecture : Tri Djoko Wahjono, Ir., M.Sc. (D0206)

Assignment : Concept of programming languages —- Chapter 3 Describing Syntax and Semantics

REVIEW QUESTIONS

11. How is the order of evaluation of attributes determined for the trees of a given attribute grammar?

Answer : The parse tree is evaluated based on its underlying BNF grammar, wit a possibility of having empty set of attributes values attached to each node.

12. What is the primary use of attribute grammars?

Answer : Attribute grammars are used to describe more of the structure of a programming language than can be described with a context-free grammar.

13. Explain the primary uses of a methodology and notation for describing the semantics of programming languages.

Answer : Programmers obviously need to know do exactly what the report language before they can use them effectively in their programs . The compiler writer must know exactly what language construction means designing implementations for them properly . If there precise semantic specification of programming languages ​​, programs written in language could potentially be proven correct without testing . Also , the compiler can be shown to produce a program that shows the exact behavior given in the definition of the language ; namely , the truth they can be verified . complete specification of the syntax and semantics of programming languages can be used by a tool to generate a compiler for the language automatically . Finally , the language designer , who will develop a semantic description their language , could be in the process of finding ambiguities and inconsistencies in their design .

14. Why can machine languages not be used to define statements in operational semantics?

Answer : Because operational semantics needs an appropriate intermediate language. While machine language is a low-level language that can't be understood easily.

15. Describe the two levels of uses of operational semantics.

Answer :

-There are different levels of uses of operational semantics. At the highest
level, the interest is in the final result of the execution of a complete program.
This is sometimes called natural operational semantics.

-At the lowest level,
operational semantics can be used to determine the precise meaning of a program
through an examination of the complete sequence of state changes that
occur when the program is executed. This use is sometimes called structural
operational semantics.

PROBLEM SET

11. Consider the following grammar:

<S> → <A> a <B> b

<A> → <A> b | b

<B> → a <B> | a

Which of the following sentences are in the language generated by this grammar?

  1. baab
  2. bbbab
  3. bbaaaaa
  4. bbaab

ANSWER :

IMG_20141015_0001 IMG_20141015_0002

12. Consider the following grammar:

<S> → a <S> c <B> | <A> | b

<A> → c <A> | c

<B> → d | <A>

Which of the following sentences are in the language generated by this grammar?

  1. abcd
  2. acccbd
  3. acccbcc
  4. acd
  5. accc

ANSWER :

IMG_20141015_0004

IMG_20141015_0005

13. Write a grammar for the language consisting of strings that have n copies of the letter a followed by the same number of copies of the letter b, where n > 0. For example, the strings ab, aaaabbbb, and aaaaaaaabbbbbbbb are in the language but a, abb, ba, and aaabb are not.

ANSWER :                           <S> -> a <S> b | ab

14. Draw parse trees for the sentences aabb and aaaabbbb, as derived from the grammar of Problem 13.

ANSWER :IMG_20141015_0006

15. Convert the BNF of Example 3.1 to EBNF.

A Grammar for a Small Language

<program> → begin <stmt_list> end

<stmt_list> → <stmt>

| <stmt> ; <stmt_list>

<stmt> → <var> = <expression>

<var> → A | B | C

<expression> → <var> + <var>

| <var> – <var>

| <var>

ANSWER :

<program> -> <stmt_list>

<stmt_list> -> <stmt>

<stmt> → <var> = <expression>

<expression> → <var> (+ | -) <var>