... >> Computer Science >> Algorithm Design >> Parsing
Definition: the analysis, by computer, of the structure of statements in a human or artificial language. For instance, Windows has to parse the command dir b: /p to determine that dir is the name of the command, b: specifies the files to be shown, and p is another parameter (in this case, it means “pause when the screen is full”). Compilers and interpreters have to parse statements in programming languages. (See COMPILER; INTERPRETER.) Programs that accept natural-language input have to parse sentences in human languages. Parsing is done by comparing the string to be parsed to a grammar, which defines possible structures. Parsing can be done either top-down or bottom-up. In top-down parsing, the computer starts by looking for a particular constituent. Parsing algorithms must be able to backtrack (back up and try alternatives) because the grammar provides alternatives. For example, a noun phrase may or may not contain an adjective, and a word like leaves can be a verb or a noun. Further, parsing algorithms usually use recursion to handle the recursive structure of human languages. For example, a noun phrase can contain a noun phrase, which can contain another noun phrase, as in the discoverer of the solution to the problem. See BACKTRACKING; NATURAL LANGUAGE PROCESSING; RECURSION.
Source: Downing, Douglas, et al. Dictionary of Computer and Internet Terms. 10th ed. New York, 2009. Print.