CD Notes
HubApplications of Compiler DesignCompiler vs Interpreter — Compiler DesignLanguage ProcessorsPhases of a CompilerWhat is Compiler Design?The AssemblerCompiler OverviewComplete Compilation ProcessThe LinkerThe LoaderThe PreprocessorFinite Automata in Lexical AnalysisIntroduction to Lexical AnalysisLex Tool - Lexical Analyzer GeneratorLexemes in Compiler DesignLexical Analyzer DesignLexical Errors and Error RecoveryPatterns in Lexical AnalysisRegular Expressions in Compiler DesignTokens in Compiler DesignAmbiguity in Grammars for Compiler DesignBottom-Up Parsing in Compiler DesignCLR Parser: Canonical LR(1) Parsing with Complete Lookahead InformationContext-Free Grammars for Syntax AnalysisDerivations in Syntax AnalysisIntroduction to Parsing in Compiler DesignLALR Parser: Practical LR(1) With State Merging for EfficiencyLL(1) Parser: Single Lookahead Predictive Parsing from First PrinciplesLR Parsers: Canonical LR Parsing for Complex Language SyntaxParse Trees in Compiler DesignPredictive Parsers: Lookahead-Guided Top-Down ParsingRecursive Descent Parsers: Procedural Approach to Top-Down ParsingShift-Reduce Parsing: Fundamental Mechanism of Bottom-Up Syntax AnalysisSLR Parser: Simple LR Parsing with Efficient AutomataTop-Down Parsing Techniques in Compiler DesignScope Management: Symbol Table Design for Language ImplementationSemantic Analysis IntroductionSemantic Errors: Detection and Reporting in Compiler ConstructionSemantic Rules: Defining Language Semantics in Compiler ConstructionSymbol Table: Core Data Structure for Semantic Analysis and Code GenerationType Checking: Static Analysis for Type Safety in Compiler DesignType Conversion and Coercion in Compiler Semantic AnalysisAttribute Grammars: Foundation of Semantic Analysis and Code GenerationDependency Graphs: Visualizing Attribute Computation Order in Semantic AnalysisInherited Attributes: Top-Down Attribute Computation for Context TransferSyntax-Directed Definitions: Attribute Grammars for Semantic AnalysisSyntax-Directed Translation Schemes: Execution Semantics and Code GenerationSynthesized Attributes: Bottom-Up Attribute Computation in Compiler DesignDirected Acyclic Graphs (DAGs) in Compiler DesignIndirect Triples in Compiler DesignIntroduction to Intermediate Code GenerationQuadruples Representation in Compiler DesignSyntax Trees as Intermediate RepresentationThree-Address Code in Compiler DesignTriples Representation in Compiler DesignActivation Records: Function Call ManagementHeap Allocation: Dynamic Memory ManagementMemory Management: Strategies and OptimizationParameter Passing: Communication Between FunctionsRuntime Environment: Program Execution ContextStack Allocation: Automatic Memory ManagementStorage Organization: Memory Sections and LayoutIntroduction to Code Generation in Compiler DesignCode Generator Design in Compiler ConstructionInstruction Selection in Code GenerationMachine Code Generation in CompilersRegister Allocation in Compiler DesignRegister Assignment Strategies in Code GenerationTarget Machine Architecture for Code GenerationIntroduction to Code Optimization in Compiler DesignCommon Subexpression Elimination (CSE) in Compiler OptimizationConstant Folding Optimization in Compiler DesignConstant Propagation in Compiler OptimizationDead Code Elimination in Compiler OptimizationGlobal Optimization Techniques in Compiler DesignLocal Optimization Techniques in Compiler DesignLoop Optimization Techniques in Compiler DesignPeephole Optimization in Compiler DesignBison: LALR Parser GeneratorFlex: Lexical Analyzer GeneratorLex: Original Lexical AnalyzerParser Generator WorkflowPractical Parser ProjectsYACC: Original Parser GeneratorBytecode and Virtual MachinesGCC ArchitectureJava Compiler and BytecodeJust-In-Time CompilationLLVM: The Low-Level Virtual MachinePython Interpreter ArchitectureWebAssembly BasicsCalculator Compiler ProjectExpression Parser ProjectLexical Analyzer ProjectMini Programming Language ProjectSyntax Checker ProjectToy Compiler Project: Minimal Complete CompilerCompiler Design CheatsheetCompiler Design Interview QuestionsGATE Compiler Design QuestionsLexical Analysis Interview QuestionsParsing Interview QuestionsGlossary of Compiler Design TermsImportant Formulas and RulesQuick Revision Notes for ExamsRecommended Books and Resources — Compiler DesignContext-Free Languages in Compiler DesignDeterministic Finite Automata (DFA) in Compiler DesignFinite Automata Review for Compiler DesignNondeterministic Finite Automata (NFA) in Compiler DesignPushdown Automata (PDA) in Compiler DesignRegular Languages in Compiler DesignTuring Machines and Their Role in Compiler Theory
Deep exploration of shift-reduce parsing: stack operations, reduction strategies, action tables, conflict types and resolution, relationship to LR parsing, practical implementations with complete examples.
Core Concept
Shift-reduce parsing is a bottom-up parsing technique using a stack and an input buffer. The parser repeatedly shifts symbols onto the stack or reduces them according to grammar productions.
Two Operations
Example
1. SHIFT: Take next input symbol, push onto stack
2. REDUCE: Pop grammar symbols from stack, push non-terminal
Parsing Algorithm
Basic Shift-Reduce Algorithm
Example
Stack = [$ ] // Input marker
Input = tokens + $
lookahead = first_token
while true:
if shift_or_reduce_decision(Stack, lookahead) == SHIFT:
Stack.push(lookahead)
lookahead = next_token()
elif shift_or_reduce_decision() == REDUCE:
production = get_production_to_reduce(Stack)
if production is S':
return ACCEPT
else:
pop_production_from_stack(production)
Stack.push(production.lhs)
else:
return ERROR
Shift vs Reduce Decisions
When to Shift
Conditions
1. No complete phrase on stack matching production RHS
2. More input needed to form phrase
3. Lookahead suggests continuing
Example
Stack: [E]
Input: + T
Lookahead: +
Might match: E → E + T (need to shift +)
Decision: SHIFT
When to Reduce
Conditions
1. Stack top matches RHS of some production
2. Lookahead confirms reduction is appropriate
3. No ambiguity with shift
Example
Stack: [id]
Input: +
Lookahead: +
Match: F → id
Decision: REDUCE
Shift-Reduce Example
Expression Parsing: 2 + 3
| E | E + T | T |
| T | num |
| [$, 2] + 3 $ reduce T | 2 |
| [$, T] + 3 $ reduce E | T |
| [$, E, +, 3] $ reduce T | 3 |
| [$, E, +, T] $ reduce E | E + T |
Conflict Resolution
Shift-Reduce Conflicts
| Problem | Both shift and reduce valid on same lookahead |
| Stack | [E] |
| Input | + T |
| Lookahead | + |
| Shift | Continue parsing E + ... |
| Reduce | Reduce E immediately |
| 1. Operator precedence | * higher than + |
| 2. Associativity | All left-associative |
Reduce-Reduce Conflicts
| Problem | Multiple productions could reduce same symbols |
| Stack | [id] |
| Input | , |
| Lookahead | , |
| Reduce by: A | id |
| Reduce by: B | id |
Parsing Table Construction
Action Table
| - shift s | Push terminal, go to state s |
| - reduce p | Reduce by production p |
| - accept | Successful parse |
| - error | Syntax error |
Example Shift-Reduce Table
State │ ID │ + │ * │ $
───────┼──────┼──────┼──────┼──────
0 │ s1 │ │ │
1 │ s2 │ r3 │ s3 │ r3
2 │ │ r1 │ r1 │ r1
3 │ s1 │ │ │
Practical Implementation
Pseudocode: Shift-Reduce Parser
Example
def shift_reduce_parse(tokens):
stack = []
token_index = 0
while True:
token = tokens[token_index]
state = get_current_state(stack)
action = ACTION[state, token]
if action == "accept":
return build_result(stack)
elif action.startswith("shift"):
stack.append(token)
token_index += 1
elif action.startswith("reduce"):
production = get_production(action)
# Pop RHS of production from stack
for _ in range(len(production.rhs)):
stack.pop()
# Push LHS non-terminal
stack.append(production.lhs)
else:
raise SyntaxError(f"State {state}, token {token}")
Relationship to LR Parsing
Shift-Reduce = LR Parsing Basis
Example
LR(k) parsing implements shift-reduce via:
1. Deterministic finite automaton (DFA) for states
2. Parsing tables (ACTION and GOTO)
3. Lookahead to resolve conflicts
LR parsers = Automated shift-reduce
LR(0) vs LR(1) Shift-Reduce
LR(0)
Uses only stack contents for decisions
Limited conflict resolution
Fewer states
LR(1)
Uses lookahead token
Resolves most conflicts
More states
Both use same shift-reduce mechanism
Error Recovery
Simple Error Recovery
Example
def shift_reduce_with_recovery(tokens):
stack = []
errors = []
for token in tokens:
try:
action = ACTION[current_state, token]
if action == "error":
# Synchronize to known state
while stack and no_valid_action(stack):
stack.pop()
errors.append(f"Error at {token}")
except:
pass # Skip token and continue
return (result, errors)
Advantages and Disadvantages
Advantages ✓
Example
1. Natural for bottom-up parsing
2. Handles left recursion naturally
3. Intuitive error handling
4. Efficient implementation
5. Basis for most practical parsers
Disadvantages ✗
Example
1. Shift-reduce conflicts (must resolve)
2. Reduce-reduce conflicts (indicate ambiguity)
3. Requires lookahead and tables
4. Not as intuitive as top-down
Quick Revision Notes
- Shift: Push lookahead onto stack, advance input
- Reduce: Pop RHS from stack, push LHS non-terminal
- Conflict resolution: Precedence/associativity for shift-reduce
- LR(0): Minimal information (no lookahead)
- LR(1): Full lookahead (powerful, larger tables)
- Automatic: Compiler-compiler generates tables
- Stack-based: Implicit call stack for recursion
Interview Q&A
Q1: What causes shift-reduce conflicts?
A: Ambiguity in the grammar when both actions (shift and reduce) are grammatically valid. Example: dangling-else problem. Resolved using operator precedence and associativity declarations.
Q2: How do you decide what production to reduce by?
A: The parser matches stack contents against grammar productions. When stack top matches a production's RHS and lookahead confirms it's safe to reduce (won't prevent valid parses), reduce by that production.
Q3: Why can't you completely eliminate shift-reduce conflicts?
A: Some shift-reduce conflicts represent genuinely ambiguous grammar or language design choices (like operator precedence). They must be resolved by declaring precedence/associativity to disambiguate.
Q4: How does lookahead help resolve conflicts?
A: Lookahead tells you what comes next. If lookahead suggests the current phrase is complete, reduce. If it suggests continuing, shift. This helps distinguish similar parse states.
Q5: What's the difference between shift-reduce and reduce-reduce conflicts?
A: Shift-reduce: shift vs reduce (often resolvable with precedence). Reduce-reduce: multiple reductions possible (usually indicates grammar ambiguity, must fix grammar).
Q6: Why are LR parsers preferred over shift-reduce by hand?
A: Hand-coded shift-reduce requires manually managing stack and making complex decisions. LR parser generators automate this: compute tables, generate code, handle conflicts systematically. Less error-prone and more maintainable.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Shift-Reduce Parsing: Fundamental Mechanism of Bottom-Up Syntax Analysis.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.
Search Terms
compiler-design, compiler design, compiler, design, syntax, analysis, shift, reduce
Related Compiler Design Topics
Continue learning this concept
Syntax AnalysisCLR Parser: Canonical LR(1) Parsing with Complete Lookahead InformationComprehensive exploration of CLR parser construction: complete item sets, lookahead propagation algorithms, full DFA generation, parsing tables, comparison with SLR/LALR, practical compiler implementation.Syntax AnalysisLALR Parser: Practical LR(1) With State Merging for EfficiencyMaster LALR parsing: state merging techniques, lookahead merge rules, DFA construction, parsing table generation, conflict detection, comparison with SLR/CLR, industry standard compiler implementation.Syntax AnalysisLL(1) Parser: Single Lookahead Predictive Parsing from First PrinciplesMaster LL(1) parsing: grammar conversion to LL(1) form, FIRST/FOLLOW computation, parsing table construction, parse decisions, error recovery, practical recursive descent implementation with examples.Syntax AnalysisLR Parsers: Canonical LR Parsing for Complex Language SyntaxComplete guide to LR(1) parsers: item sets, lookahead computation, DFA construction, parsing table generation, shift-reduce decisions, conflict resolution, and modern compiler toolchain applications.Syntax AnalysisPredictive Parsers: Lookahead-Guided Top-Down ParsingComprehensive guide to predictive parsing techniques using lookahead tokens, FIRST and FOLLOW sets, parsing tables, and practical implementations with detailed examples and parse tree diagrams.Syntax AnalysisRecursive Descent Parsers: Procedural Approach to Top-Down ParsingMaster recursive descent parsing: grammar transformation, procedure generation, backtracking mechanisms, error recovery, implementation patterns, and practical compiler design with ASCII automata diagrams.