# Recursive Descent Parser Construction

> Use when you have a formal grammar specification for a domain-specific language (or can extract one from reference implementations) and need to convert user-written query strings into structured, machine-processable representations (ASTs or JSON) that preserve domain-specific semantics—such as mass.

- Skill: `holobiomicslab/recursive-descent-parser-construction` (Agent Skill)
- Install (CLI): `npx skillmds@latest add holobiomicslab/recursive-descent-parser-construction`
- Raw SKILL.md: https://api.skillmd.com/api/skills/holobiomicslab/recursive-descent-parser-construction/raw
- Safety review: PASS (external: skill-scanner PASS, skillspector PASS)
- Works with: Claude Code, Claude.ai, OpenAI Codex
- Category: Coding & Dev Tools
- License: CC-BY-4.0
- Author: HolobiomicsLab (https://skillmd.com/u/holobiomicslab)
- Updated: 2026-09-17
- Page: https://skillmd.com/skills/holobiomicslab/recursive-descent-parser-construction

---


# recursive-descent-parser-construction

## Summary

Implement a recursive descent parser that tokenizes and builds an abstract syntax tree (AST) from a domain-specific query language, converting unstructured query strings into structured representations. This skill is essential when designing domain-specific languages (DSLs) like MassQL that must capture complex patterns and constraints while maintaining readability and precision.

## When to use

You have a formal grammar specification for a domain-specific language (or can extract one from reference implementations) and need to convert user-written query strings into structured, machine-processable representations (ASTs or JSON) that preserve domain-specific semantics—such as mass spectrometry tolerances, scan type constraints, or m/z value patterns. Use this skill when the query language must express complex patterns that are natural in the domain but would be verbose or ambiguous in generic SQL or JSON.

## When NOT to use

- The input is already a structured representation (XML, JSON, AST)—parse only unstructured query strings.
- The query language has no formal grammar or reference implementation—grammar definition must precede parser construction.
- You are implementing a general-purpose programming language compiler—recursive descent is suitable for DSLs but may not scale to complex operator precedence or large production rule sets without additional techniques.

## Inputs

- Query string in domain-specific language syntax (e.g., MassQL query as text)
- Formal grammar specification (lexical rules and production rules)
- Reference parser implementation or language documentation

## Outputs

- Abstract syntax tree (AST) as in-memory object
- AST serialized to JSON format preserving query components
- Validation report against reference examples

## How to apply

First, extract or design the formal grammar specification by analyzing a reference parser implementation (e.g., from the MassQueryLanguage GitHub repository), documenting lexical rules (token types: keywords, identifiers, operators, literals) and production rules (clause structures, expressions, constraints). Implement a tokenizer (lexer) that breaks input query strings into meaningful tokens using pattern matching or state machines. Then implement a recursive descent parser that consumes tokens in sequence, building an AST by matching production rules recursively—each grammar rule becomes a parser function that either succeeds (returning a node) or fails (triggering backtracking or error handling). Serialize the resulting AST to JSON, preserving domain-specific query components (SELECT clauses, WHERE conditions, mass tolerance parameters, scan type filters). Finally, validate the parser against a suite of reference query examples from the domain community to ensure structural correctness and semantic fidelity.

## Related tools

- **MassQueryLanguage** (Reference implementation providing grammar rules, token types, and AST structure patterns for recursive descent parser design) — https://github.com/mwang87/MassQueryLanguage
- **massql Python API** (Reference Python implementation demonstrating tokenization and AST construction via msql_engine.process_query()) — https://github.com/mwang87/MassQueryLanguage

## Examples

```
```python
from massql import msql_engine

input_query = "QUERY MS2DATA WHERE MS1MZ=572.828 TOLERANCEMZ=0.1 AND MS2PREC=572.828"
results_df = msql_engine.process_query(input_query, input_filename)
```
```

## Evaluation signals

- Parser successfully tokenizes all reference query examples without errors or exceptions.
- AST structure matches expected grammar production rules (e.g., SELECT clauses, WHERE conditions, parameter specifications are distinct AST nodes).
- JSON serialization preserves all domain-specific query components (mass tolerance values, scan type constraints, m/z patterns) without loss or mutation.
- Parser correctly rejects malformed queries (syntax errors, missing required clauses) and reports meaningful error locations.
- Round-trip validation: re-parsing serialized JSON produces an AST structurally identical to the original.

## Limitations

- Recursive descent parsing can suffer from left recursion without refactoring; the grammar must be left-factored or rewritten to avoid infinite loops.
- No changelog in the MassQueryLanguage repository, so grammar changes or parser updates may not be formally documented; rely on reference implementation and test suite for ground truth.
- Scaling to very large query strings or deeply nested expressions may cause stack overflow if recursion depth is unbounded; monitor recursion depth and consider iterative or memoized approaches for production use.
- Parser design assumes the grammar is unambiguous; ambiguous grammars require conflict resolution (e.g., shift/reduce decisions in LR parsing) beyond the scope of simple recursive descent.

## Evidence

- [other] Grammar extraction and parser implementation workflow: "Analyze the reference parser to identify the grammar rules, token types, and AST (abstract syntax tree) structure used to represent MassQL queries. Design or extract the formal grammar specification"
- [other] Tokenization step: "Implement a tokenizer (lexer) that breaks MassQL query strings into meaningful tokens (keywords, identifiers, operators, literals)."
- [other] Recursive descent parser construction: "Implement a parser (recursive descent or similar) that consumes tokens and builds a structured AST representation."
- [other] AST serialization and validation: "Serialize the AST to JSON format, preserving query components (SELECT clauses, WHERE conditions, mass tolerance, scan type constraints, etc.). Validate the parser output against reference query"
- [readme] Domain-specific language design rationale: "The Mass Spec Query Language (MassQL) is a domain specific language meant to be a succinct way to express a query in a mass spectrometry centric fashion. It is inspired by SQL, but it attempts to"