|Perl: the Markov chain saw|
Re^7: Block-structured language parsing using a Perl module?by roboticus (Canon)
|on Aug 18, 2012 at 06:43 UTC||Need Help??|
One advantage of splitting the parser and lexer is that rather than having one humongous state machine that has to cover both grammar and lexing, you can split the task into two smaller machines. As you know, state machine complexity tends to grow exponentially, so two state machines half the size of a combined one can be *much* more tractable.
Another advantage of splitting is that you can use different techniques in different places. You might use a few simple regexes for your tokenizer and some recursive descent for your parser. If necessary, you can switch techniques in one or the other without rewriting *everything*.
The last advantage (that I'm writing about) of having the parser part is that you can more easily tie "meaning" to various locations in your grammar. For example, if you're doing some simple lexing, you might discover a symbol name. But what does the symbol *mean* once you lex it? Is it part of a declaration, a function name, a reference on the LHS, a use on the RHS?. Tying the meaning to particular spots in the syntax is a pretty nice feature.
If you're keeping track of enough information in your lexer to be able to know what's going on and whether the syntax is valid, then I'd argue that you haven't written a lexer, you've written a combination lexer/parser. After all, parsing is simply recognizing correct 'statements' of the grammar, so if you can more easily merge the tokenization with the rule checks, then I wouldn't worry about the 'fancy' methods. While there's nothing wrong with that approach, it might becom burdensome when the language is large/complex enough.
By the way. I just started playing with Marpa::R2 this afternoon, after reading this thread, so I know little about it so far. But having said that, I really recommend it over Parser::RecDescent. When I tried Parser::RecDescent, it took me forever to start getting results, and it was painful, too. The debugging capabilities really drove me mad. (Reading the trace in Parse::RecDescent is *painful*.)
But my puttering around with Marpa today was much more enjoyable. I got better results *much* more easily, and after a couple hours, I had a good start on a parser for a toy language. (I'll hopefully get to finish the parser tomorrow.) If I can get it into reasonable shape, I'll try to (remember to) post it.
When your only tool is a hammer, all problems look like your thumb.