Re: original definition vs final language

[Lexicon]

in reply to original definition vs final language

The class you're taking, known as Automata Theory at my University, is a definate precursor to the Compilers class.

We wrote a Java compiler (in Java, ha ha). We broke the problem into 4 steps: lexical analysis - turning identifies, parens, +-*/, etc... into 'tokens', syntactic analysis - turning tokens into phrases, semantic analysis - matching referents in the symbol table (making all the identifiers point to the same thing), and code generation - writing java byte code.

It turns out that (for Java, and I think most other languages) lex is context-free, while syn requires a turring machine. Perl is kinda weird though. I imagine it's context free at the lex level, but I'm not sure. We put a lot of things into our languages to keep them CF (mostly keywords, ; statement delimiters, and {} block delimiters) and Perl has no shortage of it's own: Funny Characters $@%&. I recall that 1 token lookahead in the syn phase is equivalent to N token lookahead (where N is a fixed constant), so as long as Perl's oddities (like disambiguating that $x is a scalar and $x['bob'] is an array element) cannot be arbitrarily nested beyond what a simple stack can handle.

OK, enough Perl meditation.

Lexicon