I like building parsers. For those of you unfamiliar with the word, a parser is a program that interprets an input string, validating that it is of the correct form and extracting data from it when it is.
When I ran my own website for my students, before my university started using professional content management systems, I regularly wrote small data files to describe the behavior of the website and used parsers to read them.
Parsing techniques fascinate me. They all start with the notion of a grammar such as I was taught (in simple form) for the English language back in grade school. The language of acceptable input inevitably has structure and grammar seems to be an easy way to describe that structure. A sentence may be a simple noun verb for example, and a grammar rule for this one kind of sentence would be of the form sentence -> noun verb. For any meaningful language there are many grammar rules (called productions) using nonterminals (names of structures) and terminals (actual words or types of words).
The two ways I have learned to approach building a parser from a grammar are recursive descent, which I used as a webmaster, and LR parsing. Recursive descent would start at the top, such as with sentence above, and use a function to describe what its data should be in terms of noun and verb. You would also build functions for noun and verb and so on. The recursive part refers to building the top part of the parser in terms of lower parts of the parser. It allows (in my mind) simpler coding but it is capable of silent errors when there are choices of different kinds of sentence's and I didn't like that.
LR parsing is something whose theory I've enjoyed studying for several decades now. It processes an input string from the left (the L part of LR) and asks at each step can I replace some right part of the string read so far (the R part of LR) with any structure described by a grammar rule. When it works it is unambiguous, unlike with recursive descent, but you have to be ruthless in preventing ambiguities in the grammar.
So as a gift to myself for the summer I've taken an old program using recursive descent that I used when I used to teach elementary statistics regularly. I wrote small data files every time I wanted to create an image of a normal curve (determined by its center or mean and its spread or standard deviation) possibly shaded (to the left, to the right, or between two values). The code for creating those images was repetitive and really only needed a few numbers, and I created a simple data format that I would put into the data files to make my life easier.
So this summer I'm starting from scratch building an LR parser to work with those data files and create images using a more recent graphics program.
My process: a long time ago I created a program to read a grammar and identify a simple string not described by it if such a string exists. My goal is to create a grammar that will read all strings, with most strings leading to error messages.
My error messages are very simple: I was expecting these kinds of symbols at the end of what I've read in order to make it a valid input, or I was expecting these kinds of symbols at this line number and column number instead of what was there. The error messages are simple (easy for me to create) and direct to the point.
I start with an empty string; often this leads to a specific error message.
At each stage I ask if the grammar is complete yet or what is a simple string I can't parse yet.
I add a grammar rule to parse that string. (Often this leads to some combining of the new rule with existing rules. Some of the rules take care of an infinite number of strings, such as when there is an error in the input at a specific place, any string that extends that first string with any suffix has the same error.)
I repeat until I am done.
As with my favorite kind of long projects, it is chunkable: I can put in two minutes whenever I want to take a break from my other work (more directly satisfying my job description).
In particular, it is very enjoyable watching the structures build up as I keep extending the language.
Comments
Post a Comment