📝 CFG Parsing Fundamentals

🎯 What is CFG Parsing?

Context-Free Grammar (CFG) parsing is the process of analyzing a string of tokens to determine its grammatical structure according to a context-free grammar. It is fundamental to compiler design, natural language processing, and formal language theory.

Key concept: A parser takes a sequence of tokens and produces a parse tree that shows how the tokens derive from the grammar's start symbol.

Deep Explanation

CFG parsing is the heart of compiler construction. It bridges the gap between lexical analysis (recognizing tokens) and semantic analysis (understanding meaning).

Why it matters: Parsing is essential for programming languages, query languages, configuration languages, and natural language understanding.

📝 Grammar📊 Parse Tree📋 Tokens🔄 Compilers

# CFG definition
class ContextFreeGrammar:
    def __init__(self):
        self.non_terminals = set()
        self.terminals = set()
        self.productions = {}
        self.start_symbol = None
    
    def add_production(self, lhs, rhs):
        """Add a production rule: lhs -> rhs"""
        if lhs not in self.productions:
            self.productions[lhs] = []
        self.productions[lhs].append(rhs)
        self.non_terminals.add(lhs)
        for symbol in rhs:
            if not symbol.isupper():  # Convention: terminals are lowercase
                self.terminals.add(symbol)
    
    def parse(self, tokens):
        """Parse a sequence of tokens"""
        pass

# Example: Simple arithmetic grammar
# S -> E
# E -> E + T | E - T | T
# T -> T * F | T / F | F
# F -> ( E ) | num

grammar = ContextFreeGrammar()
grammar.start_symbol = 'S'
grammar.add_production('S', ['E'])
grammar.add_production('E', ['E', '+', 'T'])
grammar.add_production('E', ['E', '-', 'T'])
grammar.add_production('E', ['T'])
grammar.add_production('T', ['T', '*', 'F'])
grammar.add_production('T', ['T', '/', 'F'])
grammar.add_production('T', ['F'])
grammar.add_production('F', ['(', 'E', ')'])
grammar.add_production('F', ['num'])

📋 Grammar Types

🎯 Chomsky Hierarchy

The Chomsky hierarchy classifies grammars into four types: Type 0 (Unrestricted), Type 1 (Context-Sensitive), Type 2 (Context-Free), and Type 3 (Regular).

Grammar Classification

Type 0: Unrestricted grammars (Turing machines). Type 1: Context-sensitive grammars (αAβ → αγβ). Type 2: Context-free grammars (A → γ). Type 3: Regular grammars (A → aB or A → a).

CFG: Productions have a single non-terminal on the left side.

📋 Type 0📊 Type 1📋 Type 2🔄 Type 3

# Grammar type classification
class GrammarType:
    @staticmethod
    def is_regular(grammar):
        # Check if grammar is regular (Type 3)
        for lhs, productions in grammar.productions.items():
            for rhs in productions:
                if len(rhs) == 0:
                    continue
                if len(rhs) == 1:
                    if rhs[0] in grammar.terminals:
                        continue
                    else:
                        return False
                elif len(rhs) == 2:
                    if rhs[0] in grammar.terminals and rhs[1] in grammar.non_terminals:
                        continue
                    else:
                        return False
                else:
                    return False
        return True
    
    @staticmethod
    def is_context_free(grammar):
        # Check if grammar is context-free (Type 2)
        for lhs, productions in grammar.productions.items():
            # LHS must be a single non-terminal
            if len(lhs) != 1 or lhs not in grammar.non_terminals:
                return False
        return True
    
    @staticmethod
    def is_context_sensitive(grammar):
        # Check if grammar is context-sensitive (Type 1)
        # Productions must have |α| ≤ |γ| (non-contracting)
        for lhs, productions in grammar.productions.items():
            for rhs in productions:
                if len(rhs) == 0 and lhs != grammar.start_symbol:
                    continue
                # Context-sensitive condition
                if len(rhs) < len(lhs):
                    return False
        return True

🌳 Parse Trees

🎯 Representing Structure

A parse tree (or derivation tree) visually represents the syntactic structure of a string according to a grammar. The root is the start symbol, internal nodes are non-terminals, and leaves are terminals.

Tree Properties

Root: Start symbol. Internal nodes: Non-terminals. Leaves: Terminals (in order). Derivation: Each internal node expands according to a production. Yield: The string of leaves (the parsed input).

Ambiguity: Multiple parse trees for the same string.

🌳 Root📊 Internal📋 Leaves🔄 Derivation

# Parse tree implementation
class ParseTreeNode:
    def __init__(self, symbol, children=None):
        self.symbol = symbol
        self.children = children if children else []
        self.is_leaf = len(self.children) == 0
    
    def add_child(self, child):
        self.children.append(child)
        return self
    
    def get_yield(self):
        """Get the string of leaves"""
        if self.is_leaf:
            return self.symbol
        result = []
        for child in self.children:
            result.append(child.get_yield())
        return ''.join(result)
    
    def __repr__(self):
        if self.is_leaf:
            return self.symbol
        children_str = ', '.join(repr(c) for c in self.children)
        return f"{self.symbol}({children_str})"

# Example: Parse tree for "3 + 5 * 2"
# E -> E + T
# T -> T * F
# F -> num
# num -> 3 | 5 | 2

tree = ParseTreeNode('E')
t1 = ParseTreeNode('T')
f1 = ParseTreeNode('F')
num1 = ParseTreeNode('3')
f1.add_child(num1)
t1.add_child(f1)

tree.add_child(t1)
tree.add_child(ParseTreeNode('+'))
tree.add_child(ParseTreeNode('T'))

# Print tree
print(tree)
print("Yield:", tree.get_yield())

🔝 Top-Down Parsing

🎯 Building from the Root

Top-down parsing starts from the start symbol and expands non-terminals using productions to match the input string. It constructs the parse tree from the root to the leaves.

Top-Down Methods

Algorithm: Start with start symbol, attempt to match tokens. Predictive parsing: Lookahead to choose productions. Recursive descent: Implement each non-terminal as a function. LL(k): Left-to-right scan, leftmost derivation, k tokens lookahead.

Challenges: Left recursion must be eliminated, factoring needed.

🔝 Root📊 Expansion📋 Predictive🔄 Recursive

# Top-down parsing (recursive descent)
class RecursiveDescentParser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.position = 0
        self.current_token = tokens[0] if tokens else None
    
    def advance(self):
        self.position += 1
        if self.position < len(self.tokens):
            self.current_token = self.tokens[self.position]
        else:
            self.current_token = None
    
    def match(self, expected):
        if self.current_token and self.current_token == expected:
            self.advance()
            return True
        return False
    
    def parse_S(self):
        # S -> E
        return self.parse_E()
    
    def parse_E(self):
        # E -> T E'
        return self.parse_T() and self.parse_E_prime()
    
    def parse_E_prime(self):
        # E' -> + T E' | - T E' | ε
        if self.match('+') or self.match('-'):
            return self.parse_T() and self.parse_E_prime()
        return True  # ε
    
    def parse_T(self):
        # T -> F T'
        return self.parse_F() and self.parse_T_prime()
    
    def parse_T_prime(self):
        # T' -> * F T' | / F T' | ε
        if self.match('*') or self.match('/'):
            return self.parse_F() and self.parse_T_prime()
        return True  # ε
    
    def parse_F(self):
        # F -> ( E ) | num
        if self.match('('):
            result = self.parse_E()
            return result and self.match(')')
        elif self.current_token and self.current_token.isdigit():
            self.advance()
            return True
        return False
    
    def parse(self):
        result = self.parse_S()
        return result and self.current_token is None

🔻 Bottom-Up Parsing

🎯 Building from the Leaves

Bottom-up parsing starts from the input tokens and reduces them using productions until the start symbol is reached. It constructs the parse tree from the leaves to the root.

Bottom-Up Methods

Algorithm: Shift tokens onto stack, reduce when production matches. Shift-reduce parsing: Core bottom-up algorithm. LR(k): Left-to-right scan, rightmost derivation, k lookahead. Operator precedence: Uses operator priorities.

Advantages: More powerful than top-down, handles left recursion naturally.

🔻 Leaves📊 Shift-Reduce📋 LR(k)🔄 Stack

# Shift-reduce parser (simplified)
class ShiftReduceParser:
    def __init__(self, grammar, tokens):
        self.grammar = grammar
        self.tokens = tokens
        self.stack = []
        self.position = 0
    
    def shift(self):
        # Shift current token onto stack
        token = self.tokens[self.position]
        self.stack.append(token)
        self.position += 1
    
    def reduce(self):
        # Find production matching top of stack
        for lhs, productions in self.grammar.productions.items():
            for rhs in productions:
                if len(rhs) <= len(self.stack):
                    # Check if stack top matches rhs
                    if self.stack[-len(rhs):] == rhs:
                        # Reduce: replace rhs with lhs
                        self.stack = self.stack[:-len(rhs)]
                        self.stack.append(lhs)
                        return True
        return False
    
    def parse(self):
        self.tokens.append('$')  # End marker
        
        while True:
            # Try to reduce first (if possible)
            reduced = self.reduce()
            
            # If can't reduce, shift
            if not reduced:
                if self.position < len(self.tokens):
                    self.shift()
                else:
                    break
        
        # Check if we reduced to start symbol
        return len(self.stack) == 1 and self.stack[0] == self.grammar.start_symbol

# LR(0) item
class LR0Item:
    def __init__(self, lhs, rhs, dot_position=0):
        self.lhs = lhs
        self.rhs = rhs
        self.dot = dot_position
    
    def next_symbol(self):
        if self.dot < len(self.rhs):
            return self.rhs[self.dot]
        return None
    
    def advance_dot(self):
        return LR0Item(self.lhs, self.rhs, self.dot + 1)
    
    def __eq__(self, other):
        return (self.lhs == other.lhs and 
                self.rhs == other.rhs and 
                self.dot == other.dot)
    
    def __repr__(self):
        before = self.rhs[:self.dot]
        after = self.rhs[self.dot:]
        return f"{self.lhs} -> {' '.join(before)} . {' '.join(after)}"

📊 LL Parsing

🎯 Predictive Top-Down Parsing

LL parsing is a top-down parsing method that uses lookahead to decide which production to apply. LL(1) uses one token of lookahead.

LL Features

LL(1) grammar: Predictive parsing with one token lookahead. Parse table: Maps (non-terminal, token) to production. FIRST and FOLLOW sets: Used to construct the parse table. No left recursion: Must be eliminated.

Advantages: Simple, efficient, easy to implement.

📊 LL(1)📋 FIRST/FOLLOW🔄 Parse Table📈 Predictive

# LL(1) parser implementation
class LL1Parser:
    def __init__(self, grammar):
        self.grammar = grammar
        self.parse_table = {}
        self.build_parse_table()
    
    def compute_first(self, symbol):
        # Compute FIRST set for a symbol
        first = set()
        if symbol in self.grammar.terminals:
            first.add(symbol)
        elif symbol in self.grammar.non_terminals:
            for production in self.grammar.productions.get(symbol, []):
                for sym in production:
                    sym_first = self.compute_first(sym)
                    first.update(sym_first - {'ε'})
                    if 'ε' not in sym_first:
                        break
                else:
                    first.add('ε')
        return first
    
    def compute_follow(self, non_terminal):
        # Compute FOLLOW set for a non-terminal
        follow = set()
        if non_terminal == self.grammar.start_symbol:
            follow.add('$')
        
        for lhs, productions in self.grammar.productions.items():
            for production in productions:
                for i, symbol in enumerate(production):
                    if symbol == non_terminal:
                        # Find rest of production
                        rest = production[i+1:]
                        if rest:
                            # Add FIRST(rest) to FOLLOW
                            for sym in rest:
                                sym_first = self.compute_first(sym)
                                follow.update(sym_first - {'ε'})
                                if 'ε' not in sym_first:
                                    break
                            else:
                                # All of rest can derive ε
                                follow.update(self.compute_follow(lhs))
                        else:
                            # At end of production
                            if lhs != non_terminal:
                                follow.update(self.compute_follow(lhs))
        return follow
    
    def build_parse_table(self):
        # Build LL(1) parse table
        for non_terminal in self.grammar.non_terminals:
            for production in self.grammar.productions.get(non_terminal, []):
                first_set = self.compute_first_set(production)
                for terminal in first_set:
                    if terminal != 'ε':
                        self.parse_table[(non_terminal, terminal)] = production
                if 'ε' in first_set:
                    for terminal in self.compute_follow(non_terminal):
                        self.parse_table[(non_terminal, terminal)] = production
    
    def parse(self, tokens):
        # Parse using LL(1) parse table
        stack = ['$', self.grammar.start_symbol]
        tokens.append('$')
        pos = 0
        
        while stack:
            top = stack[-1]
            token = tokens[pos]
            
            if top in self.grammar.terminals:
                if top == token:
                    stack.pop()
                    pos += 1
                else:
                    return False
            elif top == '$':
                return token == '$'
            else:
                # Non-terminal
                production = self.parse_table.get((top, token))
                if production:
                    stack.pop()
                    # Push right-hand side in reverse order
                    for symbol in reversed(production):
                        if symbol != 'ε':
                            stack.append(symbol)
                else:
                    return False
        return True

📈 LR Parsing

🎯 Powerful Bottom-Up Parsing

LR parsing is the most powerful bottom-up parsing method. It handles all deterministic context-free grammars and is used in many compilers.

LR Types

SLR(1): Simple LR with one lookahead. CLR(1): Canonical LR (most powerful). LALR(1): Lookahead LR (practical compromise). LR(0): No lookahead (limited).

Tools: Yacc, Bison, ANTLR generate LR parsers.

📈 SLR(1)📊 CLR(1)📋 LALR(1)🔄 Yacc/Bison

# LR parser states and actions
class LRItem:
    def __init__(self, lhs, rhs, dot, lookahead=None):
        self.lhs = lhs
        self.rhs = rhs
        self.dot = dot
        self.lookahead = lookahead
    
    def next_symbol(self):
        if self.dot < len(self.rhs):
            return self.rhs[self.dot]
        return None
    
    def advance(self):
        return LRItem(self.lhs, self.rhs, self.dot + 1, self.lookahead)

class LRParser:
    def __init__(self, grammar):
        self.grammar = grammar
        self.states = []
        self.build_states()
        self.build_actions()
    
    def closure(self, items):
        # Compute LR closure
        closure_set = set(items)
        changed = True
        while changed:
            changed = False
            for item in list(closure_set):
                symbol = item.next_symbol()
                if symbol and symbol in self.grammar.non_terminals:
                    for prod in self.grammar.productions.get(symbol, []):
                        new_item = LRItem(symbol, prod, 0, item.lookahead)
                        if new_item not in closure_set:
                            closure_set.add(new_item)
                            changed = True
        return closure_set
    
    def goto(self, state, symbol):
        # Compute GOTO transition
        items = []
        for item in state:
            if item.next_symbol() == symbol:
                items.append(item.advance())
        return self.closure(items)
    
    def build_states(self):
        # Build LR states
        start_prod = [self.grammar.start_symbol + self.grammar.start_symbol]
        start_item = LRItem('S\'', start_prod, 0)
        start_state = self.closure({start_item})
        self.states.append(start_state)
        
        # Build transitions
        transitions = []
        for state in self.states:
            for symbol in self.grammar.terminals | self.grammar.non_terminals:
                next_state = self.goto(state, symbol)
                if next_state and next_state not in self.states:
                    self.states.append(next_state)
    
    def parse(self, tokens):
        # LR parsing (simplified)
        stack = [0]
        tokens.append('$')
        pos = 0
        
        while True:
            state = stack[-1]
            token = tokens[pos]
            
            # Look up action
            action = self.actions.get((state, token))
            if action is None:
                return False
            
            if action[0] == 'shift':
                stack.append(action[1])
                pos += 1
            elif action[0] == 'reduce':
                # Reduce by production
                lhs, rhs = action[1]
                for _ in range(len(rhs)):
                    stack.pop()
                state = stack[-1]
                stack.append(self.goto_state(state, lhs))
            elif action[0] == 'accept':
                return True

🔄 Recursive Descent

🎯 Direct Implementation

Recursive descent is a straightforward top-down parsing technique where each non-terminal is implemented as a function that directly recognizes the grammar.

Recursive Descent Features

Implementation: One function per non-terminal. Prediction: Often requires backtracking or lookahead. Backtracking: Try alternatives, backtrack on failure. Recursive: Naturally handles nested structures.

Advantages: Easy to understand, flexible, good error messages.

🔄 Functions📊 Backtracking📋 Predictive🈶 Nested

# Recursive descent parser with backtracking
class RecursiveDescentParser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.position = 0
        self.saved_positions = []
    
    def save_position(self):
        self.saved_positions.append(self.position)
    
    def restore_position(self):
        self.position = self.saved_positions.pop()
    
    def peek(self):
        if self.position < len(self.tokens):
            return self.tokens[self.position]
        return None
    
    def match(self, expected):
        if self.peek() == expected:
            self.position += 1
            return True
        return False
    
    def parse_S(self):
        # S -> E
        return self.parse_E()
    
    def parse_E(self):
        # E -> T ( + T | - T )*
        self.save_position()
        if self.parse_T():
            while True:
                if self.match('+'):
                    if self.parse_T():
                        continue
                    else:
                        self.restore_position()
                        return False
                elif self.match('-'):
                    if self.parse_T():
                        continue
                    else:
                        self.restore_position()
                        return False
                else:
                    return True
        self.restore_position()
        return False
    
    def parse_T(self):
        # T -> F ( * F | / F )*
        self.save_position()
        if self.parse_F():
            while True:
                if self.match('*'):
                    if self.parse_F():
                        continue
                    else:
                        self.restore_position()
                        return False
                elif self.match('/'):
                    if self.parse_F():
                        continue
                    else:
                        self.restore_position()
                        return False
                else:
                    return True
        self.restore_position()
        return False
    
    def parse_F(self):
        # F -> ( E ) | num
        if self.match('('):
            if self.parse_E() and self.match(')'):
                return True
            return False
        elif self.peek() and self.peek().isdigit():
            self.position += 1
            return True
        return False
    
    def parse(self):
        result = self.parse_S()
        return result and self.position == len(self.tokens)

🧠 Earley Parsing

🎯 General CFG Parsing

The Earley parser is a general-purpose parsing algorithm for any context-free grammar. It runs in O(n³) time and can handle ambiguous and left-recursive grammars.

Earley Features

Chart parser: Maintains sets of states. Items: (production, dot position, origin). Operations: Predict, Scan, Complete. Handles: All CFGs, including ambiguous and left-recursive.

Complexity: O(n³) for ambiguous grammars, O(n²) for unambiguous.

🧠 Chart📊 States📋 Predict/Scan/Complete🔄 O(n³)

# Earley parser implementation
class EarleyParser:
    def __init__(self, grammar):
        self.grammar = grammar
        self.charts = []
    
    def predict(self, state, chart):
        # Predict non-terminal symbols
        next_symbol = state.next_symbol()
        if next_symbol in self.grammar.non_terminals:
            for production in self.grammar.productions.get(next_symbol, []):
                new_state = EarleyState(next_symbol, production, 0, state.origin)
                if new_state not in chart:
                    chart.append(new_state)
    
    def scan(self, state, token):
        # Scan terminal symbols
        next_symbol = state.next_symbol()
        if next_symbol == token:
            return EarleyState(state.lhs, state.rhs, state.dot + 1, state.origin)
        return None
    
    def complete(self, state, chart_index):
        # Complete a non-terminal
        for chart in self.charts[state.origin:]:
            for prev_state in chart:
                if prev_state.next_symbol() == state.lhs:
                    if prev_state.dot < len(prev_state.rhs):
                        new_state = EarleyState(prev_state.lhs, prev_state.rhs, prev_state.dot + 1, prev_state.origin)
                        if new_state not in self.charts[chart_index]:
                            self.charts[chart_index].append(new_state)
    
    def parse(self, tokens):
        # Initialize chart
        self.charts = [[] for _ in range(len(tokens) + 1)]
        
        # Add start state
        start_state = EarleyState(self.grammar.start_symbol, self.grammar.productions[self.grammar.start_symbol][0], 0, 0)
        self.charts[0].append(start_state)
        
        # Process tokens
        for i in range(len(tokens) + 1):
            chart = self.charts[i]
            for j, state in enumerate(chart):
                # Predict phase
                self.predict(state, chart)
                
                # Scan phase
                if i < len(tokens):
                    scanned = self.scan(state, tokens[i])
                    if scanned and scanned not in self.charts[i + 1]:
                        self.charts[i + 1].append(scanned)
                
                # Complete phase
                if state.dot == len(state.rhs):
                    self.complete(state, i)
        
        # Check if start symbol is complete
        for state in self.charts[-1]:
            if state.lhs == self.grammar.start_symbol and state.dot == len(state.rhs) and state.origin == 0:
                return True
        return False

class EarleyState:
    def __init__(self, lhs, rhs, dot, origin):
        self.lhs = lhs
        self.rhs = rhs
        self.dot = dot
        self.origin = origin
    
    def next_symbol(self):
        if self.dot < len(self.rhs):
            return self.rhs[self.dot]
        return None
    
    def __eq__(self, other):
        return (self.lhs == other.lhs and 
                self.rhs == other.rhs and 
                self.dot == other.dot and 
                self.origin == other.origin)

📐 CYK Algorithm

🎯 Dynamic Programming Parsing

The CYK algorithm (Cocke-Younger-Kasami) is a dynamic programming algorithm for parsing Chomsky Normal Form (CNF) grammars in O(n³) time.

CYK Features

CNF required: Productions must be A → BC or A → a. Dynamic programming: Table of substrings. Cell: Set of non-terminals deriving substring. Building: Combine adjacent substrings.

Applications: Grammar analysis, RNA folding (with modifications).

📐 CNF📊 DP Table📋 O(n³)🔄 Substrings

# CYK algorithm implementation
def convert_to_cnf(grammar):
    # Convert grammar to Chomsky Normal Form
    # (Simplified - assumes grammar is already close to CNF)
    cnf_grammar = {'productions': {}, 'terminals': set(), 'non_terminals': set()}
    
    for lhs, productions in grammar.productions.items():
        for rhs in productions:
            if len(rhs) == 1 and rhs[0] in grammar.terminals:
                # Terminal production: A -> a (already CNF)
                if lhs not in cnf_grammar['productions']:
                    cnf_grammar['productions'][lhs] = []
                cnf_grammar['productions'][lhs].append(rhs)
            elif len(rhs) == 2 and rhs[0] in grammar.non_terminals and rhs[1] in grammar.non_terminals:
                # Non-terminal production: A -> BC (already CNF)
                if lhs not in cnf_grammar['productions']:
                    cnf_grammar['productions'][lhs] = []
                cnf_grammar['productions'][lhs].append(rhs)
            else:
                # Need conversion (simplified - just pass through)
                pass
    
    return cnf_grammar

def cyk_parse(grammar, tokens):
    # Convert grammar to CNF
    cnf_grammar = convert_to_cnf(grammar)
    
    n = len(tokens)
    # DP table: table[i][j] = set of non-terminals deriving tokens[i:j]
    table = [[set() for _ in range(n + 1)] for _ in range(n + 1)]
    
    # Fill length 1 substrings (terminal productions)
    for i, token in enumerate(tokens):
        for lhs, productions in cnf_grammar['productions'].items():
            for rhs in productions:
                if len(rhs) == 1 and rhs[0] == token:
                    table[i][i + 1].add(lhs)
    
    # Fill longer substrings
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length
            for k in range(i + 1, j):
                # Combine substrings table[i][k] and table[k][j]
                for lhs, productions in cnf_grammar['productions'].items():
                    for rhs in productions:
                        if len(rhs) == 2:
                            B, C = rhs
                            if B in table[i][k] and C in table[k][j]:
                                table[i][j].add(lhs)
    
    # Check if start symbol is in table[0][n]
    return grammar.start_symbol in table[0][n]

# Example usage
grammar = {
    'productions': {
        'S': [['NP', 'VP']],
        'NP': [['Det', 'N']],
        'VP': [['V', 'NP']],
        'Det': [['the'], ['a']],
        'N': [['cat'], ['dog'], ['mat']],
        'V': [['chased'], ['sat']]
    },
    'terminals': {'the', 'a', 'cat', 'dog', 'mat', 'chased', 'sat'},
    'non_terminals': {'S', 'NP', 'VP', 'Det', 'N', 'V'},
    'start_symbol': 'S'
}

result = cyk_parse(grammar, ['the', 'cat', 'chased', 'a', 'dog'])
print("Parsed:", result)

🔀 Ambiguity

🎯 Multiple Parse Trees

A grammar is ambiguous if a string can be derived in multiple ways (multiple parse trees). Ambiguity must be resolved for reliable parsing.

Handling Ambiguity

Causes: Left recursion, multiple productions, precedence issues. Resolutions: Modify grammar, use precedence rules, choose one derivation. Classic example: "I saw the man with the telescope" has multiple interpretations.

Applications: Natural language processing, programming language design.

🔀 Multiple📊 Precedence📋 Resolution🔄 NLP

# Detecting and resolving ambiguity
class AmbiguityDetector:
    def __init__(self, grammar):
        self.grammar = grammar
        self.ambiguous_grammars = set()
    
    def is_ambiguous(self, string, max_parse=3):
        # Count parse trees for a string
        count = self.count_parses(string, max_parse)
        return count > 1
    
    def count_parses(self, string, max_count=3):
        # Count number of parse trees (simplified)
        trees = self.parse_all(string, max_count)
        return len(trees)
    
    def parse_all(self, string, max_count):
        # Generate all parse trees (simplified)
        trees = []
        # Implementation uses Earley or similar to find all parses
        return trees

# Resolve ambiguity with precedence
class PrecedenceResolver:
    def __init__(self, precedence):
        self.precedence = precedence  # {'+': 1, '*': 2}
    
    def resolve_ambiguity(self, parse_trees):
        # Choose parse tree based on precedence
        if not parse_trees:
            return None
        
        # Evaluate each tree based on precedence rules
        best_tree = None
        best_score = -1
        
        for tree in parse_trees:
            score = self.evaluate_tree(tree)
            if score > best_score:
                best_score = score
                best_tree = tree
        
        return best_tree
    
    def evaluate_tree(self, tree):
        # Score tree based on operator precedence
        score = 0
        # Implementation would traverse tree
        return score

# Example: Dangling else ambiguity
# Grammar:
# S -> if E then S | if E then S else S | other
# This is ambiguous for "if a then if b then c else d"
# Resolution: "else" binds to nearest "if"

🛡️ Error Handling

🎯 Dealing with Invalid Input

Error handling in parsing deals with syntax errors in the input. It involves detection, reporting, and recovery.

Error Recovery Strategies

Error detection: Identify when input doesn't match grammar. Panic mode: Skip tokens until a synchronization point. Phrase-level recovery: Replace erroneous tokens. Error productions: Add error productions to grammar.

Reporting: Provide helpful error messages with location.

🛡️ Detection📊 Recovery📋 Reporting🔄 Panic Mode

# Error handling in parsers
class ErrorRecoveryParser:
    def __init__(self, grammar):
        self.grammar = grammar
        self.errors = []
        self.sync_set = {';', '}', ')'}
    
    def error(self, message, token, position):
        self.errors.append({
            'message': message,
            'token': token,
            'position': position
        })
    
    def panic_mode(self, tokens, position):
        # Skip tokens until synchronization point
        while position < len(tokens):
            if tokens[position] in self.sync_set:
                return position
            position += 1
        return position
    
    def phrase_level_recovery(self, expected, token):
        # Try to fix common errors
        if token == ';' and expected == ',':
            self.error("Expected ',' found ';'", token, 0)
            return True
        return False
    
    def parse_with_recovery(self, tokens):
        pos = 0
        while pos < len(tokens):
            try:
                self.parse_tokens(tokens, pos)
                break
            except SyntaxError as e:
                self.error(str(e), tokens[pos], pos)
                pos = self.panic_mode(tokens, pos + 1)
        return self.errors

# Error reporting
class ErrorReporter:
    @staticmethod
    def format_error(error, source_line):
        message = error['message']
        token = error['token']
        position = error['position']
        
        line = source_line.split('\n')[position]
        pointer = ' ' * len(line) + '^'
        
        return f"Error at position {position}:\n{line}\n{pointer}\n{message}"

# Example error handlers
def report_syntax_error(line, pos, expected, found):
    return f"""Syntax Error:
    {line}
    {' ' * pos}^
    Expected '{expected}', found '{found}'"""

💼 Applications

🎯 Where Parsing is Used

CFG parsing is fundamental to compilers, interpreters, natural language processing, and data format processing.

Application Domains

Compilers: Parsing source code. Interpreters: Evaluating expressions. NLP: Parsing natural language sentences. Data formats: JSON, XML, CSV parsing. Query languages: SQL, GraphQL parsing.

Tools: ANTLR, Yacc, Bison, XText.

💻 Compilers📊 NLP📋 Data Formats🔄 Query Languages

# Application: SQL parser (simplified)
class SQLParser:
    def __init__(self):
        self.grammar = self.build_sql_grammar()
        self.parser = RecursiveDescentParser(None)  # Simplified
    
    def build_sql_grammar(self):
        # Simplified SQL grammar
        return {
            'query': [['SELECT', 'columns', 'FROM', 'table', 'where_clause']],
            'columns': [['*'], ['column_list']],
            'column_list': [['column', 'rest_columns']],
            'rest_columns': [['', ',' 'column', 'rest_columns']],
            'table': [['identifier']],
            'where_clause': [[''], ['WHERE', 'condition']],
            'condition': [['identifier', 'op', 'value']],
            'op': [['='], ['>'], ['<'], ['!=']]
        }
    
    def parse_sql(self, query):
        tokens = self.tokenize(query)
        return self.parser.parse(tokens)

# Application: JSON parser
class JSONParser:
    def parse(self, json_string):
        self.tokens = self.tokenize(json_string)
        self.position = 0
        return self.parse_value()
    
    def parse_value(self):
        token = self.peek()
        if token == '{':
            return self.parse_object()
        elif token == '[':
            return self.parse_array()
        elif token.isdigit():
            return self.parse_number()
        elif token == 'true' or token == 'false':
            return self.parse_boolean()
        elif token == 'null':
            return self.parse_null()
        elif token.startswith('"'):
            return self.parse_string()
    
    def parse_object(self):
        obj = {}
        self.expect('{')
        if self.peek() != '}':
            while True:
                key = self.parse_string()
                self.expect(':')
                value = self.parse_value()
                obj[key] = value
                if self.peek() != ',':
                    break
                self.expect(',')
        self.expect('}')
        return obj
    
    def parse_array(self):
        arr = []
        self.expect('[')
        if self.peek() != ']':
            while True:
                arr.append(self.parse_value())
                if self.peek() != ',':
                    break
                self.expect(',')
        self.expect(']')
        return arr

# Application: Natural language parser
class NLPParser:
    def __init__(self, grammar):
        self.parser = EarleyParser(grammar)
    
    def parse_sentence(self, words):
        return self.parser.parse(words)
    
    def get_parse_tree(self, words):
        # Build parse tree from parsing result
        pass

🚀 Future Directions

🎯 The Future of Parsing

Parsing continues to evolve with neural parsing, incremental parsing, and integration with machine learning.

Emerging Trends

Neural parsing: Using neural networks for parsing. Incremental parsing: Parse partial input in real-time. Grammar learning: Automatically learn grammars. Fuzzy parsing: Handle imperfect input. Interactive parsing: Real-time feedback.

Applications: Code completion, auto-correction, natural language interfaces.

🚀 Neural📊 Incremental📋 Grammar Learning🔄 Fuzzy

# Future: Neural parser
import torch
import torch.nn as nn

class NeuralParser(nn.Module):
    def __init__(self, vocab_size, hidden_size, num_layers=2):
        super().__init__()
        self.embedding = nn.Embedding(vocab_size, hidden_size)
        self.lstm = nn.LSTM(hidden_size, hidden_size, num_layers, bidirectional=True)
        self.classifier = nn.Linear(hidden_size * 2, vocab_size)
    
    def forward(self, tokens):
        embedded = self.embedding(tokens)
        output, _ = self.lstm(embedded)
        return self.classifier(output)
    
    def parse(self, tokens):
        # Neural parsing
        with torch.no_grad():
            logits = self.forward(tokens)
            predictions = torch.argmax(logits, dim=-1)
        return predictions

# Future: Incremental parser
class IncrementalParser:
    def __init__(self, grammar):
        self.grammar = grammar
        self.state = None
        self.partial_tree = None
    
    def process_token(self, token):
        # Update parse state with new token
        self.state = self.update_state(self.state, token)
        self.partial_tree = self.build_partial_tree(self.state)
        return self.partial_tree
    
    def get_completions(self):
        # Suggest possible completions
        return self.state.get_possible_tokens()

# Future: Grammar learning
class GrammarLearner:
    def __init__(self, corpus):
        self.corpus = corpus
        self.grammar = None
    
    def learn(self):
        # Learn grammar from examples
        # Uses algorithms like SEQUITUR or ADIOS
        pass

# Future: Interactive parser (IDE-style)
class InteractiveParser:
    def __init__(self, grammar):
        self.grammar = grammar
        self.parser = EarleyParser(grammar)
    
    def parse_async(self, text, callback):
        # Parse text as it's typed
        # Provide real-time feedback
        for i in range(len(text)):
            partial = text[:i+1]
            result = self.parser.parse(partial)
            callback(i, partial, result)