Lexical Analysis Practice Questions

The lexical analyzer uses the following rules: an identifier $id$ starts with a $letter$ followed by zero or more $letter$ or $digit$ characters ($id \rightarrow letter(letter | digit)^*$), and a $number$ is a sequence of one or more $digit$ characters ($number \rightarrow digit^+$). Whitespace ($ws$) is ignored.

Scanning the string $x1 \quad 23 \quad mm \quad 78 \quad y \quad 7 \quad z \quad zz5 \quad 14 \quad A \quad 8 \quad H \quad AaYcD$, we identify the following tokens:

1. $x1$ ($id$)
2. $23$ ($number$)
3. $mm$ ($id$)
4. $78$ ($number$)
5. $y$ ($id$)
6. $7$ ($number$)
7. $z$ ($id$)
8. $zz5$ ($id$)
9. $14$ ($number$)
10. $A$ ($id$)
11. $8$ ($number$)
12. $H$ ($id$)
13. $AaYcD$ ($id$)

Counting these tokens gives a total of 13.

[CORRECT_OPTION: 13]

The symbol table is a crucial data structure used by compilers to store information about identifiers (variables, functions, etc.). It helps track properties like scope, type, and address.

Here's why option C is false:

1. Lexical Analysis Phase: The symbol table is indeed created and populated during this phase as identifiers are recognized.
2. Parsing and Semantic Analysis Phases: It is used to check for type consistency, scope rules, and other semantic checks.
3. Code Generation Phases: The symbol table is essential for allocating memory and generating machine code, as it contains address information for variables. Therefore, it is required well beyond the parsing phase.

Let's analyze each statement:

I. The symbol table is accessed throughout various phases of compilation, not just lexical and syntax analysis. It's also used during semantic analysis (for type checking and scope resolution) and code generation. Thus, statement I is FALSE.

II. Compilers for languages supporting recursion typically use a stack (for activation records) for run-time memory allocation for local variables and parameters. Heap storage is generally used for dynamic memory allocation requested by the programmer (e.g., using malloc or new), which is not a necessary consequence of supporting recursion itself. Thus, statement II is FALSE.

III. Errors related to "any variable must be declared before its use" are typically detected during semantic analysis, not syntax analysis. Syntax analysis focuses on the grammatical structure of the code, while semantic analysis deals with the meaning and consistency of the code, including declaration rules. Thus, statement III is FALSE.

Since all statements are FALSE, none of them are TRUE.

In a two-pass assembler, the primary objective of the first pass ($Pass_1$) is to scan the source code to build the symbol table. During this scan, the assembler identifies every label and subroutine name, assigning them specific memory addresses. By calculating and storing these addresses in the symbol table, the assembler effectively resolves the locations of all subroutines. Since both the definition of labels and the resolution of their associated addresses are finalized during this initial scan, both tasks occur during the first pass.

To determine the number of tokens in the C code, we identify each lexical unit sequentially:

$switch$ (1), ( (2), $inputvalue$ (3), ) (4), { (5), $case$ (6), $1$ (7), : (8)
$b$ (9), = (10), $c$ (11), $*$ (12), $d$ (13), ; (14), $break$ (15), ; (16)
$default$ (17), : (18), $b$ (19), = (20), $b$ (21), $++$ (22), ; (23)
$break$ (24), ; (25), } (26)

Summing these individual tokens results in exactly 26.

The BNF rules define <word> as either a single <letter> (length 1), or a <letter> followed by an even-length <charpair> or <intpair> (length $1 + 2n$). Consequently, any derived word must have an odd total length.

1. "pick" has length 4 (even), making it impossible to derive from these rules.
2. "picks" has length 5 (odd); it is derived via <letter> ('p') followed by <charpair> ('icks', where icks is generated by <charpair> -> <charpair><letter><letter>).
3. "c44" has length 3 (odd); it is derived via <letter> ('c') followed by <intpair> ('44').

Since both "picks" and "c44" are valid, the correct options are II and III.

The lexical analyzer uses the "longest possible prefix" rule on the input string bbaacabc.

1. The longest prefix of the string that matches any of the three patterns is bbaac. This string matches the pattern for token $T_3: c?(b|a)^*c$. Here, c? matches an empty string, (b|a)^* matches bbaa, and the final c matches c.
2. After this token is recognized, the remaining string is abc.
3. The longest prefix of the remaining string abc that matches a pattern is the entire string abc itself. This also matches the pattern for token $T_3$.
   Therefore, the sequence of tokens output by the analyzer is $T_3T_3$.

The lexical analyzer, or scanner, serves as the first phase of a compiler, accepting the raw source code as a stream of characters. It processes these characters to form lexemes and maps each lexeme to its corresponding token, typically represented as a pair: \langle \text{token_type}, \text{attribute_value} \rangle. These tokens serve as the basic building blocks that are passed sequentially to the syntax analyzer (parser) for further structural analysis. Since the lexical analyzer outputs this sequence to subsequent compilation stages, its output is defined as a stream of tokens.

In C, tokens are the smallest individual units recognized by the compiler. The statement printf("i=%d, &i=%x", i, &i); is parsed into the following distinct units:

1. printf (Identifier)
2. ( (Delimiter)
3. "i=%d, &i=%x" (String literal)
4. , (Punctuator)
5. $i$ (Identifier)
6. , (Punctuator)
7. & (Operator)
8. $i$ (Identifier)
9. ) (Delimiter)
10. ; (Punctuator)

The string literal acts as a single token, while operators (&) and punctuators are counted individually. Summing these units confirms there are $10$ tokens total.

Yacc is a standard Unix utility designed to function as a parser generator. The acronym stands for "Yet Another Compiler Compiler." In this context, the name follows a common, somewhat humorous naming convention of the era ("Yet Another..."), while "Compiler Compiler" accurately describes its role in creating a compiler's parser based on a provided formal grammar specification. Therefore, the definition maps directly to the fourth option.

In a sequential search, the algorithm iterates through each element of the symbol table of length $L$ one by one, starting from the first index. An unsuccessful search occurs when the target element is not present in the table. To conclude that the element is definitely not present, the algorithm must exhaustively check every position, performing one comparison for each of the $L$ entries. Consequently, the total number of comparisons required to guarantee an unsuccessful search is $L$.

Keywords in a programming language are predefined reserved words that have special meaning. The initial phase of a compiler that recognizes these fundamental units is called lexical analysis. During lexical analysis, the source code is scanned and broken down into a stream of tokens, where each token represents a meaningful unit like keywords, identifiers, operators, etc. This process does not involve parsing (which deals with grammatical structure), code generation, or dataflow analysis.

Lexical analysis, also known as scanning, is the first phase of a compiler. Its primary task is to read the input character stream and group characters into meaningful sequences called lexemes, producing a sequence of tokens. This process involves recognizing regular patterns in the input.

Regular expressions are used to define the patterns for tokens (e.g., keywords, identifiers, operators). Finite state automata (FSA) are the theoretical model equivalent to regular expressions, meaning they can recognize exactly the set of languages described by regular expressions (regular languages). Deterministic finite automata (DFA) are sufficient for this task as they can recognize all regular languages efficiently.

Therefore, finite state automata provide the necessary and sufficient power for lexical analysis.

The occupation density, often referred to as the load factor ($\alpha$), represents the ratio of the number of stored entries to the total capacity of the symbol table. It is calculated using the following formula:

$\alpha = \frac{\text{Number of entries}}{\text{Total table size}}$

Given that the number of entries is $25$ and the table length is $152$, we perform the calculation:

$\alpha = \frac{25}{152} \approx 0.16447$

Rounding this value to three decimal places yields an occupation density of $0.164$.

A Symbol Table is the data structure used by a compiler to store and manage information about various program entities, such as variables, functions, classes, and objects. For each identifier, the symbol table stores essential attributes like its data type, its scope (the region of the program where it is valid), and its memory location. This information is crucial for the compiler to perform semantic analysis (e.g., type checking) and to generate the correct machine code.

In FORTRAN, spaces are insignificant, meaning the compiler ignores them during the initial scanning phase. The statement DO 10 I = 1.25 is interpreted by concatenating the characters, resulting in DO10I = 1.25.

The tokenizer then identifies the following three distinct tokens:

1. $DO10I$ (a valid identifier/variable name)
2. = (an assignment operator)
3. $1.25$ (a real number literal)

This results in a total of 3 tokens.

In a standard two-pass assembler:
i. Object code generation occurs during Pass 2, utilizing the completed symbol table.
ii. Literals are identified and added to the literal table during Pass 1.
iii. The listing file is printed during Pass 2, as it requires finalized addresses and generated object code.
iv. Address resolution of local symbols occurs during Pass 1 to construct the symbol table.
This yields the sequence 2, 1, 2, 1.

In the first pass of a two-pass assembler, the primary objective is to define the symbol table and establish the memory map. By processing every source statement and incrementing the Location Counter ($LC$), the assembler builds the symbol table for all labels (C) and tracks the program size to determine the total length (B). Furthermore, it identifies literal declarations, creates a literal pool, and allocates the required memory space (A). Since generating executable machine code (like load/store instructions) requires fully resolved symbol addresses from the table, that task is deferred to the second pass, making option D incorrect.

[CORRECT_OPTION: A, B, C]

The lexical analyser, often called the scanner, serves as the first phase of the compilation process. Its fundamental role is to perform a linear scan of the source program, processing the input stream character by character. During this process, it groups the characters into logical units called tokens-such as $keywords$, $identifiers$, and $operators$-while discarding extraneous whitespace and comments. Because it handles the raw input stream before any structural or grammatical analysis occurs, it is the specific module that examines every character of the source text.

Thompson's construction for concatenation r·s: (1) Build NFA_r for r with initial state i_r and final state f_r. (2) Build NFA_s for s with initial state i_s and final state f_s. (3) Connect f_r to i_s via an ε-transition (f_r is no longer accepting). (4) The combined NFA has initial state i_r and final state f_s. This ensures the combined NFA first matches r (reaching f_r via an ε), then transitions to NFA_s to match s. For alternation r|s: a new initial state has ε-transitions to both i_r and i_s; a new final state receives ε-transitions from both f_r and f_s.