Rewrite parser in a formal grammer

[campb303]

The parser as it is functional but brittle. It needs to be rewritten as library code with exceptions, context managers and other abstracted schemes.

[benne238]

Rewriting the parser using a formal grammar

While we are able to successfully parse any given item and return an appropriate json structure, our current implementation of the ECNQueue parser is over 1000 lines along and is difficult to read. There are a couple of solutions to this problem:

1. Change how output is parsed by using a clearly defined set of rules and a formal grammar
2. Separate out the different functions of the ECNQueue into multiple scripts to make it more readable and more modular

Using a formal grammar

Currently, there is not a clearly defined set of easy to read rules in the parser; it is a series of if statements throughout the entire program, which makes readability difficult. However, the program makes sense logically:

1. Read one line from the item
2. Do something with that line based on its contents and if it is a delimiter
3. Read the next line

However this gets cumbersome as items grow in size, this logic must be done for each and every line. Using a formal grammar could alleviate two problems: readability and complexity

• This website gives a list of different parsers that could be used in a python program: https://tomassetti.me/parsing-in-python/
• This is the documentation website for PLY (one of the parsers mentioned in the website above): https://ply.readthedocs.io/en/latest/ply.html#lex-example

There a several things that stand out with how PLY (and some of the other parsers work):

1. They rely heavily on regex
2. They don't take input line by line, rather all input is passed as one large string with newlines included
3. With PLY specifically, all of the rules/delimiters are defined at the top

What this means for us is that a series of regular expressions would have to be developed to separate each section of an item, however, it has the potential to greatly reduce the length and complexity of the parser to one that is easy to read.
It is worth noting that it is possible to write the custom regex without using one of the parser packages in the list above

Separating the parser into multiple scripts

This step, depending on our implementation, should be done to reduce the amount of code in one script and increase the readability of the backend. In the parsers current state, it would make sense to separate the parser by function (and maybe sperate out the main parser function into multiple functions). Seeing how there will be a rewrite of the parser anyway, it might make more sense to not separate out the parser until a formal grammar is being used

[campb303]

Summary of Parsing In Python: Tools And Libraries mentioned above:

Parsers come in one of three variants:

1. Using an existing library if one exists.
2. Building a completely custom parser if deep integration is needed.
3. Use a parser generator by writing a grammar and generating the logic.

Parsers have a general structure of two tools:

1. A lexer that processes raw input and produces tokens
   ex: 1 + 1 => Lexer => NUM(1), OPERATOR("+", NUM(1)
2. A parser that matches patterns of tokens
   ex: ADD = NUM OPERATOR NUM; NUM(1), OPERATOR("+", NUM(1) => ADD

(Some parsers do not have a lexer and analyze raw input directly. These are called scannerless parsers.)

We currently have a custom parser built from scratch. However, it is slow and difficult to maintain. Out of the three options above, the first is not an option as there is likely no pre-written library code for this job that we haven't written and the second option is what we already have.

So the operative questions, in order, are:

1. If we choose to create a formal grammar and write a new parser, what tools should we use?
2. Do those tools present a significant performance increase?
3. Do those tools ease the maintenance process?

Related questions include:

• Are there others at ECN who have written parsers before and could help us?

[campb303]

Mark Senn is experienced with Perl, a language known for its data processing abilities, and has experience with writing parsers in Perl. He believes that Perl's parsing support would be a great candidate for the job.

A quick Google search shows very simple parsers with very little code. Ideally, I'd like to write a parser using Python to avoid have to (de)serialize data. More research is needed.

[benne238]

pyparsing

The python pyparsing module in python looks like a python native way to create custom parsing grammars directly in python.

Simple example:

# https://pyparsing-docs.readthedocs.io/en/latest/HowToUsePyparsing.html#hello-world
import pyparsing as pp

greet = pp.Word(pp.alphas) + "," + pp.Word(pp.alphas) + "!"
for greeting_str in [
            "Hello, World!",
            "Bonjour, Monde!",
            "Hola, Mundo!",
            "Hallo, Welt!",
        ]:
    greeting = greet.parseString(greeting_str)
    print(greeting)

Output:

['Hello', ',', 'World', '!']
['Bonjour', ',', 'Monde', '!']
['Hola', ',', 'Mundo', '!']
['Hallo', ',', 'Welt', '!']

This looks like a relatively easy module to use which should allow for the easier creation of a formal grammar that can parse out the different sections within a given item.
Due to the module being designed specifically in python there is no need to (de)serialize data from an outside parser.

Possible Issues

The documentation is not the greatest and some of the advanced features that we might want to use are poorly documented, so learning how to use this tool will have a learning curve that will be hindered by its poor documentation.

After attempting to code a basic program that would match to the string located between two delimiters, I found that using this tool was difficult due to the lack of information available on it. An example of a parser that might be used to separate out all of the "additional information from user" sections from a given item might look like this:

Example.py:

import pyparsing as pp
import string


info_from_user = (
    pp.Literal("=== Additional information supplied by user ===\n") + 
    pp.Word(string.printable, excludeChars="=") + 
    pp.Literal("===============================================\n")
)

reply = ("=== Additional information supplied by user ===\n"+
    "\n"+
    "Subject: stuff\n"+
    "From: someone\n"+
    "Date: some time\n"+
    "X-ECN-Queue-Original-Path: https://google.com\n"+
    "X-ECN-Queue-Original-URL: https://amazon.com\n"+
    "\n"+
    "Thanks.\n"
    "\n"+
    "===============================================\n"+
    "This shouldn't be matched"
)

print(info_from_user.parseString(reply))

One problem with this example though is that if an equal sign is included anywhere outside of the delimiter, then an exception will occur. While this has the potential to be useful, it is difficult to use.

[benne238]

Examples of Parsers

After talking with @campb303, there seems to be a particular interest in ANTLR due to its popularity. However, to get a sense of all the different parsers and the unique tools each (might) provide, a small write up with an example will be made in follow up messages to this issue

[campb303]

Next steps are to create an example that demonstrates a parser's benefits beyond what we already have.