CHAPTER 3

Nama : Aditya Isnugraha
Class   : LM01
NIM    : 1801419606

Assignment from Tri Djoko Wahjono
CHAPTER 3

- REVIEW QUESTION

11. How is the order of evaluation of attributes determined for the trees of a
      given attribute grammar?
      Answer : Expr → Expr + Term
                     Expr → Term
                     Term → Term * Factor
                     Term → Factor
                     Factor → "(" Expr ")"
                     Factor → integer

12. What is the primary use of attribute grammars?
      Answer : An attribute grammar is an extension to a context-free grammar. The primary purpose                          of an attribute grammar is it allows certain language rules to be described, such as type                        of compatibility. An attribute grammar is a formal way to define attributes for the                                productions of a formal grammar, associating these attributes to values. The evaluation                        occurs in the nodes of the abstract syntax tree, when the language is processed by some                        parser or compiler.


13. Explain the primary uses of a methodology and notation for describing
      the semantics of programming languages.
      Answer : Object modeling techniques and notations presents a methodology using a completely                          different diagrams with other techniques commonly used for data modeling and process                      modeling.


14. Why can machine languages not be used to define statements in operational
      semantics?
      Answer : Machine language can not be used to define statements in operational semantics                                  because of some problems. First, the individual steps in the execution of machine
                     language and the resulting changes to the state of the machine are too small and too                              numerous. Second, the storage of a real computer is too large and complex.


15. Describe the two levels of uses of operational semantics.
      Answer : There are different levels of uses in operational semantics. At the highest level, the                               focus is on the final result of the execution of a program, this is sometime 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.




- 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
     Answer : None of those are the language generated by the grammar, it should be k<A>aj<B>b,(A                     contains b and B contains a) in which the end will be a single b, the list of answer does                         not include an answer that ends with a single b


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
     Answer : No one of the following statements are generated.


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>bb  | abb


14. Draw parse trees for the sentences aabb and aaaabbbb, as derived from
      the grammar of Problem 13.
      Answer :  We  first derive a grammar in order to know how to draw the tree.

                     <stmt> -> <A>

                    <A> -> a<A>b | ab

                    tree for aabb

                    tree for aaaabbbb


15. Convert the BNF of Example 3.1 to EBNF.
      Answer : <program> -> begin <stmt_list> end

            .       <stmt_list> -> stmt[stmt_list]

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

            .       <var> -> A| B | C