Test Case Generation from Context-Free Grammars using Generalized Traversal of LR-Automata
summary
Algorithm generates positive and negative test suites by traversing LR-automata encoded as an LR graph, using a two-phase BFS: a flooding phase that ensures every automaton edge is visited and a path-completion phase that produces shortest accept paths. Negative tests come from four guaranteed mutations (insertion, deletion, substitution, cutting) driven by the follow set and almost-accepting states. A priority-queue optimization (reported as LR*) shrinks suites below prior grammar-based methods and speeds execution, though stubborn edges still cause performance outliers.
AI-written summary · about
chapters (5)
related talks
12mAutomatic Grammar Repair
20mAutomatic Invariant Testing for Finite-State Machines
15mFaster Reachability Analysis for LR(1) Parsers
31mSemantics-preserving Transformation of Context-free Grammars into LL(1) Form
05mVision: Bias in Systematic Grammar-Based Test Suite Construction Algorithms
20mAutomatic Repair of Regular Expressions
15mRecursive State Machine Guided Graph Folding for Context-Free Language Reachability
27mWrite Fewer Tests! From Automation to Autogeneration