Editing Parse tree (section)

{{Short description|Tree in formal language theory}}
[[File:Parse-tree.svg|thumb|Parse tree of the string "aab" with respect to the production rules <math>\begin{matrix}\text{S}&\to&\text{AB}\\
 \text{A}&\to&\text{aA}\\
 \text{A}&\to&\varepsilon\\
 \text{B}&\to&\text{b}\end{matrix}</math>]]

A '''parse tree''' or '''parsing tree'''<ref>See Chiswell and Hodges 2007: 34.</ref> (also known as a '''derivation tree''' or '''concrete syntax tree''') is an ordered, rooted [[tree (data structure)|tree]] that represents the [[syntax|syntactic]] structure of a [[string (computer science)|string]] according to some [[context-free grammar]]. The term ''parse tree'' itself is used primarily in [[computational linguistics]]; in theoretical syntax, the term ''syntax tree'' is more common.

Concrete syntax trees reflect the syntax of the input language, making them distinct from the [[abstract syntax tree]]s used in computer programming. Unlike [[sentence diagram#Reed-Kellogg system|Reed-Kellogg sentence diagram]]s used for teaching grammar, parse trees do not use distinct symbol shapes for different types of [[Constituent (linguistics)|constituents]].

Parse trees are usually constructed based on either the constituency relation of constituency grammars ([[phrase structure grammar]]s) or the dependency relation of [[dependency grammar]]s. Parse trees may be generated for [[sentence (linguistics)|sentence]]s in [[natural language]]s (see [[natural language processing]]), as well as during [[compiler|processing]] of computer languages, such as [[programming language]]s.

A related concept is that of '''phrase marker''' or '''P-marker''', as used in [[transformational generative grammar]]. A phrase marker is a linguistic expression marked as to its phrase structure. This may be presented in the form of a tree, or as a bracketed expression. Phrase markers are generated by applying [[phrase structure rules]], and themselves are subject to further transformational rules.<ref name="Chomsky2014">{{cite book|author=Noam Chomsky|title=Aspects of the Theory of Syntax|url=https://books.google.com/books?id=ljFkBgAAQBAJ&q=%22phrase+marker%22|date=26 December 2014|publisher=MIT Press|isbn=978-0-262-52740-8}}</ref> A set of possible parse trees for a [[syntactically ambiguous]] sentence is called a "parse forest".<ref>Billot, Sylvie, and Bernard Lang. "[https://hal.inria.fr/inria-00075520/document The structure of shared forests in ambiguous parsing]."</ref>