The Gateway to Computer Science Excellence
+7 votes
844 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
in Compiler Design by Active (3.5k points) | 844 views

2 Answers

+8 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
by Boss (17k points)
0
Yes, D is correct. But options A and C are not really similar :)
0
Then whats exact mean by option c) in which manner complexity ?
+1
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.
0
Ohk , means less issues with lexical analysis when it use regular languages due to its simple structure(definition of regular expression) rt , is it ?
+1
Plz describe (C) option. What is the separation here?
+3

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

0
Thank  you sir! :)
–1 vote
D) All of the above
by (67 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,157 answers
193,767 comments
93,740 users