Making parsers with higher order functions

Goal of the package

The goal of this package is to simplify the creation of transparent parsers for structured text files generated by machines like laboratory instruments. For example, we use the package to construct parsers for files generated by plate readers. The data generated by these instruments can usually be exported to text or spreadsheet files. Such files consist of lines of text organized in higher-order structures like headers with metadata and blocks of measured values, etc.. It’s often convenient to analyze the data in a program like R. To be able to do that you have to have a parser that processes these files and creates R-objects as output. The parcrpackage simplifies the task of creating such parsers.

Higher order functions in R

The parsers that are created with this package make extensive use of functional programming. If this topic is new to you then please read about Functional Programming, in particular the chapters Function Factories and Function Operators, in Hadley Wickham’s book Advanced R.

Creating parser combinators in R to parse text files

The parcr package contains a set of functions that allow you to create simple parsers with higher order functions, functions that can take functions as input and have functions as output. These are sometimes called combinators. The ideas behind the package are described in a paper by Hutton (1992). A number of the functions described in this paper are implemented with modifications in the current package. The package was also heavily inspired by the Ramble package which is written in the same vein, but without the explicit parsing of structured text files in mind.

A simple example of using parser combinators

Please realize that every function described below is a higher order function: their output is a function. In its turn, this function can take a character vector as its input. For example, literal("a") yields a function. To use that function as a parser you have to provide it with a character vector, the object that needs to be parsed, as input:

literal("a")(c("a","att"))

This parser tests whether the next element in its input is literally the string “a”. It will succeed in the example above, but will only consume the first element of its input and then stop. However, you can also use a higher order function like literal("a") as input to other higher order functions to create more complex parsers. For example, the function then takes two parsers p1 and p2 as arguments, then(p1, p2) and applies them in sequence to the input. In the parcr package the function is implemented in the infix form %then% which makes parser constructs better readable. The composite parser:

literal("a") %then% literal("att")

looks for an element with string “a” followed by an element with string “att”. Its application to the same vector:

(literal("a") %then% literal("att"))(c("a","att"))

will completely consume the input. In this way, using a number of standard parsers defined in the package, you can quickly construct flexible parsers taking complex input. Furthermore, the functions also allow you to construct a desired R object as output while parsing.

The functions in the parcr package

We will now discuss all of the parser combinator functions present in the package. You should also study their help pages. In particular the Pseudocode listed for each of them should help you to understand their properties.

The fundamental parsers

The six fundamental parsers allow you to construct a parser that will completely consume input, or to fail when the input does not satisfy the specifications of the parser.

succeed("A")("abc")
#> $L
#> $L[[1]]
#> [1] "A"
#> 
#> 
#> $R
#> [1] "abc"
succeed(data.frame(title="Keisri hull", author="Jaan Kross"))(c("Unconsumed","text"))
#> $L
#> $L[[1]]
#>         title     author
#> 1 Keisri hull Jaan Kross
#> 
#> 
#> $R
#> [1] "Unconsumed" "text"

fail()("abc")
#> []

literal('abc')(c('abc','def'))
#> $L
#> $L[[1]]
#> [1] "abc"
#> 
#> 
#> $R
#> [1] "def"

starts_with_a <- function(x) {grepl("^a", x)}
satisfy(starts_with_a)(c('abc','def'))
#> $L
#> $L[[1]]
#> [1] "abc"
#> 
#> 
#> $R
#> [1] "def"

literal('a')(c('ab','a'))
#> []

(literal("a") %then% literal("att") %then% eof())(c("a","att"))
#> $L
#> $L[[1]]
#> [1] "a"
#> 
#> $L[[2]]
#> [1] "att"
#> 
#> 
#> $R
#> list()

(literal("a") %then% literal("att"))(c("a","att"))
#> $L
#> $L[[1]]
#> [1] "a"
#> 
#> $L[[2]]
#> [1] "att"
#> 
#> 
#> $R
#> character(0)

(literal('A') %or% satisfy(starts_with_a))(c('abc','def'))
#> $L
#> $L[[1]]
#> [1] "abc"
#> 
#> 
#> $R
#> [1] "def"

(literal('A') %then% satisfy(starts_with_a))(c('A', 'abc'))
#> $L
#> $L[[1]]
#> [1] "A"
#> 
#> $L[[2]]
#> [1] "abc"
#> 
#> 
#> $R
#> character(0)

(literal('>') %thenx% satisfy(starts_with_a))(c('>', 'abc'))
#> $L
#> $L[[1]]
#> [1] "abc"
#> 
#> 
#> $R
#> character(0)

Modifying the output of a parser

As said, the six fundamental parsers allow you to construct a parser that will completely consume input. However, when this parser succeeds its output will, apart from the fact that every element is put in a list, be equal to the input. In general, this is not very useful if you want to use the output in other code. Therefore, we have two functions that allow you to modify the output of successful parser. The basic functions for modifying output of a parser are:

• p %ret% c : when parser p is successful it returns the object c (a string or NULL).
• p %using% f : when parser p is successful function f() is applied to the input and its output is stored as the result.

Examples

(literal('a') %ret% "We have an 'a'")(c('a','b'))
#> $L
#> $L[[1]]
#> [1] "We have an 'a'"
#> 
#> 
#> $R
#> [1] "b"

(satisfy(starts_with_a) %using% toupper)(c('abc','d'))
#> $L
#> $L[[1]]
#> [1] "ABC"
#> 
#> 
#> $R
#> [1] "d"

Derived parsers

Derived parsers are constructed from the six fundamental parsers.

zero_or_one(satisfy(starts_with_a))(c('acc','aat','cgg'))
#> []

zero_or_more(satisfy(starts_with_a))(c('cat','gac','cct'))
#> $L
#> list()
#> 
#> $R
#> [1] "cat" "gac" "cct"

one_or_more(satisfy(starts_with_a))(c('att','aac','cct'))
#> $L
#> $L[[1]]
#> [1] "att"
#> 
#> $L[[2]]
#> [1] "aac"
#> 
#> 
#> $R
#> [1] "cct"

exactly(2, satisfy(starts_with_a))(c('att','aac','cct'))
#> $L
#> $L[[1]]
#> [1] "att"
#> 
#> $L[[2]]
#> [1] "aac"
#> 
#> 
#> $R
#> [1] "cct"

match_n(1, satisfy(starts_with_a))(c('att','aac','cct'))
#> $L
#> $L[[1]]
#> [1] "att"
#> 
#> 
#> $R
#> [1] "aac" "cct"

numbers <- function(x) {
  m <- gregexpr("[[:digit:]]+", x)
  matches <- as.numeric(regmatches(x,m)[[1]])
  if (length(matches)==0) {
    return(list()) # we signal parser failure when no numbers were found
  } else {
    return(matches)
  }
}

match_s(numbers)(" 101 12 187 # a comment on these numbers")
#> $L
#> $L[[1]]
#> [1] 101  12 187
#> 
#> 
#> $R
#> character(0)

starts_with_a <- function(x) grepl("^a",x[1])
# don's forget to use satisfy(), it turns starts_with into a parser
by_split(one_or_more(satisfy(starts_with_a)), ",", fixed = TRUE)("atggc,acggg,acttg")
#> $L
#> $L[[1]]
#> [1] "atggc"
#> 
#> $L[[2]]
#> [1] "acggg"
#> 
#> $L[[3]]
#> [1] "acttg"
#> 
#> 
#> $R
#> character(0)

by_symbol(literal(">") %thenx% one_or_more(literal("b")), finish = FALSE)(">bb")
#> $L
#> $L[[1]]
#> [1] "b"
#> 
#> $L[[2]]
#> [1] "b"
#> 
#> 
#> $R
#> character(0)

EmptyLine()("")
#> $L
#> $L[[1]]
#> [1] ""
#> 
#> 
#> $R
#> character(0)

Spacer()(c(" ","\t\t\t", "atgcc"))
#> $L
#> list()
#> 
#> $R
#> [1] "atgcc"

MaybeEmpty()(c("ggacc","gatccg", "atgcc"))
#> $L
#> list()
#> 
#> $R
#> [1] "ggacc"  "gatccg" "atgcc"

(literal("Interesting") %then% 
  Ignore() %then% 
  eof())(c("Interesting", LETTERS))
#> $L
#> $L[[1]]
#> [1] "Interesting"
#> 
#> 
#> $R
#> list()

Example application: a parser for fasta sequence files

As an example of a somewhat realistic application let’s try to write a parser for fasta-formatted files for mixed nucleotide and protein sequences.

Such a fasta file could look like the example below

>sequence_A
GGTAAGTCCTCTAGTACAAACACCCCCAAT
TCTGTTGCCAGAAAAAACACTTTTAGGCTA
>sequence_B
ATTGTGATATAATTAAAATTATATTCATAT
TATTAGAGCCATCTTCTTTGAAGCGTTGTC
TATGCATCGATC

>sequence_C
MTEITAAMVKELRESTGAGMMDCKNALSET
NGDFDKAVQLLREKGLGKAAKKADRLAAEG
ENEYKALVAELEKE

where the first two are nucleotide sequences and the last is a protein sequence¹.

Since fasta files are text files we could read such a file using readLines(). Below we simulate the result of reading the file above by loading the nuclfasta and protfasta data sets present in the package. The consist of character vectors.

data("fastafile")

We can distinguish the following higher order components in a fasta file:

• A fasta file: consists of one or more sequence blocks until the end of the file.
• A sequence block: consist of a header² and a nucleotide sequence or a protein sequence. A sequence block could be preceded by zero or more empty lines.
• A nucleotide sequence: consists of one or more nucleotide sequence strings.
• A protein sequence: consists of one or more protein sequence strings.
• A header is a string that starts with a “>” immediately followed by a title without spaces.
• A nucleotide sequence string is a string without spaces that consists entirely of symbols from the set {G,A,T,C}.
• A protein sequence string is a string without spaces that consists entirely of symbols from the set {A,R,N,D,B,C,E,Q,Z,G,H,I,L,K,M,F,P,S,T,W,Y,V}.

It now becomes clear what I mean when I say that the package allows us to write transparent parsers: the description above of the structure of fasta files can be translated straight into code for a Fasta() parser:

Fasta <- function() {
  one_or_more(SequenceBlock()) %then%
    eof()
}

SequenceBlock <- function() {
  MaybeEmpty() %then% 
    Header() %then% 
    (NuclSequence() %or% ProtSequence())
}

NuclSequence <- function() {
  one_or_more(NuclSequenceString())
}

ProtSequence <- function() {
  one_or_more(ProtSequenceString())
}

Notice that these elements are functions taking no input, hence the empty argument brackets () behind their names. They can take input when needed, for example to change their behavior (like match_n(), or see the other example below).

Now we need to define the string-parsers Header(), NuclSequenceString() and ProtSequenceString() that recognize and process these elements in the character vector fastafile. We use functions from stringr to do this in three helper functions, and we use match_s() to create parsers from these.

# returns the title after the ">" in the sequence header
parse_header <- function(line) {
  # Study stringr::str_match() to understand what we do here
  m <- stringr::str_match(line, "^>(\\w+)")
  if (is.na(m[1])) {
    return(list()) # signal failure: no title found
  } else {
    return(m[2])
  }
}

# returns a nucleotide sequence string
parse_nucl_sequence_line <- function(line) {
  # The line must consist of GATC from the start (^) until the end ($)
  m <- stringr::str_match(line, "^([GATC]+)$")
  if (is.na(m[1])) {
    return(list()) # signal failure: not a valid nucleotide sequence string
  } else {
    return(m[2])
  }
}

# returns a protein sequence string
parse_prot_sequence_line <- function(line) {
  # The line must consist of ARNDBCEQZGHILKMFPSTWYV from the start (^) until the
  # end ($)
  m <- stringr::str_match(line, "^([ARNDBCEQZGHILKMFPSTWYV]+)$")
  if (is.na(m[1])) {
    return(list()) # signal failure: not a valid protein sequence string
  } else {
    return(m[2])
  }
}

Then we define the parsers.

Header <- function() {
  match_s(parse_header)
}

NuclSequenceString <- function() {
  match_s(parse_nucl_sequence_line)
}

ProtSequenceString <- function() {
  match_s(parse_prot_sequence_line)
}

Now we have all the elements that we need to apply the Fasta() parser.

Fasta()(fastafile)
#> $L
#> $L[[1]]
#> [1] "sequence_A"
#> 
#> $L[[2]]
#> [1] "GGTAAGTCCTCTAGTACAAACACCCCCAAT"
#> 
#> $L[[3]]
#> [1] "TCTGTTGCCAGAAAAAACACTTTTAGGCTA"
#> 
#> $L[[4]]
#> [1] "sequence_B"
#> 
#> $L[[5]]
#> [1] "ATTGTGATATAATTAAAATTATATTCATAT"
#> 
#> $L[[6]]
#> [1] "TATTAGAGCCATCTTCTTTGAAGCGTTGTC"
#> 
#> $L[[7]]
#> [1] "TATGCATCGATC"
#> 
#> $L[[8]]
#> [1] "sequence_C"
#> 
#> $L[[9]]
#> [1] "MTEITAAMVKELRESTGAGMMDCKNALSET"
#> 
#> $L[[10]]
#> [1] "NGDFDKAVQLLREKGLGKAAKKADRLAAEG"
#> 
#> $L[[11]]
#> [1] "ENEYKALVAELEKE"
#> 
#> 
#> $R
#> list()

Apart from match_s(), we have used only the six fundamental parsers. Therefore, the output is almost the same as the parsed input. This is not very useful because it is difficult to extract the individual sequences and titles from it; we would have to write sort of parser again to process this output. To mend this, we have to modify the output of the parsers. The first thing that we will do is to let every sequence block be returned as an element of a list. To achieve this we extend the SequenceBlock parser by changing its output with the %using% operator:

SequenceBlock <- function() {
  MaybeEmpty() %then% 
    Header() %then% 
    (NuclSequence() %or% ProtSequence()) %using%
    function(x) list(x)
}

Now the result is a list of three lists, one for each sequence block.

Fasta()(fastafile)[["L"]]
#> [[1]]
#> [[1]][[1]]
#> [1] "sequence_A"
#> 
#> [[1]][[2]]
#> [1] "GGTAAGTCCTCTAGTACAAACACCCCCAAT"
#> 
#> [[1]][[3]]
#> [1] "TCTGTTGCCAGAAAAAACACTTTTAGGCTA"
#> 
#> 
#> [[2]]
#> [[2]][[1]]
#> [1] "sequence_B"
#> 
#> [[2]][[2]]
#> [1] "ATTGTGATATAATTAAAATTATATTCATAT"
#> 
#> [[2]][[3]]
#> [1] "TATTAGAGCCATCTTCTTTGAAGCGTTGTC"
#> 
#> [[2]][[4]]
#> [1] "TATGCATCGATC"
#> 
#> 
#> [[3]]
#> [[3]][[1]]
#> [1] "sequence_C"
#> 
#> [[3]][[2]]
#> [1] "MTEITAAMVKELRESTGAGMMDCKNALSET"
#> 
#> [[3]][[3]]
#> [1] "NGDFDKAVQLLREKGLGKAAKKADRLAAEG"
#> 
#> [[3]][[4]]
#> [1] "ENEYKALVAELEKE"

In principle, this output is easier to extract information from, but we can improve on it. First, we want the sequences to appear as one long string, not as separate character vectors corresponding to the lines in the sequence block. Therefore, we extend the NuclSequence and ProtSequence parsers collapsing their output:

NuclSequence <- function() {
  one_or_more(NuclSequenceString()) %using% 
    function(x) paste0(x, collapse = "")
}

ProtSequence <- function() {
  one_or_more(ProtSequenceString()) %using% 
  function(x) paste0(x, collapse="")
}

Then we get

Fasta()(fastafile)[["L"]]
#> [[1]]
#> [[1]][[1]]
#> [1] "sequence_A"
#> 
#> [[1]][[2]]
#> [1] "GGTAAGTCCTCTAGTACAAACACCCCCAATTCTGTTGCCAGAAAAAACACTTTTAGGCTA"
#> 
#> 
#> [[2]]
#> [[2]][[1]]
#> [1] "sequence_B"
#> 
#> [[2]][[2]]
#> [1] "ATTGTGATATAATTAAAATTATATTCATATTATTAGAGCCATCTTCTTTGAAGCGTTGTCTATGCATCGATC"
#> 
#> 
#> [[3]]
#> [[3]][[1]]
#> [1] "sequence_C"
#> 
#> [[3]][[2]]
#> [1] "MTEITAAMVKELRESTGAGMMDCKNALSETNGDFDKAVQLLREKGLGKAAKKADRLAAEGENEYKALVAELEKE"

This looks much better: we know that the first element in each of these lists is the title and the second element is the complete sequence. Then why not just attach a name to these elements? This would make extracting the information even easier. Furthermore, we also report whether the sequence is a nucleotide or a protein sequence by adding a type tag.

Header <- function() {
  match_s(parse_header) %using% 
    function(x) list(title = unlist(x))
}

NuclSequence <- function() {
  one_or_more(NuclSequenceString()) %using% 
    function(x) list(type = "Nucl", sequence = paste0(x, collapse=""))
}

ProtSequence <- function() {
  one_or_more(ProtSequenceString()) %using% 
    function(x) list(type = "Prot", sequence = paste0(x, collapse=""))
}

Finally, we have our desired output.

d <- Fasta()(fastafile)[["L"]]
d
#> [[1]]
#> [[1]]$title
#> [1] "sequence_A"
#> 
#> [[1]]$type
#> [1] "Nucl"
#> 
#> [[1]]$sequence
#> [1] "GGTAAGTCCTCTAGTACAAACACCCCCAATTCTGTTGCCAGAAAAAACACTTTTAGGCTA"
#> 
#> 
#> [[2]]
#> [[2]]$title
#> [1] "sequence_B"
#> 
#> [[2]]$type
#> [1] "Nucl"
#> 
#> [[2]]$sequence
#> [1] "ATTGTGATATAATTAAAATTATATTCATATTATTAGAGCCATCTTCTTTGAAGCGTTGTCTATGCATCGATC"
#> 
#> 
#> [[3]]
#> [[3]]$title
#> [1] "sequence_C"
#> 
#> [[3]]$type
#> [1] "Prot"
#> 
#> [[3]]$sequence
#> [1] "MTEITAAMVKELRESTGAGMMDCKNALSETNGDFDKAVQLLREKGLGKAAKKADRLAAEGENEYKALVAELEKE"

Let’s present the result more concisely using the names of these elements:

invisible(lapply(d, function(x) {cat(x$type, x$title, x$sequence, "\n")}))
#> Nucl sequence_A GGTAAGTCCTCTAGTACAAACACCCCCAATTCTGTTGCCAGAAAAAACACTTTTAGGCTA 
#> Nucl sequence_B ATTGTGATATAATTAAAATTATATTCATATTATTAGAGCCATCTTCTTTGAAGCGTTGTCTATGCATCGATC 
#> Prot sequence_C MTEITAAMVKELRESTGAGMMDCKNALSETNGDFDKAVQLLREKGLGKAAKKADRLAAEGENEYKALVAELEKE

Example application: parsers with parameters

In the examples above we showed how to create parsers without parameters. It is easy and useful to sometimes create parsers with parameters. The parameters are used to change the behavior of the parsers. For example, when writing online course material I use a simple structured question template that is converted to html when the syllabus is generated. It consists mostly of markdown content. Its parser makes use of parametrized parsers. The structure of such a question template document is as follows³:

#### INTRO
## Title about a set of questions

This is optional introductory text to a set of questions.
Titles preceded by four hashes are not allowed in a question template.

#### QUESTION
This is the first question

#### TIP
This would be a tip. tips are optional, and multiple tips can be given. Tips are
wrapped in hide-reveal style html elements.

#### TIP
This would be a second tip.

#### ANSWER
The answer to the question is optional and is wrapped in a hide-reveal html element.

#### QUESTION
This is the second question. No tips for this one

#### ANSWER
Answer to the second question

<optionally more questions>

I stored this example content in a vector qtemp to parse it later.

You notice the recurring structure of a header with four hashes #### and some text following it. These headers represent four types of elements: intro, question, tip and answer. Instead of writing separate parsers we could create a generic parser for such elements as:

HeaderAndContent <- function(type) {
    (Header(type) %then% Content()) %using% 
    function(x) list(list(type=type, content=unlist(x)))
}

Then we define each of the four parsers as:

Intro <- function() HeaderAndContent("intro")
Question <- function() HeaderAndContent("question")
Tip <- function() HeaderAndContent("tip")
Answer <- function() HeaderAndContent("answer")

The function Header(type) is defined as

Header <- function(type) satisfy(header(type)) %ret% NULL

# This must also be a generic function: a function that generates a function to 
# recognize a header of type 'type'
header <- function(type) {
  function(x) grepl(paste0("^####\\s+", toupper(type), "\\s*"), x)
}

The content consists of one or more lines not starting with ####, which includes empty lines. We discard trailing empty lines.

Content <- function() {
  (one_or_more(match_s(content))) %using%
    function(x) stringr::str_trim(paste0(x,collapse="\n"), "right")
}

content <- function(x) {
  if (grepl("^####", x)) list()
  else x
}

The complete template is defined as follows

Template <- function() {
  zero_or_more(Intro()) %then%
    one_or_more(QuestionBlock()) %then%
    eof()
}

where QuestionBlock() is defined using the previously defined elements as

QuestionBlock <- function() {
    Question() %then%
    zero_or_more(Tip()) %then%
    zero_or_one(Answer()) %using%
    function(x) list(x)
}

We can now parse the input. We wrap the Template() parser in the reporter() function to have proper error messaging and warnings, if applicable. Furthermore only the L-element, the parsed input, is returned.

reporter(Template())(qtemp)
#> [[1]]
#> [[1]]$type
#> [1] "intro"
#> 
#> [[1]]$content
#> [1] "## Title about a set of questions\n\nThis is optional introductory text to a set of questions.\nTitles preceded by four hashes are not allowed in a question template."
#> 
#> 
#> [[2]]
#> [[2]][[1]]
#> [[2]][[1]]$type
#> [1] "question"
#> 
#> [[2]][[1]]$content
#> [1] "This is the first question"
#> 
#> 
#> [[2]][[2]]
#> [[2]][[2]]$type
#> [1] "tip"
#> 
#> [[2]][[2]]$content
#> [1] "This would be a tip. tips are optional, and multiple tips can be given. Tips are\nwrapped in hide-reveal style html elements."
#> 
#> 
#> [[2]][[3]]
#> [[2]][[3]]$type
#> [1] "tip"
#> 
#> [[2]][[3]]$content
#> [1] "This would be a second tip."
#> 
#> 
#> [[2]][[4]]
#> [[2]][[4]]$type
#> [1] "answer"
#> 
#> [[2]][[4]]$content
#> [1] "The answer to the question is optional and is wrapped in a hide-reveal html element."
#> 
#> 
#> 
#> [[3]]
#> [[3]][[1]]
#> [[3]][[1]]$type
#> [1] "question"
#> 
#> [[3]][[1]]$content
#> [1] "This is the second question. No tips for this one"
#> 
#> 
#> [[3]][[2]]
#> [[3]][[2]]$type
#> [1] "answer"
#> 
#> [[3]][[2]]$content
#> [1] "Answer to the second question"