Citizendia
Your Ad Here

In computer science, lexical analysis is the process of converting a sequence of characters into a sequence of tokens. Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their Programs performing lexical analysis are called lexical analyzers or lexers. A lexer is often organized as separate scanner and tokenizer functions, though the boundaries may not be clearly defined.

Contents

Lexical grammar

The specification of a programming language will include a set of rules, often expressed syntactically, specifying the set of possible character sequences that can form a token or lexeme. A programming language is an Artificial language that can be used to write programs which control the behavior of a machine particularly a Computer. For its use in the context of Computer Science see Lexical analysis. The whitespace characters are often ignored during lexical analysis. In Process management, the White Space as described by Geary A

Token

A token is a categorized block of text. The block of text corresponding to the token is known as a lexeme. For its use in the context of Computer Science see Lexical analysis. A lexical analyzer processes lexemes to categorize them according to function, giving them meaning. This assignment of meaning is known as tokenization. A token can look like anything: English, gibberish symbols, anything; it just needs to be a useful part of the structured text.

Consider this line in the C programming language: sum=3+2; Tokenized in the following table:

lexeme token type
sum IDENT
= ASSIGN_OP
3 NUMBER
+ ADD_OP
2 NUMBER
; SEMICOLON

Tokens are frequently defined by regular expressions, which are understood by a lexical analyzer such as lex. In Computing, regular expressions provide a concise and flexible means for identifying strings of text of interest such as particular characters words or patterns of characters In Computer science, lex is a program that generates lexical analyzers ("scanners" or "lexers" The lexical analyzer reads in a stream of characters, identifies the lexemes in the stream, and categorizes them into tokens. This is called "tokenizing. " If the lexer finds an invalid token, it will report an error.

Following tokenizing is parsing. In Computer science and Linguistics, parsing, or more formally syntactic analysis, is the process of analyzing a sequence of tokens to From there, the interpreted data may be loaded into data structures, for general use, interpretation, or compiling. A compiler is a Computer program (or set of programs that translates text written in a computer language (the source language) into another

Consider a text describing a calculation: "46 - number_of(cows); ". The lexemes here might be: "46", "-", "number_of", "(", "cows", ")" and ";". The lexical analyzer will denote lexemes "46" as 'number', "-" as 'character' and "number_of" as a separate token. Even the lexeme ";" in some languages (such as C) has some special meaning.

Scanner

The first stage, the scanner, is usually based on a finite state machine. 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 known as lexemes). For its use in the context of Computer Science see Lexical analysis. For instance, an integer token may contain any sequence of numerical digit characters. In Mathematics and Computer science, a digit is a symbol (a number symbol e 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 known as the maximal munch rule). In Computer programming, the "maximal munch" principle is the rule that as much of the Input as possible should be processed when creating some construct In some languages the lexeme creation rules are more complicated and may involve backtracking over previously read characters. Backtracking is a type of Algorithm that is a refinement of Brute force search.

Tokenizer

Tokenization is the process of demarcating and possibly classifying sections of a string of input characters. The resulting tokens are then passed on to some other form of processing. The process can be considered a sub-task of parsing input. In Computer science and Linguistics, parsing, or more formally syntactic analysis, is the process of analyzing a sequence of tokens to

Take, for example, the following string. Unlike humans, a computer cannot intuitively 'see' that there are 9 words. To a computer this is only a series of 43 characters. 

The quick brown fox jumps over the lazy dog

A process of tokenization could be used to split the sentence into word tokens. Although the following example is given as XML there are many ways to store tokenized input:

<sentence>
  <word>The</word>
  <word>quick</word>
  <word>brown</word>
  <word>fox</word>
  <word>jumps</word>
  <word>over</word>
  <word>the</word>
  <word>lazy</word>
  <word>dog</word>
 </sentence>

A lexeme, however, is only a string of characters known to be of a certain kind (eg, a string literal, a sequence of letters). Don't change "Extensible" For its use in the context of Computer Science see Lexical analysis. In order to construct a token, the lexical analyzer needs a second stage, the evaluator, which goes over the characters of the lexeme to produce a value. The lexeme's type combined with its value is what properly constitutes a token, which can be given to a parser. (Some tokens such as parentheses do not really have values, and so the evaluator function for these can return nothing. The evaluators for integers, identifiers, and strings can be considerably more complex. Sometimes evaluators can 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

net_worth_future = (assets - liabilities);

might be converted (with whitespace suppressed) into the lexical token stream:

NAME "net_worth_future" 
EQUALS 
OPEN_PARENTHESIS 
NAME "assets" 
MINUS 
NAME "liabilities" 
CLOSE_PARENTHESIS 
SEMICOLON

Though it is possible and sometimes necessary to write a lexer by hand, lexers are often generated by automated tools. These tools generally accept regular expressions that describe the tokens allowed in the input stream. In Computing, regular expressions provide a concise and flexible means for identifying strings of text of interest such as particular characters words or patterns of characters Each regular expression is associated with a production 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 table for a finite state machine (which is plugged into template code for compilation and execution).

Regular expressions compactly represent patterns that the characters in lexemes might follow. In Computing, regular expressions provide a concise and flexible means for identifying strings of text of interest such as particular characters words or patterns of characters For example, for an English-based language, a NAME token might be any English alphabetical character or an underscore, followed by any number of instances of any ASCII alphanumeric character or an underscore. English is a West Germanic language originating in England and is the First language for most people in the United Kingdom, the United States This could be represented compactly by the string [a-zA-Z_][a-zA-Z_0-9]*. This means "any character a-z, A-Z or _, followed by 0 or more of a-z, A-Z, _ or 0-9".

Regular expressions and the finite state machines they generate are not powerful enough to handle recursive patterns, such as "n opening parentheses, followed by a statement, followed by n closing parentheses. " They are not capable of keeping count, and verifying that n is the same on both sides — unless you have a finite set of permissible values for n. It takes a full-fledged parser to recognize such patterns in their full generality. A parser can push parentheses on a stack and then try to pop them off and see if the stack is empty at the end.

The Lex programming tool and its compiler is designed to generate code for fast lexical analysers based on a formal description of the lexical syntax. In Computer science, lex is a program that generates lexical analyzers ("scanners" or "lexers" It is not generally considered sufficient for applications with a complicated set of lexical rules and severe performance requirements; for instance, the GNU Compiler Collection uses hand-written lexers. The GNU Compiler Collection (usually shortened to GCC) is a set of Compilers produced for various Programming languages by the GNU Project

Lexer generator

Lexical analysis can often be performed in a single pass if reading is done a character at a time. Single-pass lexers can be generated by tools such as the classic flex. flex (fast Lexical analyzer generator is a Free software alternative to lex.

The lex/flex family of generators uses a table-driven approach which is much less efficient than the directly coded approach. With the latter approach the generator produces an engine that directly jumps to follow-up states via goto statements. Tools like re2c and queχ have proven (e. g. article about re2c) to produce engines that are between two to three times faster than flex produced engines. It is in general difficult to hand-write analyzers that perform better than engines generated by these latter tools.

The simple utility of using a scanner generator should not be discounted, especially in the developmental phase, when a language specification might change daily. The ability to express lexical constructs as regular expressions facilitates the description of a lexical analyzer. In Computing, regular expressions provide a concise and flexible means for identifying strings of text of interest such as particular characters words or patterns of characters Some tools offer the specification of pre- and post-conditions which are hard to program by hand. In that case, using a scanner generator may save a lot of development time.

Lexical analyzer generators

See also

References

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic