GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
356 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.1k points)   | 356 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 (12.4k 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 (53 points)  


Top Users Mar 2017
  1. rude

    5118 Points

  2. sh!va

    3054 Points

  3. Rahul Jain25

    2920 Points

  4. Kapil

    2730 Points

  5. Debashish Deka

    2602 Points

  6. 2018

    1574 Points

  7. Vignesh Sekar

    1422 Points

  8. Akriti sood

    1382 Points

  9. Bikram

    1350 Points

  10. Sanjay Sharma

    1128 Points

Monthly Topper: Rs. 500 gift card

21,531 questions
26,861 answers
61,191 comments
23,206 users