parsing

process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar

Uses your system voice; voice and rate in settings.

≈ 8 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

  • Polskianalizator składniowy
  • Englishparsing
  • 한국어구문 분석
  • 中文语法分析器
  • 简体中文语法分析器
  • 繁體中文語法分析器
  • 中文語法分析器
  • 中文语法分析器
  • 中文語法分析器

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Parsing, syntax analysis, or syntactic analysis is a process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar by breaking it into parts. The term parsing comes from Latin pars (orationis), meaning part (of speech).

The term has slightly different meanings in different branches of linguistics and computer science. Traditional sentence parsing is often performed as a method of understanding the exact meaning of a sentence or word, sometimes with the aid of devices such as sentence diagrams. It usually emphasizes the importance of grammatical divisions such as subject and predicate.

Within computational 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 a parse tree showing their syntactic relation to each other, which may also contain semantic information. Some parsing algorithms generate a parse forest or list of parse trees from a string that is syntactically ambiguous.

The term is also used in psycholinguistics 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." This term is especially common when discussing which linguistic cues help speakers interpret garden-path sentences.

Within computer science, the term is used in the analysis of computer languages, referring to the syntactic analysis of the input code into its component parts in order to facilitate the writing of compilers and interpreters. 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 a time series signal from a XML document. x: int = 1 print(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 = 1 print(y) program that cannot be parsed with less than 2 token lookahead. Top: C grammar excerpt.

Bottom: a parser has digested the tokens " int v;main(){ " and is about to choose a rule to derive Stmt. Looking only at the first lookahead token " v ", it cannot decide which of both alternatives for Stmt 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 to LL, LR, and LALR parsers, where it is often explicitly indicated by affixing the lookahead to the algorithm name in parentheses, such as LALR(1). Most programming 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 to this trend came in 19901 when Terence Parr created ANTLR for his Ph.D. thesis, a parser generator for efficient LL(k) parsers, where k 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. It helps the parser take the correct action in case of conflicts.

For example, parsing the if statement in the case of an else clause. It eliminates many duplicate states and eases the burden of an extra stack. A C language non-lookahead parser will have around 10,000 states.

A lookahead parser will have around 300 states. Example: Parsing the Expression 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 is . 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. Simple non-lookahead parser actions Initially Input = [1, +, 2, *, 3] Shift "1" onto stack from input (in anticipation of rule3).

Input = [+, 2, *, 3] Stack = [1] Reduces "1" to expression "E" based on rule3. Stack = [E] Shift "+" onto stack from input (in anticipation of rule1). Input = [2, *, 3] Stack = [E, +] Shift "2" onto stack from input (in anticipation of rule3).

Input = [*, 3] Stack = [E, +, 2] Reduce stack element "2" to Expression "E" based on rule3. Stack = [E, +, E] Reduce stack items [E, +, E] and new input "E" to "E" based on rule1. Stack = [E] Shift "*" onto stack from input (in anticipation of rule2).

Input = [3] Stack = [E,*] Shift "3" onto stack from input (in anticipation of rule3). Input = [] (empty) Stack = [E, *, 3] Reduce stack element "3" to expression "E" based on rule3. Stack = [E, *, E] Reduce stack items [E, *, E] and new input "E" to "E" based on rule2.

Stack = [E] 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 user has to enclose expressions within parentheses. This often is not a viable solution.

The parser needs to have more logic to backtrack and retry whenever a rule is violated or not complete. The similar method is followed in LL parsers. Alternatively, the parser or grammar needs to have extra logic to delay reduction and reduce only when it is absolutely sure which rule to reduce first.

This method is used in LR parsers. This correctly parses the expression but with many more states and increased stack depth. Lookahead parser actions Shift 1 onto stack on input 1 in anticipation of rule3.

It does not reduce immediately. Reduce stack item 1 to simple Expression on input + based on rule3. The lookahead is +, so we are on path to E +, so we can reduce the stack to E. Shift + onto stack on input + in anticipation of rule1.

Shift 2 onto stack on input 2 in anticipation of rule3. Reduce stack item 2 to Expression on input * based on rule3. The lookahead * expects only E before it.

Now stack has E + E and still the input is *. It has two choices now, either to shift based on rule2 or reduction based on rule1. Since * has higher precedence than + based on rule4, we shift * onto stack in anticipation of rule2.

Shift 3 onto stack on input 3 in anticipation of rule3. Reduce stack item 3 to Expression after seeing end of input based on rule3. Reduce stack items E * E to E based on rule2.

Reduce stack items E + E to E based on rule1. The parse tree generated is correct and simply than non-lookahead parsers. This is the strategy followed in LALR parsers.

Chapman, Nigel P., LR Parsing: Theory and Practice, Cambridge University Press, 1987. Grune, Dick; Jacobs, Ceriel J.H., Parsing Techniques - A Practical Guide, Vrije Universiteit Amsterdam, Amsterdam, the Netherlands. Originally published by Ellis Horwood, Chichester, England, 1990;

The Lemon LALR Parser Generator Stanford Parser The Stanford Parser Turin University Parser Natural language parser for the Italian, open source, developed in Common Lisp by Leonardo Lesmo, University of Torino, Italy. Short history of parser construction

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378947210 under CC BY-SA 4.0; modifications have been made.

References

  1. ↩Wikipedia “parsing” revision 1378947210 · retrieved 2026-10-20 publication date (×1) · confidence 0.95 revision URL

Provenance

snapshot parsing-023124-7f90a8d7c424b6c7 · hash 7f90a8d7c424b6c75c7fc1525f5896d0f089e710880368a4d539635130627de1 · captured 2026-10-06 · ledger · version history

Cite this page as: encyclopegia.org, “parsing”, snapshot parsing-023124-7f90a8d7c424b6c7. https://encyclopegia.org/a/parsing