GATE1994-1.18

Question

Which of the following features cannot be captured by context-free grammars?

• A. Syntax of if-then-else statements

• B. Syntax of recursive procedures

• C. Whether a variable has been declared before its use

• D. Variable names of arbitrary length

Answer 1

It will be C.

Since CFG's are used to show syntactic rules while designing compiler, and syntactic rules don't check for meaningful things such as if a variable has been declared before its use or not. Such things are meant to be handled by Semantic Analysis phase (requires power of a context sensitive grammar).

For D, a regular expression does not restrict the string length. Languages have restriction for variable name length for storing purpose like in symbol table.

For A, if then else is inherently ambiguous. But CFG can represent inherently ambiguous languages just that there are more than one parse trees possible for some strings.

Comments

I Agree with this point .

But it implies that "C language" or " Fortran  language " is essentially a CSL language .

---

See this question: https://gateoverflow.in/463/gate2008-51
To check variable is declared before use, we have to parse strings like $ \left\{wcw\mid w \: \in \left(a\mid b\right)^* \right\}$, That can not be done using PDA.

---

C is CSL or CFL ?

(For those who are wondering like me.)

Answer is here: https://gateoverflow.in/45246/is-c-language-cfl-or-strict-csl

---

Can you elaborate option d? How can CFG capture variable length of arbitary  name?

---

for option B, some examples for showing recursive style of cfg are...
E->E+E/E-E/E*E/(E) ,  E->id    or    S->aSb/bSa/SS/ε   or S->aSa/bSb/a/b/ε etc

---

For  this lang dpda available

{wcw∣w∈(a∣b)∗}. So why this "whether a variable has been declared before it's use " cannot be captured by context free grammar

Answer 2

c will be answer bcz the limitation of syntax analyzer are 

• it cannot determine if a token is valid,(that will be take care of by lexical nalyzer and valid token are identifers, special symbols, alphabets these are to be consider valid tokens)
• it cannot determine if a token is declared before it is being used,
• it cannot determine if a token is initialized before it is being used,
• it cannot determine if an operation performed on a token type is valid or not   so for that to handle these we go for semantic analysis phase

Comments

@Arjun @rajan

They are asking what cant be designed using CFG. Ofcourse we use CFG for option (c).

I doubt about option A and D.

For A, which i inherently ambigious, I think Ullman book has procedure for making it unambigious.

I dont know how can you detect multi-length variable i.e (  ATR -> aS where ATR is single variable.)

---

How we use CFG for C?

For D, a regular expression does not restrict the string length. Languages have restriction for variable name length for storing purpose like in symbol table.

For A, yes, if then else is inherently ambiguous. But CFG can represent inherently ambiguous languages just that there are more than one parse trees possible for some strings.

---

For C, even though we use semantic rules, they are auxillay to CFG. So, base is parsing for semantic rules. So, thats possible.

For D, we use lexical analysis. @Arjun, I didnt get your point here.

For A, if you have more than 1 parse tree means you interpreted the syntax in more than 1 way which means you failed.

---

Can anyone explain option B ?

---

i think ww can be use for c where w is (a+b)^*