LR(1) Parsing Table for the Grammar

Step 1: EXTRACT - Given Data

Grammar: $$S \to AA$$ $$A \to 0A$$ $$A \to \varepsilon$$

• Terminals: $${0, $}$$
• Non-terminals: ${S, A}$
• Marks: 10

Step 2: SOLVE

Augmented Grammar

$$ \begin{aligned} (0)\ & S' \to S\ (1)\ & S \to AA\ (2)\ & A \to 0A\ (3)\ & A \to \varepsilon \end{aligned} $$

Canonical LR(1) Item Sets

Closure rule: For $[B \to \alpha \bullet C\beta, a]$, add $[C \to \bullet \gamma, b]$ for each $b \in \text{FIRST}(\beta a)$.

$$I_0 = \text{Closure}([S' \to \bullet S, $])$$

• $$[S' \to \bullet S, $]$$
• $$[S \to \bullet AA, $]$$ (dot before $S$, FIRST($$$ $$) = $$$ $$)
• Dot before first $A$; lookahead $=$ FIRST$$(A$) = {0, $}$$ (since $A \Rightarrow \varepsilon$):
  • $$[A \to \bullet 0A, 0/$]$$
  • $$[A \to \bullet, 0/$]$$

Transitions: $S \to I_1$, $A \to I_2$, $0 \to I_3$

$I_1 = \text{goto}(I_0, S)$

• $$[S' \to S \bullet, $]$$ (Accept)

$I_2 = \text{goto}(I_0, A)$

• $$[S \to A \bullet A, $]$$
• Dot before second $A$; lookahead $=$ FIRST($$$ $$) $$= {$}$$:
  • $$[A \to \bullet 0A, $]$$
  • $$[A \to \bullet, $]$$

Transitions: $A \to I_4$, $0 \to I_5$

$I_3 = \text{goto}(I_0, 0)$

• $$[A \to 0 \bullet A, 0/$]$$
• Dot before $A$; lookahead $$= {0, $}$$:
  • $$[A \to \bullet 0A, 0/$]$$
  • $$[A \to \bullet, 0/$]$$

Transitions: $A \to I_6$, $0 \to I_3$ (self-loop, same item set)

$I_4 = \text{goto}(I_2, A)$

• $$[S \to AA \bullet, $]$$ (reduce by rule 1)

$I_5 = \text{goto}(I_2, 0)$

• $$[A \to 0 \bullet A, $]$$
• $$[A \to \bullet 0A, $]$$
• $$[A \to \bullet, $]$$

Transitions: $A \to I_7$, $0 \to I_5$ (self-loop)

$I_6 = \text{goto}(I_3, A)$

• $$[A \to 0A \bullet, 0/$]$$ (reduce by rule 2)

$I_7 = \text{goto}(I_5, A)$

• $$[A \to 0A \bullet, $]$$ (reduce by rule 2)

Reduce actions

• $I_0$: $$[A \to \bullet, 0/$]$$ → reduce by rule 3 on $0$ and $$$ $$
• $I_2$: $$[A \to \bullet, $]$$ → reduce by rule 3 on $$$ $$
• $I_3$: $$[A \to \bullet, 0/$]$$ → reduce by rule 3 on $0$ and $$$ $$
• $I_4$: reduce by rule 1 on $$$ $$
• $I_5$: $$[A \to \bullet, $]$$ → reduce by rule 3 on $$$ $$
• $I_6$: reduce by rule 2 on $0$ and $$$ $$
• $I_7$: reduce by rule 2 on $$$ $$

Notation: $sn$ = shift and go to state $n$; $rn$ = reduce by production $n$; $acc$ = accept; blank = error.

LR(1) Parsing Table

Note on conflicts (States 0 and 3)

In states $I_0$ and $I_3$ the item $[A \to \bullet, 0]$ calls for reduce by rule 3 on input $0$, while the items $[A \to \bullet 0A, \dots]$ call for shift on $0$. This is a shift/reduce conflict on 0.

Resolving in favor of shift (standard convention, and required for this grammar to accept strings like $00$), the entries $s3$ / $s5$ are used on input $0$. With this resolution the parser works correctly. Strictly, the grammar is not LR(1) because of this genuine shift/reduce conflict in states 0 and 3, so I have shown both actions in those cells.

Final Result

The canonical collection has 8 states ($I_0$ through $I_7$), and the completed LR(1) table is as shown above, with shift/reduce conflicts on input 0 in states 0 and 3 (resolved by shift).

FIRST and FOLLOW Computation

Given data (Grammar)

$$S \rightarrow AB$$ $$A \rightarrow 0A' \mid 1A' \mid \varepsilon$$ $$A' \rightarrow SSA' \mid \varepsilon$$ $$B \rightarrow AS \mid 1$$

Non-terminals: $S, A, A', B$
Terminals: $0, 1$
Start symbol: $S$

Step 1: FIRST Sets

FIRST(A)

From $A \rightarrow 0A' \mid 1A' \mid \varepsilon$: $$FIRST(A) = {0, 1, \varepsilon}$$

FIRST(B)

From $B \rightarrow AS \mid 1$:

• $B \rightarrow 1$ gives $1$
• $B \rightarrow AS$: add $FIRST(A)\setminus{\varepsilon} = {0,1}$; since $\varepsilon \in FIRST(A)$, also add $FIRST(S)$.

Since $S$ cannot derive $\varepsilon$ (needs both $A$ and $B$ to vanish, but $B$ cannot), $FIRST(S)$ adds only ${0,1}$: $$FIRST(B) = {0, 1}$$

FIRST(S)

From $S \rightarrow AB$:

• Add $FIRST(A)\setminus{\varepsilon} = {0,1}$
• Since $\varepsilon \in FIRST(A)$, add $FIRST(B) = {0,1}$
• $\varepsilon$ not added (B cannot derive $\varepsilon$) $$FIRST(S) = {0, 1}$$

FIRST(A')

From $A' \rightarrow SSA' \mid \varepsilon$:

• $A' \rightarrow \varepsilon$ gives $\varepsilon$
• $A' \rightarrow SSA'$: add $FIRST(S) = {0,1}$ $$FIRST(A') = {0, 1, \varepsilon}$$

Summary

Step 2: FOLLOW Sets

Rules: Start gets $$$ $$; for $X\to \alpha Y\beta$ add $FIRST(\beta)\setminus{\varepsilon}$ to $FOLLOW(Y)$; if $\varepsilon\in FIRST(\beta)$ or $\beta$ empty, add $FOLLOW(X)$ to $FOLLOW(Y)$.

FOLLOW(S)

• Start symbol: add $$$ $$
• $A' \rightarrow SSA'$:
  • First $S$ followed by $SA'$: add $FIRST(S)\setminus{\varepsilon}={0,1}$
  • Second $S$ followed by $A'$: add $FIRST(A')\setminus{\varepsilon}={0,1}$; since $\varepsilon\in FIRST(A')$, add $FOLLOW(A')$
• $B \rightarrow AS$: $S$ at end, add $FOLLOW(B)$

$$FOLLOW(S) = {$, 0, 1} \cup FOLLOW(A') \cup FOLLOW(B)$$

FOLLOW(A)

• $S \rightarrow AB$: $A$ followed by $B$, add $FIRST(B)\setminus{\varepsilon}={0,1}$; $\varepsilon\notin FIRST(B)$, no more.
• $B \rightarrow AS$: $A$ followed by $S$, add $FIRST(S)\setminus{\varepsilon}={0,1}$; $\varepsilon\notin FIRST(S)$, no more. $$FOLLOW(A) = {0, 1}$$

FOLLOW(A')

• $A \rightarrow 0A' \mid 1A'$: $A'$ at end, add $FOLLOW(A)={0,1}$
• $A' \rightarrow SSA'$: $A'$ at end, add $FOLLOW(A')$ (itself, no new info) $$FOLLOW(A') = {0, 1}$$

FOLLOW(B)

• $S \rightarrow AB$: $B$ at end, add $FOLLOW(S)$ $$FOLLOW(B) = FOLLOW(S)$$

Resolve FOLLOW(S) and FOLLOW(B)

$$FOLLOW(S) = {$, 0, 1} \cup FOLLOW(A') \cup FOLLOW(B)$$ $$= {$, 0, 1} \cup {0,1} \cup FOLLOW(B)$$

Since $FOLLOW(B) = FOLLOW(S)$, this is self-referential and adds nothing new: $$FOLLOW(S) = {$, 0, 1}$$ $$FOLLOW(B) = {$, 0, 1}$$

Final Answer

Symbol Table Operations and Activation Tree

Part 1: Operations Performed in Symbol Table

A symbol table is a data structure used by compilers to store information about source-program constructs (identifiers, their types, storage locations, scope, etc.). The analysis phase collects this information and the synthesis phase uses it to generate target code.

Basic Operations on a Symbol Table

Information Stored in Each Entry

Each entry in the symbol table typically contains:

• Name: Name of the identifier (stored directly or as a pointer to a string table)
• Type: Type of identifier (variable, label, procedure, etc.)
• Location/Offset: Position in storage where the identifier is stored
• Scope: Region of the program where the current definition is valid
• Other attributes: Array limits, record fields, parameter lists, return values, etc.

Part 2: Activation Tree

(Standard compiler design concept; notes are thin on this topic, so supplemented from standard CS knowledge)

Definition

An activation tree is a tree data structure used to represent the way control flows among procedures (functions) during the execution of a program. Each node in the tree represents an activation record (also called a stack frame) of a procedure call.

Key Points

• Each call to a procedure creates a new activation (node).
• The root of the tree represents the activation of the main program.
• If procedure A calls procedure B, then the node for B is a child of the node for A.
• The execution of activations follows a last-in, first-out (LIFO) order, which is why a runtime stack can be used to implement it.
• Control enters a child node when a procedure is called and returns to the parent node when the procedure finishes.

Properties

1. The lifetime of an activation of procedure A includes the lifetime of all activations called by A.
2. Activations are non-overlapping or nested -- they never partially overlap.
3. The path from the root to the currently executing node represents the current state of the runtime stack.

Example

Consider the following program:

main() {
    A();
    B();
}
A() {
    C();
}
B() { }
C() { }

The activation tree is:

        main
       /    \
      A      B
      |
      C

Explanation:

• main calls A, so A is the left child of main.
• A calls C, so C is the child of A.
• After A (and C) finish, main calls B, so B is the right child of main.

Relation to Runtime Stack

At any point during execution, the stack contains exactly the activations on the path from the root to the currently executing node in the activation tree. For example:

• When C is executing: Stack = [main, A, C]
• When B is executing: Stack = [main, B]

Summary

Roles of Macros and Preprocessor; One Pass vs Multi-Pass Compiler

1. Roles of Macros and Preprocessor

A preprocessor is a tool that processes the source code before it is passed to the compiler. It is generally considered a part of the compiler system and produces input for the compiler proper.

Key Functions of a Preprocessor:

i) Macro Processing: A preprocessor allows a user to define macros, which are shorthands for longer constructs. When the preprocessor encounters a macro call, it replaces it with the corresponding expanded code before compilation begins.

• Example: #define MAX 100 replaces every occurrence of MAX with 100.

ii) File Inclusion: The preprocessor handles header file inclusion by inserting the content of specified files into the program text.

• Example: #include <stdio.h> inserts the standard I/O header file.

iii) Rational Preprocessor: These preprocessors augment older languages with more modern flow-of-control and data structuring facilities, making legacy code more manageable.

iv) Language Extensions: These preprocessors attempt to add capabilities to the language by building in macro-like constructs, effectively extending what the base language can express.

2. One Pass vs Multi-Pass Compiler

One Pass Compiler:

A compiler in which all phases are combined and executed in a single pass over the source program.

Multi-Pass Compiler:

A compiler in which different phases are grouped into multiple passes, each pass reading the output of the previous one.

Comparison Table:

Summary:

• A one pass compiler is simpler and faster but less flexible, as it cannot easily handle forward references.
• A multi-pass compiler is more powerful and can perform better optimization since it has a complete view of the program through intermediate representations.

Type Conversion and Type Checking

Explicit Type Conversion

Explicit type conversion (also called type casting) is a conversion that is manually performed by the programmer by writing a specific instruction in the source code. The programmer explicitly specifies the target type to which a value should be converted.

Example:

int a = 10;
float b = (float) a;   // programmer explicitly casts int to float

Implicit Type Conversion

Implicit type conversion (also called type coercion) is a conversion that is automatically performed by the compiler without any explicit instruction from the programmer. The compiler applies conversion rules defined by the type system when operands of different types are used together.

Example:

int a = 5;
float b = 3.2;
float c = a + b;   // compiler automatically converts 'a' to float

Here, the integer a is automatically promoted to float before the addition is performed.

Why Do We Need to Check the Type of a System?

The collection of different data types and their associated rules to assign types to programming language constructs is known as type systems. A type checker implements a type system.

Type checking is necessary for the following reasons:

1. Ensures Type Correctness

Type checking verifies that operations are applied to compatible types. Without it, meaningless operations (such as adding a string to an integer) could go undetected.

2. Prevents Runtime Errors

Catching type mismatches at compile time avoids unexpected crashes or incorrect results at runtime.

3. Enforces Language Rules

Type systems define informal rules such as:

"If both operands of addition are of type integer, then the result is of type integer."

The type checker enforces these rules consistently across the program.

4. Supports Semantic Correctness

Even if a program is syntactically correct, it may be semantically wrong due to type mismatches. Type checking adds a layer of semantic validation.

Justification with an Example

Consider the following expression:

int x = 5;
char ch = 'A';
int result = x + ch;

Without type checking: The compiler would not know whether adding an int and a char is valid, and the result type would be undefined or erroneous.

With type checking: The type checker applies the rule:

The type checker detects that char can be implicitly converted to int (ASCII value of 'A' = 65), so:

result = 5 + 65 = 70

This is a valid, well-typed expression. If instead we wrote:

int x = 5;
char *str = "hello";
int result = x + str;   // TYPE ERROR

The type checker would flag this as a type error because adding an integer and a string pointer violates the type rules, preventing a potential runtime crash.

Summary

Type checking is essential to ensure that every operation in a program is applied to operands of appropriate and compatible types, making programs safe, correct, and predictable.

LL(1) Parsing Table Construction

Given Data

Grammar: $$S \rightarrow AS1 \mid C$$ $$A \rightarrow 0$$ $$C \rightarrow 2C \mid \varepsilon$$

Non-terminals: $S, A, C$; Terminals: $0, 1, 2$; End marker: $$$ $$.

Note: In $AS1$, the symbol $1$ is treated as a terminal.

Step 1: FIRST Sets

FIRST(A): $A \to 0 \Rightarrow$ FIRST(A) = ${0}$

FIRST(C): $C \to 2C$ gives $2$; $C \to \varepsilon$ gives $\varepsilon$ $$FIRST(C) = {2, \varepsilon}$$

FIRST(S):

• $S \to AS1$: FIRST(A) = ${0}$ (A is non-nullable), so add $0$
• $S \to C$: FIRST(C) = ${2, \varepsilon}$, add $2$ and $\varepsilon$ $$FIRST(S) = {0, 2, \varepsilon}$$

Step 2: FOLLOW Sets

Start: $$FOLLOW(S) \supseteq {$}$$

Production $S \to AS1$:

• After $A$ is $S$: $FOLLOW(A) \supseteq FIRST(S)\setminus{\varepsilon} = {0,2}$. Since $\varepsilon \in FIRST(S)$, continue to next symbol $1$: add ${1}$. So $FOLLOW(A) \supseteq {0,2,1}$.
• After inner $S$ is $1$: $FOLLOW(S) \supseteq {1}$

Production $S \to C$: $FOLLOW(C) \supseteq FOLLOW(S)$

Production $C \to 2C$: After $C$ is nothing: $FOLLOW(C) \supseteq FOLLOW(C)$ (no change)

Final: $$FOLLOW(S) = {1, $}$$ $$FOLLOW(A) = {0, 1, 2}$$ $$FOLLOW(C) = {1, $}$$

Step 3: PREDICT (SELECT) Sets

Step 4: LL(1) Parsing Table

Verification

Each cell holds at most one production, so no conflict exists. The grammar is LL(1).

Symbol Table and General Structure of LR Parser

Part 1: Symbol Table

A symbol table is a data structure used by a compiler to store information about the identifiers (variables, functions, objects, etc.) encountered in the source program.

The lexical analyzer helps to identify tokens and enters them into the symbol table. It stores attributes such as:

• Name of the identifier
• Type (integer, float, etc.)
• Scope (local, global)
• Memory location / address
• Size

The symbol table is accessed and updated by almost all phases of the compiler (lexical analysis, syntax analysis, semantic analysis, code generation, etc.). It allows the compiler to quickly look up and verify identifier information during compilation.

Part 2: General Structure of an LR Parser

An LR parser is a bottom-up parser that uses right-most derivation in reverse. It is more powerful than top-down parsers and can handle a larger class of grammars.

Block Diagram of LR Parser

Input:  a1  a2  ...  an  $
                |
         +------+------+
         |   LR Parser  |
         +------+------+
              |
    +---------+---------+
    |                   |
 Action Table        Goto Table
(Terminals + $)    (Non-terminals)
    |                   |
  S(shift), R(reduce),
  Accept, Error
         |
       Stack
   [State | Symbol]
   Sm | Xm
   Sm-1 | Xm-1
   ...
   S0

Components of LR Parser

Working of LR Parser

1. The parser starts with an initial state S0 on the stack.
2. It reads the current input symbol a and the top state Sm.
3. It consults the Action Table with [Sm, a]:
   • Shift (S): Push the next state onto the stack and advance input.
   • Reduce (R): Pop symbols from the stack according to the production rule and push the goto state.
   • Accept: Parsing is successful.
   • Error: Syntax error is reported.
4. The Goto Table is used after a reduction to determine the new state.

Augmented Grammar

Before constructing the LR parsing table, the grammar is augmented. If G is a grammar with start symbol S, the augmented grammar G' adds a new start symbol S' with production:

S' -> S

This ensures the parser has a definite accept state.

Types of LR Parsers

• SLR (Simple LR): Uses LR(0) items with FOLLOW sets
• CLR / LR(1): Uses LR(1) items with look-ahead symbols; more powerful
• LALR: Merges states of LR(1) to reduce table size

LR parsers are high power, use right-most derivation, and have a larger parsing table compared to top-down parsers.