Parsing
From Wikipedia, the free encyclopedia.
In grammar and linguistics, parsing is the process by which a person makes sense of a sentence, usually by breaking it down into words or phrases. Parsing used to be taught as a formal activity in schools as part of language education.
Parsing is also used, usually with negative connotation, to describe the over-analysis of a person's remarks, or a portion thereof, for the purpose of discerning meaning which was not intended. It may also refer to a close inspection of a statement to separate its literal meaning from the initial impression it conveys. (For example, former U.S. President Bill Clinton was frequently accused of making statements that required careful parsing, in an attempt to avoid technical or legal untruth while still implying a desired meaning.)
In computer science, parsing is the process of splitting up a continuous stream of characters (read from a file or keyboard input, for example) into meaningful tokens, and then building a parse tree from those tokens. The name is by analogy with the usage in grammar and linguistics.
There are two primary ways to parse a stream:
- Top-down parsing - a parse tree is constructed starting from the top and deriving down
- Bottom-up parsing - a parse tree is constructed starting from the bottom and reducing up
A parser is a computer program that carries out this task.
In some machine translation and natural language processing systems, human languages are parsed by computer programs. Human sentences are not easily parsed by programs, as there is substantial ambiguity in the structure of human language.
The most common use of parsers is to parse computer programming languages. These have simple and regular grammars. The description below describes the common case of parsing a language with two levels of grammar: lexical and syntactic.
The first stage is the token generation, or lexical parse phase. For example, a calculator program would look at input like "12*(3+4)^2" and split it into the tokens 12, *, (, 3, +, 4, ), ^ and 2, each of which is a meaningful symbol in the context of an arithmetic expression. The parser would contain rules to tell it that the characters *, +, ^, ( and ) mark the start of a new token, so meaningless tokens like "12*" or "(3" will not be generated.
The next stage is syntactic parsing or syntax analysis, which is checking that the tokens form an allowable expression. This is usually done with reference to a context-free grammar (CFG) which recursively defines components that can make up an expression and the order in which they must appear.
The final phase is semantic parsing or analysis, which is working out the implications of the expression just validated and taking the appropriate action. In the case of a calculator, the action is to evaluate the expression; a compiler, on the other hand, would generate the machine language that performs the functionality stated in the code.
