5 ms·
"Parsers work at the grammatical level, lexers work at the word level." Is this correct to say?
by lolptdr 11y ago
"Parsers work at the grammatical level, lexers work at the word level."
Is this correct to say?
- gliese1337 11y agoYes. For a given definition of "word", anyway, but "word" is fiddly enough we can assume they mean something sensible. A stricter definition would be "lexers work at the lexical level" for NLP (in which case it's nearly tautologically obvious), or "lexers work at the token level" for programming languages. (Creds: lexing / wordbreaking is the topic of my masters research in linguistics. Tries are a good starting point for that, but it turns out that they are a special case of simple morphological analyzer, and you need more complicated ones to do a good job on natural languages.)
- eliben 11y agoI guess only if you consider punctuation to be "words". A more accurate description would be "lexers work at the atom level", IOW breaking the input into atoms - the smallest non-breakable lexical units that are used in a grammar.
- jahewson 11y agoLexers work at the lexeme level, which are generally understood to be words, assuming that a word is a non-decomposable unit of language.
- agumonkey 11y agoSimilar to the atom / compound forms described by McCarthy.
- munificent 11y agoYes, as long as you include punctuation in your definition of "word". I like to think of it like this: A lexer takes a sequence of characters and produces a sequence of tokens. List in, list out. It just chunks runs of characters together. A parser takes in a sequence of tokens and produces a tree. It produces a nested data structure from a flat input.
- ch 11y agoRight, a lexer is a mapping function. A parser is a fold.
- nostrademons 11y agoA lexer is a fold as well - there are usually fewer elements in the output list than in the input list. A mapping function implies a 1:1 correspondence, because the recursion is abstracted out into map() and the map function can't accumulate any state during the computation. (At least in traditional FP technology; the Mapper in MapReduce isn't actually a true map function, it's more like an unfold.)
- ch 11y agoAh true I am incorrect on the lexer as a map. Had I thought on that half a second more I would have saved myself some embarrassment. :)
- TheLoneWolfling 11y agoI've always understood it to be this: A lexer is for a regular language (in the formal sense), whereas a parser is for a context-sensitive (or context-free) language. Or, for a less formal description. A lexer's transformation is one that can be expressed as a function of <<input symbol or end of file>, position in file, state> -> <<some finite number of output symbols (including zero)>, <state or done>>, where state is finite. A lexer can work without backtracking or arbitrary memory usage. Whereas a parser potentially requires either arbitrary (but finite) backtracking or arbitrary (but finite) memory usage. The boundary gets a little fuzzy, though. For instance, constants, at least for any language that allows arbitrary-sized integers.