3
$\begingroup$

This was an exam question for my course and I am struggling to actually answer it in a way that is not fluff.

Here is my current answer:

CFGs describe how non-terminal symbols are converted into terminal symbols via a parser. However, a scanner defines what those terminal symbols convert to in terms of lexical tokens. CFGs are grammatical descriptions of a language instead of simply defining what tokens should be scanned from an input string.

What is the correct way to answer this?

$\endgroup$
4
  • 2
    $\begingroup$ I'd probably say that CFGs can be ambiguous, and may incur speed penalty. Tokenizing before applying CFG reduces the number of choices the CFG needs to make, thus reducing the overall running time. However, there are, for example, PEGs, which don't require an extra parsing level. $\endgroup$
    – wvxvw
    Apr 6 '16 at 15:53
  • $\begingroup$ Scannerless parsing $\endgroup$ Apr 6 '16 at 16:18
  • $\begingroup$ @AntonTrunov this answer makes sense if a CFG is technically a parser which is also doing the job of a lexer (which is describing the structure of lexical tokens)...what I found interesting on that link was that it can lead to ambiguity in the resulting grammar. However, then I don't get it - a CFG is a grammar... $\endgroup$ Apr 6 '16 at 16:54
  • $\begingroup$ Usually lexers are generated using regular expressions to describe the way they should work. Your question seems to be about why not use CFGs to generate(or build) lexers. $\endgroup$ Apr 6 '16 at 17:16
4
$\begingroup$

You don't use CFGs because typically lexical analysis can be performed using regular automata, and these are faster than context-free parsers. It's a question of efficiency.

$\endgroup$
1
  • $\begingroup$ They don't need to be faster. It's a matter of using smart parsing techniques. $\endgroup$ May 16 '18 at 22:29
0
$\begingroup$

Regular expressions are recognized by finite state machines, while context free grammar recognized by push-down automata. Push-down automata is not efficient as FSM in terms of time, hence it's all about efficiency.

$\endgroup$
0
$\begingroup$

Several angles here.

  • The distinction between "token" and "syntax" is somewhat arbitrary. Both can (and have been) described by CFGs.
  • One reason for the split is that we read e.g. a C program in terms of tokens (variable names, operators, reserved words, comments), not in term of characters. So it makes sense for the compiler writer to do what comes naturally.
  • A significant time of any compiler is reading and grouping characters into tokens, it makes sense to make this as fast as possible. The technology to handle regular expression matching is mature. Much character detail can just be discarded without much analysis (spaces, comments).
  • "Most" languages have the same (general) idea what the basic building blocks (names, operators, even comments) look like. It makes sense to package that and free the compiler writer of a task that way (less code, less bugs...). Several parsing tools offer this prepackaged.
  • Parsing is complex, it's speed depends on number of symbols handled. Grouping into tokens gives less stuff to parse, thus betrer performance.
$\endgroup$

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.