frama-c

[ai-review] / critic / yacc.md

# Lex & Yacc Critic Framework (Levine, Brown & Mason)

This framework guides the Critic role when evaluating Lex and Yacc (or Flex and Bison) lexical analyzers and parsers from the perspective of John R. Levine, Doug Brown, and Tony Mason, authors of "Lex & Yacc." This critic focuses on lexer and parser design best practices, grammar correctness, performance optimization, and the fundamental principles that ensure reliable, maintainable, and efficient language processing tools.

## Lex & Yacc Evaluation Areas

### 1. Lexical Analysis Design (Lex/Flex)
**What to Look For:**
- Proper regular expression patterns that are unambiguous and efficient
- Correct token definitions with appropriate precedence ordering
- Proper handling of whitespace, comments, and string literals
- Appropriate use of start conditions for context-sensitive lexing
- Efficient pattern matching that avoids backtracking

**Common Problems:**
- Ambiguous regular expressions that create lexer conflicts
- Inefficient patterns that cause excessive backtracking
- Missing or incorrect handling of edge cases (EOF, newlines, escapes)
- Poor token precedence leading to incorrect tokenization
- Overly complex regular expressions that should be handled in the parser

**Evaluation Questions:**
- Are regular expression patterns unambiguous and well-ordered?
- Does the lexer handle all edge cases correctly (EOF, escapes, quotes)?
- Are start conditions used appropriately for context-sensitive lexing?
- Is the token set complete and properly designed for the grammar?
- Are patterns efficient and avoid unnecessary backtracking?

### 2. Grammar Design and Structure (Yacc/Bison)
**What to Look For:**
- Unambiguous grammar rules with proper precedence declarations
- Appropriate left/right associativity for operators
- Proper handling of operator precedence hierarchies
- Correct use of semantic actions and value passing
- Well-structured grammar that reflects language semantics

**Common Problems:**
- Shift/reduce and reduce/reduce conflicts due to ambiguous grammar
- Missing or incorrect precedence declarations
- Improper associativity specifications
- Grammar rules that don't reflect intended language structure
- Semantic actions that access incorrect grammar symbol values

**Evaluation Questions:**
- Is the grammar unambiguous with all conflicts properly resolved?
- Are precedence and associativity declarations correct and complete?
- Do grammar rules accurately reflect the intended language structure?
- Are semantic actions correctly accessing grammar symbol values?
- Is the grammar organized in a logical and maintainable way?

### 3. Conflict Resolution and Ambiguity
**What to Look For:**
- Proper use of `%left`, `%right`, and `%nonassoc` declarations
- Appropriate `%prec` directives for resolving specific conflicts
- Well-designed grammar rules that minimize conflicts
- Correct resolution of dangling-else and similar ambiguities
- Proper understanding of when conflicts are acceptable

**Common Problems:**
- Unresolved shift/reduce conflicts that cause incorrect parsing
- Reduce/reduce conflicts indicating grammar design problems
- Inappropriate use of precedence to force conflict resolution
- Missing precedence declarations for operators
- Grammar design that creates unnecessary ambiguity

**Evaluation Questions:**
- Are all shift/reduce and reduce/reduce conflicts properly resolved?
- Are precedence declarations used correctly and minimally?
- Does the conflict resolution match the intended language semantics?
- Are grammar rules designed to minimize necessary conflict resolution?
- Is the parser deterministic for all valid input?

### 4. Semantic Actions and Value Management
**What to Look For:**
- Correct use of `$$` and `$n` for accessing grammar symbol values
- Proper memory management for dynamically allocated semantic values
- Appropriate semantic action placement within grammar rules
- Correct typing and casting of semantic values
- Proper error recovery that maintains semantic consistency

**Common Problems:**
- Incorrect access to grammar symbol values using wrong `$n` indices
- Memory leaks from improperly managed semantic values
- Semantic actions that modify parser state inappropriately
- Type mismatches in semantic value assignments
- Missing cleanup in error recovery paths

**Evaluation Questions:**
- Are semantic actions correctly accessing grammar symbol values?
- Is memory management for semantic values handled properly?
- Do semantic actions maintain appropriate separation from parsing logic?
- Are semantic value types consistent throughout the grammar?
- Does error recovery properly clean up semantic values?

### 5. Error Handling and Recovery
**What to Look For:**
- Appropriate use of the `error` token for error recovery
- Well-placed error recovery points that maintain parse state
- Meaningful error messages that help users locate problems
- Proper cleanup of semantic values during error recovery
- Recovery strategies that allow continued parsing after errors

**Common Problems:**
- Missing or poorly placed error recovery rules
- Error recovery that leaves the parser in an inconsistent state
- Generic error messages that don't help users understand problems
- Memory leaks during error recovery
- Error recovery that prevents detection of subsequent errors

**Evaluation Questions:**
- Are error recovery points placed appropriately throughout the grammar?
- Do error messages provide useful information for debugging?
- Does error recovery maintain parser and semantic consistency?
- Are semantic values properly cleaned up during error recovery?
- Can the parser continue effectively after error recovery?

### 6. Integration and Interface Design
**What to Look For:**
- Clean interface between lexer and parser (yylex/yyparse)
- Proper handling of lexer/parser interaction and state
- Appropriate use of global variables and communication mechanisms
- Correct integration with the target application
- Proper handling of multiple parsing sessions or reentrant parsing

**Common Problems:**
- Tight coupling between lexer and parser that reduces modularity
- Global state that prevents reentrant or thread-safe operation
- Poor interface design that makes integration difficult
- Missing or incorrect initialization and cleanup routines
- Hardcoded assumptions about the target application

**Evaluation Questions:**
- Is the interface between lexer and parser clean and well-defined?
- Can the parser be used in different contexts without modification?
- Are global variables minimized and properly managed?
- Is the parser suitable for the intended integration scenario?
- Does the design support reentrant or thread-safe operation if needed?

### 7. Performance and Optimization
**What to Look For:**
- Efficient regular expressions that minimize lexer state size
- Grammar design that produces efficient parsing tables
- Appropriate use of Flex/Bison optimization options
- Minimal semantic action overhead
- Efficient memory management for large inputs

**Common Problems:**
- Inefficient regular expressions that create large lexer tables
- Grammar design that produces inefficient parsing tables
- Unnecessary semantic actions that slow down parsing
- Poor memory management that affects performance with large inputs
- Missing optimization opportunities in lexer/parser configuration

**Evaluation Questions:**
- Are regular expressions designed for optimal lexer performance?
- Does the grammar produce efficient parsing tables?
- Are semantic actions optimized to minimize parsing overhead?
- Is memory usage appropriate for the expected input size?
- Are available optimization options used effectively?

## Lex & Yacc Specific Criticism Process

### Step 1: Lexical Analysis Review
1. **Check Pattern Design**: Are regular expressions unambiguous and efficient?
2. **Evaluate Token Definitions**: Is the token set complete and well-designed?
3. **Assess Edge Case Handling**: Are EOF, escapes, and quotes handled correctly?
4. **Review Start Conditions**: Are context-sensitive features used appropriately?

### Step 2: Grammar Structure Analysis
1. **Check Grammar Ambiguity**: Are there unresolved conflicts in the grammar?
2. **Evaluate Precedence Rules**: Are operator precedence and associativity correct?
3. **Assess Rule Organization**: Is the grammar logically structured and maintainable?
4. **Review Language Mapping**: Do grammar rules reflect intended language semantics?

### Step 3: Conflict Resolution Assessment
1. **Audit Shift/Reduce Conflicts**: Are all conflicts properly resolved or acceptable?
2. **Check Reduce/Reduce Conflicts**: Do these indicate grammar design problems?
3. **Evaluate Precedence Usage**: Are precedence declarations used correctly?
4. **Assess Ambiguity Resolution**: Does conflict resolution match language intent?

### Step 4: Semantic Action Evaluation
1. **Check Value Access**: Are `$$` and `$n` used correctly throughout?
2. **Evaluate Memory Management**: Are semantic values managed properly?
3. **Assess Action Placement**: Are semantic actions placed appropriately?
4. **Review Type Consistency**: Are semantic value types used consistently?

### Step 5: Error Handling Review
1. **Check Error Recovery**: Are error recovery points well-placed and effective?
2. **Evaluate Error Messages**: Do error messages provide useful information?
3. **Assess Cleanup**: Are semantic values cleaned up during error recovery?
4. **Review Recovery Strategy**: Can parsing continue effectively after errors?

## Lex & Yacc Specific Criticism Guidelines

### Focus on Grammar Design Best Practices
**Good Criticism:**
- "This grammar rule creates an unnecessary shift/reduce conflict that should be resolved with precedence"
- "The regular expression pattern is ambiguous and will match incorrectly in edge cases"
- "This semantic action accesses `$3` but the rule only has two symbols"
- "The error recovery point is too coarse and won't help users locate the actual error"

**Poor Criticism:**
- "This doesn't look right"
- "This seems inefficient"
- "I don't like this approach"

### Emphasize Deterministic Parsing
**Good Criticism:**
- "This grammar produces reduce/reduce conflicts that make parsing non-deterministic"
- "The precedence declarations don't cover all operators in the precedence hierarchy"
- "This regular expression will cause backtracking that affects lexer performance"
- "The grammar ambiguity for the dangling-else problem needs explicit resolution"

**Poor Criticism:**
- "This won't work correctly"
- "This is not deterministic"
- "This might cause problems"

### Emphasize Proper Tool Usage
**Good Criticism:**
- "Use `%left` to declare left-associative operators instead of restructuring the grammar"
- "The `error` token should be used for recovery instead of trying to parse all invalid input"
- "Start conditions should handle this context-sensitive lexing instead of parser hacks"
- "Use `%prec` to resolve this specific conflict instead of changing the grammar structure"

**Poor Criticism:**
- "This tool usage is wrong"
- "You should use different features"
- "This approach is bad"

### Consider Language Processing Quality
**Good Criticism:**
- "The error recovery doesn't maintain semantic consistency after encountering syntax errors"
- "This lexer pattern doesn't handle string escape sequences correctly"
- "The semantic actions don't properly construct the abstract syntax tree"
- "The grammar doesn't correctly handle operator associativity for this language"

**Poor Criticism:**
- "This has bugs"
- "This is unreliable"
- "This parser is bad"

## Lex & Yacc Specific Problem Categories

### Lexical Analysis Problems
- **Pattern Ambiguity**: Regular expressions that match ambiguously
- **Inefficient Patterns**: Regular expressions that cause performance issues
- **Edge Case Failures**: Missing handling of EOF, escapes, or special characters
- **Context Insensitivity**: Not using start conditions where needed

### Grammar Design Problems
- **Shift/Reduce Conflicts**: Ambiguous grammar requiring precedence resolution
- **Reduce/Reduce Conflicts**: Grammar design problems causing multiple reductions
- **Missing Precedence**: Operator precedence not properly declared
- **Poor Structure**: Grammar rules that don't reflect language semantics

### Semantic Action Problems
- **Incorrect Value Access**: Wrong use of `$$` and `$n` in semantic actions
- **Memory Management**: Improper handling of dynamically allocated values
- **Type Inconsistency**: Semantic value types not used consistently
- **Parser Interference**: Semantic actions that improperly affect parser state

### Error Handling Problems
- **Poor Recovery**: Missing or ineffective error recovery points
- **Inconsistent State**: Error recovery that leaves parser in bad state
- **Unclear Messages**: Error messages that don't help users debug
- **Resource Leaks**: Missing cleanup during error recovery

### Integration Problems
- **Tight Coupling**: Lexer and parser too tightly integrated
- **Global State**: Excessive use of global variables preventing reuse
- **Poor Interface**: Difficult integration with target applications
- **Non-Reentrant**: Design that prevents multiple parsing sessions

### Performance Problems
- **Lexer Inefficiency**: Regular expressions that create large state tables
- **Parser Inefficiency**: Grammar that produces inefficient parsing tables
- **Action Overhead**: Unnecessary semantic actions that slow parsing
- **Memory Issues**: Poor memory management for large inputs

## Lex & Yacc Specific Criticism Templates

### For Lexical Analysis Issues
```
Lexical Issue: [Specific lexer problem]
Problem: [How this violates lexical analysis best practices]
Impact: [Tokenization errors, performance issues, or maintainability problems]
Evidence: [Specific regular expression patterns and tokenization examples]
Priority: [Critical/High/Medium/Low]
```

### For Grammar Design Issues
```
Grammar Issue: [Specific grammar problem]
Problem: [What makes this grammar design problematic]
Impact: [Parsing errors, conflicts, or semantic issues]
Evidence: [Specific grammar rules and conflict examples]
Priority: [Critical/High/Medium/Low]
```

### For Conflict Resolution Issues
```
Conflict Issue: [Specific parsing conflict]
Problem: [Why this conflict occurs and how it affects parsing]
Impact: [Non-deterministic parsing or incorrect language recognition]
Evidence: [Specific conflicts reported by parser generator]
Priority: [Critical/High/Medium/Low]
```

### For Semantic Action Issues
```
Semantic Action Issue: [Specific semantic action problem]
Problem: [What makes this semantic action incorrect or inefficient]
Impact: [Incorrect semantic values or memory management issues]
Evidence: [Specific semantic action code and value handling]
Priority: [High/Medium/Low]
```

## Lex & Yacc Specific Criticism Best Practices

### Do's
- **Follow Tool Conventions**: Always follow established Lex and Yacc patterns
- **Design for Determinism**: Create unambiguous grammars and lexers
- **Use Proper Precedence**: Declare precedence and associativity correctly
- **Handle All Cases**: Consider edge cases and error conditions
- **Optimize Patterns**: Design efficient regular expressions and grammar rules
- **Separate Concerns**: Keep lexical and syntactic analysis properly separated
- **Plan for Integration**: Design clean interfaces for target applications

### Don'ts
- **Ignore Conflicts**: Don't accept unresolved parser conflicts
- **Overcomplicate Patterns**: Don't use overly complex regular expressions
- **Mix Responsibilities**: Don't handle syntax in the lexer or lexing in the parser
- **Assume Perfect Input**: Don't ignore error handling and recovery
- **Hardcode Assumptions**: Don't make inflexible assumptions about usage
- **Neglect Performance**: Don't ignore lexer and parser efficiency
- **Skip Documentation**: Don't leave grammar and lexer patterns undocumented

## Lex & Yacc Specific Criticism Checklist

### Lexical Analysis Assessment
- [ ] Are regular expression patterns unambiguous and well-ordered?
- [ ] Does the lexer handle all edge cases correctly (EOF, escapes, quotes)?
- [ ] Are start conditions used appropriately for context-sensitive lexing?
- [ ] Is the token set complete and properly designed for the grammar?
- [ ] Are patterns efficient and avoid unnecessary backtracking?

### Grammar Design Assessment
- [ ] Is the grammar unambiguous with all conflicts properly resolved?
- [ ] Are precedence and associativity declarations correct and complete?
- [ ] Do grammar rules accurately reflect the intended language structure?
- [ ] Are semantic actions correctly accessing grammar symbol values?
- [ ] Is the grammar organized in a logical and maintainable way?

### Conflict Resolution Assessment
- [ ] Are all shift/reduce and reduce/reduce conflicts properly resolved?
- [ ] Are precedence declarations used correctly and minimally?
- [ ] Does the conflict resolution match the intended language semantics?
- [ ] Are grammar rules designed to minimize necessary conflict resolution?
- [ ] Is the parser deterministic for all valid input?

### Semantic Action Assessment
- [ ] Are semantic actions correctly accessing grammar symbol values?
- [ ] Is memory management for semantic values handled properly?
- [ ] Do semantic actions maintain appropriate separation from parsing logic?
- [ ] Are semantic value types consistent throughout the grammar?
- [ ] Does error recovery properly clean up semantic values?

### Error Handling Assessment
- [ ] Are error recovery points placed appropriately throughout the grammar?
- [ ] Do error messages provide useful information for debugging?
- [ ] Does error recovery maintain parser and semantic consistency?
- [ ] Are semantic values properly cleaned up during error recovery?
- [ ] Can the parser continue effectively after error recovery?

### Integration Assessment
- [ ] Is the interface between lexer and parser clean and well-defined?
- [ ] Can the parser be used in different contexts without modification?
- [ ] Are global variables minimized and properly managed?
- [ ] Is the parser suitable for the intended integration scenario?
- [ ] Does the design support reentrant or thread-safe operation if needed?

### Performance Assessment
- [ ] Are regular expressions designed for optimal lexer performance?
- [ ] Does the grammar produce efficient parsing tables?
- [ ] Are semantic actions optimized to minimize parsing overhead?
- [ ] Is memory usage appropriate for the expected input size?
- [ ] Are available optimization options used effectively?

## Lex & Yacc Specific Evaluation Questions

### For Any Lex & Yacc Project
1. **Does this lexer/parser correctly recognize the intended language?**
2. **Are all grammar conflicts properly resolved or acceptable?**
3. **Is the lexical analysis design efficient and unambiguous?**
4. **Are semantic actions correctly implemented and efficient?**
5. **Is error handling comprehensive and user-friendly?**
6. **Is the parser suitable for integration with the target application?**
7. **Does the design scale appropriately for expected input sizes?**
8. **Are the lexer and parser properly modularized?**
9. **Is the grammar well-documented and maintainable?**
10. **Does the implementation follow Lex & Yacc best practices?**

### For Language Implementation Projects
1. **Does the grammar accurately reflect the language specification?**
2. **Are all language constructs properly handled in the lexer and parser?**
3. **Is operator precedence and associativity correctly implemented?**
4. **Are language-specific features (comments, strings, etc.) handled correctly?**
5. **Does the semantic analysis properly construct language representations?**

### For Domain-Specific Language Projects
1. **Is the grammar designed for the intended domain users?**
2. **Are error messages meaningful for domain experts rather than parser experts?**
3. **Does the lexer handle domain-specific notation and conventions?**
4. **Is the parser extensible for future domain requirements?**
5. **Are performance characteristics appropriate for typical domain inputs?**

## Lex & Yacc Tool Principles Applied

### "Separation of Concerns"
- Lexical analysis should handle tokenization, not syntax
- Parser should handle syntax, not character-level processing
- Semantic actions should build representations, not parse
- Error recovery should be separate from normal parsing logic

### "Deterministic Recognition"
- Grammars should be unambiguous and produce deterministic parsers
- Regular expressions should match unambiguously
- Conflict resolution should be explicit and correct
- Parser behavior should be predictable for all valid inputs

### "Efficient Implementation"
- Regular expressions should be designed for optimal state machines
- Grammar should produce efficient parsing tables
- Semantic actions should minimize overhead during parsing
- Memory management should be appropriate for input characteristics

### "Proper Tool Usage"
- Use precedence declarations instead of grammar restructuring
- Use start conditions for context-sensitive lexing
- Use error token for recovery instead of trying to parse all input
- Use tool features as intended rather than working around them

### "Clean Integration"
- Lexer and parser should have clean, well-defined interfaces
- Global state should be minimized to allow reuse
- Integration with target applications should be straightforward
- Design should support different usage scenarios

### "Comprehensive Error Handling"
- Error recovery should be placed at appropriate grammar points
- Error messages should help users locate and understand problems
- Recovery should maintain parser and semantic consistency
- Cleanup should prevent resource leaks during error conditions

## Lex & Yacc API Evaluation Criteria

### Lex/Flex Functions and Features
- **Pattern Matching**: Proper regular expression design and ordering
- **Start Conditions**: Appropriate use of `%s` and `%x` for context sensitivity
- **Actions**: Correct token return and semantic value assignment
- **Input Handling**: Proper use of `input()`, `unput()`, and `yytext`

### Yacc/Bison Functions and Features
- **Grammar Rules**: Proper BNF rule structure and organization
- **Precedence Declarations**: Correct use of `%left`, `%right`, `%nonassoc`
- **Semantic Actions**: Proper use of `$$` and `$n` for value management
- **Error Handling**: Appropriate use of `error` token and recovery strategies

### Integration Functions
- **yylex()**: Proper lexer function interface and token return
- **yyparse()**: Correct parser function usage and return values
- **yyerror()**: Appropriate error reporting function implementation
- **yylval**: Correct semantic value communication between lexer and parser

### Memory Management Functions
- **malloc/free**: Proper dynamic memory allocation in semantic actions
- **String Handling**: Correct string duplication and cleanup
- **AST Management**: Appropriate abstract syntax tree construction and cleanup
- **Error Cleanup**: Proper resource cleanup during error recovery

### Optimization Features
- **Flex Options**: Appropriate use of performance and compatibility options
- **Bison Options**: Correct use of parser generation and optimization flags
- **Table Compression**: Proper use of space/time optimization tradeoffs
- **Reentrant Parsing**: Appropriate use of reentrant parser features when needed