Jest Grammar-Based Fuzzing

This challenge focuses on implementing grammar-based fuzzing within a Jest testing environment. Fuzzing is a powerful technique for discovering bugs by feeding unexpected or malformed inputs to a program. Grammar-based fuzzing utilizes a formal definition of valid input structures to generate more targeted and effective test cases.

Problem Description

Your task is to create a Jest test suite that incorporates grammar-based fuzzing to test a hypothetical function that parses simple arithmetic expressions. The parser is expected to handle addition and subtraction of integers.

You need to:

Define a grammar: Create a formal grammar that describes valid arithmetic expressions (e.g., "number + number", "number - number", "number").
Implement a grammar-based generator: Write a function that, given the grammar, generates random, yet syntactically valid, arithmetic expressions.
Integrate with Jest: Use this generator within a Jest test.each or similar construct to run multiple tests with generated inputs.
Test a parser function: Assume a parseExpression(expression: string): number function exists (you will need to mock or provide a simple implementation for testing purposes). This function should return the evaluated result of the expression.
Handle invalid inputs: While the generator should produce valid expressions, your fuzzer should also consider how to generate slightly malformed expressions to test the parser's robustness (e.g., extra spaces, unexpected characters at the end).

Key Requirements:

The grammar should be clear and representable in a programmatic way.
The generator should be able to produce a variety of valid expressions based on the grammar.
Jest tests should execute the parser with generated inputs.
The fuzzer should have a mechanism to introduce controlled "mutations" or deviations from the strict grammar to test error handling.

Expected Behavior:

For valid generated expressions, the parseExpression function should return the correct numerical result.
For slightly malformed expressions, the parseExpression function might throw an error or return a specific error indicator (you'll define this behavior for your mock parser).
The Jest tests should report whether generated inputs pass or fail as expected.

Edge Cases to Consider:

Single numbers (e.g., "5").
Expressions with only addition or only subtraction.
Expressions with alternating operators.
Expressions with large numbers.
Malformed expressions (e.g., trailing operators, invalid characters).

Examples

Example 1: Valid Expression Generation

Input to generator: (based on grammar for "number + number")
Output from generator: "123 + 45"
Hypothetical parseExpression("123 + 45"): 168
Jest Test Outcome: Pass

Example 2: Valid Expression Generation

Input to generator: (based on grammar for "number")
Output from generator: "999"
Hypothetical parseExpression("999"): 999
Jest Test Outcome: Pass

Example 3: Malformed Expression Test

Input to generator: (introducing a mutation to "number + number")
Output from generator: "78 + " (trailing operator)
Hypothetical parseExpression("78 + "): Should throw an error or return a specific error value.
Jest Test Outcome: Pass (if the parser correctly identifies the error)

Constraints

The grammar should be representable using simple data structures (e.g., objects, arrays) in TypeScript.
The number of generated test cases should be configurable, allowing for a reasonable number (e.g., 100-1000) to be run per test suite execution.
The parseExpression function, for the purpose of this challenge, can be a simplified implementation that handles basic cases and throws errors for invalid syntax. It does not need to be a full-fledged robust parser.
Tests should execute within a reasonable time frame for typical CI/CD environments.

Notes

Consider using a grammar definition format like Extended Backus–Naur Form (EBNF) or a simplified recursive structure.
Think about how to randomly select grammar rules and elements.
For introducing mutations, consider simple operations like character insertion, deletion, or substitution, applied to otherwise valid generated strings.
The goal is to demonstrate the process of grammar-based fuzzing in Jest, not to build the most sophisticated fuzzer or parser. You might find libraries for grammar definition or fuzzing helpful for inspiration, but aim to implement the core logic yourself.