1. Construct the CLR(1) parse table for below grammar.
S → CC C → cC C→d Show the actions of the parser for the input string dd.
https://youtu.be/fpPzWswvkJw?si=l9AYsf_2h9X_mbsi
2. Define Derivation and Parse Tree? And Derive (using LMD and RMD) the string aaabbabbba using the below grammar and construct parse tree? S → aB | bA A → a | aS | bAA B → b| bS| aBB
A derivation is a process that uses a set of production rule to derive a string.
Parse tree is also known derivation tree, is a graphical representation of derivation process. https://www.gatevidyalay.com/parse-tree-derivations-automata/
3. Define Left Recursion and Eliminate left recursion for the following grammar. E→E+T/T T → T*F /F F→ ( E ) / id
Left recursion occurs when the leftmost variable of the right-hand side of a grammar rule is the same as the variable on the left-hand side
i. L={w/where w is of even length and begin with 01}
Regular expression for the given language = (0 + 1)*01
Step-01: All strings of the language ends with substring “01”. So, length of substring = 2. Thus, Minimum number of states required in the DFA = 2 + 1 = 3. It suggests that minimized DFA will have 3 states.
Step-02: MINIMUM STRING
We will construct DFA for the following strings- 01 001 101 0101…………. L(M) = { W | w end with 01}
Step-03: The required DFA is Step 4: Transition table
Step5: Transition function
DFA action for the input string 0001 Consider M(q0, 0001) M(q1,001) M(q1,01) M (q1,1) ( q2, ℇ ) Since, we reached the final state at the end of input, the string 0001 is accepted by M.
ii. L= string ending with abba over {a, b}
Regular expression for the given language = (a + b)*abba
Step-01: All strings of the language ends with substring “abba”. So, length of substring = 4. Thus, Minimum number of states required in the DFA = 4 + 1 = 5. It suggests that minimized DFA will have 5 states.
Step-02: We will construct DFA for the following strings- abba aabba ab abba abb abba abba abba
L(M) = { W | w ENDS WITH THE SUBSTRING abba }
Step-03: The required DFA is
Step 4: Transition table
Step5: Transition function DFA action for the input string ab abba Consider (q0, ab abba ) M( q1, b abba ) M( q2, abba ) M ( q1, bba ) M ( q2, ba ) M ( q3, a ) ( q4, ℇ ) Since, we reached the final state at the end of input, the string ab abba is accepted by M.
iii. L=string starting with 101 over {0,1}
Regular expression for the given language = 101(0 + 1)*
Step-01: All strings of the language starts with substring “101”. So, length of substring = 3. Thus, Minimum number of states required in the DFA = 3 + 2 = 5. It suggests that minimized DFA will have 5 states.
Step-02: We will construct DFA for the following strings 101 1010 1011 10110 101101
Step-03: The required DFA is
7. Explain the phases of compiler with a neat diagram and example
A compiler operates in phases. A phase is a logically interrelated operation that takes source program in one representation and produces output in another representation.
Compilation process is partitioned into no-of-sub processes called “phases”.
The analysis phase creates an intermediate representation from the given source code. The synthesis phase creates an equivalent target program from the intermediate representation.
1.Lexical Analysis: Lexical analysis or Lexical analyzer is the initial stage or phase of the compiler. This phase scans the source code and transforms the input program into a series of a token. A token is basically the arrangement of characters that defines a unit of information in the source code. a program that executes the process of lexical analysis is called a scanner, tokenizer, or lexer.
It is accountable for terminating the comments and white spaces from the source program. 2. Syntax Analysis: In the compilation procedure, the Syntax analysis is the second stage. Here the provided input string is scanned for the validation of the structure of the standard grammar. Basically, in the second phase, it analyses the syntactical structure and inspects if the given input is correct or not in terms of programming syntax. It accepts tokens as input and provides a parse tree as output. It is also known as parsing in a compiler.
3. Semantic Analysis: In the process of compilation, semantic analysis is the third phase. It scans whether the parse tree follows the guidelines of language. It also helps in keeping track of identifiers and expressions. In simple words, we can say that a semantic analyzer defines the validity of the parse tree, and the annotated syntax tree comes as an output.
4. Intermediate Code Generation: The parse tree is semantically confirmed; now, an intermediate code generator develops three address codes. A middle-level language code generated by a compiler at the time of the translation of a source program into the object code is known as intermediate code or text.
Till intermediate code, it is the same for every compiler out there, but after that, it depends on the platform. To build a new compiler we don’t need to build it from scratch. We can take the intermediate code from the already existing compiler and build the last two parts 5. Code optimizer: Now coming to a phase that is totally optional, and it is code optimization. It is used to enhance the intermediate code. This way, the output of the program is able to run fast and consume less space. To improve the speed of the program, it eliminates the unnecessary strings of the code and organises the sequence of statements.
6. Code Generator: The final stage of the compilation process is the code generation process. In this final phase, it tries to acquire the intermediate code as input which is fully optimised and map it to the machine code or language. Later, the code generator helps in translating the intermediate code into the machine code.
Example:
8. Construct predictive parsing table and parse the string id+id*id.
9. What is an ambiguous and un ambiguous grammar?Identify the following grammar is ambiguous or not. E→E+E | E*E | (E) |-E |id for the sentence id+id*id
Ambiguous grammar is a context-free grammar that can have more than one parse tree for a given string. Unambiguous grammar is a context-free grammar that has only one parse tree for a given string.
(4,5,10,11,12,13,14,15,16 solutions are not there in this doc as I don’t have answers for those.)
