KBP Assignment

Concepts of Programming Language 10th edition

Chapter 3

For Mr. TriDjokoWahjono

Review Question

1. Define syntax and semantics.

Syntax : The form of its expressions, statements, and program units.

Semantics : The meaning of those expressions, statements, and program units.

5. What is the difference between a sentence and a sentential form?

Sentence : The strings of a language.

sentential : Each of the strings in the derivation, including <program>.

7. What three extensions are common to mose EBNFs?

C if-else statement.

The use of braces in an RHS to indicate that the enclosed part can be repeated indefinitely or left out altogether.

The third common extension deals with multiple-choice options.

8. Distinguish between static and dynamic semantics.

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.

Dynamic semantics is describing the meaning of the programs. Programmers need to know precisely what statements of a language do. Compile writers determine the semantics of a language for which they are writing compilers from English descriptions.

10. What is the difference between synthesized and an inherited attribute?

Synthesized attributes are used to pass semantic information up a parse tree. Inherited attributes pass semantic information down and across a tree.

12. What is the primary use of attribute grammars?

An attribute grammar is a device used to describe more of the structure of a programming language that can be described with a context-free grammar. An attribute grammar is an extension to a context-free grammar.

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

Machine language can’t be used to define statements in operational semantics 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.

Problem Set

1. Syntax error and semantic error are two types of compilation error. Explain the difference between the two in a program with examples.

syntax error : if (a==1) b=2

-->syntax error : there's no semicolon (;) at the end of the statement

semantic error : for (int i=0;i<=n;i++) i--;

-->semantic error : basically a logical error

13. 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.

<S> -> a<S>bb | abb

14. Draw parse trees for the sentences abb and aabbbb, as derived from the grammar of Problem number 13.

abb :            <S>

                   /   |   \

                 a    b   b

aabbbb :           <S>

                       /   |   \   \

                     a  <S>  b b

                         /  |  \

                        a  b  b

15. Convert the BNF of Example 3.1 to EBNF.

<program> -> begin {stmt} end

<stmt> -> <var> = <expression>

<var> -> A | B | C

<expression> -> <var> [ ( + | - ) <var> ]

16. Convert the BNF of Example 3.3 to EBNF.

<assign> -> <id> = <expr>

<id> -> A | B | C

<expr> -> <expr> { ( + | * ) <expr> }

                 | ( <expr> )

                 | <id>

17. Convert the following EBNF to BNF:

     S -> A{bA}

     A -> a[b]A

     

     <S> -> <A> | <S>b<A>

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

18. What is a fully attributed parse tree?

– a parse tree with all attribute values computed

– conceptually attribute values are computed after

parse tree is constructed by compiler

–  not really the way it’s done.