{"id":"133b81a9-0bd1-4938-b466-0db3339a53d7","arxiv_id":"2507.13117","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors extract semantic actions from recursive descent parser executions and attach them to grammar rules, producing attributed grammars that reproduce the parser's behavior.","lead":"This paper introduces a method for automatically recovering formal input specifications from parser programs by observing them at runtime. The result is an attributed grammar, a combined description of the input language and the computation applied to each input.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 'comprehensive specification recovery' claim is unsupported because the method explicitly omits error/exception paths and the evaluation compares only curated happy-path outputs, so recovered attributed grammars are not shown to reproduce full parser behavior.","rationale":"I assess the central claim as an equivalence claim between the recovered attributed grammar and the program's input-processing behavior. The strongest support is Table IV, but the evaluation protocol only compares outputs on a small number of manually selected valid inputs, and Section V explicitly concedes that exception/error semantics are not extracted. Since a parser's behavior includes rejecting invalid inputs and raising exceptions, the omitted semantics are not peripheral; they are part of the specification being recovered. This makes the abstract's 'comprehensive specification recovery' and the Section I claim that the AG 'captures both syntax and semantics' unsupported by the presented evidence. My concern differs from the reader's weakest assumption: the structural-isomorphism assumption (Section III-D) is a correctness risk for the mapping, but even when the mapping succeeds, the recovered grammar only models successful executions. The concrete test I propose would distinguish 'AG reproduces the program on the tested happy-path inputs' from 'AG is a comprehensive specification.' I do not see this as a reason to reject the paper; the method is plausible and the limitations are stated honestly. It is, however, a reason to keep the verdict conditional and to require either a scoped claim ('partial, happy-path reconstruction') or an evaluation that includes exception behavior and automatically generated inputs.","tokens_in":8209,"tokens_out":5045,"duration_ms":61555,"concrete_test":"Take one benchmark with 100% reported accuracy (e.g., CgiDecode). Reconstruct its AG exactly as described, then execute both the original parser and an interpreter for the AG on three input sets: (1) the original curated valid inputs; (2) a larger automatically generated set of valid inputs from the assumed grammar, including boundary cases such as empty strings, repeated/optional constructs, deep nesting, and overlapping token prefixes; and (3) invalid inputs that trigger the parser's exception/error paths. Compare the full observable behavior—output values, acceptance/rejection, and exceptions. If sets (2) or (3) produce any mismatch, then the recovered AG is not a comprehensive specification and the claim must be weakened to 'partial happy-path reconstruction.' Ideally this check is run by an independent implementation, since no artifact is released.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that the inferred attributed grammar AG reproduces the program's input-processing behavior, i.e., I→AG→O is equivalent to I→P→O. The paper's own Section V states that the method 'currently captures only semantics along the happy path, meaning executions that complete without exceptions' and that 'semantics related to exceptional or error-handling behavior are not tracked.' Section IV measures accuracy by comparing serialized outputs on inputs that are valid by construction and manually curated to achieve statement coverage. As a result, even a 100% benchmark supports only the claim that the AG matches the program on the tested successful inputs, not that it is a comprehensive specification of the parser's behavior. A parser's behavior includes rejecting malformed inputs and raising exceptions; an AG that silently succeeds on those inputs, or omits the corresponding semantic actions, is not behaviorally equivalent to P. This is not an implementation detail but a scope limitation of the recovered artifact, so the abstract's 'comprehensive specification recovery' and Section I's claim that the attributed grammar 'captures both syntax and semantics' are overstated relative to the evidence. The structural-isomorphism assumption in Section III-D is a related risk, but the exception-path omission is sufficient by itself to undermine the central claim as phrased.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a dynamic-analysis technique for enriching an existing context-free grammar of a recursive-descent parser with semantic actions, yielding an attributed grammar. Given a grammar and a parser program, the method generates syntactically valid inputs, executes the parser to obtain a runtime parse tree, derives a derivation tree from the grammar, maps nodes between the two trees under a type-and-yield-range isomorphism assumption, and transfers semantic code from the program into the grammar. The paper presents a running example (a number parser), a small evaluation of seven parser benchmarks from the literature, and reports output-agreement accuracies ranging from 59% to 100%. The author's central claim is that the recovered attributed grammar reproduces the program's input-processing behavior and constitutes a comprehensive specification.","tokens_in":8369,"tokens_out":4751,"duration_ms":57779,"significance":"If the approach worked as stated, it would be a useful contribution to specification mining: prior grammar-mining work mostly recovers syntax, while this paper targets the under-explored problem of recovering semantic actions. The proposed mapping between parse-tree node types and grammar constructs is concrete, and the running example demonstrates the intended mechanism. However, the current evidence supports only a narrow feasibility claim: the evaluation uses a small set of manually curated examples, two benchmarks reach only 59% accuracy, and the paper's own limitations section concedes that exceptional and error-handling behavior is not modeled. The significance is therefore preliminary rather than established, and the paper's stronger wording, such as \"comprehensive specification recovery,\" is not justified by the presented results. I also note that no artifact or reproducibility package is mentioned, which limits independent verification.","major_comments":[{"comment":"The central specification-recovery claim is contradicted by the paper's own scope statement. The abstract and Section I assert that the approach yields \"comprehensive specification recovery\" and \"complete attributed grammars that capture both syntax and semantics,\" but Section V states that the method captures only happy-path semantics and does not track exceptional or error-handling behavior. Since a parser's behavior includes rejecting malformed inputs and raising exceptions, an attributed grammar that omits those behaviors is not behaviorally equivalent to the original program on all inputs. The accuracy measurement in Section IV only compares outputs on inputs that are valid by construction, so it cannot support the unqualified equivalence claim I → AG → O made in Section III. Please rephrase the contribution as recovery of happy-path semantic actions, or extend the method to exception paths and demonstrate that equivalence on invalid inputs as well.","section":"Abstract, §I, §III, §V"},{"comment":"The evaluation does not exercise the input-generation step described in the method. Section III-A says that grammar fuzzing combining the Efficient Grammar Fuzzer and Grammarinator's cooldown strategy is used to achieve grammar coverage, but Section IV states \"we manually crafted inputs to achieve full statement coverage.\" Consequently, the reported accuracies are evidence for the mapping and transfer steps on hand-picked inputs only; the fuzzing pipeline is never evaluated. Moreover, MathExpr and MicroJson reach only 59% accuracy, and the text's explanation (\"certain functions were not fully covered,\" \"an incorrect placement of a semantic rule\") does not quantify which grammar rules or program paths were covered or missed. Please either run and report the fuzzing-based end-to-end pipeline, or explicitly present the evaluation as a manually curated feasibility study with per-benchmark coverage data.","section":"§III-A, §IV, Table IV"},{"comment":"The accuracy metric is close to an internal consistency check. Semantic actions embedded into the attributed grammar are, by construction, verbatim statements of the program's own code, and the correctness test compares the outputs of the attributed-grammar interpreter with outputs of the same program. High agreement therefore shows that the extraction-and-placement pipeline preserved the original statements on the tested inputs, not that the inferred semantics are correct against an independent specification. For example, if the mapping misplaced a semantic action, the test would detect it on the exercised trace, but it would not detect a semantic action that is itself an incorrect implementation of the intended language semantics. The paper should state this distinction explicitly and add at least one validation that is not purely transcription fidelity, such as checking the recovered attributed grammar against a separately written reference specification for one of the benchmarks.","section":"§III-D, §III-E, §IV"},{"comment":"The structural-isomorphism assumption behind the node mapping is load-bearing and is acknowledged to be narrow. Section III-D assumes that input-character nodes correspond to terminals, function nodes to nonterminals, loops to repetitions, and conditions to options or choices, with corresponding nodes covering the same input ranges. Section V then concedes that the method \"does not handle substantial deviations such as grammar rule indirections, function calls, or major control flow differences\" and that some examples from prior work had to be adapted to fit the format. Given this concession, the general framing about \"recursive descent parsers\" in Section I overstates the applicability. The paper should characterize the class of parsers the method actually covers (e.g., one-function-per-grammar-rule, no exception handling inside parsing functions, no recursion-versus-repetition mismatches) and state this assumption prominently in the introduction and abstract.","section":"§III-D, §V"}],"minor_comments":[{"comment":"The line references in the text do not match the line numbering of Listing 1; for example, the root node Number is attributed to \"line 1\" while the function definition appears on line 4 of the listing, and the conditional in the text's \"line 3\" appears on line 6 of the listing. Please align these references or explain the numbering scheme.","section":"§III-C, Listing 1"},{"comment":"The caption says that the subscript numbers represent the terminal yield, but the subscripts are intervals such as [1-3]; please clarify that these are input position ranges covered by the node, and state whether intervals are inclusive.","section":"Figure 2"},{"comment":"The bottom-up function-to-nonterminal mapping algorithm is described informally; in particular, the termination condition and the behavior when no node with matching terminal yield exists are not defined. A short pseudocode listing or a precise invariant would make the algorithm reproducible.","section":"§III-D.2"},{"comment":"Reference [16] contains the stray word \"unread\" in the bibliographic entry, and the affiliation line \"Institut for System Software\" appears to be a typo for \"Institute.\" These should be corrected.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"This reads like an early-stage workshop-style report rather than a fully validated journal contribution. The core idea is worth pursuing, but the evaluation is small, manual, and the reported accuracy is largely a transcription-fidelity check. I would encourage the editor to invite a major revision that recalibrates the claims to happy-path semantic-action recovery and adds either the fuzzing-based end-to-end experiment or an explicit independent validation. Rejection seems too harsh because the limitations are stated openly and can be addressed within the manuscript's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Main thing to know: this is the first paper I've seen that tries to recover the semantic half of an attributed grammar by tracing a recursive descent parser at runtime and mapping its control-flow behavior onto a known syntactic grammar. That's a genuinely new framing, and the running example (number parser) is clear enough that you can see exactly what the mapping is supposed to do. The related-work comparison is fair about the difference: prior semantic inference uses I/O examples, RL, constraint mining, or genetic search; this one has direct access to code and uses dynamic traces to align statements with grammar positions.\n\nThe paper does several things well. The four-step mapping (characters to terminals, functions to nonterminals, control flow to options/choices/repetitions, and fallback handling for unmapped nodes) is concrete and plausibly automatable. The authors are honest about limitations: they explicitly say they only capture the happy path, that the mapping breaks on major structural deviations like recursion vs. iteration, and that some benchmarks had to be adapted. That honesty is worth something.\n\nThe soft spots are also clear, and they're load-bearing for the central claim. The abstract says 'comprehensive specification recovery,' but Section V concedes that all exception/error-handling semantics are ignored. A parser's behavior includes rejecting malformed input; an attributed grammar that only reproduces outputs on valid inputs is not a comprehensive specification of the program. The evaluation confirms the narrower reading: inputs were manually crafted for statement coverage, not the fuzzing pipeline described in the method, and two of seven benchmarks sit at 59%. On those, the paper says the failures are due to uncovered functions and one mis-placed semantic rule, but without an artifact or a precise description of how arbitrary statements become semantic rules, it's hard to tell whether those are implementation bugs or signs the transfer step is underspecified. There's also a mild circularity: the AG is built by embedding the program's own statements, so the accuracy measure mostly checks that the transcription reproduces the program, not that the AG matches an independent specification.\n\nEven with those caveats, the core idea deserves referee time. The paper is a short, honest feasibility report, not a mature tool. A serious referee should ask for artifact release, a fuzzing-based evaluation, and a scope statement that matches the evidence. I'd send it out, with the expectation that the authors tighten their claims and expand the evaluation. I wouldn't cite it as a definitive result yet, but I'd want it on my radar.","headline":"Novel dynamic tracing approach for semantic grammar recovery, but the 'comprehensive specification' claim outruns the happy-path evaluation.","tokens_in":8934,"tokens_out":2191,"would_cite":false,"duration_ms":24881,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A parser's runtime behavior can be lifted into an attributed grammar, recovering both syntax and semantics from code alone.","keywords":["attributed grammar inference","specification recovery","semantic action extraction","recursive descent parser","dynamic program analysis","parse tree mapping","grammar fuzzing","input grammars"],"falsifier":"Run both the original parser and the reconstructed attributed grammar on inputs that exercise exception handling or uncovered functions; the paper reports such inputs already exist for MathExpr (13 of 32 outputs disagree) and MicroJson (9 of 22 outputs disagree). Any such mismatch shows that the recovered grammar is not yet a complete behavioral specification for inputs beyond the covered execution paths.","tokens_in":7953,"feed_emoji":"⚙️","tokens_out":7701,"duration_ms":87776,"temperature":0.7,"pith_summary":"Legacy systems that parse structured input often lack a written specification of what the input means or how it is processed. The paper claims that this missing semantic specification can be recovered automatically: starting from a syntactic grammar and a recursive descent parser implementation, it runs the parser on generated inputs, records the runtime parse tree, aligns that tree with the grammar's derivation tree, and lifts the parser's semantic statements into the grammar as attributes and semantic rules. The result is an attributed grammar, a single executable description of both syntax and input-to-output behavior. Preliminary results show that for four of seven small benchmarks the reconstructed grammar reproduces the original program's output on every tested input, with the remaining three failing on exception handling, uncovered functions, or misplacement of one semantic rule.","feed_headline":"Parser code becomes executable grammars that reproduce its behavior","feed_subtitle":"Matching runtime control flow to grammar structure recovers what input processing does, not just its syntax.","key_machinery":"The load-bearing object is the node-mapping table between the runtime parse tree and the grammar derivation tree, together with the terminal-yield range attached to each node. In the parse tree, input-character accesses, function calls, loops, and conditionals become nodes; in the derivation tree, terminals, nonterminals, repetitions, options, and choices become nodes. Mapping proceeds by matching terminal sequences first, then matching functions to nonterminals bottom-up, then matching control-flow nodes to grammar structures within each function's scope; unmapped semantics are pushed to nearby children. This table is what lets ordinary imperative code be transferred into formal semantic actions at the correct positions in the grammar.","core_discovery":"The central claim is that an attributed grammar can be inferred from a recursive descent parser by dynamic analysis, provided that a syntactic grammar for the same input language is already available. The key step is a type-and-yield mapping between two trees built from the same input: the parse tree produced by observing the running parser and the derivation tree produced by parsing that input with the grammar. When the mapping succeeds, code that is not part of syntax checks is grouped into semantic blocks and inserted at the corresponding grammar positions, with function calls, parameters, return statements, and assignments translated into attribute rules. The paper argues that the resulting attributed grammar faithfully reproduces the original program's input-processing behavior, and the evaluation reports exact output agreement on four of seven benchmarks.","pith_inferences":["Editorial inference: if the mapping were extended with grammar normalization, for example by converting iteration to recursion or eliminating left recursion, the same trace-alignment idea could cover many hand-written parsers that do not literally mirror the supplied grammar.","Editorial inference: the recovered semantic actions could support differential testing, where the original parser and the generated attributed grammar are both run on fuzzed inputs and any output disagreement flags a behavioral difference.","Editorial inference: combining the approach with symbolic or concolic execution to reach exception-raising inputs would address the paper's stated happy-path limitation and let error-handling semantics be captured."],"forward_implications":["For parsers that follow the assumed recursive descent style, specification recovery can cover semantics as well as syntax, turning the recovered attributed grammar into an executable specification of input processing.","Because the recovered attributed grammar is executable, it can be used to generate inputs with known expected outputs, providing a test oracle for the original parser and for future modifications.","The mined grammar can be read by humans as documentation of a parser's behavior, filling a gap left by missing or outdated specifications.","The method currently captures only happy-path semantics: exception and error-handling behavior is not recovered, and inputs must avoid runtime exceptions such as evaluating asin(x) outside the valid domain.","The mapping tolerates only minor structural differences between parser and grammar; recursion instead of iteration, grammar rule indirections, or major control-flow deviations are not handled."],"supporting_citations":[{"why":"Supplies the dynamic control-flow method for constructing parse trees from program executions, which the mapping step depends on.","marker":"[5]"},{"why":"Supplies the efficient grammar fuzzing algorithm used to generate syntactically valid covering inputs.","marker":"[15]"},{"why":"Supplies the coverage and cooldown strategy that balances generated input diversity during grammar fuzzing.","marker":"[16]"},{"why":"Defines attributed grammars, the target formalism that gives semantics to syntax rules.","marker":"[3]"},{"why":"Introduces the attribute-grammar-mining and grammar-fuzzing concepts that the current approach extends.","marker":"[7]"},{"why":"Provides enhanced input-generation techniques for grammar mining that shape the evaluation setup.","marker":"[9]"},{"why":"Supplies the standard leftmost-derivation construction used to build derivation trees from the grammar.","marker":"[17]"}],"fun_headline_variants":["Parser code yields attributed grammars that capture semantics","Mining semantics: attributed grammars from parser behavior","From parser code to attributed grammars via runtime tracing","Attributed grammars inferred by observing parser executions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method assumes that the shape of the running parser mirrors the shape of the grammar, so that every parser function matches a grammar rule, every loop matches a repetition, and every condition matches an option or choice covering the same input range; when parser and grammar diverge structurally, the mapping fails.","fun_headline_variants_meta":{"raw":{"variants":["Parser code yields attributed grammars that capture semantics","Mining semantics: attributed grammars from parser behavior","From parser code to attributed grammars via runtime tracing","Attributed grammars inferred by observing parser executions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00018,"raw_usage":{"total_tokens":1240,"prompt_tokens":820,"completion_tokens":420,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":436,"completion_tokens_details":{"reasoning_tokens":359}},"tokens_in":436,"tokens_out":420,"duration_ms":4685,"temperature":1.0,"reasoning_tokens":359,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T16:29:58.371117+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run both the original parser and the reconstructed attributed grammar on inputs that exercise exception handling or uncovered functions; the paper reports such inputs already exist for MathExpr (13 of 32 outputs disagree) and MicroJson (9 of 22 outputs disagree). Any such mismatch shows that the recovered grammar is not yet a complete behavioral specification for inputs beyond the covered execution paths.","supporting_citations":[{"cited_title":"The fuzzing book,","cited_arxiv_id":null,"evidence_quote":"Supplies the efficient grammar fuzzing algorithm used to generate syntactically valid covering inputs."},{"cited_title":"Grammarinator: a grammar-based open source fuzzer,","cited_arxiv_id":null,"evidence_quote":"Supplies the coverage and cooldown strategy that balances generated input diversity during grammar fuzzing."},{"cited_title":"Towards Attribute Grammar Mining by Symbolic Execution,","cited_arxiv_id":null,"evidence_quote":"Introduces the attribute-grammar-mining and grammar-fuzzing concepts that the current approach extends."},{"cited_title":"Generating Inputs for Grammar Mining using Dynamic Symbolic Execution,","cited_arxiv_id":null,"evidence_quote":"Provides enhanced input-generation techniques for grammar mining that shape the evaluation setup."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the standard leftmost-derivation construction used to build derivation trees from the grammar."}],"review_version":1}