GATE CS
A compiler translates source code in phases, and the first phase, lexical analysis, turns characters into tokens. Typical questions ask which phase does what, which phase reports which error, and how many tokens a C fragment has. Most of these are settled by the longest-match rule and by knowing what is and is not a token.
8 previous-year questions · 8 solved · 5 practice questions
A compiler works in phases. Each phase reads the output of the one before it and produces a new representation of the program. The phases in order are lexical analysis, syntax analysis, semantic analysis, intermediate code generation, code optimisation and code generation. Code optimisation is optional: a compiler can skip it and still produce correct code.
Phase | Input | Output |
|---|---|---|
Lexical analysis | Stream of characters | Stream of tokens |
Syntax analysis | Tokens | Parse tree or syntax tree |
Semantic analysis | Syntax tree | Annotated syntax tree (types checked, names resolved) |
Intermediate code generation | Annotated tree | Intermediate code, for example three-address code |
Code optimisation | Intermediate code | Better intermediate code |
Code generation | Intermediate code | Target (machine or assembly) code |
The front end is the part that depends on the source language: lexical, syntax and semantic analysis and intermediate code generation. The back end is the part that depends on the target machine: code generation and the machine-dependent part of optimisation. Machine-independent optimisation works on the intermediate code and depends on neither. Intermediate code is the meeting point, so one front end can be paired with several back ends, and one back end with several front ends.
A pass is one reading of the whole program, in some representation. Several phases can be grouped into one pass. For example, the lexer, parser and semantic analyser often run together, with the parser asking the lexer for tokens one at a time.
Phase | Formal tool used |
|---|---|
Lexical analysis | Regular expressions and finite automata |
Syntax analysis | Context-free grammars and pushdown automata (parsers) |
Semantic analysis | Type rules and syntax-directed definitions (attributes) |
EXAM TIP
A phase takes the output of the previous phase as its input. The parser never sees characters or comments; it sees only tokens. Balanced parentheses are not a regular language, so the lexer cannot check them. That check belongs to the parser.
The symbol table is a data structure that stores information about names in the program: for each identifier its type, scope and where it is stored (such as its memory offset), and for a function its parameter types and return type. It is created and filled in the early phases: the lexical analyser may enter a lexeme, and later the parser and semantic analyser add attributes. Semantic analysis, optimisation and code generation read it. It is not itself a phase. Every phase also reports its errors through an error handler, and the lexer tracks line numbers so that messages can point to the source.
Kind of error | Detected in | Example |
|---|---|---|
Lexical | Lexical analysis | Illegal character such as |
Syntax | Syntax analysis | Missing semicolon, unbalanced parentheses, |
Semantic | Semantic analysis | Undeclared variable, type mismatch, wrong number of arguments |
EXAM TIP
Decide the phase by what is wrong. Characters that match no token pattern are a lexical error. A misspelled keyword or name that still forms a valid identifier is not lexical. A wrong order of tokens is syntactic. A correctly ordered statement that breaks a meaning rule (types, declarations) is semantic.
Lexical analysis is the only phase that reads the characters of the source. It groups them into meaningful units and removes comments and white space, which the later phases never see. It usually runs as a subroutine that the parser calls each time it needs the next token, and it enters identifiers in the symbol table.
Term | Meaning | Example |
|---|---|---|
Token | A category name (with an optional attribute) passed to the parser |
|
Lexeme | The actual character sequence matched in the source |
|
Pattern | The rule describing every lexeme of a token, usually a regular expression | letter followed by letters or digits, for |
A token such as id has many possible lexemes. A token such as if has just one lexeme. Tokens are usually the keywords, identifiers, constants, string literals, operators and punctuation symbols.
Regular definitions (a common convention)
letter: any of a to z or A to Z, together with the underscore
digit: any of 0 to 9
id: letter followed by zero or more letters or digits
number: one or more digits, optionally a fraction, optionally an exponent
Keywords such as if, else, while are single fixed strings
At each position the lexical analyser must decide which lexeme to take. Two rules decide it. Longest match (maximal munch): take the longest prefix of the remaining input that matches any pattern. Priority: if the longest match fits more than one pattern, the pattern listed first wins.
Keywords also match the identifier pattern. For example, if fits both. So the keyword rule is listed before the identifier rule. That choice gives if as a keyword, while iffy is still one identifier, because the identifier match is longer.
Input | Tokens by longest match | Count |
|---|---|---|
|
| 3 |
|
| 4 |
|
| 5 |
|
| 1 |
|
| 1 |
EXAM TIP
Longest match is greedy. At each position the lexer takes the longest match, whether or not the rest of the input can then be tokenised and whether or not the program parses. It never picks a shorter token to help later. In x+++++y it produces x, ++, ++, +, y, and the program is rejected later, even though x++ + ++y would have been valid.
Procedure
Ignore comments (both block and line) and white space. They are not tokens.
Scan left to right, taking the longest match at each position.
Count each keyword, identifier, constant, operator and punctuation symbol as one token. Operators made of several characters, such as ++, +=, >=, -> and <<=, are one token each.
Count a whole string literal, including the quotes and any spaces inside it, as one token.
Count a character constant such as 'a' as one token.
WORKED EXAMPLE
How many tokens are in this fragment?
int a = 5; /* set */ if (a >= 3) printf("hi %d", a);The comment is ignored.
Statement 1: int, a, =, 5, ; gives 5 tokens.
Statement 2 head: if, (, a, >=, 3, ) gives 6 tokens.
Call: printf, (, "hi %d", ,, a, ), ; gives 7 tokens.
Total: 5 + 6 + 7 = 18.
Answer: 18
EXAM TIP
The text inside a string literal is never split into tokens, and a comment may contain words that look like code, so ignore them as well.
A lexical error occurs when no pattern matches the input at the current position, for example an illegal character or an unterminated string literal. Many mistakes still form valid tokens, so the lexer cannot catch them. A misspelled keyword such as whiel is a valid identifier. It is caught later only if the resulting token sequence breaks a syntax rule or a meaning rule.
Common recovery strategies
Panic mode: delete characters from the remaining input until a valid token starts
Delete one extra character
Insert a missing character
Replace one character by another
Transpose two adjacent characters
A lexer generator takes a list of patterns (regular expressions) with an action for each, and produces a lexical analyser. Internally it builds a finite automaton for the patterns, typically an NFA converted to a DFA, and runs it with longest match and priority by order to choose the token.
PREVIOUS-YEAR QUESTIONS
Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.
See these papers in full: GATE CSE 2026 Set 1 · GATE CSE 2026 Set 2 · GATE CSE 2025 Set 1 · GATE CSE 2024 Set 2 · GATE CSE 2023 · GATE CSE 2020 · GATE CSE 2018
Consider the following C statements:
char *str1 = "Hello; /* Statement S1 */
char *str2 = "Hello;"; /* Statement S2 */
int *str3 = "Hello"; /* Statement S3 */Which of the following options is/are correct?
S1 and S2 have syntactic errors
S2 has a lexical error and S3 has a syntactic error
S1 has a lexical error and S3 has a semantic error
S1 has a syntactic error and S3 has a semantic error
A lexical analyzer uses the following token definitions
For the string given below,
x1 23mm 78 y 7z zz5 14A 8H AaYcD
the number of tokens (excluding ) that will be produced by the lexical analyzer is ______. (answer in integer)
Which ONE of the following statements is FALSE regarding the symbol table?
Symbol table is responsible for keeping track of the scope of variables.
Symbol table can be implemented using a binary search tree.
Symbol table is not required after the parsing phase.
Symbol table is created during the lexical analysis phase.
Consider the following two sets:
Set X: P. Lexical Analyzer; Q. Syntax Analyzer; R. Intermediate Code Generator; S. Code Optimizer
Set Y: 1. Abstract Syntax Tree; 2. Token; 3. Parse Tree; 4. Constant Folding
Which one of the following options is the CORRECT match from Set X to Set Y ?
P – 4; Q – 1; R – 3; S – 2
P – 2; Q – 3; R – 1; S – 4
P – 2; Q – 1; R – 3; S – 4
P – 4; Q – 3; R – 2; S – 1
Consider the following statements regarding the front-end and back-end of a compiler.
S1: The front-end includes phases that are independent of the target hardware.
S2: The back-end includes phases that are specific to the target hardware.
S3: The back-end includes phases that are specific to the programming language used in the source code.
Identify the CORRECT option.
Only S1 is TRUE.
Only S1 and S2 are TRUE.
S1, S2, and S3 are all TRUE.
Only S1 and S3 are TRUE.
Consider the following statements.
I. Symbol table is accessed only during lexical analysis and syntax analysis.
II. Compilers for programming languages that support recursion necessarily need heap storage for memory allocation in the run-time environment.
III. Errors violating the condition 'any variable must be declared before its use' are detected during syntax analysis.
Which of the above statements is/are TRUE?
I only
I and III only
II only
None of I, II, and III
Which one of the following statements is FALSE?
Context-free grammar can be used to specify both lexical and syntax rules.
Type checking is done before parsing.
High-level language programs can be translated to different Intermediate Representations.
Arguments to a function can be passed using the program stack.
A lexical analyzer uses the following patterns to recognize three tokens , , and over the alphabet .
: a? (b|c)* a
: b? (a|c)* b
: c? (b|a)* c
Note that 'x?' means 0 or 1 occurrence of the symbol x. Note also that the analyzer outputs the token that matches the longest possible prefix.
If the string bbaacabc is processed by the analyzer, which one of the following is the sequence of tokens it outputs?
OTHER EXAMS
From ISRO's Scientist/Engineer written test: ISRO CS 2025, ISRO CS 2023. They are not counted in the GATE numbers on this page.
30. Which compiler phase receives tokenized output?
Lexical Analyser
Parser
Pre-processor
Assembler
Consider the NFA with epsilon-transitions below, which is meant to accept strings corresponding to a lexical token id. Here the token digit corresponds to the extended regular expression [0-9] and letter corresponds to [a-z A-Z]. In the diagram, a small incoming edge indicates a start state while a double circle indicates a final state.
Which of the following extended regular expressions corresponds to the token id?
Tap to open full sizeAn NFA with epsilon-transitions. A start state (small incoming arrow from the left) has an edge labelled 'letter' to a double-circled final state F. From F, two epsilon edges leave: the upper one goes to a state from which an edge labelled 'letter' leads to another state, and the lower one goes to a state from which an edge labelled 'digit' leads to another state. Each of these two end states has an epsilon edge into a common join state at the right. From the join state a long epsilon edge, drawn as an arc over the top, returns to F.
letter (letter | digit)*
(letter | digit)* letter
(letter | digit)*
letter (letter* | digit*)
Which sequence below best describes the order in which the phases of a compiler typically work?
Syntax analysis, lexical analysis, semantic analysis, code optimization, intermediate code generation
Lexical analysis, syntax analysis, semantic analysis, code optimization, intermediate code generation
Syntax analysis, lexical analysis, syntax analysis, semantic analysis, intermediate code generation, code optimization
Lexical analysis, syntax analysis, semantic analysis, intermediate code generation, code optimization
PRACTICE
How many tokens does the C statement below contain? Assume the lexical analyser uses the longest-match rule.
x = y+++z;Answer:
Scan left to right with longest match: x, =, y.
At +++ the longest operator is ++, so the next token is ++.
The remaining + is a token, then z, then ;.
Tokens: x, =, y, ++, +, z, ; which is 7.
In a C program, a variable is used without being declared. In which phase of the compiler is this error normally detected?
Lexical analysis
Syntax analysis
Semantic analysis
Code generation
Answer: (C)
The statement uses valid tokens in a valid order, so lexical and syntax analysis accept it.
Checking that a name is declared needs the symbol table, which is a semantic check.
The answer is C.
Which of the following statements are correct?
For the input a<=b, a lexical analyser using longest match produces three tokens.
A missing closing parenthesis is normally reported by the lexical analyser.
A type mismatch, such as assigning a string literal to an int variable, is normally detected by type checking during semantic analysis.
White space between two tokens is passed to the parser as a separate token.
Answer: (A), (C)
A is true: the tokens are a, <=, b.
B is false: unbalanced parentheses are a syntax error found by the parser.
C is true: a type mismatch is a semantic error found by type checking.
D is false: white space is discarded by the lexical analyser.
The correct options are A and C.
How many tokens does the following C fragment contain?
for (i = 0; i < 10; i++) /* loop */
s += a[i]; // addAnswer:
Comments are ignored.
for, (, i, =, 0, ; gives 6 tokens.
i, <, 10, ; gives 4 tokens, total 10.
i, ++, ) gives 3 tokens, total 13.
s, +=, a, [, i, ], ; gives 7 tokens (+= is one token).
Total: 13 + 7 = 20.
A lexical analyser has three patterns, listed in this order: R1 = a+, R2 = a+b, R3 = b. It applies longest match, and priority by order for ties. How many tokens does it produce for the input aaabaa?
2
3
4
6
Answer: (A)
At the first character, R1 matches aaa (3 characters) and R2 matches aaab (4 characters). The longest is R2, so the first token is aaab.
The remaining input is aa. R1 matches aa, and R2 and R3 do not match.
There are 2 tokens, so the answer is A.
OFFICIAL GATE 2027 SYLLABUS WORDING
Copied from the GATE 2027 syllabus; see all 2027 syllabi.
GATE CS
Lexical analysis
Preparing in Kolkata? IAE Academy's course for GATE CSE.