11. Design a NFA and convert it into its equivalent DFA for the pattern (a/b)*a(aa/ab/ba/bb).
**
The given pattern (a/b)*a(aa/ab/ba/bb) consists of:
1. (a/b)* → Any combination of a and b (including empty string).
2. a → Ensures the last a before the final part.
3. (aa/ab/ba/bb) → The string must end with any of aa, ab, ba, or bb.
Step 1: Design the NFA
1. Start state q0 allows any sequence of a or b ((a/b)*).
2. A transition on a moves to q1.
3. The final part (aa/ab/ba/bb) leads to final states.
NFA Representation:
(q0) --a,b--> (q0) // Loop for (a/b)*
(q0) --a--> (q1) // Reaching the required 'a'
(q1) --a--> (q2) // Matching aa
(q1) --b--> (q3) // Matching ab
(q2) --a,b--> (qF) // Reaching final state for aa, ab
(q3) --a,b--> (qF) // Reaching final state for ba, bb
Step 2: Convert NFA to DFA
• Convert non-deterministic states to deterministic ones using -closure.
• Construct a DFA with each state representing a set of NFA states.
[Link] a short note on the lexical analyzer tool, Lex.
Lex is a Lexical Analyzer Generator used for tokenizing source code in compiler design. It converts regular
expressions into a Finite Automaton that identifies tokens.
Features of Lex:
[Link] Recognition:
Uses regex to define keywords, identifiers, numbers, and symbols.
[Link] Lexical Analysis:
Generates a C program that implements the lexical analyzer.
Input Format (Lex File Structure):
%{ Definitions %}
%%
Regular Expressions { Actions }
%%
Example: Tokenizing identifiers and numbers
[a-zA-Z_][a-zA-Z0-9_]* { printf("IDENTIFIER"); }
[0-9]+ { printf("NUMBER"); }
Output:
•Generates a function yylex() that reads input and identifies tokens.
Use in Compiler Design:
- Lex works with Yacc (Yet Another Compiler Compiler) for syntax analysis in parsing.
-
20. How to eliminate left recursion in a CFG? Explain with an ex-ample.
Left recursion occurs when a non-terminal calls itself on the left side of a production rule.
Algorithm to Remove Left Recursion:
1. Identify the left-recursive rules:
A→A |
2. Rewrite using a new non-terminal A':
A→ A'
A'→ A'|
Example: Before Elimination (Left Recursive Grammar):
E→E+T|T
After Elimination:
E→TE'
E'→+TE'|
Now, E does not call itself on the left, removing left recursion.
22. Define recursive descent parser. Write a code segment to generate a parse tree for a given
string w.r.t. production rules of a given grammar.
A Recursive Descent Parser is a top-down parser that uses a set of re-cursive functions to process
input according to the grammar rules.
Example Grammar:
E→TE'
E'→+TE'|
T→FT'
T'→*FT'|
F → (E) | id
Recursive Descent Parser (C Code Example):
void E() {
T();
E_prime();
}
void E_prime() {
if (lookahead == '+') {
match('+');
T();
E_prime();
}
}
void T() {
F();
T_prime();
}
void T_prime() {
if (lookahead == '*') {
match('*');
F();
T_prime();
}
}
void F() {
if (lookahead == 'id') match('id');
else if (lookahead == '(') {
match('(');
E();
match(')');
}
}
How It Works:
- E() calls T(), which calls F(), which matches id.
- Recursively expands based on input tokens.
23. Define the term first() & follow() used in predictive parsing. FIRST Set:
• FIRST(X) contains all terminals that can appear at the beginning of any string derived from X.
• Rules to Compute FIRST(X):
1. If X is a terminal, then FIRST(X) = {X}.
2. If X → Y1 Y2 ... Yk, add FIRST(Y1) to FIRST(X).
3. If Y1 can derive , check FIRST(Y2), and so on.
Example:
E→TE'
T→FT'
F → (E) | id
• FIRST(E) = { ( , id }
• FIRST(T) = { ( , id }
FOLLOW Set:
• FOLLOW(X) contains terminals that appear immediately after X in some derivation.
• Rules to Compute FOLLOW(X):
1. If X is the start symbol, add $ (EOF).
2. If A → X , add FIRST( ) to FOLLOW(X).
3. If can derive , add FOLLOW(A) to FOLLOW(X).
Example:
- FOLLOW(E) = { $, ) }
- FOLLOW(T) = { +, ) }
24. Write the procedure to check if a grammar is LL(1) or not.
A grammar is LL(1) if it can be parsed by a predictive parser without back-tracking.
Steps to Check LL(1) Grammar:
1. Compute FIRST and FOLLOW Sets for All Non-Terminals.
2. Check the Predictive Parsing Table:
• If a non-terminal A has A → and A → , then FIRST( ) FIRST( ) = .
3. Check Unique Entries in the Parsing Table:
• Each entry in the parsing table must contain at most one produc-tion rule.
Example:
E→TE'
E'→+TE'|
T→FT'
T'→*FT'|
F → (E) | id
• FIRST & FOLLOW Sets:
FIRST(E) = { ( , id } FOLLOW(E) = { $, ) }
• No conflicts in FIRST and FOLLOW sets → Grammar is LL(1).
[Link] operator precedence parsing algorithm. Algorithm for Operator Precedence parsing:
1. Initialize stack with $.
2. Read tokens from input.
3. Compare precedence between top of stack and input symbol using the precedence table.
• If f(a) < g(a), shift input to stack.
• If f(a) > g(a), reduce stack contents using a production rule.
4. Repeat until stack contains $E$ and input is fully parsed.
Example for id + id * id:
Step 1: Stack: $, Input: id + id * id $
Step 2: Shift id → Stack: $ id, Input: + id * id $
Step 3: Reduce id → E → Stack: $ E, Input: + id * id $
Step 4: Shift + → Stack: $ E +, Input: id * id $
Step 5: Shift id → Stack: $ E + id, Input: * id $
Step 6: Reduce id → E → Stack: $ E + E, Input: * id $
Step 7: Shift * → Stack: $ E + E *, Input: id $
Step 8: Shift id → Stack: $ E + E * id, Input: $
Step 9: Reduce id → E → Stack: $ E + E * E, Input: $
Step 10: Reduce `E + E * E` → `E`
Step 11: Accept!
31. How to check if a grammar is LR(1) or not?
A grammar is LR(1) if it can be parsed by an LR(1) parser without con-flicts.
Steps to Check LR(1) Grammar:
1. Construct LR(1) Items:
• Add . markers for different parsing steps.
• Example: E → •E + T
2. Compute Closure & GOTO Functions:
• Use First() & Follow() sets.
3. Build the LR(1) Parsing Table:
• If there are no Shift-Reduce or Reduce-Reduce conflicts, the grammar is LR(1).
Example:
E→E+T|T
T→F*F|F
F → id
This can be parsed using LR(1) since each step is uniquely determined.