Balisage Paper: Pulse, Parse, and Ponder

Introduction

Nuclear Magnetic Resonance (NMR) spectroscopy is a powerful analytical technique that capitalizes on the magnetic properties of certain atomic nuclei Cavanagh, et al, 1996. At its core, NMR involves placing a material sample in a strong external magnetic field, exciting it with radio-frequency (RF) pulses, and detecting the resulting signal as the nuclei in the material relax. This phenomenon is the basis for the diagnostic technique of Magnetic Resonance Imaging (MRI) which is a useful complement to X-ray devices, as MRI has good contrast for soft tissues.

A typical NMR (or MRI) experiment involves repeatedly exciting the nuclei in the sample with a complex sequence of tens to hundreds of pulses at multiple frequencies. Each time the so-called pulse sequence is applied to the sample (called a “scan”), it is done with slightly different parameters, such as durations of delays and the lengths, powers, and phases of pulses. By analyzing how the resulting signals vary with those parameters, a scientist can determine information about the chemical bonding and spatial organization of the molecules in the samples.

The design and description of those pulse sequences is very complex; enumeration of the thousands to millions of parameter values for each experiment would be prohibitively costly in time and effort. To facilitate pulse sequence design and specification, several custom programming languages have been devised.

Pulse programs act as both a description of an experiment procedure and, when combined with a parameter file for a particular execution, a proxy record of the exact sequence of pulses and data measurements that produced a particular a data file. Currently the most common language used for writing these pulse programs is the Bruker^[1] pulse programming language, which has been developed over several decades to support the operation of Bruker-manufactured NMR spectrometers.

A standardized, structured representation of pulse code would enable new capabilities and make others substantially faster. Currently, ensuring consistency between pulse sequences described in scientific publications and their practical execution on spectrometers necessitates substantial expertise. Experts are required to meticulously compare textual descriptions with the actual pulse code to verify that the experiment functions as expected. This task is inherently prone to inaccuracies and is a considerable demand on time. Processing pulse code into structured data that can then be analyzed and transformed in a uniform manner would enable automatic comparison of different versions of an experiment, conversion of pulse code for use with experiment simulators, automatic determination of reasonable data processing parameters, annotation of the data for each scan with the exact RF that produced it, and could be the first step towards more efficient and partially automated authoring of pulse code.

To perform the parsing of Bruker pulse code, we chose to use Invisible XML Pemberton, 2021. The Invisible XML (iXML) specification describes an extended Backus-Naur Form (EBNF) syntax for specifying context-free grammars and specifies how a parameterized parser should take an input file and an input grammar and produce an annotated parse tree in XML format. Notably, iXML parsers are single-pass and do not perform lexical analysis before parsing. This approach has the advantage that the complete specification for the language and the details of the parse tree output format can be specified in a single file. However, it sacrifices the known advantages of the separation of lexical analysis and parsing that have been identified in compiler construction.

An important detail of the iXML specification is its handling of ambiguity in parse trees Tovey Walsh, 2023. Version 1.0 of the iXML specification requires that compliant parsers report if the parse of an input file is ambiguous; however, they are not required to return all possible parse trees and the specification does not specify how a single parse tree should be chosen from the possibilities. iXML compliant parsers are insensitive to the order of production rules in a grammar, which is used in some parsers to implicitly define precedence. However, pragmas have been introduced by Hillman et al. Hillman, 2022 as a mechanism for imparting extra information to the parser. These pragmas can be used to indicate priorities among ambiguous parsing options, providing a nuanced control over the parsing process; but, at present, pragmas are not standardized and are implementation-specific Tovey Walsh, 2023.

In this work, we will detail the Bruker Pulse Programming language, our approach to writing a grammar to parse it in iXML, and an assessment of iXML for use in this case.

#define ACQ_START1(phref1,phrec1) (de adc1 phrec1 syrec1) (1u 1u phref1:r):f1

"d0=in0/2-larger(p2,p4)/2-p21*2/3.1416"

d0 p1 ph1 d0

#include <CHN_defs.incl>
#include <trigg.incl>

; declarations of user-defined commands
define delay ONTIME
define loopcounter T1evo
define pulse mixing

; relations evaluated at compile time
"mixing=(l1*TauR)"
"acqt0=-(p1*2/3.1416)-0.5u"
…
; macro language conditional inclusion
#ifdef CDC
"T1evo=larger(td1,cnst30)"
"d30=T1evo*(in30+2u)"
#endif
; end of setup section

Prepare, ze ; start of experiment section, line labeled as "Prepare"

; relations evaluated at run time
"d30=d30/2"
"ONTIME=aq+d0+d30+p15"

; conditional inclusion of pulse sequence commands
#ifndef lacq
#include <acq_prot.incl>
#include <ONTIME_prot.incl>
#endif
…
Start, 30m  do:H ; Line is labeled "Start".
                 ; with 30 millisecond delay, during which
                 ; the "do" command is executed on channel H 
  d1
  trigg
  1u fq=0.0:H
; core-language conditional statement, with relation
; as the condition
if "l0>0" {
  "d51=d0-2u"
}
  (p3  pl2 ph1):H ; execute pulse of length P3, at power level PL2, with phase PH1, on channel H
  (p15:sp41 ph2):C  (p15:sp40 ph0):H ; simultaniously execute pulses on channels C and H
…
  (mixing ph20 pl14):H ; execution of user-defined pulse "mixing"
  (p1 pl1 ph4):C  (0.5u pl12):H
  0.5u cpds2:H
gosc ph31 ; cause the receiver to start measurement, with phase PH31, into a buffer
1m do:H
lo to Start times ns ; statement causing program execution to jump to the line labeld "Start"

; mc macro which writes buffered data to file #0, calculates changes to several parameters, and jumps execution to the line labeled "Start", among other actions.
30m mc #0 to Start
  F1PH(calph(ph3, -90), caldel(d0, +in0) & caldel(d30, -in30) & calclc(l0, 1))
HaltAcqu, 1m
Exit ; end of experiment section
; start of phase cycle definitions
ph2 = {0}*8 {2}*8 ; phase cycle definition using condensed syntax
ph3 = 1 1 3 3 ; phase cycle definition using literal syntax
ph31= 2 0 1 3  0 2 3 1
      0 2 3 1  2 0 1 3

Approach to Grammar Construction

The lack of specification and incompleteness of available documentation meant that the grammar had to be inferred from example, but because automated inference of context-free grammars form examples is impractical, the grammar had to be constructed through a combination of intuition and trial and error. Initial rules were written according to guidelines in Bruker documentation, but unspecified behavior had to be determined from example code. To assist with development and testing, a corpus of test code was compiled from multiple sources including published pulse programs, pulse programs uploaded to the BioMagResBank Ulrich, et al., 2008, code shared on the websites of NMR researchers, and examples available on Github (https://github.com). Together this constitutes approximately 350,000 lines of pulse code spread across about 2000 files.

Because a pulse program is both a procedure and an experimental record, it is beneficial to capture as much information as possible in the parse tree by exploiting knowledge about customary usage. However, when command types and other information cannot be determined with a context-free grammar, it is still worthwhile to include every token in the parse tree with as much specificity as possible. Our approach is inspired by other work such as SuperC Gazillo & Grimm, 2012, which, among other strategies, parses C preprocessor directives and C code together by adding rules that capture patterns of customary usage of macros but includes base cases for code that requires context-sensitivity or other information. This approach amounts to adding special cases to the grammar that do not change the language it recognizes, but infers additional semantic information which is included in the resulting parse tree.

Challenges Faced

#if defined(CALC_P0) || defined(ERNSTANG)
...
#endif

"if ( INCR1 > in0 ) { in14 = 0; } else { in14=in0-INCR1; }"

if (l5 > 2) {
p1 ph1
}
else {
p1 ph2
}

if "l0 % 2 == 1" {
...
}

F1I(ip3*2, 2, ip13*2, 2)
F1PH(ip4 & ip5 & ip29, id0)

d12 fq=cnst18(bf ppm):f1

; …

define pulse mixing

; …

"mixing=(l1*TauR)"

; …

; start of pulse sequence commands
1, ze

; …

mixing ph20 pl14
; …

manifest_append    <F1 type="Diff_VarGrad" subType="CONVEX" gradList="$gpnam31" littleDelta="$gradPulseDur" bigDelta="$bigDelta" 
    gradAmpFactor="$cnst52" gradShapeIntegFac="$cnst53" gradCalib="$cnst63" C="$cnst7">
    <comment>
        Modified Stejskal Tanner equation for CONVEX applies
        g[i] = gradList[i]*gradAmpFactor*gradCalib 
        b[i] = pow(2*Pi*gamma*g[i]*gradShapeIntegFac*littleDelta, 2)*(bigDelta*(1 + C) - littleDelta*(1 + pow(C, 2))/3)
        I[i]/I0 = exp(-b[i]*D)
    </comment>
</F1>manifest_end

 
   manifest_append_statement: -"manifest_append",-not_manifest_end*,-"manifest_end".
           -not_manifest_end:      (~["m"] | m_not_anifest_end).
          -m_not_anifest_end: "m", (~["a"] | a_not_nifest_end).
           -a_not_nifest_end: "a", (~["n"] | n_not_ifest_end).
            -n_not_ifest_end: "n", (~["i"] | i_not_fest_end).
             -i_not_fest_end: "i", (~["f"] | f_not_est_end).
              -f_not_est_end: "f", (~["e"] | e_not_st_end).
               -e_not_st_end: "e", (~["s"] | s_not_t_end).
                -s_not_t_end: "s", (~["t"] | t_not__end).
                 -t_not__end: "t", (~["_"] | __not_end).
                  -__not_end: "_", (~["e"] | e_not_nd).
                   -e_not_nd: "e", (~["n"] | n_not_d).
                    -n_not_d: "n", (~["d"]).

Strategies for Implementing Negative Matches in iXML

The problem of implementing negative matches for any rule in a context-free grammar is intractable because context-free languages are not closed under complement Hopcroft, et al., 2000. However, regular languages are closed under complement, union, and intersection. Because regular languages are recognized by deterministic finite state automata (DFSAs), it is possible to build a DFSA that recognize a string as a member of a regular language A unless it is also a member of regular language B, by using standard methods to construct the complement of the DFSA recognizing strings in B, and intersecting it with the DFSA that recognizes strings in A.

For the simplified problem of recognizing identifiers consisting of lower case Latin letters (identifier: ["a"-"z"].) that are not the keywords "foo", "bar", or "baz" (keyword: "foo"| ("ba",("r"|"z")).), the problem is efficiently solved by constructing a Deterministic *Acyclic* Finite State Automaton (DAFSA), using an algorithm described by Daciuk et al. Daciuk, et al., 2000, for {"foo","bar","baz"} Figure 1, and making a few modifications:

Figure 1: Deterministic *Acyclic* Finite State Automaton.

The result Figure 2 is a DFSA that is "complete" with respect to the set of all strings that are valid keywords or identifiers, and for which keywords end in the "keyword" state and non-keyword identifiers end in the "identifier" state.

Figure 2: Augmented Deterministic *Acyclic* Finite State Automaton.

A DFSA recognizing a regular language can be converted into iXML by writing production rules for each state with alternatives for all incoming transitions, each consisting of the nonterminal for the state it leads from, followed by one of the symbols allowed by that transition. Implementing this procedure for the "foo", "bar", "baz" example, results in the following iXML grammar:

   document: (keyword|identifier)++#a. 
    keyword: state_2,["r";"z"]| state_4,"o". 
 identifier: id_prefix| state_1| state_2| state_3| state_4. 
 -id_prefix: start,["a";"cde";"g"-"z"]| 
             state_1,["b"-"z"]| 
             state_2,["a"-"q";"s"-"y"]| 
             state_3,["a"-"n";"p"-"z"]| 
             state_4,["a"-"n";"p"-"z"]| 
             -keyword,["a"-"z"]| 
             id_prefix,["a"-"z"]. 
   -state_4: state_3,"o". 
   -state_3: start,"f". 
   -state_2: state_1,"a". 
   -state_1: start,"b". 
     -start: .

When used to parse the string,

"foo
bar
baz
fo
foot
bat
tar"

that grammar produces the following parse tree,

<document>
   <keyword>foo</keyword>
   <keyword>bar</keyword>
   <keyword>baz</keyword>
   <identifier>fo</identifier>
   <identifier>foot</identifier>
   <identifier>bat</identifier>
   <identifier>tar</identifier>
</document>

This approach to construct rules for recognizing non-keyword identifiers introduces an extra step in the process of authoring a grammar but is ultimtely a minor inconvenience once implemented. In the Bruker language grammar, it greatly decreases the verbosity of hand-written rules. The tension between simplicity and expressivity is not unique to iXML. A project with some parallels to iXML is that of XML Schema Definition (XSD) and simpler schema languages. XSD is a comprehensive language for defining the structure and data types of XML documents, capable of handling both simple and complex schemas. At the same time, RELAX NG was developed to offer a different approach, focusing on a more concise and flexible syntax. Both XSD and RELAX NG were designed to meet specific needs and use cases within the XML community. Invisible XML's simplicity and generality are significant strengths that could be impacted by the inclusion of high-level features like negative matches. Using iXML as a target for code generation is a possible strategy for enhancing its application to complex problems and has proved useful in dealing with the large number of keywords present in Bruker pulse programs.

Comparison of iXML to other Parsing Tools

Parsing of text is a widely-explored area with a long history. Several approaches have gained popularity with various advantages and disadvantages. Traditional parser generators like Bison Donnelly & Stallman, 2021, use grammars specified in Backus-Naur Form (BNF) or its variants and produce parsers by generating code in various programming languages. This automation significantly reduces development time and produces consistently effective and efficient parsers, but it introduces rigidity and requires generation and compilation for each new grammar or change to an existing grammar Aho, et al., 2006.

Parsing Expression Grammars (PEGs) effectively eliminate ambiguity in grammars by greedily choosing the first rule that matches the text being parsed Ford, 2004. This approach, utilized by tools like PEG.js, and by CPython for parsing Python source code, facilitates a sometimes more intuitive handling of language constructs that might pose complexities for traditional BNF-based parsers. It also has the distinct advantage of not requiring compilation, significantly speeding up grammar development. However, its reliance on backtracking can cause lower efficiency than parsers based on Earley or the LR-family or parsing algorithms.

Parametrized parsers, like iXML, in contrast to parsers from hand-written or generated parsers, take a grammar as an input alongside the text to be parsed Pemberton, 2019. This approach could sacrifice some efficiency by making it difficult to implement certain optimizations but gains in flexibility by having a uniform interface that is independent of the language being parsed. iXML, specifically, takes a grammar defined in a single text file and outputs parse trees in XML, which has a rich ecosystem of libraries and tools that facilitate downstream use. The Tree-sitter parser generator brings together an interesting combination of features; it has graceful error handling, built-in support for composition, and a uniform API for interacting with the parse tree Brunsfeld, et al., 2024. Like iXML, Tree-sitter aims to address the proliferation of highly customized parsers and the resulting difficulty of dealing with their many different interfaces, restrictions, and dependencies. As a parser generator, Tree-sitter has a build step that takes an input grammar, specified in JavaScript, and generates a parser as a dependency-free library written in C, whose functions can then be called from many different languages. However, this approach has the disadvantage, shared by all parser generators, that every new grammar or modification to an existing grammar requires going through a build step that produces a separate parser. Having a separate library for each language causes increased space requirements and, when Tree-sitter itself is updated, requires rebuilding every parser to take advantage of any new features or bug fixes. However, despite these difficulties, Tree-sitter has become very popular, especially as a backend for providing syntax highlighting, indentation, formatting, and other features in integrated development environments, where its fast incremental parsing and error handling allow the parse tree to be maintained alongside code that is being actively edited, with minimal latency. The two main advantages that Tree-sitter has over iXML with regards to the problems encountered in implementing a grammar for the Bruker Pulse Programming Language are its support for complex rules, enabled by code generation, and its support for grammar composition.

Tree-sitter grammars are specified in JavaScript, which is then executed to produce a new grammar in a BNF-like JSON syntax. This design choice allows Tree-sitter to implement complex grammatical constructs such as regular expressions, negative matches, and priority, which are then translated into a simpler grammatical syntax. It also means that the grammar author has access to JavaScript to ease in the implementation of repetitive or cumbersome grammatical rules. This approach, using a BNF-style grammar as the target of code generation, is one possible avenue that could be used to add higher level features to iXML. It has the advantage of making grammar authoring easier but, adds extra layers of complexity and latency while decreasing the readability of the resulting grammar. However, it maintains iXML's advantages in terms of a uniform parse tree representation and the benefits of using a single parsing program for many languages.

Tree-sitter's approach to grammar composition could be more difficult to adapt for use with iXML. Tree-sitter uses "queries" implemented as S-expressions, to describe patterns in the parse tree that should be identified and actions to perform when the patterns are found. Grammar composition is accomplished by writing queries that recognize where source code of a different language, for instance a SQL query specified as a string inside of a Python program, might be found and adds a trigger for the identified text to be parsed by the appropriate parser for that language.

def get_data(connection):
    query = "SELECT * FROM data WHERE value > 10"
    result = connection.execute(query)
    return result.fetchall()

Here, if the Python parser is augmented with a rule that indicates that a string may contain code in a different language, it could be identified as valid SQL syntax, and parsed as such. This sort of behavior could be implemented in iXML by adding the ability to include grammars in other grammars, or through a pragma-based syntax. This kind of ability has many other applications; continuing with Python as an example, it is common for a script to contain regular expressions, HTML, URLs, etc. Supporting grammar composition would have the added benefits of increasing grammar modularity and decreasing repetition.

Future Work

The ability to parse Bruker pulse code into a structured representation will enable many applications that were previously laborious or impossible. A practical next step would be to develop a procedure for converting the parse tree into an abstract syntax tree (AST) to facilitate the development of an interpreter that could act as a "virtual spectrometer". The ability to simulate code execution would allow researchers to recreate the sequence of RF pulses and the layout of measurements in the data file without immediate access to a spectrometer or tedious manual interpretation.

Both the syntax and the customary usage of Bruker Pulse Programming Language have evolved over its lifetime, and programming styles can vary, but the conceptual structure of pulse sequences has remained fairly consistent. Normalizing an AST into a more abstract representation of the pulse sequence would facilitate comparison across pulse sequence and pulse programming language versions. A sufficiently general pulse sequence representation could be used as a canonical representation, not just for pulse programs for Bruker spectrometers, but for pulse code written for any current or historical spectrometer. The ability to apply the rich ecosystem that exists around XML promises to greatly accelerate this and other parse tree transformations.

NMR spectroscopy, especially as applied to structural biology and metabolomics, suffers from fragmentation and a history of limited exchange of both pulse code and experimental data. As the rate of scientific development and publishing accelerates, the need for tools that help automate the comparison and interchange of ideas and techniques becomes even more important.

Conclusions

Invisible XML proved to be an effective tool for parsing Bruker pulse code. While it lacks some higher-level features common to other parsing tools, its simplicity made it relatively easy to understand errors, and the lack of a build step made the iterative process of editing and testing a grammar efficient . While the problem of inferring a grammar from examples is complex, iXML adds very little extra cognitive load to the grammar developer. The concise syntax of iXML makes it an attractive target for code generation, where it plays a role similar to an intermediate language in analogy to some compiler designs. The question of whether higher level grammar constructs should be implemented via code generation, as pragmas, or as additions to the iXML grammar syntax requires careful consideration. As it stands, invisible XML is simple and powerful enough that, once it is supported and integrated more widely, it could supplant regular expressions for many tasks, with the benefit of much greater clarity.

Scientific measurements are increasingly performed and collected using complex computerized equipment, often controlled by proprietary software. Often, the details of the measurement are hidden from the experimenter and readers of resulting papers, intentionally or not, by incomplete documentation, or by a lack of expertise in interpretation of the configuration files and the particular measurement device. Tools like invisible XML, that make configuration files and control programs for scientific devices more accessible and interpretable consequently improve the accessibility, reproducibility, and long-term usefulness of measurements and the conclusions they support.

Acknowledgements

This research was conducted as part of the NMRbox project, supported by the U.S. National Institutes of Health under grant number NIH/NIGMS 1P41GM111135, and as part of the Network for Advanced NMR, supported by the U.S. National Science Foundation under grant number 1946970.