Skip to main content

One of the Very Many Ways in Which I am Strange

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

Popular posts from this blog

Holiday Break

I have been teaching for 37 years now, and I go through many of the same things at the end of the Fall semester each year. There is relief at the completion of a significant task (teaching each of my classes) but there is a good deal of physical and mental weariness and aches. I could sleep for several days straight if not for my sleep disorder. By and large my mind is not very sharp and as an introvert I try to be pleasant with loved ones but am not outgoing at all. With age the feeling of being drained deepens in more and more ways. Of course this is when we have, almost every year, taken a road trip to visit birth families in the Northeast, a full day of driving each way, often involving winter weather far worse than what we are accustomed to in NC. I love my birth family members as well but as with my created family I am weary and not very outgoing. The conversation is rarely about me and my day-to-day life but rather about younger family members and family friends that I do not kn...
Post a Comment
Read more

Accountability

Mathematics as a discipline teaches accountability. Every claim, whether it be a computation result or a statement (theorem) about how things work is accountable. We teach this accountability developmentally, with lower expectations at the beginning, and sometimes folk who study mathematics casually don't understand this. In my multivariable calculus classes, which I teach most frequently, I usually phrase my expectations as "give me a reason to believe your answer", citing my time working at an investment bank where my recommendations had financial repercussions and my supervisor never took my word for anything. In higher-level mathematics classes such as Abstract Algebra or Analysis I can be more explicit: these are the things we all agree to assume, these are the proof techniques which we understand; can you make an argument that convinces the community who have accepted those axioms and rules of inference that what you claim is true? We work hard to remove the ego fro...
Post a Comment
Read more

Contents of Most Recent Email to NC Senators

 Sent to Senators Tillis and Budd of NC this morning: My uncle was a police detective in Philadelphia before he retired. He showed his face and his badge to all he talked to on the job; he gave his name and business card to the public he served. This is what law enforcement officials have done in this country as policy until now; what if anything has changed?   The violent thugs serving in ICE are not law enforcement. They do not protect and serve; they attack and refuse to identify themselves. They are a paramilitary force responsible only to President Trump and his minions, who reflexively desecrate the memory of their victims. All dishonor themselves daily, all lack integrity. Immigration is a serious issue. Using brutal thugs to deal with it is like using a chainsaw to remove an appendix. The appendix may need to come out but using a chainsaw is a silly solution that kills people. It is painful to think of all the children incarcerated by ICE. It is unthinkable to all...
Post a Comment
Read more