Chapter 3

Concepts of Programming Languages 10th Edition – Robert W. Sebesta
Page 182-186
Lecturer : Tri Djoko Wahjono

Review Questions (Randomly 10 of 29)

  1. Define syntax and semantics. (Number 1)
    – Syntax is the form of its expressions, statements, and program units. Semantics is the meaning of those expressions, statements, and program units.
  2. Who are language descriptions for? (Number 2)
    – Language description is used to make a statement more bold and provide a better imagery.
  3. What is the difference between a sentence and a sentential form? (Number 5)
    – Sentence is the strings of a language. Sentential is each of the strings in the derivation, including <program>.
  4. What three extensions are common to most EBNFs ? (Number 7)
    – Denotes an optional part of an RHS, Use of braces in an RHS to indicate that the enclosed part can be repeated indefinitely or left out altogether, and Multi Choice options.
  5. Distinguish between static and dynamic semantics. (Number 8)
    – Static semantics is more on the legal forms of programs (syntax rather symantics) and is only indirectly related to the meaning of the programs during execution. Static semantics is so named because the analysis required to check these specifications can be done at compile time. In many cases, the semantic rules of language state its type constraints.
  6. What is the difference between a synthesized and an inherited attribute ? (Number 10)
    – Synthesized attributes are used to pass semantic information up a parse tree. Inherited attributes pass semantic information down and across a tree.
  7. What is the primary use of attribute grammars ? (Number 12)
    –  Attribute grammar is primary used to provide complete descriptions of the syntax and static semantics of programming languages.
  8. Why can machine languages not be used to define statements in operational semantics? (Number 14)
    – Because the individual steps in the execution of machine language and the resulting changes to the state of machine are too small and too numerous.
  9. In denotational semantics, what are the syntactic and semantic domains?  (Number 16)
    – The mapping functions of a denotational semantics programming language specification, like all functions in math, have a domain and a range, the domain is called the syntactic domain, and the range is called the semantic domain.
  10. Which semantics approach is most widely known? (Number 18)
    Denotational semantics.

Problem Sets (Randomly 10 of 28)

  1. Syntax error and semantic error are two types of compilation error. Explain the difference between the two in a program with examples. (Number 1)
    – Syntax error : if (a==1) b=2
    example : syntax error : there’s no semicolon (;) at the end of the statement
     Semantic error : for (int i=0;i<=n;i++) i–;
    example : semantic error : basically a logical error
  2. Rewrite the BNF of Example 3.4 to represent operator – and operator / instead of operator + and operator *. (Number 3)
    <assign>-> <id> = <expr>
    <id> -> A| B| C
    <expr>-> <expr> -<term>
    <term>-> <term> / <factor>
    | <factor>
    <factor> -> (<expr>)
  3. Prove that the following grammar is ambiguous
    <S> -> <A>
    <S> -> <A> * <A> | <id>
    <id> -> x | y | z (Number 8)
    – If the grammar generates a different parse tree, then we can say the grammar is ambiguous. The grammar generates two different parse trees.
  4. Modify the grammar of Example 3.4 to add a unary minus operator that has higher precedence than either + or *. (Number 9)
    We can assume that the operators can precede any operand. And than we can replace the rule.
    <factor> → <id> with <factor> → + <id> | – <id>
  5. Describe, in English, the language defined by the following grammar :
    <S> -> <X><Y>
    <X> -> x<X> | x
    <Y> -> y<Y> | y (Number 10)
    One or more x’s followed by one or more y’s.
  6. 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. bbaabb
    b. bbaba
    c. bbaaaabb
    d. abaabb (Number 11)
    – The answer is
    bbaabb and bbaaaabb (a and c)
  7. Write a grammar for the language consisting of strings that have n copies of the letter a followed by double the number of copies of the letter b, where n>0. For example, the strings abb, aabbbb, aaaabbbbbbbb, are in the language but a, aabb, ba, and aaabb are not. (Number 13)
    <S> -> a<S>bb | abb
  8. Convert the BNF of Example 3.3 to EBNF. (Number 16)
    <assign> → <id> = <expr>
    <id> → A | B | C
    <expr> → <expr> (+ | -) <expr>
    | (<expr>)
    | <id>
  9. Convert the following EBNF to BNF:
    S -> A{bA}
    A -> a[b]A (Number 17)
    <S> -> <A> | <S>b<A>
    <A> -> a<A> | ab<A>
  10. What is a fully attributed parse tree ? (Number 18)
    A parse tree whose attributes have been computed.
This entry was posted in KBP. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s