15
$\begingroup$

It's possible to parse a document using a single pass from a state machine. What is the benefit of having two passes, ie. having a lexer to convert text to tokens, and having a parser to test production rules on those tokens? Why not have a single pass that applies production rules directly to the text?

$\endgroup$
  • 2
    $\begingroup$ Related: programmers.stackexchange.com/questions/128888/… $\endgroup$ – User Feb 28 '15 at 9:22
  • 2
    $\begingroup$ This has already been discussed on CS,stackexchange, with many very technical comments in an answer to Expressive power of lexer + parser. But there may be room there for further answers. $\endgroup$ – babou Feb 28 '15 at 12:52
  • $\begingroup$ I wonder if pipeline-style parallelism (albeit highly imbalanced stages) might be a side advantage. Both instruction and data cache behavior might also be interesting. How much (if at all) such would reduce compile time would depend on the specific hardware. $\endgroup$ – Paul A. Clayton Feb 28 '15 at 13:41
  • $\begingroup$ One fairly obvious (at least to me) reason is that you can then use the scanner tool separately. In practice, I frequently use flex to scan input, but seldom need the full power of yacc. $\endgroup$ – jamesqf Feb 28 '15 at 19:01
13
$\begingroup$

You don't have to separate them. People combine them into scannerless parsers.

The key disadvantage of scannerless parsers appears to be that the resulting grammars are rather complicated -- more complicated than the corresponding combination of a regular expression doing lexing and a context-free grammar doing parsing on the token-stream. In particular, grammars for scannerless parsing tend towards ambiguity. It's easier to remove ambiguity for grammars working on a token-stream.

A pragmatic benefit of using a dedicated upfront lexing phase is that you don't couple the subsequent parser with lexical detail. This is useful during early programming language development, when the lexical and syntactic details are still changing frequently.

$\endgroup$
  • 1
    $\begingroup$ Having one pass instead of two passes involves closure properties. If you consider that lexers are transducers belonging to a formal family $T$, that can be combined with parsers belonging to a formal family $P$, you must wonder whether composing them stays in the same family $P$, or requires a more complex formal family $P_T$, thus requiring different algorithmics, and possibly more difficult tuning of syntax. Parsing technology often relies on specialized families (such as LR or LL variants) that may not have the right closure properties. $\endgroup$ – babou Feb 28 '15 at 12:45
  • $\begingroup$ @babou Yes that is correct. I don't know any formal results of the form regular-expression composed with LL(k) goes out of LL(k), or similar. Moreover, lexing is usually not done with regular languages, but with something more powerful, namely regular languages extended with longest-match and keyword-first priorities. I'm not sure what exact language class that is and what its closure properties are. $\endgroup$ – Martin Berger Feb 28 '15 at 12:48
  • 2
    $\begingroup$ If your look-ahead involves reading an identifier, the composition will require unbounded look-ahead, since there is (in principle) no bound on the length of identifiers. $\endgroup$ – babou Feb 28 '15 at 12:56
  • $\begingroup$ @babou I'm not sure. If the longest keyword is 17 characters long, then any string that is longer must be an identifier, or lexically invalid. $\endgroup$ – Martin Berger Feb 28 '15 at 13:00
  • $\begingroup$ But you identifier, or possibly a string, number or other literal, is a sequence more than 17 individual symbols, that may stand before the token you actually need. That is a big look-ahead, unbounded. You may end up with a non-deterministic language. $\endgroup$ – babou Feb 28 '15 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.