Compiler Design and Construction · Unit 2 · 22 hrs
Lexical, Syntax and Semantic Analysis
Exam-focused notes for Lexical, Syntax and Semantic Analysis (Compiler Design and Construction, CSC376): what the TU syllabus asks and how it has actually been tested, with 35 solved past questions from this unit.
What this unit covers
- Lexical Analysis: Its role
- Specification and Recognition of tokens
- Input Buffer
- Finite Automata relevant to compiler construction syntactic specification of languages
- Optimization of DFA based pattern matchers
- Syntax Analysis: Its role
- Basic parsing techniques: Problem of Left Recursion
- Left Factoring
- Ambiguous Grammar
- Top-down parsing
- Bottom-up parsing
- LR parsing
- Semantic Analysis: Static & Dynamic Checks
- Typical Semantic errors
- Scoping
- Type Checking
- Syntax directed definitions (SDD) & Translation (SDT)
- Attribute Types: Synthesized & Inherited
- Annotated Parse Tree
- S-attributed and L-attributed grammar
- Applications of syntax directed translation
- Type Systems
- Type Checking and Conversion
LR parsing
Give an example of reduce-reduce conflict. Construct the SLR parsing table for the following grammar.E→(L)∣aE \rightarrow (L) \mid aE→(L)∣aL→L,E∣EL \rightarrow L, E \mid EL→L,E∣E[10]
A reduce-reduce conflict occurs when, in a single LR state, two or more complete items (items with the dot at the far right) call for reduction by different productions, and a lookahead symbol is in the FOLLOW set of more than one of the corresponding left-...
Full solved answer →Define core item. Compute the LR(1) item sets for the following grammar. S→AAS \rightarrow AAS→AAA→aA∣bA \rightarrow aA \mid bA→aA∣b[5]
Grammar: - $S \rightarrow AA$ - $A \rightarrow aA \mid b$ The core of an LR(1) item $[A \rightarrow \alpha.\beta, a]$ is its first component $A \rightarrow \alpha.\beta$, i.e., the underlying LR(0) item with the look-ahead removed. Two LR(1) item sets have ...
Full solved answer →Construct the LR(1) parsing table for the following grammar.S→AaAbS \rightarrow AaAbS→AaAbA→BbBaA \rightarrow BbBaA→BbBaA→εA \rightarrow \varepsilonA→εB→εB \rightarrow \varepsilonB→ε[10]
Number the productions: - (0) $S' \to S$ - (1) $S \to AaAb$ - (2) $A \to BbBa$ - (3) $A \to \varepsilon$ - (4) $B \to \varepsilon$ Terminals: $$a, b, \$ $$. Non-terminals: $S', S, A, B$. - $\text{FIRST}(B) = \{\varepsilon\}$ - $\text{FIRST}(A)$: from $A \to...
Full solved answer →Given the following grammar with SLR parsing table, test whether the string "int * (int + int)" will be accepted or rejected.
$$ \begin{aligned} E &\to T + E \quad \ldots (1) \ E &\to T \quad \ldots (2) \ T &\to int * T \quad \ldots (3) \ T &\to int \quad \ldots (4) \ T &\to (E) \quad \ldots (5) \end{aligned} $$
$$\begin{array}{|c|c|c|c|c|c|c||c|c|}\hline & \text{ACTION} & & & & & & \text{GOTO} & \ \hline \text{STATE} & \text{int} & * & + & ( & ) & $ & E & T \ \hline 1 & S5 & & & S4 & & & 2 & 3 \ \hline 2 & & & & & & \text{ACC} & & \ \hline 3 & & S6 & & & R2 & R2 & & \ \hline 4 & S5 & & & S4 & & & 7 & 3 \ \hline 5 & & S8 & R4 & & R4 & R4 & & \ \hline 6 & S5 & & & S4 & & & 9 & 3 \ \hline 7 & & & & & S10 & & & \ \hline 8 & S5 & & & S4 & & & & 11 \ \hline 9 & & & & & R1 & R1 & & \ \hline 10 & & & R5 & & R5 & R5 & & \ \hline 11 & & & R3 & & R3 & R3 & & \ \hline \end{array} $$
Grammar: - (1) $E \rightarrow T + E$ - (2) $E \rightarrow T$ - (3) $T \rightarrow int T$ - (4) $T \rightarrow int$ - (5) $T \rightarrow (E)$ Input string: int ( int + int ) $ Parsing table (as given): STATE int + ( ) \$ E T --------------------------- 1 S5 ...
Full solved answer →Differentiate between LR(0) and LR(1) algorithm. Construct LR(1) parse table of the following grammar.S→AAS \rightarrow AAS→AAA→aA∣bA \rightarrow aA | bA→aA∣b[10]
S.N. LR(0) LR(1) -------------------- 1 Item has no look-ahead: form $[A \to \alpha.\beta]$ Item carries a look-ahead: form $[A \to \alpha.\beta, a]$ 2 Reductions applied on all input symbols (LR(0)/SLR use FOLLOW) Reduction applied only on the item's speci...
Full solved answer →Construct SLR parsing table for the following grammar.S→aAa∣bAb∣baS \rightarrow aAa | bAb | baS→aAa∣bAb∣ba[6]
The grammar as given is: $$S \rightarrow aAa \mid bAb \mid ba$$ The nonterminal $A$ appears on the right-hand side but no productions for $A$ are given. A grammar with an undefined nonterminal is incomplete and cannot generate a language or produce a valid ...
Full solved answer →Construct SLR parse table for the following grammarS→ES \rightarrow ES→EE→E+T∣TE \rightarrow E+T|TE→E+T∣TT→T∗F∣FT \rightarrow T*F|FT→T∗F∣FF→idF \rightarrow idF→id[6]
Grammar: - $S \rightarrow E$ - $E \rightarrow E + T \mid T$ - $T \rightarrow T F \mid F$ - $F \rightarrow id$ Terminals: $\{+, , id\}$, plus endmarker $$\$ $$ Non-terminals: $\{S, E, T, F\}$ $$ \begin{aligned} &(0)\ S' \rightarrow S\\ &(1)\ S \rightarrow E\...
Full solved answer →Create the LR(1) parsing table for following grammar.S→AAS \rightarrow AAS→AAA→0AA \rightarrow 0AA→0AA→εA \rightarrow \varepsilonA→ε[10]
Grammar: $$S \to AA$$ $$A \to 0A$$ $$A \to \varepsilon$$ - Terminals: $$\{0, \$\}$$ - Non-terminals: $\{S, A\}$ - Marks: 10 $$ \begin{aligned} (0)\ & S' \to S\\ (1)\ & S \to AA\\ (2)\ & A \to 0A\\ (3)\ & A \to \varepsilon \end{aligned} $$ Closure rule: For ...
Full solved answer →What is a symbol table? Discuss the general structure of an LR parser. [5]
--- 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...
Full solved answer →Generate the LR(0) item sets for the following grammar. A→BBA \rightarrow BBA→BBB→bB∣aB \rightarrow bB \mid aB→bB∣a[5]
Grammar: - $A \to BB$ - $B \to bB \mid a$ Start symbol: $A$. Terminals: $\{a, b\}$. Non-terminals: $\{A, B\}$. - $(0)\ A' \to A$ - $(1)\ A \to BB$ - $(2)\ B \to bB$ - $(3)\ B \to a$ $I0 = \text{Closure}(\{A' \to \cdot A\})$ $A' \to \cdot A$ adds $A \to \cdo...
Full solved answer →Basic parsing techniques
Compute the FIRST and FOLLOW of the non-terminals in the following grammar. S→(L)∣1S \rightarrow (L) \mid 1S→(L)∣1L→L;S∣εL \rightarrow L;S \mid \varepsilonL→L;S∣ε[5]
Grammar: $$S \rightarrow (L) \mid 1$$ $$L \rightarrow L\,;\,S \mid \varepsilon$$ - Non-terminals: $S$, $L$ - Terminals: $($, $)$, $1$, $;$ - Start symbol: $S$ --- FIRST(S): - $S \rightarrow (L)$ gives first symbol $($ - $S \rightarrow 1$ gives first symbol ...
Full solved answer →Define Left recursive grammar. Remove left recursion from the following grammar. S→SB∣CaS \rightarrow SB | CaS→SB∣CaB→Bb∣cB \rightarrow Bb | cB→Bb∣cC→aB∣aC \rightarrow aB | aC→aB∣a[5]
Grammar productions: - $S \rightarrow SB \mid Ca$ - $B \rightarrow Bb \mid c$ - $C \rightarrow aB \mid a$ A grammar is left recursive if it contains a non-terminal $A$ such that there is a derivation $A \Rightarrow^{+} A\alpha$ for some string $\alpha$ of g...
Full solved answer →Attribute Types
Describe the synthesized attribute and inherited attribute with an example. [5]
Definition: Attributes of a node that are derived from its children nodes are called synthesized attributes. - Information flows bottom-up in the parse tree (from children to parent). - A node's attribute value is computed from the attribute values of its c...
Full solved answer →Define attribute grammar with example of inherited and synthesized attributes. [5]
An attribute grammar (also called a Syntax-Directed Definition, SDD) is a context-free grammar together with attributes and semantic rules, where: - Attributes are associated with grammar symbols (terminals and non-terminals) - Semantic rules are associated...
Full solved answer →Differentiate between synthesized and inherited attributes with example. [5]
Attributes of a node that are derived from its children nodes are called synthesized attributes. - Information flows bottom-up in the parse tree (from children to parent). - A node's attribute value is computed from the attribute values of its children. Att...
Full solved answer →Top-down parsing
What is a type expression? List the properties of LL(1) grammar. [5]
--- The type of a language construct is denoted by a type expression. A type expression is either a basic type or is formed by applying an operator called a type constructor to other type expressions. The sets of basic types and constructors depend on the l...
Full solved answer →Differentiate between one-pass and multi-pass compiler. Construct the LL(1) parsing table for the following grammar.S→ABCDS \rightarrow ABCDS→ABCDA→a∣εA \rightarrow a | \varepsilonA→a∣εB→bB \rightarrow bB→bC→0∣εC \rightarrow 0 | \varepsilonC→0∣εD→d∣εD \rightarrow d | \varepsilonD→d∣ε[10]
Feature One-Pass Compiler Multi-Pass Compiler --------- Number of scans Scans source exactly once Scans source/intermediate form multiple times Speed Faster compilation Slower (multiple traversals) Memory usage Requires less memory Requires more memory (int...
Full solved answer →Find the FIRST and FOLLOW of all the non terminals in following grammar. S→aAbcD∣εS \rightarrow aAbcD | \varepsilonS→aAbcD∣εA→SD∣εA \rightarrow SD | \varepsilonA→SD∣εC→SaC \rightarrow SaC→SaD→aBD∣εD \rightarrow aBD | \varepsilonD→aBD∣ε[5]
Grammar productions: $$S \rightarrow aAbcD \mid \varepsilon$$ $$A \rightarrow SD \mid \varepsilon$$ $$C \rightarrow Sa$$ $$D \rightarrow aBD \mid \varepsilon$$ Non-terminals present in productions: $S, A, C, D$ (and $B$ appears on the RHS of $D \rightarrow ...
Full solved answer →Differentiate between recursive descent and non-recursive predictive parsing method. Find first and follow of all the non-terminals in the following grammar.E→TA;A→+TA∣ε;T→FB;B→∗FB∣ε;F→(E)∣idE \rightarrow TA; A \rightarrow +TA|\varepsilon; T \rightarrow FB; B \rightarrow *FB|\varepsilon; F \rightarrow (E)|idE→TA;A→+TA∣ε;T→FB;B→∗FB∣ε;F→(E)∣id[6]
Grammar: $$E \rightarrow TA$$ $$A \rightarrow +TA \mid \varepsilon$$ $$T \rightarrow FB$$ $$B \rightarrow FB \mid \varepsilon$$ $$F \rightarrow (E) \mid \text{id}$$ Non-terminals: $E, A, T, B, F$. Terminals: $+, , (, ), \text{id}$. --- Basis Recursive Desce...
Full solved answer →Compute the FIRST and FOLLOW of all the non-terminals in following grammar. S→ABS \rightarrow ABS→ABA→0A′∣1A′∣εA \rightarrow 0A' \mid 1A' \mid \varepsilonA→0A′∣1A′∣εA′→SSA′∣εA' \rightarrow SSA' \mid \varepsilonA′→SSA′∣εB→AS∣1B \rightarrow AS \mid 1B→AS∣1[5]
$$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$ --- From $A \rightarrow 0A' \mid 1A' \mid \varepsilon$...
Full solved answer →Construct the LL(1) parsing table for the following grammar. S→AS1∣CS \rightarrow AS1 \mid CS→AS1∣CA→0A \rightarrow 0A→0C→2C∣εC \rightarrow 2C \mid \varepsilonC→2C∣ε[5]
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. --- FIRST(A): $A \to 0 \Rightarrow$...
Full solved answer →Specification and Recognition of tokens
How does a Lexical Analyzer recognize a token? Give an example to make it clear. Convert the regular expression $a(a+b)(b+c)⭒a# to DFA.[10]
--- A Lexical Analyzer (scanner) reads the source program character by character from left to right, groups sequences of characters into meaningful units called lexemes, and classifies each lexeme into a token by matching it against predefined patterns (spe...
Full solved answer →Syntax directed definitions
Describe about syntax directed translation with an example. [5]
Syntax Directed Translation (SDT) refers to a method of compiler implementation where the source language translation is completely driven by the parser. In SDT, a parse tree or syntax tree is constructed and the values of attributes at the nodes of the tre...
Full solved answer →Annotated Parse Tree
What is annotated parse tree? Define S-attributed grammar with an example. [5]
--- An annotated parse tree is a parse tree in which each node is labeled with its grammar symbol along with the values of its associated attributes. In Syntax-Directed Translation (SDT), semantic rules are used to compute attribute values at each node of t...
Full solved answer →Syntax Directed Definition and Annotated Parse Tree
A Syntax-Directed Definition (SDD) is a context-free grammar in which each grammar symbol is associated with a set of attributes, and each production is associated with a set of semantic rules for computing the values of those attributes. - Attributes may b...
Full solved answer →Syntax Directed Definition and Annotated Parse Tree
A Syntax-Directed Definition (SDD) is a context-free grammar in which each grammar symbol is associated with a set of attributes, and each production is associated with a set of semantic rules for computing the values of those attributes. - Attributes may b...
Full solved answer →Finite Automata relevant to compiler construction syntactic specification of languages
List out the tasks performed by Lexical Analyser. Define DFA. Convert the Regular Expression (a+b)∗a(a+b)(a+b)^*a(a+b)(a+b)∗a(a+b) to DFA directly.[10]
- RE to convert (canonical/deduplicated form): $r = (a+b)^\,a\,(a+b)$ - Alphabet: $\Sigma = \{a, b\}$ - Marks: 10 Note: The question string repeats the pattern; the intended standard example is $(a+b)^a(a+b)$. --- 1. Scanning the source program character by...
Full solved answer →Given a regular expression (ε+0)∗10(\varepsilon + 0)^* 10(ε+0)∗10. Construct the DFA recognizing the pattern described by this regular expression using syntax tree based reduction.[6]
Append the end marker : $$(\varepsilon+0)^ \cdot 1 \cdot 0 \cdot (\varepsilon+0)^ \cdot 1 \cdot 0 \cdot \$$ Assign position numbers to terminal leaves ($\varepsilon$ leaves get none): Symbol Position ------------------ $0$ (first star) 1 $1$ (first) 2 $0$ (...
Full solved answer →List out the major tasks carried out in Lexical Analysis Phase. Convert the following NFA to DFA.[6]
Part 1: Conceptual question - list major tasks of the lexical analysis phase. Part 2: "Convert the following NFA to DFA." - Missing data: The actual NFA (state transition diagram or table) is not present in the question text provided. No states, transitions...
Full solved answer →Type Checking and Conversion
Define type checking. Differentiate between type casting and coercion? Write SDT to carry out type checking for the following expression. $E \rightarrow n \mid E * E \mid E == E \mid E[E] \mid E \uparrow$ [10]
--- Type checking is the process performed during semantic analysis where the compiler verifies that each operator in an expression has operands of compatible (matching) types as defined by the language specification. - It ensures that operations are applie...
Full solved answer →Write Syntax Directed Definition to carry out type checking for the following expression.E→id∣E1 op E2∣E1 relop E2∣E1[E2]∣E1↑E \rightarrow id | E1 \text{ op } E2 | E1 \text{ relop } E2 | E1[E2] | E1↑E→id∣E1 op E2∣E1 relop E2∣E1[E2]∣E1↑[6]
Type checking is a key part of semantic analysis. A Syntax-Directed Definition (SDD) associates attributes with grammar symbols and semantic rules with productions. For type checking, each expression E carries a synthesized attribute E.type that is computed...
Full solved answer →Differentiate between static and dynamic type checking. How can we carry out type checking for the following expression using syntax-directed definition?
$S \rightarrow id = E$
$S \rightarrow \text{if } E \text{ then } S1$
$S \rightarrow \text{while } E \text{ do } S1$
$S \rightarrow S1; S2$
[6]
--- Type checking is the process of verifying that each operation in a program receives the correct number and type of operands. Feature Static Type Checking Dynamic Type Checking --------- When performed At compile time At run time Speed Faster execution (...
Full solved answer →Define explicit and implicit type conversion. Why do we need to check type of the system? Justify with an example. [5]
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. ...
Full solved answer →Bottom-up parsing
What are the disadvantages of shift reduce parsing. Perform shift reduce parsing of string w = (x-x). (x/x) for given grammar. E→E−E∣E/E∣(E)∣xE \rightarrow E-E | E/E | (E) | xE→E−E∣E/E∣(E)∣x[5]
Grammar: $$E \rightarrow E - E \mid E / E \mid (E) \mid x$$ Input string: $w = (x-x).(x/x)$ Terminals visible in string: (, ), x, -, /, . Note on missing data: The grammar defines operators - and / only. The string contains a . (dot) operator between the tw...
Full solved answer →What is shift reduce parsing techniques? Show shift reduce parsing action for the string (x+x)*a, given the grammar[6]
- String to parse: (x+x)a - Grammar: Not explicitly printed in the question (the phrase "given the grammar" appears but no production rules follow). The standard expression grammar suitable for this string is assumed and stated explicitly below. This is the...
Full solved answer →Make Unit 2 stick
Practice CSC376 with flashcards & quizzes