parsing TDS as a regular language

On Mon, 22 Aug 2011 09:04:29 -0400
"James K. Lowden" <[email protected]> wrote:

> The first step is to reduce TDS to BNF.  The step before that (!)
> might be to reduce it to a tabular description from which the BNF and
> documentation can be generated.  
> 
> > A grammar can be turned into a parser and tree walker with a tool
> > like the Gold Parser: http://www.devincook.com/goldparser/
> 
> Yes, I was thinking along just those lines.  Gold doesn't run on
> Linux, though, and LALR is more complex than we need to parse TDS.  
...
> http://www.cs.rhul.ac.uk/research/languages/projects/rdp.html

http://www.freetds.org/doc/tds-nfa.pdf

I was fortunate to engage Dr. Johnstone of the RDP project on the
question of parser-generators for TDS.  He replied that a Deterministic
Finite Automaton would be smaller and faster if TDS is a
regular language, which I'm certain it is.  

The above diagram is my second attempt at a state diagram for
processing TDS.  An NFA can be reduced to a state transition table,
from which a finite automaton can be generated.  I've never done that
sort of thing, but there's no better way to learn than by doing.  If
you're interested, give me a shout and we'll work together.  

If you want to contribute without programming, grep for "marker" in
your TDSDUMP file, and trace the sequence on the NFA.  You should
always reach "accept".  If you don't, please post the sequence and I'll
update the diagram.  

Because not everyone knows, let me explain that "regular language" is a
term of art.  It roughly means the input stream can be processed in
finite memory, which roughly means you don't need stack.  We process
TDS tokens now without stacking them.  (Sure, C has a stack for
function calls, but TDS doesn't.  At no point do we resume processing
the prior token, having set it aside to process the current one.)  

Thus, an automaton will do.  

If you want to know more, a book will serve you better than the Web.
That said, I can recommend these to get you started.  

http://www.cs.uky.edu/~lewis/texts/theory/automata/fin-auto.pdf
http://lambda.uta.edu/cse5317/notes/node1.html
http://www.fastar.org/publications/PhD_Watson.pdf

You might also be interested to know, if you don't already, that
"regular expressions" are parsers of regular languages (and are
*proved* to be insufficient for non-regular languages).  Not only
that, but in searching for links like those above I came across a
facinating discussion of how PCRE went terribly wrong by ignoring the
CS fundamentals on which it was based:

http://swtch.com/~rsc/regexp/regexp1.html

You could do worse than read Russ Cox's whole blog.  It will take just a
few hours.  

+++

I suspect that many programmers, myself included, experience computer
science more as archeology than science.  We begin in the present
(BASIC back in the day, now maybe Java or Python) and if we're mildly
curious slowly uncover the layers of what came before: interpreters,
compilers, bytecodes, machines.  Eventually we hit rock bottom, the
fundamentals on which our civilization was founded: math and logic.
That's happened to me more than once, and each time I feel I've
discovered a new ancient civilization, as if I'd walked into a
prehistoric cave.  But, you know, it's not so old: a lot of those
paintings were signed by Ken Thompson and Rob Pike.  

--jkl