 | Merging this article or section with parsing may be desirable. (Discuss) | A parser is a computer program or a component of a program that analyses the grammatical structure of an input, with respect to a given formal grammar, a process known as parsing. Typically, a parser transforms some input text into a data structure that can be processed easily, e.g. for semantic checking, code generation or simply to ease the further understanding of the input. Such a data structure usually captures the implied hierarchy of the input and forms a tree or even a graph. Wikipedia does not have an article with this exact name. ...
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. ...
A computer program (often simply called a program) is an example of computer software that prescribes the actions (computations) that are to be carried out by a computer. ...
The structure of a thing is how the parts of it relate to each other, how it is put together. This contrast with process, which is how the thing works; but process requires a viable structure. ...
Information processing In information processing, input is the process of receiving information from an object. ...
In computer science a formal grammar is an abstract structure that describes a formal language precisely, i. ...
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. ...
A binary tree, a simple type of branching linked data structure. ...
In general, semantics (from the Greek semantikos, or significant meaning, derived from sema, sign) is the study of meaning, in some sense of that term. ...
In computer science, code generation is the process by which a compiler converts a syntactically-correct program into a series of instructions that could be executed by a machine. ...
The coniferous Coast Redwood, the tallest tree species on earth A tree can be defined as a large, perennial, woody plant. ...
Parsers can be made both for natural languages and for programming languages. Programming language parsers tend to be based on context free grammars as fast and efficient parsers can be written for them. Context free grammars however are limited in their expressiveness because they can describe only a limited number of languages Informally, the range of memorization is limited. E.g., one cannot memorize the occurance of a construct over an arbitrary length of input which is necessary if in a language a construct has to be mentioned first before one can refer to it. More powerful grammars however cannot be parsed efficiently or are not intuitive at all. Thus, a common strategy to accept such language constructs is to relax the parser, i.e. let it accept a broader language with invalid constructs and filter these afterwards. Note that it is usually not a problem to find a context free grammar including all desired language constructs. Rather, it is often impossible to restrict a context free grammar to descibe only valid constructs. The term natural language is used to distinguish languages spoken by humans for general-purpose communication from constructs such as computer-programming languages or the languages used in the study of formal logic, especially mathematical logic. ...
A programming language or computer language is a standardized communication technique for expressing instructions to a computer. ...
In linguistics and computer science, a context-free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a non-terminal symbol and w is a string consisting of terminals and/or non-terminals. ...
For example LALR parsers are capable of efficiently analysing a wide class of context free grammars. Such parsers are usually not written by hand but generated by parser generators. Look-Ahead LR parsers or LALR parsers are a specialized form of LR parsers that can deal with more context-free grammars than Simple LR parsers but less than LR(1) parsers can. ...
A compiler-compiler or parser generator is a utility for generating the source code of a parser, interpreter or compiler from an annotated language description in the form of a grammar (usually in BNF) plus code that is associated with each of the rules of the grammar that should be...
The task of the parser can be summarized as to determine if and how the input can be derived from the start symbol with the rules of the formal grammar. A parser can do this in essentially two ways: it can start with the input and attempt to rewrite it to the start symbol, a so-called bottom-up parser, or it can start with the start symbol and try to rewrite it to the input, a so-called top-down parser. For example LL parsers are top-down parsers and LR parsers are bottom-up parsers. Bottom-up parsing is a technique that can be used in compilers that translate human-readable computer languages to assembly language or pseudocode. ...
A compiler parses input from a programming language to assembly language or an internal representation by matching the incoming symbols to Backus-Naur form production rules. ...
An LL parser is a table-based top-down parser for a subset of the context-free grammars. ...
In computer science, an LR parser is a type of bottom-up parser for context-free grammars that is very commonly used by computer programming language compilers (and other associated tools). ...
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). In linguistics and computer science, a context-free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a non-terminal symbol and w is a string consisting of terminals and/or non-terminals. ...
There are several meanings of derivation: A derivation in abstract algebra is a linear map that satisfies Leibniz law. ...
Overview of parsers
Top-down parsers Some of the parsers that use top-down parsing include: A compiler parses input from a programming language to assembly language or an internal representation by matching the incoming symbols to Backus-Naur form production rules. ...
A recursive descent parser is a top-down parser built from a set of mutually-recursive procedures or a non-recursive equivalent where each such procedure usually implements one of the production rules of the grammar. ...
An LL parser is a table-based top-down parser for a subset of the context-free grammars. ...
A packrat parser is a form of parser similar to a recursive descent parser in construction, except that during the parsing process it memoizes the intermediate results of all invocations of the mutually recursive parsing functions. ...
Bottom-up parsers Some of the parsers that use bottom-up parsing include: Bottom-up parsing is a technique that can be used in compilers that translate human-readable computer languages to assembly language or pseudocode. ...
In computer science, an LR parser is a type of bottom-up parser for context-free grammars that is very commonly used by computer programming language compilers (and other associated tools). ...
A Simple LR parser or SLR parser is an LR parser for which the parsing tables are generated as for an LR(0) parser except that it only performs a reduction with a grammar rule A → w if the next symbol on the input stream is in the follow set...
Look-Ahead LR parsers or LALR parsers are a specialized form of LR parsers that can deal with more context-free grammars than Simple LR parsers but less than LR(1) parsers can. ...
A canonical LR parser or LR(1) parser is an LR parser whose parsing tables are constructed in a similar way as with LR(0) parsers except that the items in the item sets also contain a follow, i. ...
The Earley parser is a type of chart parser mainly used for parsing in computational linguistics, named after its inventor, Jay Earley. ...
The Cocke-Younger-Kasami (CYK) algorithm (alternatively called CKY) determines whether a string can be generated by a given context-free grammar and, if so, how it can be generated. ...
See also A chart parser is a type of parser commonly used for natural languages that uses a data-driven approach based on a set of grammatical rules and a dictionary with each of the possible grammatical senses of each word indicated. ...
A compiler-compiler or parser generator is a utility for generating the source code of a parser, interpreter or compiler from an annotated language description in the form of a grammar (usually in BNF) plus code that is associated with each of the rules of the grammar that should be...
SableCC is an open source compiler generator (or interpreter generator) in Java. ...
JavaCC (Java Compiler Compiler) is a parser generator for the Java programming language. ...
It is requested that an image(s) should be included, to improve the articles quality. ...
Lex is a program that generates lexical analyzers (scanners). Lex is commonly used with the yacc parser generator. ...
A pass can refer to: a mountain pass, a low place in a mountain range allowing easier passage a strait or passage, usually used of one that is very narrow but still navigable permission to be away from ones unit for a short period in the U.S. military...
The Spirit Parser Framework is an object oriented recursive descent parser generator framework implemented using template meta-programming techniques. ...
Shallow parsing (light parsing) is an analysis of a sentence which identifies the constituents (noun groups, verbs,...), but does not specify their internal structure, nor their role in the main sentence. ...
References - This article was originally based on material from the Free On-line Dictionary of Computing, which is licensed under the GFDL.
The Free On-line Dictionary of Computing (FOLDOC) is an on-line, searchable encyclopedic dictionary of computing subjects. ...
GNU logo The GNU Free Documentation License (GNU FDL or simply GFDL) is a copyleft license for free content, designed by the Free Software Foundation (FSF) for the GNU project. ...
External links - TFunctionParser (http://www.MHGSoft.de?Parser) Comprehensive Mathematical Parser (more than 90 functions and operations)
- UCalc Fast Math Parser (http://www.ucalc.com/mathparser) A commercial expression parser
- muParser (http://muparser.sourceforge.net/) An Open Source parser for mathematical expressions
- Parsing Techniques - A Practical Guide (http://www.cs.vu.nl/~dick/PTAPG.html) by Dick Grune and Ceriel J.H. Jacobs.
|
Feeds |
Contact