Information AboutParser |
| CATEGORIES ABOUT PARSING | |
| algorithms on strings | |
| compiler theory | |
| parsingalgorithms on strings | |
| compiler theory | |
| parsing | |
| formal languages | |
| syntax | |
| programming language implementation | |
|
In Computer Science and Linguistics , parsing (more formally ''syntactic analysis'') is the process of analyzing a sequence of Tokens to determine its grammatical structure with respect to a given Formal Grammar . A '''parser''' is the component of a Compiler that carries out this task. Parsing transforms input text into a data structure, usually a tree, which is suitable for later processing and which captures the implied hierarchy of the input. Lexical Analysis creates tokens from a sequence of input characters and it is these tokens that are processed by a parser to build a data structure such as Parse Tree or Abstract Syntax Trees . Parsing is also an earlier term for the diagramming of sentences of natural languages, and is still used for the diagramming of Inflected languages, such as the Romance Languages or Latin . There are tools, called parser generators, that can automatically generate a parser (in some programming language) from a grammar written in Backus-Naur Form (e.g. Yacc - yet another compiler compiler). HUMAN LANGUAGES 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. In order to parse natural language data, researchers must first agree on the Grammar to be used. The choice of syntax is affected by both Linguistic and computational concerns; for instance some parsing systems use Lexical Functional Grammar , but in general, parsing for grammars of this type is known to be NP-complete . Head-driven Phrase Structure Grammar is another linguistic formalism which has been popular in the parsing community, but other research efforts have focused on less complex formalisms such as the one used in the Penn Treebank . Shallow Parsing aims to find only the boundaries of major constituents such as noun phrases. Another popular strategy for avoiding linguistic controversy is Dependency Grammar parsing. Most modern parsers are at least partly Statistical ; that is, they rely on a corpus of training data which has already been annotated (parsed by hand). This approach allows the system to gather information about the frequency with which various constructions occur in specific contexts. ''(See Machine Learning .)'' Approaches which have been used include straightforward PCFG s (probabilistic context free grammars), Maximum Entropy , and Neural Net s. Most of the more successful systems use ''lexical'' statistics (that is, they consider the identities of the words involved, as well as their Part Of Speech ). However such systems are vulnerable to Overfitting and require some kind of smoothing to be effective. Parsing algorithms for natural language cannot rely on the grammar having 'nice' properties as with manually-designed grammars for programming languages. As mentioned earlier some grammar formalisms are very computationally difficult to parse; in general, even if the desired structure is not Context-free , some kind of context-free approximation to the grammar is used to perform a first pass. Algorithms which use context-free grammars often rely on some variant of the CKY Algorithm , usually with some Heuristic to prune away unlikely analyses to save time. ''(See Chart Parsing .)'' However some systems trade speed for accuracy using, eg, linear-time versions of the Shift-reduce algorithm. A somewhat recent development has been Parse Reranking in which the parser proposes some large number of analyses, and a more complex system selects the best option. PROGRAMMING LANGUAGES The most common use of a parser is as a component of a Compiler . This parses the Source Code of a Computer Programming Language to create some form of internal representation. Programming languages tend to be specified in terms of a Context-free Grammar because fast and efficient parsers can be written for them. Parsers are usually not written by hand but are generated by Parser Generator s. Context-free grammars are limited in the extent to which they can express all of the requirements of a language. Informally, the reason is that the memory of such a language is limited. The grammar cannot remember the presence of a construct over an arbitrarily long input; this is necessary for a language in which, for example, a name must be declared before it may be referenced. More powerful grammars that can express this constraint, however, cannot be parsed efficiently. Thus, it is a common strategy to create a relaxed parser for a context-free grammar which accepts a superset of the desired language constructs (that is, it accepts some invalid constructs); later, the unwanted constructs can be filtered out. Overview of process The following example demonstrates the common case of parsing a computer language with two levels of grammar: lexical and syntactic.
The next stage is syntactic parsing or syntactic analysis, which is checking that the tokens form an allowable expression. This is usually done with reference to a Context-free Grammar which recursively defines components that can make up an expression and the order in which they must appear. However, not all rules defining programming languages can be expressed by context-free grammars alone, for example type validity and proper declaration of identifiers. These rules can be formally expressed with Attribute Grammar s. 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 code. Attribute grammars can also be used to define these actions. TYPES OF PARSERS The task of the parser is essentially to determine if and how the input can be derived from the start symbol of the grammar. This can be done in essentially two ways:
Another important distinction is whether the parser generates a ''leftmost derivation'' or a ''rightmost derivation'' (see Context-free Grammar ). LL parsers will generate a leftmost Derivation and LR parsers will generate a rightmost derivation (although usually in reverse). EXAMPLES OF PARSERS Top-down parsers Some of the parsers that use Top-down Parsing include: Bottom-up parsers Some of the parsers that use Bottom-up Parsing include:
REFERENCES
SEE ALSO Parsing concepts Parser Development Software See also: List Of Parsers comparison table. Free Software
= Wikimedia Commercial |
|
|