361

Are lexers and parsers really that different in theory?

It seems fashionable to hate regular expressions: coding horror, another blog post.

However, popular lexing based tools: pygments, geshi, or prettify, all use regular expressions. They seem to lex anything...

When is lexing enough, when do you need EBNF?

Has anyone used the tokens produced by these lexers with bison or antlr parser generators?

7
  • 2
    yes. I am trying to parse autohotkey. I was able to build a syntax highlighter using pygments really fast. But antlr is taking much longer... I haven't seen a lot of cross pollination between the two tools.
    – Naveen
    May 16, 2010 at 9:32
  • 80
    Its only fashionable to hate regular expressions when they are misused. Many people try to use regular expressions when context-free parsing is needed. They always fail. And they blame regular expression technology. That's much like complaining that your hammer is a crummy saw. True, but you won't get a lot of sympathy.
    – Ira Baxter
    May 17, 2010 at 21:51
  • 2
    I am starting to pick up some speed with antlr, thankfully. A lot of lexing is context-free and sometimes even context dependent also by the way.
    – Naveen
    May 25, 2010 at 5:22
  • 2
    One fundamental aspect of the lexer vs parser issue is that lexers are based on finite automata (FSA), or more precisely finite transducers (FST). Most parsing formalisms (not just Context-Free) are closed under intersection with FSA or application of FST. Hence using the simpler regular expression based formnalism for lexer does not increase the complexity of syntactic structures of the more complex parser formalisms. This is an absolutely major modularity issue when defining structure and semantics of languages, happily ignored by the high voted answers.
    – babou
    Dec 27, 2014 at 11:39
  • It should be noted that lexers and parsers do not have to be different, e.g. LLLPG and earlier versions of ANTLR use the same LL(k) parsing system for both lexers and parsers. The main difference is that regexes are usually sufficient for lexers but not parsers.
    – Qwertie
    Apr 7, 2016 at 10:36

6 Answers 6

554

What parsers and lexers have in common:

  1. They read symbols of some alphabet from their input.

    • Hint: The alphabet doesn't necessarily have to be of letters. But it has to be of symbols which are atomic for the language understood by parser/lexer.
    • Symbols for the lexer: ASCII characters.
    • Symbols for the parser: the particular tokens, which are terminal symbols of their grammar.
  2. They analyse these symbols and try to match them with the grammar of the language they understood.

    • Here's where the real difference usually lies. See below for more.
    • Grammar understood by lexers: regular grammar (Chomsky's level 3).
    • Grammar understood by parsers: context-free grammar (Chomsky's level 2).
  3. They attach semantics (meaning) to the language pieces they find.

    • Lexers attach meaning by classifying lexemes (strings of symbols from the input) as the particular tokens. E.g. All these lexemes: *, ==, <=, ^ will be classified as "operator" token by the C/C++ lexer.
    • Parsers attach meaning by classifying strings of tokens from the input (sentences) as the particular nonterminals and building the parse tree. E.g. all these token strings: [number][operator][number], [id][operator][id], [id][operator][number][operator][number] will be classified as "expression" nonterminal by the C/C++ parser.
  4. They can attach some additional meaning (data) to the recognized elements.

    • When a lexer recognizes a character sequence constituting a proper number, it can convert it to its binary value and store with the "number" token.
    • Similarly, when a parser recognize an expression, it can compute its value and store with the "expression" node of the syntax tree.
  5. They all produce on their output a proper sentences of the language they recognize.

    • Lexers produce tokens, which are sentences of the regular language they recognize. Each token can have an inner syntax (though level 3, not level 2), but that doesn't matter for the output data and for the one which reads them.
    • Parsers produce syntax trees, which are representations of sentences of the context-free language they recognize. Usually it's only one big tree for the whole document/source file, because the whole document/source file is a proper sentence for them. But there aren't any reasons why parser couldn't produce a series of syntax trees on its output. E.g. it could be a parser which recognizes SGML tags sticked into plain-text. So it'll tokenize the SGML document into a series of tokens: [TXT][TAG][TAG][TXT][TAG][TXT]....

As you can see, parsers and tokenizers have much in common. One parser can be a tokenizer for other parser, which reads its input tokens as symbols from its own alphabet (tokens are simply symbols of some alphabet) in the same way as sentences from one language can be alphabetic symbols of some other, higher-level language. For example, if * and - are the symbols of the alphabet M (as "Morse code symbols"), then you can build a parser which recognizes strings of these dots and lines as letters encoded in the Morse code. The sentences in the language "Morse Code" could be tokens for some other parser, for which these tokens are atomic symbols of its language (e.g. "English Words" language). And these "English Words" could be tokens (symbols of the alphabet) for some higher-level parser which understands "English Sentences" language. And all these languages differ only in the complexity of the grammar. Nothing more.

So what's all about these "Chomsky's grammar levels"? Well, Noam Chomsky classified grammars into four levels depending on their complexity:

  • Level 3: Regular grammars

    They use regular expressions, that is, they can consist only of the symbols of alphabet (a,b), their concatenations (ab,aba,bbb etd.), or alternatives (e.g. a|b).
    They can be implemented as finite state automata (FSA), like NFA (Nondeterministic Finite Automaton) or better DFA (Deterministic Finite Automaton).
    Regular grammars can't handle with nested syntax, e.g. properly nested/matched parentheses (()()(()())), nested HTML/BBcode tags, nested blocks etc. It's because state automata to deal with it should have to have infinitely many states to handle infinitely many nesting levels.
  • Level 2: Context-free grammars

    They can have nested, recursive, self-similar branches in their syntax trees, so they can handle with nested structures well.
    They can be implemented as state automaton with stack. This stack is used to represent the nesting level of the syntax. In practice, they're usually implemented as a top-down, recursive-descent parser which uses machine's procedure call stack to track the nesting level, and use recursively called procedures/functions for every non-terminal symbol in their syntax.
    But they can't handle with a context-sensitive syntax. E.g. when you have an expression x+3 and in one context this x could be a name of a variable, and in other context it could be a name of a function etc.
  • Level 1: Context-sensitive grammars

  • Level 0: Unrestricted grammars
    Also called recursively enumerable grammars.

13
  • 75
    Oh yeah? So what are those "words or tokens"? They're just sentences in the regular language, consisting of letters of the alphabet. And what are those "constructs" or "trees" in the parser? They're also sentences, but in a different, higher-level language, for which the particular tokens are alphabetical symbols. The difference is not what you've said, but in the COMPLEXITY OF THE LANGUAGE USED. Confront your -1 with any handbook about the parsing theory.
    – SasQ
    Feb 19, 2012 at 18:20
  • 3
    @SasQ Would it be fair to say that both Lexers and Parsers take some grammar and a series of tokens as input ?
    – Parag
    Jul 24, 2012 at 12:01
  • 4
    Quite so. They both take a series of symbols from the alphabet they recognize. For lexer, this alphabet consists just of plain characters. For parser, the alphabet consists of terminal symbols, whatever they are defined. They could be characters, too, if you don't use lexer and use one-character identifiers and one-digit numbers etc (quite useful at first stages of developement). But they're usually tokens (lexical classes) because tokens are a good abstraction: you can change the actual lexemes (strings) they stand for, and parser doesn't see the change.
    – SasQ
    Aug 2, 2012 at 1:02
  • 8
    For example, you can use a terminal symbol STMT_END in your syntax (for the parser) to denote the end of instructions. Now you can have a token with the same name associated with it, generated by the lexer. But you can change the actual lexeme it stands for. Eg. you can define STMT_END as ; to have C/C++-like source code. Or you can define it as end to have it somehow similar to Pascal-style. Or you can define it as just '\n' to end the instruction with the end of line, like in Python. But the syntax of instruction (and the parser) stays unchanged :-) Only lexer needs to be changed.
    – SasQ
    Aug 2, 2012 at 1:08
  • 32
    Hours on wikipedia and google didn't help, but you explained Chomsky's grammars in 3 minutes. Thank you.
    – enrey
    Mar 20, 2013 at 15:26
127

Yes, they are very different in theory, and in implementation.

Lexers are used to recognize "words" that make up language elements, because the structure of such words is generally simple. Regular expressions are extremely good at handling this simpler structure, and there are very high-performance regular-expression matching engines used to implement lexers.

Parsers are used to recognize "structure" of a language phrases. Such structure is generally far beyond what "regular expressions" can recognize, so one needs "context sensitive" parsers to extract such structure. Context-sensitive parsers are hard to build, so the engineering compromise is to use "context-free" grammars and add hacks to the parsers ("symbol tables", etc.) to handle the context-sensitive part.

Neither lexing nor parsing technology is likely to go away soon.

They may be unified by deciding to use "parsing" technology to recognize "words", as is currently explored by so-called scannerless GLR parsers. That has a runtime cost, as you are applying more general machinery to what is often a problem that doesn't need it, and usually you pay for that in overhead. Where you have lots of free cycles, that overhead may not matter. If you process a lot of text, then the overhead does matter and classical regular expression parsers will continue to be used.

10
  • 49
    Nice explanation, Ira. Adding to your analogy: While lexers are about getting the words right, parsers are about getting the sentences right. "See spot run" and "spot run See" are both valid as far as a lexer is concerned. It takes a parser to determine that phrase structure is wrong (in English grammar).
    – Alan
    May 24, 2010 at 15:16
  • 4
    The theory is very different. Most parser technologies are trying to handle context-free languages to some degree (some do only part, e.g., LALR, some do it all, e.g., GLR). Most lexer technologies only try to do regular expressions.
    – Ira Baxter
    Jun 8, 2010 at 9:42
  • 4
    The theory is different, because it has been proposed by many different people and use different terminology and algorithms. But if you look them closely, you can spot the similarities. For example, the problem of left recursion is very similar to the problem of non-determinism in NFAs, and removing left recursion is similar to removing non-determinism and converting NFA into DFA. Tokens are sentences for the tokenizer (output), but alphabetical symbols for the parser (input). I don't deny the differences (Chomsky levels), but similarities help a lot in design.
    – SasQ
    Feb 19, 2012 at 18:24
  • 2
    My officemate was into category theory. He showed how the categorical theory notion of sheaves covered all kinds of pattern matching, and was able to derive LR parsing from an abstract categorical specification. So in fact, if you go abstract enough, you can find such commonalities. The point of category theory is you can often abstract "all the way up"; I'm sure you could build a category theory parser that erased the differences. But any practical uses of it have to instantiate down to the specific problem domain, and then the differences show up as real.
    – Ira Baxter
    Oct 30, 2013 at 0:55
  • 1
    What lexer should return is a "token IDENTIFIER 's'", "token +", "token STRING 'hello world'". Yes this is the job for the lexer and easily done, especially if you have a lexer-generator program that will accept sepearate regexes for each token type. You have no idea what "hairy" is :-{{ We produce COBOL parsers, which have lexers for COBOL tokens feeding them. Our COBOL lexer (which handles 7 full dialects of COBOL) has 22,000 (YES!) lines of regex definitions of all the different tokens that all 7 COBOL dialects can produce. Yes, this was hard to build and test even with good tools
    – Ira Baxter
    Apr 13 at 22:17
35

When is lexing enough, when do you need EBNF?

EBNF really doesn't add much to the power of grammars. It's just a convenience / shortcut notation / "syntactic sugar" over the standard Chomsky's Normal Form (CNF) grammar rules. For example, the EBNF alternative:

S --> A | B

you can achieve in CNF by just listing each alternative production separately:

S --> A      // `S` can be `A`,
S --> B      // or it can be `B`.

The optional element from EBNF:

S --> X?

you can achieve in CNF by using a nullable production, that is, the one which can be replaced by an empty string (denoted by just empty production here; others use epsilon or lambda or crossed circle):

S --> B       // `S` can be `B`,
B --> X       // and `B` can be just `X`,
B -->         // or it can be empty.

A production in a form like the last one B above is called "erasure", because it can erase whatever it stands for in other productions (product an empty string instead of something else).

Zero-or-more repetiton from EBNF:

S --> A*

you can obtan by using recursive production, that is, one which embeds itself somewhere in it. It can be done in two ways. First one is left recursion (which usually should be avoided, because Top-Down Recursive Descent parsers cannot parse it):

S --> S A    // `S` is just itself ended with `A` (which can be done many times),
S -->        // or it can begin with empty-string, which stops the recursion.

Knowing that it generates just an empty string (ultimately) followed by zero or more As, the same string (but not the same language!) can be expressed using right-recursion:

S --> A S    // `S` can be `A` followed by itself (which can be done many times),
S -->        // or it can be just empty-string end, which stops the recursion.

And when it comes to + for one-or-more repetition from EBNF:

S --> A+

it can be done by factoring out one A and using * as before:

S --> A A*

which you can express in CNF as such (I use right recursion here; try to figure out the other one yourself as an exercise):

S --> A S   // `S` can be one `A` followed by `S` (which stands for more `A`s),
S --> A     // or it could be just one single `A`.

Knowing that, you can now probably recognize a grammar for a regular expression (that is, regular grammar) as one which can be expressed in a single EBNF production consisting only from terminal symbols. More generally, you can recognize regular grammars when you see productions similar to these:

A -->        // Empty (nullable) production (AKA erasure).
B --> x      // Single terminal symbol.
C --> y D    // Simple state change from `C` to `D` when seeing input `y`.
E --> F z    // Simple state change from `E` to `F` when seeing input `z`.
G --> G u    // Left recursion.
H --> v H    // Right recursion.

That is, using only empty strings, terminal symbols, simple non-terminals for substitutions and state changes, and using recursion only to achieve repetition (iteration, which is just linear recursion - the one which doesn't branch tree-like). Nothing more advanced above these, then you're sure it's a regular syntax and you can go with just lexer for that.

But when your syntax uses recursion in a non-trivial way, to produce tree-like, self-similar, nested structures, like the following one:

S --> a S b    // `S` can be itself "parenthesized" by `a` and `b` on both sides.
S -->          // or it could be (ultimately) empty, which ends recursion.

then you can easily see that this cannot be done with regular expression, because you cannot resolve it into one single EBNF production in any way; you'll end up with substituting for S indefinitely, which will always add another as and bs on both sides. Lexers (more specifically: Finite State Automata used by lexers) cannot count to arbitrary number (they are finite, remember?), so they don't know how many as were there to match them evenly with so many bs. Grammars like this are called context-free grammars (at the very least), and they require a parser.

Context-free grammars are well-known to parse, so they are widely used for describing programming languages' syntax. But there's more. Sometimes a more general grammar is needed -- when you have more things to count at the same time, independently. For example, when you want to describe a language where one can use round parentheses and square braces interleaved, but they have to be paired up correctly with each other (braces with braces, round with round). This kind of grammar is called context-sensitive. You can recognize it by that it has more than one symbol on the left (before the arrow). For example:

A R B --> A S B

You can think of these additional symbols on the left as a "context" for applying the rule. There could be some preconditions, postconditions etc. For example, the above rule will substitute R into S, but only when it's in between A and B, leaving those A and B themselves unchanged. This kind of syntax is really hard to parse, because it needs a full-blown Turing machine. It's a whole another story, so I'll end here.

1
  • 1
    You state that EBNF is "just a convenience / shortcut notation / "syntactic sugar" over the standard Chomsky's Normal Form (CNF) grammar rules". But CNF has hardly anything to do with the topic at hand. EBNF can easily be transformed into standard BNF. Period. It is syntactic sugar for standard BNF.
    – babou
    Jun 11, 2014 at 12:35
14

To answer the question as asked (without repeating unduly what appears in other answers)

Lexers and parsers are not very different, as suggested by the accepted answer. Both are based on simple language formalisms: regular languages for lexers and, almost always, context-free (CF) languages for parsers. They both are associated with fairly simple computational models, the finite state automaton and the push-down stack automaton. Regular languages are a special case of context-free languages, so that lexers could be produced with the somewhat more complex CF technology. But it is not a good idea for at least two reasons.

A fundamental point in programming is that a system component should be buit with the most appropriate technology, so that it is easy to produce, to understand and to maintain. The technology should not be overkill (using techniques much more complex and costly than needed), nor should it be at the limit of its power, thus requiring technical contortions to achieve the desired goal.

That is why "It seems fashionable to hate regular expressions". Though they can do a lot, they sometimes require very unreadable coding to achieve it, not to mention the fact that various extensions and restrictions in implementation somewhat reduce their theoretical simplicity. Lexers do not usually do that, and are usually a simple, efficient, and appropriate technology to parse token. Using CF parsers for token would be overkill, though it is possible.

Another reason not to use CF formalism for lexers is that it might then be tempting to use the full CF power. But that might raise sructural problems regarding the reading of programs.

Fundamentally, most of the structure of program text, from which meaning is extracted, is a tree structure. It expresses how the parse sentence (program) is generated from syntax rules. Semantics is derived by compositional techniques (homomorphism for the mathematically oriented) from the way syntax rules are composed to build the parse tree. Hence the tree structure is essential. The fact that tokens are identified with a regular set based lexer does not change the situation, because CF composed with regular still gives CF (I am speaking very loosely about regular transducers, that transform a stream of characters into a stream of token).

However, CF composed with CF (via CF transducers ... sorry for the math), does not necessarily give CF, and might makes things more general, but less tractable in practice. So CF is not the appropriate tool for lexers, even though it can be used.

One of the major differences between regular and CF is that regular languages (and transducers) compose very well with almost any formalism in various ways, while CF languages (and transducers) do not, not even with themselves (with a few exceptions).

(Note that regular transducers may have others uses, such as formalization of some syntax error handling techniques.)

BNF is just a specific syntax for presenting CF grammars.

EBNF is a syntactic sugar for BNF, using the facilities of regular notation to give terser version of BNF grammars. It can always be transformed into an equivalent pure BNF.

However, the regular notation is often used in EBNF only to emphasize these parts of the syntax that correspond to the structure of lexical elements, and should be recognized with the lexer, while the rest with be rather presented in straight BNF. But it is not an absolute rule.

To summarize, the simpler structure of token is better analyzed with the simpler technology of regular languages, while the tree oriented structure of the language (of program syntax) is better handled by CF grammars.

I would suggest also looking at AHR's answer.

But this leaves a question open: Why trees?

Trees are a good basis for specifying syntax because

  • they give a simple structure to the text

  • there are very convenient for associating semantics with the text on the basis of that structure, with a mathematically well understood technology (compositionality via homomorphisms), as indicated above. It is a fundamental algebraic tool to define the semantics of mathematical formalisms.

Hence it is a good intermediate representation, as shown by the success of Abstract Syntax Trees (AST). Note that AST are often different from parse tree because the parsing technology used by many professionals (Such as LL or LR) applies only to a subset of CF grammars, thus forcing grammatical distorsions which are later corrected in AST. This can be avoided with more general parsing technology (based on dynamic programming) that accepts any CF grammar.

Statement about the fact that programming languages are context-sensitive (CS) rather than CF are arbitrary and disputable.

The problem is that the separation of syntax and semantics is arbitrary. Checking declarations or type agreement may be seen as either part of syntax, or part of semantics. The same would be true of gender and number agreement in natural languages. But there are natural languages where plural agreement depends on the actual semantic meaning of words, so that it does not fit well with syntax.

Many definitions of programming languages in denotational semantics place declarations and type checking in the semantics. So stating as done by Ira Baxter that CF parsers are being hacked to get a context sensitivity required by syntax is at best an arbitrary view of the situation. It may be organized as a hack in some compilers, but it does not have to be.

Also it is not just that CS parsers (in the sense used in other answers here) are hard to build, and less efficient. They are are also inadequate to express perspicuously the kinf of context-sensitivity that might be needed. And they do not naturally produce a syntactic structure (such as parse-trees) that is convenient to derive the semantics of the program, i.e. to generate the compiled code.

10
  • Yes, parse trees and ASTs are different, but pretty much not in a really useful way. See my discussion of this: stackoverflow.com/a/1916687/120163
    – Ira Baxter
    Jan 15, 2019 at 16:28
  • @IraBaxter I do not agree with you, but I do not really have time now to draft a clean answer to your post. Basically, you are taking a pragmatic point of view (and also defending your own system, I think). This is even easier because you are using general CF parsers (however GLR may not be the most efficient), rather than deterministic ones as in some systems. I consider AST as the reference representation, which lends itself to formally defined treatment, provably correct transformations, mathematical proofs, unparsing to multiple concrete representations, etc.
    – babou
    Jan 18, 2019 at 18:40
  • The "pragmatic" view is the reason I claim they aren't very different in a useful way. And I simply do not believe that using an (ad hoc AST) gives you "provably correct transforms"; your ad hoc AST has no obvious relation to the actual grammar of the langauge being processed (and here, yes, my system is defensible in that our "AST" is provably an isomorphic equivalent to the BNF). Ad hoc ASTs dont give you any additional capability to unparse to "multiple concrete representations). You objection to GLR (not most efficient) seems pretty pointless. Nor are they nondeterministic.
    – Ira Baxter
    Jan 18, 2019 at 20:27
  • So in fact I don't understand any part of your objection to my comment. You'll have to write that "clean answer".
    – Ira Baxter
    Jan 18, 2019 at 20:28
  • @IraBaxter Comments are too constrained for a proper answer (suggestion?). "Ad hoc" is not a proper qualifiers for AST I advocate, which should be (sometimes is) the reference syntax. This is historically true, looking both at the history of the concept of AST in computer science, and at the history of formal systems as terms (trees) in a sorted algebra, together with interpretation. AST is the reference form, not a derived one. See also modern proof systems and automatic program generation. You may be biased by the fact that you have to work from a concrete syntax designed by others.
    – babou
    Jan 19, 2019 at 14:35
8

There are a number of reasons why the analysis portion of a compiler is normally separated into lexical analysis and parsing ( syntax analysis) phases.

  1. Simplicity of design is the most important consideration. The separation of lexical and syntactic analysis often allows us to simplify at least one of these tasks. For example, a parser that had to deal with comments and white space as syntactic units would be. Considerably more complex than one that can assume comments and white space have already been removed by the lexical analyzer. If we are designing a new language, separating lexical and syntactic concerns can lead to a cleaner overall language design.
  2. Compiler efficiency is improved. A separate lexical analyzer allows us to apply specialized techniques that serve only the lexical task, not the job of parsing. In addition, specialized buffering techniques for reading input characters can speed up the compiler significantly.
  3. Compiler portability is enhanced. Input-device-specific peculiarities can be restricted to the lexical analyzer.

resource___Compilers (2nd Edition) written by- Alfred V. Abo Columbia University Monica S. Lam Stanford University Ravi Sethi Avaya Jeffrey D. Ullman Stanford University

0
6

The parser will typically combine the tokens produced by the lexer and group them.

The parser defined as the analysis of an input to organize the data according to the rule of a grammar while the lexer transforms a sequence of characters in a sequence of tokens

Let’s look at the following example and imagine that we are trying to parse an addition.

437 + 734

The lexer scans the text and find 4, 3, 7 and then a space ( ). The job of the lexer is to recognize that the characters 437 constitute one token of type NUM.

enter image description here

Then the lexer finds a + symbol, which corresponds to a second token of type PLUS, and lastly it finds another token of type NUM.

See more detail:
A Guide to Parsing: Algorithms and Terminology

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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