Thesis: Parsing

As a part of my Mathematics Masters program I am writing a thesis on formal languages, grammars, and parsing. While I'm still in the process of working out exactly what I'm going to do, it will probably involve looking at extensions to Context Free Grammars to enable realistic parsing of Context Sensitive languages.

If you're interested in a very basic, non theoretical introduction to parsing thats very understandable, the tutorial Let's Build a Compiler, by Jack Crenshaw is VERY good. It was perhaps the first thing I read on parsing that really demystified it for me.

Oh yeah, if you're thinking about going to grad school some day, give this a good long read. It gave me hope when I was the throws of trying to finish my B.S. Really, its got some good stuff :).

The linguistics teacher at our school retired a few years back(before I realized how interested I was in the topic) and no other teacher at Tech was qualified to teach the class, so I missed out on it. Anyway, he's now back in a teaching position(but not actively doing research), and so the Fall of 2003 I got the opportunity to take the class. As part of our work we had to do a paper on some aspect of linguistics. Here's my paper: Artificial Languages: A Study of Formal Grammars.

The Partial Correspondence Problem and its Applications to Formal Languages By: Matthew Estes March 4th, 2004 Graduate Seminar Tennessee Tech University Abstract An explanation of the Partial Correspondence Problem, and several examples illustrating its use as a proof technique for Decidability problems in Formal Languages. Several results from Knuth's "On the Translation of Languages from Left to Right" will be given to illustrate its applications. (To Be Posted). Slides

Work Products

• (To Be Posted). The Partial Correspondence Problem and its Applications to Formal Languages, March 4th, 2004. Slides from Graduate Seminar talk.

  Abstract An explanation of the Partial Correspondence Problem, and several examples illustrating its use as a proof technique for Decidability problems in Formal Languages. Several results from Knuth's "On the Translation of Languages from Left to Right" will be given to illustrate its applications.

• Proposal for Master's Thesis Research Topic, January 9th, 2004. This is my proposal given to my graduate committee for the specific research I would like to do in Formal Languages and Parsing. Heavily annotated bibliography.
• Artificial Languages: A Study of Formal Grammars, November 17th, 2003. Paper for English 5511 class Introduction to Descriptive Linguistics.
• An Introduction to the theory of Formal Languages and Parsing, October 9th, 2003. Slides from Graduate Seminar talk.

  Abstract The notion of Formal Languages and their grammars will be introduced and defined and their relevance Mathematics and other fields explained. The topic of parsing will be introduced as an algorithmic method of exploiting the information contained in the grammar to reconstruct a particular sentence from the Language.

  This talk will be based on material in the first three chapters of "Parsing Techniques: A Practical Guide" by Grune, et al. freely available online at http://www.cs.vu.nl/~dick/PTAPG.html. Material will also be presented from "Grammars for Programming Languages" by Cleaveland as well as "A Decidability Criterion for van Wijngaarden Grammars" by P. Deussen, Acta Informatica, vol. 5, pg. 353-375.

  This talk was presented again at Western Kentucky University's 23rd Annual Mathematics Symposium the weekend of November 21-22, 2003.

Bibliography

• Parsing Techniques: A Practical Guide, 1991. Availability: http://www.cs.vu.nl/~dick/PTAPG.html
• Recursive Adaptable Grammars, by John Shutt. Availability: http://www.cs.wpi.edu/~jshutt/thesis/top.html
• Existence of a van Wijngaarden syntax for every Recursively Enumerable Set, by M. Sintzoff in Annales do la Societe Scientifique de Bruxelles, T. 81, II, pages 115-118, 1967. Availability: ILL
• Two-level Grammar as a Functional Programming Language, by Edupuganty and B.R. Bryant, in Computer Journal, volume 32, issue 1, pages 36-44, February 1989 - Availability: TTU Library
• A Decidability Criterion for van Wijngaarden Grammars, by P. Deussen, in Acta Informatica, volume 5, pages 353-375, 1975. Availability: ILL
• Two-level Meta-Controlled Substitution Grammars, by Meersman and Rozenberg, in Acta Informatica, volume 10, pages 323-339, 1978. Availability: ILL
• On Parsing Two-level Grammars, by Lutz Micheal Wegner, in Acta Informatica, volume 14, pages 175-193, 1980. Availability: ILL
• Practical LL(1)-based Parsing of van Wijngaarden Grammars, by A.J. Fisher, in Acta Informatica, volume 21, pages 559-584, 1985. Availability: ILL
• Grammars for Programming Languages, by Cleveland, 1977. Availability: TTU Library(QA76.7.C57)
• A Mathematical Theory of Communication, by Claude Shannon, 1948. Availability: http://cm.bell-labs.com/cm/ms/what/shannonday/paper.html
• Language Files, 8th Edition
• Computability, Complexity, and Language
• Speech and Language Processing

Related

• The Anti-Mac
• The Macintosh Human-Interface Guidelines
• The Art of Unix Programming
• In the Beginning was the Command Line
• Godel, Escher, Bach
• Larry Wall
  • Perl, the First Postmodern Programming Language
  • The First State of the Onion
  • The Second State of the Onion
  • The Third State of the Onion
• Let's Build a Compiler, by Jack Crenshaw. A very good introduction to parsing if all this theory gets to you. It will also lead you to a place where you can start reading a real work. I really recommend this as a basic introduction, especially for those who are impatient and want to write code as soon as possible.

Yeah, I know I need to give a few more details about these. I will. Its on the todo list(isn't everything? :).