abstract-syntax-tree-construction
Summary
Parse domain-specific query language strings into structured abstract syntax tree (AST) representations that capture the hierarchical syntax and semantics of the query. This skill is essential when implementing a domain-specific language (DSL) interpreter that needs to transform human-readable query expressions into machine-processable intermediate representations for validation and execution.
When to use
Apply this skill when you have a tokenized sequence of domain-specific language tokens and need to construct a hierarchical, unambiguous representation that can be validated against language design principles (expressiveness, precision, scalability, readability) and passed to downstream execution engines. Specifically, use this when building a parser for SQL-inspired query syntax extended with domain-specific assumptions (e.g., mass spectrometry-specific filters like mass-to-charge ratio, retention time, intensity thresholds).
When NOT to use
- Input query is already in a pre-parsed, canonical intermediate format (JSON, protobuf) — proceed directly to validation or execution.
- Query syntax is unambiguous, fully deterministic, and requires no hierarchical decomposition — a simple state machine or regex-based matcher may suffice.
- The domain-specific language has no formal grammar definition or the grammar is under active revision — defer AST construction until the grammar is stabilized.
Inputs
- tokenized query string (sequence of lexical tokens from domain-specific query language)
- formal grammar definition (BNF or EBNF describing syntax and operator precedence)
- mass spectrometry query expressions (MS1MZ, MS2DATA, retention time, intensity filters, tolerance parameters)
Outputs
- abstract syntax tree (AST) or query object representation
- canonical serialization (JSON or Python pickle) of the parse tree
- structured query object ready for execution or analysis
How to apply
Begin by defining a formal grammar capturing the domain-specific language syntax and mass spectrometry-specific operators (e.g., MS1MZ, MS2DATA, tolerance parameters, intensity matching clauses). Construct a tokenizer that lexically analyzes input query strings into recognized tokens (keywords, literals, operators). Build a recursive descent parser or use a parser generator (ANTLR, PLY) that consumes the token sequence and produces a structured AST or query object. At each parse step, validate that clauses respect domain constraints (e.g., retention time and mass-to-charge filters are semantically coherent). Return the AST in a canonical, serializable format (JSON or pickled Python object) suitable for downstream query validation and execution across single spectra or entire data repositories.
Related tools
- ANTLR (Parser generator for constructing recursive descent parsers from formal grammars; generates lexer and parser from DSL grammar specification)
- PLY (Python Lex-Yacc) (Python-based parser generator for tokenization and AST construction from domain-specific query syntax)
- MassQL reference implementation (Reference Python API demonstrating tokenization, parsing, and AST construction for SQL-inspired mass spectrometry queries; includes msql_engine.process_query() for query execution) — https://github.com/mwang87/MassQueryLanguage
Examples
from massql import msql_engine; results_df = msql_engine.process_query('QUERY scaninfo(MS2DATA) WHERE MS1MZ=100', 'input_file.mzML')
Evaluation signals
- AST structure reflects the syntactic hierarchy and operator precedence of the query language; nested clauses are correctly subordinated (e.g., WHERE predicates are children of QUERY nodes).
- All terminals in the parse tree are valid tokens from the domain; no spurious or unrecognized tokens remain.
- Roundtrip property: serializing the AST back to query syntax and re-parsing should produce an isomorphic tree.
- Query validation passes: the AST respects domain constraints (e.g., mass-to-charge filters have valid numeric ranges, tolerance parameters are positive, intensity match clauses are semantically coherent).
- Downstream execution engines (query engines) can traverse the AST without ambiguity to generate results; no missing or malformed subtrees.
Limitations
- Parser construction requires a stable, complete formal grammar; incomplete or ambiguous grammar specifications lead to parse conflicts and incorrect AST structures.
- Performance degrades for deeply nested queries (e.g., complex boolean expressions with many AND/OR clauses) or very long token streams; recursive descent parsers may hit stack limits.
- Error recovery and diagnostic messaging depend on parser implementation; generic parser generators may produce unhelpful error messages for domain experts unfamiliar with parsing concepts.
- Domain-specific assumptions (e.g., mass spectrometry filter semantics) must be encoded in the grammar or as post-parse validation; the parser alone cannot enforce domain correctness without explicit constraints.
Evidence
- [other] Construct a parser (e.g., using recursive descent or parser generator such as ANTLR or PLY) that consumes tokens and produces a structured abstract syntax tree (AST) or query object representation.: "Construct a parser (e.g., using recursive descent or parser generator such as ANTLR or PLY) that consumes tokens and produces a structured abstract syntax tree (AST) or query object representation."
- [other] Validate the parse tree against MassQL design principles: expressiveness (captures complex MS patterns), scalability (handles single spectrum to repository queries), and readability (natural MS semantics).: "Validate the parse tree against MassQL design principles: expressiveness (captures complex MS patterns), scalability (handles single spectrum to repository queries), and readability (natural MS"
- [other] Return the parse tree in a canonical format (e.g., JSON or pickled Python object) for downstream query execution or analysis.: "Return the parse tree in a canonical format (e.g., JSON or pickled Python object) for downstream query execution or analysis."
- [readme] MassQL is inspired by SQL, but it attempts to bake in assumptions of mass spectrometry to make querying much more natural for mass spectrometry users.: "MassQL is inspired by SQL, but it attempts to bake in assumptions of mass spectrometry to make querying much more natural for mass spectrometry users."
- [readme] Language Grammar, Reference Implementation Python API, Command line Utility to execute: "Language Grammar, Reference Implementation Python API, Command line Utility to execute"
1---2name: abstract-syntax-tree-construction3description: Use when you have a tokenized sequence of domain-specific language tokens and need to construct a hierarchical, unambiguous representation that can be validated against language design principles (expressiveness, precision, scalability, readability) and passed to downstream execution engines.4license: CC-BY-4.05---67# abstract-syntax-tree-construction89## Summary1011Parse domain-specific query language strings into structured abstract syntax tree (AST) representations that capture the hierarchical syntax and semantics of the query. This skill is essential when implementing a domain-specific language (DSL) interpreter that needs to transform human-readable query expressions into machine-processable intermediate representations for validation and execution.1213## When to use1415Apply this skill when you have a tokenized sequence of domain-specific language tokens and need to construct a hierarchical, unambiguous representation that can be validated against language design principles (expressiveness, precision, scalability, readability) and passed to downstream execution engines. Specifically, use this when building a parser for SQL-inspired query syntax extended with domain-specific assumptions (e.g., mass spectrometry-specific filters like mass-to-charge ratio, retention time, intensity thresholds).1617## When NOT to use1819- Input query is already in a pre-parsed, canonical intermediate format (JSON, protobuf) — proceed directly to validation or execution.20- Query syntax is unambiguous, fully deterministic, and requires no hierarchical decomposition — a simple state machine or regex-based matcher may suffice.21- The domain-specific language has no formal grammar definition or the grammar is under active revision — defer AST construction until the grammar is stabilized.2223## Inputs2425- tokenized query string (sequence of lexical tokens from domain-specific query language)26- formal grammar definition (BNF or EBNF describing syntax and operator precedence)27- mass spectrometry query expressions (MS1MZ, MS2DATA, retention time, intensity filters, tolerance parameters)2829## Outputs3031- abstract syntax tree (AST) or query object representation32- canonical serialization (JSON or Python pickle) of the parse tree33- structured query object ready for execution or analysis3435## How to apply3637Begin by defining a formal grammar capturing the domain-specific language syntax and mass spectrometry-specific operators (e.g., MS1MZ, MS2DATA, tolerance parameters, intensity matching clauses). Construct a tokenizer that lexically analyzes input query strings into recognized tokens (keywords, literals, operators). Build a recursive descent parser or use a parser generator (ANTLR, PLY) that consumes the token sequence and produces a structured AST or query object. At each parse step, validate that clauses respect domain constraints (e.g., retention time and mass-to-charge filters are semantically coherent). Return the AST in a canonical, serializable format (JSON or pickled Python object) suitable for downstream query validation and execution across single spectra or entire data repositories.3839## Related tools4041- **ANTLR** (Parser generator for constructing recursive descent parsers from formal grammars; generates lexer and parser from DSL grammar specification)42- **PLY (Python Lex-Yacc)** (Python-based parser generator for tokenization and AST construction from domain-specific query syntax)43- **MassQL reference implementation** (Reference Python API demonstrating tokenization, parsing, and AST construction for SQL-inspired mass spectrometry queries; includes msql_engine.process_query() for query execution) — https://github.com/mwang87/MassQueryLanguage4445## Examples4647```48from massql import msql_engine; results_df = msql_engine.process_query('QUERY scaninfo(MS2DATA) WHERE MS1MZ=100', 'input_file.mzML')49```5051## Evaluation signals5253- AST structure reflects the syntactic hierarchy and operator precedence of the query language; nested clauses are correctly subordinated (e.g., WHERE predicates are children of QUERY nodes).54- All terminals in the parse tree are valid tokens from the domain; no spurious or unrecognized tokens remain.55- Roundtrip property: serializing the AST back to query syntax and re-parsing should produce an isomorphic tree.56- Query validation passes: the AST respects domain constraints (e.g., mass-to-charge filters have valid numeric ranges, tolerance parameters are positive, intensity match clauses are semantically coherent).57- Downstream execution engines (query engines) can traverse the AST without ambiguity to generate results; no missing or malformed subtrees.5859## Limitations6061- Parser construction requires a stable, complete formal grammar; incomplete or ambiguous grammar specifications lead to parse conflicts and incorrect AST structures.62- Performance degrades for deeply nested queries (e.g., complex boolean expressions with many AND/OR clauses) or very long token streams; recursive descent parsers may hit stack limits.63- Error recovery and diagnostic messaging depend on parser implementation; generic parser generators may produce unhelpful error messages for domain experts unfamiliar with parsing concepts.64- Domain-specific assumptions (e.g., mass spectrometry filter semantics) must be encoded in the grammar or as post-parse validation; the parser alone cannot enforce domain correctness without explicit constraints.6566## Evidence6768- [other] Construct a parser (e.g., using recursive descent or parser generator such as ANTLR or PLY) that consumes tokens and produces a structured abstract syntax tree (AST) or query object representation.: "Construct a parser (e.g., using recursive descent or parser generator such as ANTLR or PLY) that consumes tokens and produces a structured abstract syntax tree (AST) or query object representation."69- [other] Validate the parse tree against MassQL design principles: expressiveness (captures complex MS patterns), scalability (handles single spectrum to repository queries), and readability (natural MS semantics).: "Validate the parse tree against MassQL design principles: expressiveness (captures complex MS patterns), scalability (handles single spectrum to repository queries), and readability (natural MS"70- [other] Return the parse tree in a canonical format (e.g., JSON or pickled Python object) for downstream query execution or analysis.: "Return the parse tree in a canonical format (e.g., JSON or pickled Python object) for downstream query execution or analysis."71- [readme] MassQL is inspired by SQL, but it attempts to bake in assumptions of mass spectrometry to make querying much more natural for mass spectrometry users.: "MassQL is inspired by SQL, but it attempts to bake in assumptions of mass spectrometry to make querying much more natural for mass spectrometry users."72- [readme] Language Grammar, Reference Implementation Python API, Command line Utility to execute: "Language Grammar, Reference Implementation Python API, Command line Utility to execute"
HolobiomicsLab 