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

Related questions

+1 vote
2 answers
1
0 votes
2 answers
3
asked in Compiler Design by prasitamukherjee Loyal (3.4k points)   | 162 views
Top Users Jan 2017
  1. Debashish Deka

    7172 Points

  2. Habibkhan

    4696 Points

  3. Vijay Thakur

    4308 Points

  4. sudsho

    4090 Points

  5. saurabh rai

    4024 Points

  6. Arjun

    3292 Points

  7. santhoshdevulapally

    3066 Points

  8. GateSet

    3016 Points

  9. Bikram

    3014 Points

  10. Sushant Gokhale

    2892 Points

Monthly Topper: Rs. 500 gift card

18,838 questions
23,808 answers
51,589 comments
20,148 users