GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
452 views
A context free grammar can be used to model the lexical concerns of a HLL. This is not normally done and a regular grammar is used for the structure of lexemes because
(A) The cfg will blow up unnecessarily
(B) The structure of lexemes can be described by the simpler regular grammar
(C) There is a separation of concerns which controls complexity.
(D) All of the above
asked in Compiler Design by Boss (5.7k points)   | 452 views

2 Answers

+5 votes
Ans should be D) All the above

A) yes it is true , as we know regular languages are implemented by finite automata which is more efficient to implement than context free languages implementation (using push down automata which is used stack ) .

B) structure of lexeme usually  be in letter(letter+digit )* and regular grammar describe it .

c) same reason as option a) .

for more detail ref: http://www.iith.ac.in/~ramakrishna/Compilers-Aug15/slides/02-lexical-analysis-part-1.pdf
answered by Veteran (13.2k points)  
Yes, D is correct. But options A and C are not really similar :)
Then whats exact mean by option c) in which manner complexity ?
Option C is more towards Software Engineering terms- that is, how difficult to manage different versions of the code and all. Option A is concerning more time complexity- that is how much time compilation takes.
Ohk , means less issues with lexical analysis when it use regular languages due to its simple structure(definition of regular expression) rt , is it ?
Plz describe (C) option. What is the separation here?

Separation means- Lexical analysis phase takes care of tokenization and parsing phase takes care of syntax checking. i.e., the two tasks of tokenization and parsing are separated - makes software maintenance and development easy- in object oriented model we get 2 objects here, one for lexical analysis and one for parsing. 

In option A, it says that if we don't use a separate lex phase, our CFG will be much bigger and this can increase the parsing time. CYK algorithm for parsing runs in $\Theta \left(n^3 . |G|\right)$, where $n$ is the length of the parsing string and $|G|$ is the size of the grammar in CNF form. https://en.wikipedia.org/wiki/CYK_algorithm

Thank  you sir! :)
0 votes
D) All of the above
answered by (63 points)  


Top Users Sep 2017
  1. Habibkhan

    7142 Points

  2. Warrior

    2640 Points

  3. Arjun

    2480 Points

  4. rishu_darkshadow

    2466 Points

  5. A_i_$_h

    2214 Points

  6. nikunj

    1980 Points

  7. manu00x

    1846 Points

  8. makhdoom ghaya

    1770 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,133 questions
33,705 answers
79,886 comments
31,105 users