Question

7. Lexical analyzer, is the first phase in compiler, Of what use is this to the whole compilation and 14 marks) what are the formal concepts involved ? 8. Describe this language using a Regular Expression: all strings beginning with a digit, followed 13 marks] by either a or b, and ending with an non-vowel uppercase letter 9. Write a context free granimar for the strings that consist of equal number of a's followed by equal number of b's. Attempt to represent this using a regular expression. What can you. (4 marks conclude? 10. Find a regular expression for language over the alphabet (0, 1) in which all the strings contain [5 marks) at least two 0's. Convert your expression to an equivalent NFA 11. Briefly explain how parse tree and the set of production rules help in language translation (At 13 marks] the semantic analysis phase) 12. Use the following SDT to convert an infix expression (9 3+2) to it post-fix equivalent. Praduction Semantic rules E E T (prini("") T iprlat ( T-T-P [5 marks] (print (num.lval) F-num 13, Briefly explain the relevance of DAG and TAC at the Intermediate code generation phase, Give an example of DAG(Directed Acyclic Graph) with its equivalent TACCThree-Address Code). (6 marks) 14. Parser table is very important in predictive parsing; construct a parser table for the following CFG: S ACB CbB | Ba A da BC B-gle C- hE [10 marks) 15. Bring up a question and it's equivalent solution from the topics we've covered so far. [4 marks] (Note: no similac question to the ones presented here) Perer taole

Answer 1

Question 7:

Lexical analyzer is the first phase of the compiler that is used to convert source code into stream of tokens which is passed to the next phase syntax analyzer.

For example: int x = 5;

will be converted to [int,keyword][x,identifier][assignment][5,constant][terminator]

Lexical analyzer uses the concept of regular languages such as regular expressions, finite automata, regular grammar,etc.

Question 8:

Let D be the set of digits, and N be the set of non-vowel upper case letter

D = {0,1,2,3,4,5,6,7,8,9}

N = {B,C,D,F,G,H,J,K,L,M,N,P,Q,R,S,T,V,W,X,Y,Z}

Regular expression:

(0+1+2+3+4+5+6+7+8+9)(a+b)(B+C+D+F+G+H+J+K+L+M+N+P+Q+R+S+T+V+W+X+Y+Z)

or

D(a+b)N

Question 9:

The language can be represented as:

S ={epsilon, ab, aabb, aaabbb, aaaabbbb,....} = {aⁿbⁿ, n>=0}

Context free grammar:

$\\S \rightarrow aSb| \epsilon$

The regular expression cannot be constructed for the this language as this is not a regular language.

Question 10:

Regular expression is:

$\\(0+1)^*0(0+1)^*0(0+1)^*$

Corresponding NFA is: