Review & Problem Set for Chapter 3 from Concepts of Programming Languages Tenth Edition by Robert Sebesta

REVIEW Chapter 3

1. Define syntax and semantics.
the syntax of a programming language is the form of its expressions, statements, and program units. Its semantics is the meaning of those expressions, statements, and program units.

3. Describe the operation of a general language generator.
Language generator is a device that can be used to generate the sentences of languages. Language generator operates by generating a sentence of language, however language generators is unpredictable.

5. What is the difference between a sentence and a sentential form?
The difference is that a sentential form is any string derivable from the start symbol while sentence is a sentential form which contains only terminal symbols.

6. Define a left-recursive grammar rule.
A left recursive grammar rule is a grammar rule that has its left hand side also appearing at the beginning of its RHS, this left recursion specifies left associatively.

8. Distinguish between static and dynamic semantics.
The static semantic define restriction on the structure of valid texts that are hard or impossible to express ins standard syntactic formalisms while dynamic semantic defines how and when the various constructs of a language should produce a program behavior.

10. What is the difference between a synthesized and an inherited attribute?
The synthesized attributes are the result of the attribute evaluation rules, and may also use the values of the inherited attributes. The inherited attributes are passed down from parent nodes. In some approaches, synthesized attributes are used to pass semantic information up the parse tree, while inherited attributes help pass semantic information down it.

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 than is possible with a context-free grammar. 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.

19. What two things must be defined for each language entity in order to construct a denotational description of the language?
objects and functions

20. Which part of an inference rule is the antecedent? 
The antecedent is the top part of an inference rule.

21. When a grammar rule said to be left recursive?
When a grammar rule has its LHS also appearing at the beginning of its RHS, the rule is said to be left-recursive. This left recursion specifies left associativity.


PROBLEM SET Chapter 3

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 is due to we doesn't follow the rule of a language and the compiler/interpreter unable to recognize, for example in C, missing a semicolon, will result in a syntax error. While semantic error is a logical error, for example 5 + 5 = 7.

3. Rewrite the BNF of example 3.4 to represent operator – and operator / instead of operator + and operator *.
.       <assign> => <id>  = <expr>

.       <id> => A|B|C

.       <expr>=> <expr> – <term> | <term>

.       <term> => <term> / <factor> | <factor>

.       <factor>=> (<expr>)   | <id>


10. Describe, in English, the language defined by the following grammar:

<S> -> <X> <Y>

<X> -> x<X> | x

<Y> -> y<Y> | y

Answer :
<S> -> <X> <Y>

S is defined as the statement <X> <Y>

.        <X> -> x<X> | x

while <X> itself is defined as x<X> or just x(this statement is able to loop back to X so that X can contain x inside the function. This will result in an k number of x

.        <Y> -> y<Y> | y

while <Y> is defined as y<Y> or just y(this statement is able to loop back to y so that Y can contain a inside the function. This will result in an j number of y (same case as X)

because X can contain k number of x and Y can contain j number of y, this will result in <S> -> k*<x >j*<y> whereas k is >= 1 and j is >= 1 therefore allowing unlimited amount of x and y.
 
11. Consider the following grammar:

<S> -> <A>a <B> b

<A> -> <A>b | b

<B> -> a<B> | a

Answer :
in my opinion, 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

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 string abb, aabbbb, and aaaabbbbbbbb are in the language byt a, aabb, ba, and aaabb are not.
<S> => a<S>bb<S>  | abb


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> }


16. Convert the BNF of example 3.3 to EBNF.
.      <assign> -> id = <expr>

.      <id> -> A|B|C

.      <expr> -> <expr> {(+ | *) <expr>) | <id>


17. Convert the following EBNF to BNF:

S -> a{bA}

A ->a[b]A

Answer :

.    S -> A | AX

.       X -> bA | bAX

.       A -> aA | abA


18. What is a fully attributed parse tree?
A fully attributed parse tree is a parse tree which are the attributes in all its nodes are computed.