Lexical tokenization is conversion of a text into (semantically or syntactically) meaningful lexical tokens belonging to categories defined by a "lexer" program. In case of a natural language, those categories include nouns, verbs, adjectives, punctuations etc. In case of a programming language, the categories include identifiers, operators, grouping symbols, data types and language keywords. Lexical tokenization is related to the type of tokenization used in large language models (LLMs) but with two differences. First, lexical tokenization is usually based on a lexical grammar, whereas LLM tokenizers are usually probability-based. Second, LLM tokenizers perform a second step that converts the tokens into numerical values.
Rule-based programs A rule-based program, performing lexical tokenization, is called tokenizer, lexer or scanner, although scanner is also a term for the first stage of a lexer. A lexer forms the first phase of a compiler frontend in processing. Analysis generally occurs in one pass. Lexers and parsers are most often used for compilers, but can be used for other computer language tools, such as prettyprinters or linters. Lexing can be divided into two stages: the scanning, which segments the input string into syntactic units called lexemes and categorizes these into token classes, and the evaluating, which converts lexemes into processed values.
Lexers are generally quite simple, with most of the complexity deferred to the syntactic analysis or semantic analysis phases, and can often be generated by a lexer generator, notably lex or derivatives. However, lexers can sometimes include some complexity, such as phrase structure processing to make input easier and simplify the parser, and may be written partly or fully by hand, either to support more features or for performance.
Disambiguation of "lexeme"
What is called "lexeme" in rule-based natural language processing is not equal to what is called lexeme in linguistics. What is called "lexeme" in rule-based natural language processing can be equal to the linguistic equivalent only in analytic languages, such as English, but not in highly synthetic languages, such as fusional languages. What is called a lexeme in rule-based natural language processing is more similar to what is called a word in linguistics (not to be confused with a word in computer architecture), although in some cases it may be more similar to a morpheme.
Lexical token and lexical tokenization
A lexical token is a string with an assigned and thus identified meaning, in contrast to the probabilistic token used in large language models. A lexical token consists of a token name and an optional token value. The token name is a category of a rule-based lexical unit.page 111, "Compilers Principles, Techniques, & Tools, 2nd Ed." (WorldCat) by Aho, Lam, Sethi and Ullman, as quoted in https://stackoverflow.com/questions/14954721/what-is-the-difference-between-token-and-lexeme
+ Examples of common tokens Token name(lexical category) Explanation Sample token values identifier Names assigned by the programmer. , , keyword Reserved words of the language. , , separator/punctuator Punctuation characters and paired delimiters. }, (, ; operator Symbols that operate on arguments and produce results. , , literal Numeric, logical, textual, and reference literals. , , comment Line or block comments. Usually discarded. , whitespace Groups of non-printable characters. Usually discarded. –
Consider this expression in the C programming language:
The lexical analysis of this expression yields the following sequence of tokens:
A token name is what might be termed a part of speech in linguistics.
Lexical tokenization is the conversion of a raw text into (semantically or syntactically) meaningful lexical tokens, belonging to categories defined by a "lexer" program, such as identifiers, operators, grouping symbols, and data types. The resulting tokens are then passed on to some other form of processing. The process can be considered a sub-task of parsing input.
For example, in the text string: The quick brown fox jumps over the lazy dog
the string is not implicitly segmented on spaces, as a natural language speaker would do. The raw input, the 43 characters, must be explicitly split into the 9 tokens with a given space delimiter (i.e., matching the string " " or regular expression ).
When a token class represents more than one possible lexeme, the lexer often saves enough information to reproduce the original lexeme, so that it can be used in semantic analysis. The parser typically retrieves this information from the lexer and stores it in the abstract syntax tree. This is necessary in order to avoid information loss in the case where numbers may also be valid identifiers.
Tokens are identified based on the specific rules of the lexer. Some methods used to identify tokens include regular expressions, specific sequences of characters termed a flag, specific separating characters called delimiters, and explicit definition by a dictionary. Special characters, including punctuation characters, are commonly used by lexers to identify tokens because of their natural use in written and programming languages. A lexical analyzer generally does nothing with combinations of tokens, a task left for a parser. For example, a typical lexical analyzer recognizes parentheses as tokens but does nothing to ensure that each "(" is matched with a ")".
When a lexer feeds tokens to the parser, the representation used is typically an enumerated type, which is a list of number representations. For example, "Identifier" can be represented with 0, "Assignment operator" with 1, "Addition operator" with 2, etc.
Tokens are often defined by regular expressions, which are understood by a lexical analyzer generator such as lex, or handcoded equivalent finite-state automata. The lexical analyzer (generated automatically by a tool like lex or hand-crafted) reads in a stream of characters, identifies the lexemes in the stream, and categorizes them into tokens. This is termed tokenizing. If the lexer finds an invalid token, it will report an error.
Following tokenizing is parsing. From there, the interpreted data may be loaded into data structures for general use, interpretation, or compiling.
Lexical grammar The specification of a programming language often includes a set of rules, the lexical grammar, which defines the lexical syntax. The lexical syntax is usually a regular language, with the grammar rules consisting of regular expressions; they define the set of possible character sequences (lexemes) of a token. A lexer recognizes strings, and for each kind of string found, the lexical program takes an action, most simply producing a token.
Two important common lexical categories are white space and comments. These are also defined in the grammar and processed by the lexer but may be discarded (not producing any tokens) and considered non-significant, at most separating two tokens (as in if x instead of ifx). There are two important exceptions to this. First, in off-side rule languages that delimit blocks with indenting, initial whitespace is significant, as it determines block structure, and is generally handled at the lexer level; see phrase structure, below. Secondly, in some uses of lexers, comments and whitespace must be preserved – for examples, a prettyprinter also needs to output the comments and some debugging tools may provide messages to the programmer showing the original source code. In the 1960s, notably for ALGOL, whitespace and comments were eliminated as part of the line reconstruction phase (the initial phase of the compiler frontend), but this separate phase has been eliminated and these are now handled by the lexer.
Details Scanner The first stage, the scanner, is usually based on a finite-state machine (FSM). It has encoded within it information on the possible sequences of characters that can be contained within any of the tokens it handles (individual instances of these character sequences are termed lexemes). For example, an integer lexeme may contain any sequence of numerical digit characters. In many cases, the first non-whitespace character can be used to deduce the kind of token that follows and subsequent input characters are then processed one at a time until reaching a character that is not in the set of characters acceptable for that token (this is termed the maximal munch, or longest match, rule). In some languages, the lexeme creation rules are more complex and may involve backtracking over previously read characters. For example, in C, one 'L' character is not enough to distinguish between an identifier that begins with 'L' and a wide-character string literal.
Evaluator A lexeme, however, is only a string of characters known to be of a certain kind (e.g., a string literal, a sequence of letters). The second stage of a lexical analyzer, the evaluator, goes over the characters of the lexeme to produce a value containing relevant information for the parser.
The lexeme's type combined with its value is what properly constitutes a token. The value in the token can be whatever is deemed necessary for the parser to interpret a token of that type. Some examples of typical values produced by an evaluator include:
A token for an identifier will often simply contain the characters of the associated lexeme. Token values for keywords and special characters are usually omitted, as the type alone contains all the information needed. Evaluators processing integer literals may pass the string on as is (deferring evaluation to the semantic analysis phase), or may perform evaluation themselves to produce numeric values. For a simple quoted string literal, the evaluator needs to remove only the quotes, but the evaluator for an escaped string literal may also incorporate a lexer, which unescapes the escape sequences.
The evaluator may also suppress a lexeme entirely, concealing it from the parser, which is useful for whitespace and comments.
For example, in the source code of a computer program, the string
might be converted into the following lexical token stream; where each line represents a token composed of a TYPE followed by an optional value: IDENTIFIER "net_worth_future" EQUALS OPEN_PARENTHESIS IDENTIFIER "assets" MINUS IDENTIFIER "liabilities" CLOSE_PARENTHESIS SEMICOLON
Lexers may be written by hand. This is practical if the list of tokens is small, but lexers generated by automated tooling as part of a compiler-compiler toolchain are more practical for a larger number of potential tokens. These tools generally accept regular expressions that describe the tokens allowed in the input stream. Each regular expression is associated with a production rule in the lexical grammar of the programming language that evaluates the lexemes matching the regular expression. These tools may generate source code that can be compiled and executed or construct a state transition table for a finite-state machine (which is plugged into template code for compiling and executing).
Regular expressions compactly represent patterns that the characters in lexemes might follow. For example, for an English-based language, an IDENTIFIER token might be any English alphabetic character or an underscore, followed by any number of instances of ASCII alphanumeric characters and/or underscores. This could be represented compactly by the string . This means "any character a-z, A-Z or _, followed by 0 or more of a-z, A-Z, _ or 0-9".