Complier Design |

Complier Design Question and Answers

( Suggestion : keep refreshing the page for updated content & Search Questions Using Find )

Q1. Analyze the following line of code and show how the line is converted to target code in assembly language over the various phase of compiler a = bc*cd+50.00

Answer.

Let’s break down the given line of code: a = bc * cd + 50.00

This is a simple expression involving multiplication, addition, and assignment. The compilation process involves several phases, including lexical analysis, syntax analysis, semantic analysis, intermediate code generation, code optimization, code generation, and code optimization.

Lexical Analysis: The first phase involves breaking the code into tokens. For the given line, tokens could be: a, =, bc, *, cd, +, 50.00.
Syntax Analysis: The syntax analysis phase checks whether the tokens form a valid syntax according to the language’s grammar. In this case, it verifies that the assignment and expression structure are correct.
Semantic Analysis: This phase checks for the meaning of the expressions. It ensures that the types of bc, cd, and 50.00 are compatible for the operations involved.
Intermediate Code Generation: The compiler generates an intermediate code that represents the operations without concern for the target architecture. For simplicity, let’s use a pseudo-code. The intermediate code might look like:
t1 = bc
t2 = t1 * cd
t3 = t2 + 50.00
a = t3
Code Optimization: The compiler may perform optimizations on the intermediate code. These optimizations aim to improve the efficiency of the generated code.
Code Generation: The intermediate code is translated into assembly code specific to the target architecture. Assembly code generation depends on the architecture, and it may vary. As an example, let’s assume a simple hypothetical assembly code:
LOAD bc, R1 ; Load bc into register R1
MUL R1, cd ; Multiply R1 by cd
ADD 50.00, R1 ; Add 50.00 to R1
STORE R1, a ; Store the result in variable a
Code Optimization (again): The generated assembly code may undergo further optimization to improve its performance or reduce its size.

It’s important to note that the actual assembly code generated can vary depending on the target architecture and compiler optimizations. The example above is a simplified illustration for explanatory purposes.

b. Construct DFA for the language L(M) = {x | x is a string of (zero or more) ) a’s, b’s and c’s such that x does not contain the substring aa}

Answer.
To construct a deterministic finite automaton (DFA) for the language

L (M) = {x ∣ x

is a string of zero or more

a

‘s,

b

‘s, and

c

‘s such that

x

does not contain the substring

aa

), we can follow these steps:Let’s define the DFA

M

as follows:1. Set of States (Q):
Q={90, 91, 92}
qo is the initial state.
q₁ is the state after reading a single a
q₂ is an accepting state indicating that the string does not contain the substring aa.2. Input Alphabet (Σ):
E = {a,b,c}3. Transition Function (d):
δ(qo, a) = 91 (Reading a transitions to q₁)
d(qo, b) = qo (Reading b stays in qo)
* δ(40, c) = 40 (Reading c stays in go)
d(qı, a) = 92 (Reading a again leads to q2, which is an accepting state)
d(qı, b) = go (Reading b goes back to go)
8(41, c) = 40 (Reading c goes back to go)
• δ(92, a) = 42 (Once in q2, stay in q₂)
8(q2, b) = 92 (Once in q₂, stay in q₂)
8(92, c) = 42 (Once in q₂, stay in q₂)4. Start State (go):
qo is the start state.
5. Accepting State (q₂):
q2 is an accepting stateThe DFA

M

is then defined as

M = (Q, Σ, δ, q_{0}, {q_{2}})

.This DFA recognizes strings over the alphabet

{a, b, c}

such that the substring

aa

is not present in the string. It accepts strings that may contain any number of

a

‘s,

b

‘s, and

c

‘s, as long as there are no consecutive

a

‘s.

Q2. Design regular expression for the following Languages:
a. L= {we {a, b}*w is even}.
b. L = {we {0, 1}*length of w is odd }.
c. L= {we {0, 1}*atmost one pair consecutive 1’s).
d. L= {w € {0, 1}*:
e. L = {we {a,b}*: the third character is 0) w contains an odd number of a’s}.
f. L = {we {0, 1}*: every pair of adjacent 0’s appears before any pair of adjacent 1’s}

Answer.

Let’s design regular expressions for the given languages:

a. $L = {w \in {a, b}^{*} ∣ length of w is even}$ ^(a{2}|b{2})*(a|b)?$

b. $L = {w \in {0, 1}^{*} ∣ length of w is odd}$ ^(0|1)(0{2}|1{2})*(0|1)$

c. $L = {w \in {0, 1}^{*} ∣ at most one pair of consecutive 1’s}$ ^(0*10*1{0,1}0*)*$

d. $L = {w \in {0, 1}^{*} ∣ every block of 0’s is immediately followed by a block of 1’s}$ ^((0+1+)+0*)*$

e. $L = {w \in {a, b}^{*} ∣ the third character is 0 and w contains an odd number of a’s}$ ^(.{2}0.*(a.*a){2})*a.*$

f. $L = {w \in {0, 1}^{*} ∣ every pair of adjacent 0’s appears before any pair of adjacent 1’s}$ ^(0*10*1*)*0*$

These regular expressions are designed based on the given language descriptions. Keep in mind that there might be alternative solutions or variations depending on the specific interpretation of the language requirements.

Q3. Consider the grammar
S→S && S
S→S || S
S→!S
S→ (S)
S→ true
S→ false
Write the parse tree, LMD and RMD for the expression true && true || false

Answer.
Sure, let’s build the parse tree, leftmost derivation (LMD), and rightmost derivation (RMD) for the expression true && true || false based on the given grammar:Grammar:

S → S && S
S → S || S
S → !S
S → (S)
S → true
S → false

Expression: true && true || false

Parse Tree:

 ||
/ \
&& false
/ \
true true

Leftmost Derivation (LMD):

S
=> S && S
=> true && S
=> true && S || S
=> true && true || S
=> true && true || false

Rightmost Derivation (RMD):

S
=> S && S
=> S && true
=> S || true
=> true || true
=> true || false

In the parse tree, each non-terminal node represents a substitution according to the grammar rules, and the leaves represent the actual terminals (true, false). The leftmost and rightmost derivations show step-by-step how the expression is derived using the grammar rules.

Q4. Consider the grammar
S→aB | aC | Sd | Se
B→bBc | f
C→g
Eliminate the left recursion; Find the FIRST & FOLLOW for the above grammar.

Answer.
To eliminate left recursion from the given grammar, we need to rewrite the production rules. The original grammar is:

S → aB | aC | Sd | Se
B → bBc | f
C → g

Let’s eliminate left recursion:

S → aX | Se
X → B | C | Yd | Ze
Y → bBc | f
Z → ε | Yd | Ze
B → bBc | f
C → g

Now, let’s find the FIRST and FOLLOW sets for the modified grammar:

FIRST Sets:

FIRST(S) = {a}
FIRST(X) = {b, f, g, ε}
FIRST(Y) = {b, f}
FIRST(Z) = {ε}

FOLLOW Sets:

FOLLOW(S) = {$, d, e}
FOLLOW(X) = {$, d, e}
FOLLOW(Y) = {d, e}
FOLLOW(Z) = {d, e}

Note: $ represents the end of the input.

These sets are found based on the following rules:

If there is a production A → αBβ, then everything in FIRST(β) except ε is in FOLLOW(B).
If there is a production A → αB or A → αBβ where FIRST(β) contains ε, then everything in FOLLOW(A) is in FOLLOW(B).
ε is in FOLLOW(A) if A is the start symbol.

These sets are used in constructing predictive parsing tables and for implementing parsers in compiler design.

Q5. Construct LR(0) parsing table for the following grammar
S→aAb | bB
A→Aa |ε
B→ Bb |ε

Answer.

The LR(0) parsing table is used in bottom-up parsing to determine the actions to take based on the current state of the parsing process and the lookahead symbol. Here’s the LR(0) parsing table for the given grammar:
Grammar:

S → aAb | bB
A → Aa | ε
B → Bb | ε

LR(0) Items:

S’ → .S, $
S → .aAb, $
S → .bB, $
A → .Aa, a | ε
B → .Bb, b | ε

Parsing Table:

| State | Action   | Goto  | a     | b    | $    |
|-------|----------|-------|-------|------|------|
| 0     | Shift(1) |       | 2     | 3    |      |
| 1     |          |       |       |      | Accept |
| 2     | Shift(4) |       |       |      |       |
| 3     | Shift(5) |       |       |      |       |
| 4     | Shift(1) |       | 6     | 3    |       |
| 5     | Shift(5) |       |       | 7    |       |
| 6     |          | Reduce|       |      | Reduce|
| 7     |          | Reduce|       |      | Reduce|

In the table:

“Shift” means to shift to the state indicated in the table.
“Reduce” means to apply the reduction indicated in the table.
“Accept” means the input is accepted.

The entries in the table are determined based on the LR(0) items and the transitions between states.

Q6. a) Design minimum state Deterministic Finite Automata for a formal language containing “0011” as a substring over Σ = {a,b}

Answer.
To design a minimum state Deterministic Finite Automaton (DFA) for a formal language containing “0011” as a substring over the alphabet Σ = {a, b}, we need to ensure that the DFA recognizes strings that have “0011” as a substring and rejects those that do not.Let’s design the DFA. The states will represent the different phases of the string being processed, and transitions will be determined based on the input symbols. We’ll aim to keep the number of states to a minimum.States:

q0: Initial state
q1: After reading ‘0’
q2: After reading ’00’
q3: After reading ‘001’
q4: Accepting state (after reading ‘0011’)

Transitions:

From q0:
- On ‘0’ -> q1
- On ‘1’ -> q0
From q1:
- On ‘0’ -> q2
- On ‘1’ -> q0
From q2:
- On ‘0’ -> q2
- On ‘1’ -> q0
From q3:
- On ‘0’ -> q2
- On ‘1’ -> q4
From q4:
- On ‘0’ or ‘1’ -> q4 (stay in the accepting state)

Here is the transition table:

State	0	1
q0	q1	q0
q1	q2	q0
q2	q2	q0
q3	q2	q4
q4	q4	q4

In this DFA:

The initial state is q0.
The accepting state is q4.
All transitions are deterministic.

This DFA will accept any string that contains “0011” as a substring and will transition to the accepting state (q4) when it encounters the substring. If a string does not contain the substring, it will not reach the accepting state.

b) Design Regular expression for language over (a, b) with even number of a’s followed by an odd number of b’s

Answer.
You can use the following regular expression to match strings over the alphabet {a, b} with an even number of ‘a’s followed by an odd number of ‘b’s:

^(aa)*(b(bb)*)+$

Explanation:

^: Anchors the expression to the beginning of the string.
(aa)*: Matches zero or more occurrences of ‘aa’ (even number of ‘a’s).
(b(bb)*)+: Matches one or more occurrences of ‘b’ followed by zero or more occurrences of ‘bb’ (odd number of ‘b’s).
$: Anchors the expression to the end of the string.

This regular expression ensures that the string starts with an even number of ‘a’s and is followed by an odd number of ‘b’s.

Q7. Analyze if the following grammar is suitable for top down parsing? If not, correct it such that it becomes suitable for top down parsing
S→CtS | iCtSeS | a
C→b

Answer.

The grammar you provided is not suitable for top-down parsing as it contains left-recursive productions. Left-recursive productions can cause infinite loops in top-down parsers. Let’s analyze the given grammar:

S → CtS
S → iCtSeS
S → a
C → b

The production S → CtS is left-recursive because it starts with the same non-terminal (S) that it is trying to derive. To make it suitable for top-down parsing, we need to eliminate left recursion. Here’s the corrected grammar:

S → aS'
S' → CtS' | iCtSeS' | ε
C → b

In this corrected grammar:

S → aS’ allows the production to start with ‘a’.
S’ → CtS’ | iCtSeS’ | ε handles the remaining cases, including an empty string (ε).

This eliminates left recursion and allows for a suitable top-down parsing approach.

For More Updates Join Our Channels :

Complier Design Question and Answers

Related

You might also like

Database System & Applications Question & Answers

Database Systems and Application Question and Answers

DSA