GATE CSE 2018 | Question: 8

Question

Which one of the following statements is FALSE?

• A. Context-free grammar can be used to specify both lexical and syntax rules
• B. Type checking is done before parsing
• C. High-level language programs can be translated to different Intermediate Representations
• D. Arguments to a function can be passed using the program stack

Comments

Type checking is done during the semantic analysis phase of a compiler.

Compilation Phases and Type Checking:

1. Lexical Analysis: Scans the source code and converts it into tokens.
2. Syntax Analysis: Analyzes the token stream to form a parse tree based on the syntax rules (grammar) of the language.
3. Semantic Analysis: Performs checks on the parse tree for semantic consistency, which includes type checking. 
4. Intermediate Code Generation: Converts the code to an intermediate representation.
5. Optimization: Improves the intermediate code for performance.
6. Code Generation: Converts the optimized intermediate code to target machine code.
7. Code Optimization (optional): Further optimizes the generated code.

So, type checking is a key part of the semantic analysis phase.

Answer 1

A. Since Lexical rules are nothing but regular expressions, we can use CFGs to represent such rules.(Every Type-$3$ grammar is Type-$2$ grammar) Additionally, syntax rules can be represented by CFGs. (True)

B. Type checking is done during Semantic Analysis phase which comes after Parsing. (False)

C. We have various types of Intermediate Code Representations, ex $3$-address code, Postfix notation, Syntax trees. (True)

D. Program stack holds the activation record of the function called, which stores function parameters, return value, return address etc.(True)

Correct Answer: $B$

Comments

Can u please explain what is lexical rules & syntax rules here ??

---

How can we use CFG's to impose Type3 Grammar restrictions?

 

Answer 2

Type Checking always be done after parse tree generation.
So option (b) is FALSE.

Comments

in semantic analysis phase

Answer 3

B is clearly false as type checking is done using SDTs which is basically semantic analysis.SDTs are basically parse trees hence parsing needs to be done first and then only can we do type checking.

Answer 4

A. Context-free grammar can be used to specify both lexical and syntax rules
Theoretically Valid

1. Lexical rules (tokens) are specified using regular expressions (regular grammar).

2. Context-free grammar (CFG) is used to specify syntax rules (structure of sentences).

   So, CFG cannot specify both lexical and syntax rules — only syntax.

Let’s break it down:

🔹 Lexical rules:

• Lexical rules define tokens (identifiers, keywords, numbers, etc.).

• These are usually described by regular expressions or regular grammars, because the lexical structure of programming languages is regular, not context-free.

🔹 Syntax rules:

• Syntax rules describe how tokens are combined to form valid statements or expressions.

• These are specified using context-free grammars (CFGs)

Since every regular language (Type 3) is also a context-free language (Type 2),
it’s theoretically true that a context-free grammar can describe lexical rules as well — because CFGs can represent all regular languages.

But here’s the compiler design interpretation:

• In practice, lexical rules are not written using CFGs — because regular expressions are simpler and more efficient for tokenizing.

• So compilers use regular grammars for the lexical part and CFGs for syntax.

• Hence:

• Theoretically: A is true (since every regular language is also context-free).

• Practically (compiler design context):  A is considered false because we don’t use CFGs for lexical rules.

• Must read =  https://cs.stackexchange.com/questions/55567/why-do-we-not-use-cfgs-to-describe-the-structure-of-lexical-tokens?utm_source=chatgpt.com

B. Type checking is done before parsing
Also false, but let’s compare.

• Parsing happens before type checking.

• Type checking is part of semantic analysis, which occurs after parsing.

But since only one statement is expected to be false, we must check which is more wrong according to compiler design context.

C. High-level language programs can be translated to different Intermediate Representations
 True — compilers often use multiple IRs (e.g., AST, three-address code, SSA form).

D. Arguments to a function can be passed using the program stack
 True — standard calling conventions use the program stack to pass arguments.

The Answer should be A ,B if they haven't asked which one of the following 

• A: True (theoretically valid)

• B: False (type checking occurs after parsing)

• C: True

• D: True

So the most accurate False is (B)

 

Comments

but broo every regular is cfg

 

---

Bro I have explained above ,CFG can do that  but It is not that much efficient

---

ok got it brooooo