GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
343 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)   | 343 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)  

Related questions

+1 vote
2 answers
1
0 votes
2 answers
3
asked in Compiler Design by prasitamukherjee Loyal (3.7k points)   | 214 views
Top Users Feb 2017
  1. Arjun

    5396 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3952 Points

  4. Aboveallplayer

    3086 Points

  5. Debashish Deka

    2564 Points

  6. sriv_shubham

    2318 Points

  7. Smriti012

    2240 Points

  8. Arnabi

    2008 Points

  9. mcjoshi

    1696 Points

  10. sh!va

    1684 Points

Monthly Topper: Rs. 500 gift card

20,863 questions
26,023 answers
59,698 comments
22,136 users