Assignment #3

Pengajar : Tri Djoko Wahjono

Review Question :

11. How is the order of evaluation of attributes determined for the trees of a 

      given attribute grammar?

       =>Now, consider the process of computing the attribute values of 

            a parse tree, which is sometimes called decorating the parse 

            tree. If all attributes were inherited, this could proceed in a 

            completely top-down order, from the root to the leaves. 

            Alternatively, it could proceed in a completely bottomup order, 

            from the leaves to the root, if all the attributes were synthesized. 

            Because our grammar has both synthesized and inherited 

            attributes, the evaluation process cannot be in any single direction. 

           The following is an evaluation of the attributes, in an order in 

           which it is possible to compute them:

                1. <var>.actual_type ← look-up(A) (Rule 4)

                2. <expr>.expected_type ← <var>.actual_type (Rule 1)

                3. <var>[2].actual_type ← look-up(A) (Rule 4)

                    <var>[3].actual_type ← look-up(B) (Rule 4)

                4. <expr>.actual_type ← either int or real (Rule 2)

                5. <expr>.expected_type == <expr>.actual_type is either

                     TRUE or FALSE (Rule 2)

12. What is the primary use of attribute grammars?

       =>to describe both the syntax and the static semantics of programs. 

           Attribute grammars are a formal approach both to describing and 

           checking the correctness of the static semantics rules of a program.

13. Explain the primary uses of a methodology and notation for 

      describing the semantics of programming languages.

      => To describing syntax because it will help programer  to 

            know precisely what the statements of a language do before they 

            can use them effectively in their programs and  If there were a 

            precise semantics specification of a programming language, 

            programs written in the language potentially could be proven 

            correct without testing.

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

       operational semantics?

       =>because machine language is too low-level to be easily Understood.

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

      =>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?

         a. baab

         b. bbbab

         c. bbaaaaa

         d. bbaab

         =>  

                <A> will generate one or more consecutive b's
                <B> will generate one or more consecutive a's
                So <A> a <B> b  will generate
                One or more b's followed by One a followed by One or more a's 

                followed  by a b which is the same as One or more b's followed 

                by Two a's followed by a b Which matches a and d 

 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?

       a. abcd

       b. acccbd

       c. acccbcc

       d. acd

       e. accc

         => <A> generates one or more c's
              <B> will generate either One d or a string of one or more c's
               So S will generate
               a  <S>  c   {d | c's} | c's | b
               which matches a and e

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.

=>       S -> ab

                b ->bb

14. Draw parse trees for the sentences aabb and aaaabbbb, as derived from

the grammar of Problem 13.

         =>

            

        

15. Convert the BNF of Example 3.1 to EBNF.

         =>  

         <program> -> begin <stmt_list> end

         .       <stmt_list> -> stmt[stmt_list]

         .       <stmt> -> <var> = <expressions>

         .       <var> -> A| B | C

     .       <expressions> -> <var> {(+|-)< var> }