Introduction

This artifact reproduces the experiments from submission #49 - Synthesizing Parsing Expression Grammars via Analysis-based Pruning.

Requirements

The artifact ships with a pre-built ./pegsyn executable. Running it only requires:

• JDK 11+

To rebuild from source (optional), additionally:

• sbt 1.x

Build (optional)

sbt build

Smoke test (< 1 min)

./pegsyn synthesize spec/no4.spec -synthesize:all -synthesize:log=1

Run results and detailed information (per-iteration candidates, prune/optimize stats, timing breakdown) can be inspected in logs/recent/no4.an_bn_cn.log.

Result layout

The reproduction scripts populate result/ as follows:

result/
  tables/
    table3-accuracy.csv             # Table 3 — accuracy vs. LLM baselines
    table4-spacentime.csv           # Table 4 — search-space and time
    table5-optimize.csv             # Table 5 — optimization breakdown
  output/
    pegsyn-result/<spec>/answer<i>.res        # PEGs synthesized by our system
    ex-result/<spec>/succ/answer<i>.res       # LLM PEGs (no description prompt)
    desc-result/<spec>/succ/answer<i>.res     # LLM PEGs (with description prompt)
  ablation/
    {B,G-Opt,G-X-Opt,G-X-S,G-X-S-Opt}/
      summary.tsv                   # one row per spec (input to `pegsyn table`)
      <noN>.<name>.log              # per-spec synthesize log
      pegsyn-result/<spec>/answer<i>.res

pre-result/ has the same layout and ships the exact data used in the submission, so you can inspect any of those files directly without rerunning the pipeline.

Test inputs

data/test-inputs/<spec>/ holds the strings used by evaluate to score synthesized PEGs against the oracle:

data/test-inputs/<spec>/
  succ.tests        # inputs the oracle accepts
  fail.tests        # inputs the oracle rejects
  imp.tests         # the small "important" subset (used by -evaluate:simple)

By default evaluate reads every *.tests file under the spec directory; pass -evaluate:simple to score against imp.tests only.

data/{ex,desc}-result/ holds the LLM-baseline answers used by Table 3 (see "Reproduce the paper" below for how run/table3.sh consumes them).

Reproduce the paper

Each table has its own shell script. They all run the 15 benchmarks in spec/ with a 5-minute per-benchmark timeout, cache each ablation under result/ablation/<name>/, and skip configurations that are already complete — so re-running is cheap and run_all.sh can resume after an interrupt.

./run/table3.sh    # ~3 min   -> result/tables/table3-accuracy.csv
./run/table4.sh    # ~2 hours -> result/tables/table4-spacentime.csv
./run/table5.sh    # ~2 min   -> result/tables/table5-optimize.csv
./run/all.sh       # ~2 hours total (runs all three; reuses cached ablations)

Time estimates are based on the paper's hardware. The tables map to ablations as follows:

Script	Ablations run
run/table3.sh	G-X-S-Opt (full system)
run/table4.sh	B, G-Opt, G-X-Opt, G-X-S-Opt
run/table5.sh	G-X-S, G-X-S-Opt

run/table3.sh evaluates our PEGs against two LLM baselines. If result/output/{ex,desc}-result/ are missing, it copies the snapshot used in the paper from data/{ex,desc}-result/. To re-issue the LLM requests yourself, fill in src/main/resources/config.json with a valid api-key (and optionally org-id/model), then run:

./run/llm_request.sh   # writes result/output/{ex,desc}-result/<spec>/{succ,fail}/answer<i>.res

The prompt template lives at src/main/resources/base.prompt and can be edited; per-spec sections (Description, Symbols, Predefined, Examples) are appended automatically.

Knobs for any of the scripts (env vars):

• T=<minutes> — per-benchmark synthesize timeout (default 5).
• SPEC_DIR=<path> — single spec file or alternate spec dir (default spec).
• N=<int> — number of successful LLM responses per spec for llm_request.sh (default 1).

For a faster smoke run, use a smaller timeout and a single spec, e.g. T=1 SPEC_DIR=spec/no1.spec ./run/table3.sh.

Synthesize options

Pruning (Sec. 4-5):

• -synthesize:prune-ill — partial PEGs with infinite-loop recursion (Sec. 4.1)
• -synthesize:prune-red — partial PEGs with reducible syntax (Sec. 4.2)
• -synthesize:prune-gram — both grammar prunings above
• -synthesize:prune-sin — single-example pruning (Sec. 5.3)
• -synthesize:prune-mul — multi-example pruning (Sec. 5.4)
• -synthesize:prune-example — both example prunings above
• -synthesize:prune-all — all pruning techniques

Scoring (Sec. 6):

• -synthesize:score — potential-based ordering
• -synthesize:alpha=K — scoring hyperparameter (default 3.0)

Optimization (Sec. 7):

• -synthesize:opt-ti — example-trie + incremental abstract interpretation
• -synthesize:opt-all — all optimizations (adds packrat memoization)

Misc:

• -synthesize:all — everything above on
• -synthesize:t=N — timeout in minutes (default 5m)

Spec format

Each spec/noN.spec file declares:

- Name        : <id>
- Description : <free text>
- Symbols     : <comma-separated terminals>
- Predefined  :
  - <Nt> <- <expr>                  # predefined non-terminals (optional)
- Oracle      : <PEG expression>    # ground-truth PEG (optional)
- Examples    :
  - "<input>" -> "<remaining>"      # input string and its expected leftover

To add a new benchmark, drop a spec/noN.spec file with the format above and rerun any of the commands.

Code layout

src/main/scala/pegsyn/
  PEGSyn.scala            # entry point, phase wiring
  peg/                    # PEG / NPEG data types and parsers
  spec/                   # spec file parser and data types
  synthesizer/            # core enumeration loop
  analyzer/               # grammar and example analyses (pruning)
    grammar/              #   Sec. 4 checkers (left-recursion, reducible, ...)
    example/              #   Sec. 5 abstract interpretation
  interp/                 # PEG interpreter (used as oracle / for examples)
  phase/                  # CLI phases (synthesize, evaluate, request, ...)
  util/                   # parsers, logger, collections