Parsing,syntax analysis, orsyntactic analysis is a process of analyzing astring ofsymbols, either innatural language,computer languages ordata structures, conforming to the rules of aformal grammar by breaking it into parts. The termparsing comes from Latinpars (orationis), meaningpart (of speech).[1]
The term has slightly different meanings in different branches oflinguistics andcomputer science. Traditionalsentence parsing is often performed as a method of understanding the exact meaning of a sentence or word, sometimes with the aid of devices such assentence diagrams. It usually emphasizes the importance of grammatical divisions such assubject andpredicate.
Withincomputational linguistics the term is used to refer to the formal analysis by a computer of a sentence or other string of words into its constituents, resulting in aparse tree showing their syntactic relation to each other, which may also containsemantic information.[citation needed] Some parsing algorithms generate aparse forest or list of parse trees from a string that issyntactically ambiguous.[2]
The term is also used inpsycholinguistics when describing language comprehension. In this context, parsing refers to the way that human beings analyze a sentence or phrase (in spoken language or text) "in terms of grammatical constituents, identifying the parts of speech, syntactic relations, etc."[1] This term is especially common when discussing which linguistic cues help speakers interpretgarden-path sentences.
Within computer science, the term is used in the analysis ofcomputer languages, referring to the syntactic analysis of the input code into its component parts in order to facilitate the writing ofcompilers andinterpreters. The term may also be used to describe a split or separation.
In data analysis, the term is often used to refer to a process extracting desired information from data, e.g., creating atime series signal from aXML document.
The traditional grammatical exercise of parsing, sometimes known asclause analysis, involves breaking down a text into its componentparts of speech with an explanation of the form, function, and syntactic relationship of each part.[3] This is determined in large part from study of the language'sconjugations anddeclensions, which can be quite intricate for heavilyinflected languages. To parse a phrase such as "man bites dog" involves noting that thesingular noun "man" is thesubject of the sentence, the verb "bites" is thethird person singular of thepresent tense of the verb "to bite", and the singular noun "dog" is theobject of the sentence. Techniques such assentence diagrams are sometimes used to indicate relation between elements in the sentence.
Parsing was formerly central to the teaching of grammar throughout the English-speaking world, and widely regarded as basic to the use and understanding of written language.[citation needed]
 | This sectionneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources in this section. Unsourced material may be challenged and removed.(February 2013) (Learn how and when to remove this message) |
In somemachine translation andnatural language processing systems, written texts in human languages are parsed by computer programs.[4] Human sentences are not easily parsed by programs, as there is substantialambiguity in the structure of human language, whose usage is to convey meaning (orsemantics) amongst a potentially unlimited range of possibilities, but only some of which are germane to the particular case.[5] So an utterance "Man bites dog" versus "Dog bites man" is definite on one detail but in another language might appear as "Man dog bites" with a reliance on the larger context to distinguish between those two possibilities, if indeed that difference was of concern. It is difficult to prepare formal rules to describe informal behaviour even though it is clear that some rules are being followed.[citation needed]
In order to parse natural language data, researchers must first agree on thegrammar to be used. The choice of syntax is affected by bothlinguistic and computational concerns; for instance some parsing systems uselexical functional grammar, but in general, parsing for grammars of this type is known to beNP-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 PennTreebank.Shallow parsing aims to find only the boundaries of major constituents such as noun phrases. Another popular strategy for avoiding linguistic controversy isdependency grammar parsing.
Most modern parsers are at least partly statistical; that is, they rely on acorpus 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.(Seemachine learning.) Approaches which have been used include straightforwardPCFGs (probabilistic context-free grammars),[6]maximum entropy,[7] andneural nets.[8] Most of the more successful systems uselexical statistics (that is, they consider the identities of the words involved, as well as theirpart of speech). However such systems are vulnerable tooverfitting and require some kind ofsmoothing to be effective.[citation needed]
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 difficult to parse computationally; in general, even if the desired structure is notcontext-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 theCYK algorithm, usually with someheuristic to prune away unlikely analyses to save time.(Seechart parsing.) However some systems trade speed for accuracy using, e.g., linear-time versions of theshift-reduce algorithm. A somewhat recent development has beenparse reranking in which the parser proposes some large number of analyses, and a more complex system selects the best option.[citation needed] Innatural language understanding applications,semantic parsers convert the text into a representation of its meaning.[9]
Inpsycholinguistics, parsing involves not just the assignment of words to categories (formation of ontological insights), but the evaluation of the meaning of a sentence according to the rules of syntax drawn by inferences made from each word in the sentence (known asconnotation). This normally occurs as words are being heard or read.
Neurolinguistics generally understands parsing to be a function of working memory, meaning that parsing is used to keep several parts of one sentence at play in the mind at one time, all readily accessible to be analyzed as needed. Because the human working memory has limitations, so does the function of sentence parsing.[10] This is evidenced by several different types of syntactically complex sentences that demonstrate potential issues for mental parsing of sentences.
The first, and perhaps most well-known, type of sentence that challenges parsing ability is the garden-path sentence. These sentences are designed so that the most common interpretation of the sentence appears grammatically faulty, but upon further inspection, these sentences are grammatically sound. Garden-path sentences are difficult to parse because they contain a phrase or a word with more than one meaning, often their most typical meaning being a different part of speech.[11] For example, in the sentence, "the horse raced past the barn fell", raced is initially interpreted as a past tense verb, but in this sentence, it functions as part of an adjective phrase.[12] Since parsing is used to identify parts of speech, these sentences challenge the parsing ability of the reader.
Another type of sentence that is difficult to parse is an attachment ambiguity, which includes a phrase that could potentially modify different parts of a sentence, and therefore presents a challenge in identifying syntactic relationship (i.e. "The boy saw the lady with the telescope", in which the ambiguous phrase with the telescope could modify the boy saw or the lady.)[11]
A third type of sentence that challenges parsing ability is center embedding, in which phrases are placed in the center of other similarly formed phrases (i.e. "The rat the cat the man hit chased ran into the trap".) Sentences with 2 or in the most extreme cases 3 center embeddings are challenging for mental parsing, again because of ambiguity of syntactic relationship.[13]
Within neurolinguistics there are multiple theories that aim to describe how parsing takes place in the brain. One such model is a more traditional generative model of sentence processing, which theorizes that within the brain there is a distinct module designed for sentence parsing, which is preceded by access to lexical recognition and retrieval, and then followed by syntactic processing that considers a single syntactic result of the parsing, only returning to revise that syntactic interpretation if a potential problem is detected.[14] The opposing, more contemporary model theorizes that within the mind, the processing of a sentence is not modular, or happening in strict sequence. Rather, it poses that several different syntactic possibilities can be considered at the same time, because lexical access, syntactic processing, and determination of meaning occur in parallel in the brain. In this way these processes are integrated.[15]
Although there is still much to learn about the neurology of parsing, studies have shown evidence that several areas of the brain might play a role in parsing. These include the left anterior temporal pole, the left inferior frontal gyrus, the left superior temporal gyrus, the left superior frontal gyrus, the right posterior cingulate cortex, and the left angular gyrus. Although it has not been absolutely proven, it has been suggested that these different structures might favor either phrase-structure parsing or dependency-structure parsing, meaning different types of parsing could be processed in different ways which have yet to be understood.[16]
Discourse analysis examines ways to analyze language use and semiotic events. Persuasive language may be calledrhetoric.
| This sectiondoes notcite anysources. Please helpimprove this section byadding citations to reliable sources. Unsourced material may be challenged andremoved.(February 2013) (Learn how and when to remove this message) |
Aparser is a software component that takes input data (typically text) and builds adata structure – often some kind ofparse tree,abstract syntax tree or other hierarchical structure, giving a structural representation of the input while checking for correct syntax. The parsing may be preceded or followed by other steps, or these may be combined into a single step. The parser is often preceded by a separatelexical analyser, which creates tokens from the sequence of input characters; alternatively, these can be combined inscannerless parsing. Parsers may be programmed by hand or may be automatically or semi-automatically generated by aparser generator. Parsing is complementary totemplating, which produces formattedoutput. These may be applied to different domains, but often appear together, such as thescanf/printf pair, or the input (front end parsing) and output (back end code generation) stages of acompiler.
The input to a parser is typically text in somecomputer language, but may also be text in a natural language or less structured textual data, in which case generally only certain parts of the text are extracted, rather than a parse tree being constructed. Parsers range from very simple functions such asscanf, to complex programs such as the frontend of aC++ compiler or theHTML parser of aweb browser. An important class of simple parsing is done usingregular expressions, in which a group of regular expressions defines aregular language and a regular expression engine automatically generating a parser for that language, allowingpattern matching and extraction of text. In other contexts regular expressions are instead used prior to parsing, as the lexing step whose output is then used by the parser.
The use of parsers varies by input. In the case of data languages, a parser is often found as the file reading facility of a program, such as reading in HTML orXML text; these examples aremarkup languages. In the case ofprogramming languages, a parser is a component of acompiler orinterpreter, which parses thesource code of acomputer programming language to create some form of internal representation; the parser is a key step in thecompiler frontend. Programming languages tend to be specified in terms of adeterministic context-free grammar because fast and efficient parsers can be written for them. For compilers, the parsing itself can be done in one pass or multiple passes – seeone-pass compiler andmulti-pass compiler.
The implied disadvantages of a one-pass compiler can largely be overcome by addingfix-ups, where provision is made for code relocation during the forward pass, and the fix-ups are applied backwards when the current program segment has been recognized as having been completed. An example where such a fix-up mechanism would be useful would be a forward GOTO statement, where the target of the GOTO is unknown until the program segment is completed. In this case, the application of the fix-up would be delayed until the target of the GOTO was recognized. Conversely, a backward GOTO does not require a fix-up, as the location will already be known.
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 at thesemantic analysis (contextual analysis) step.
For example, inPython the following is syntactically valid code:
x:int=1print(x)
The following code, however, is syntactically valid in terms of the context-free grammar, yielding a syntax tree with the same structure as the previous, but violates the semantic rule requiring variables to be initialized before use:
x:int=1print(y)
The following example demonstrates the common case of parsing a computer language with two levels of grammar: lexical and syntactic.
The first stage is the token generation, orlexical analysis, by which the input character stream is split into meaningful symbols defined by a grammar ofregular expressions. For example, a calculator program would look at an input such as "12 * (3 + 4)^2" and split it into the tokens12,*,(,3,+,4,),^,2, each of which is a meaningful symbol in the context of an arithmetic expression. The lexer 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 parsing or syntactic analysis, which is checking that the tokens form an allowable expression. This is usually done with reference to acontext-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 withattribute grammars.
The final phase issemantic parsing or analysis, which is working out the implications of the expression just validated and taking the appropriate action.[17] In the case of a calculator or interpreter, the action is to evaluate the expression or program; a compiler, on the other hand, would generate some kind of code. Attribute grammars can also be used to define these actions.
Thetask 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:
LL parsers andrecursive-descent parser are examples of top-down parsers that cannot accommodateleft recursiveproduction rules. Although it has been believed that simple implementations of top-down parsing cannot accommodate direct and indirect left-recursion and may require exponential time and space complexity while parsingambiguous context-free grammars, more sophisticated algorithms for top-down parsing have been created by Frost, Hafiz, and Callaghan[20][21] which accommodateambiguity andleft recursion in polynomial time and which generate polynomial-size representations of the potentially exponential number of parse trees. Their algorithm is able to produce both left-most and right-most derivations of an input with regard to a givencontext-free grammar.
An important distinction with regard to parsers is whether a parser generates aleftmost derivation or arightmost derivation (seecontext-free grammar). LL parsers will generate a leftmostderivation and LR parsers will generate a rightmost derivation (although usually in reverse).[18]
Somegraphical parsing algorithms have been designed forvisual programming languages.[22][23] Parsers for visual languages are sometimes based ongraph grammars.[24]
Adaptive parsing algorithms have been used to construct "self-extending"natural language user interfaces.[25]
A simple parser implementation reads the entire input file, performs an intermediate computation or translation, and then writes the entire output file,such as in-memorymulti-pass compilers.
Alternative parser implementation approaches:
 | This articleis inlist format but may read better asprose. You can help byconverting this article, if appropriate.Editing help is available.(January 2017) |
Some of the well known parser development tools include the following:
| This sectiondoes notcite anysources. Please helpimprove this section byadding citations to reliable sources. Unsourced material may be challenged andremoved.(April 2012) (Learn how and when to remove this message) |
intv;main(){" and is about to choose a rule to deriveStmt. Looking only at the first lookahead token "v", it cannot decide which of both alternatives forStmt to choose; the latter requires peeking at the second token.Lookahead establishes the maximum incoming tokens that a parser can use to decide which rule it should use. Lookahead is especially relevant toLL,LR, andLALR parsers, where it is often explicitly indicated by affixing the lookahead to the algorithm name in parentheses, such as LALR(1).
Mostprogramming languages, the primary target of parsers, are carefully defined in such a way that a parser with limited lookahead, typically one, can parse them, because parsers with limited lookahead are often more efficient. One important change[citation needed] to this trend came in 1990 whenTerence Parr createdANTLR for his Ph.D. thesis, aparser generator for efficient LL(k) parsers, wherek is any fixed value.
LR parsers typically have only a few actions after seeing each token. They are shift (add this token to the stack for later reduction), reduce (pop tokens from the stack and form a syntactic construct), end, error (no known rule applies) or conflict (does not know whether to shift or reduce).
Lookahead has two advantages.[clarification needed]
Example: Parsing the Expression1 + 2 * 3[dubious –discuss]
| Set of expression parsing rules (called grammar) is as follows, | ||
| Rule1: | E → E + E | Expression is the sum of two expressions. |
| Rule2: | E → E * E | Expression is the product of two expressions. |
| Rule3: | E → number | Expression is a simple number |
| Rule4: | + has less precedence than * | |
Most programming languages (except for a few such as APL and Smalltalk) and algebraic formulas give higher precedence to multiplication than addition, in which case the correct interpretation of the example above is1 + (2 * 3).Note that Rule4 above is a semantic rule. It is possible to rewrite the grammar to incorporate this into the syntax. However, not all such rules can be translated into syntax.
Initially Input = [1, +, 2, *, 3]
The parse tree and resulting code from it is not correct according to language semantics.
To correctly parse without lookahead, there are three solutions:
The parse tree generated is correct and simplymore efficient[clarify][citation needed] than non-lookahead parsers. This is the strategy followed inLALR parsers.
