What is the Difference Between Parse Tree and Syntax Tree

The main difference between parse tree and syntax tree is that parse tree is a hierarchical structure that represents the derivation of the grammar to obtain input strings while syntax tree is a way of representing the syntax of a programming language as a hierarchical form similar to a tree

A parse tree is a concrete representation of the input. It contains all the information about the input. On the other hand, a syntax tree represents the syntax of a programming language as a tree. It helps to generate symbol tables required for compilers and later code generation.

Key Areas Covered

1. What is Parse Tree
     – Definition, Functionality
2. What is Syntax Tree
     – Definition, Functionality
3. What is the Difference Between Parse Tree and Syntax Tree
     – Comparison of Key Differences

Key Terms

Abstract Syntax Tree, Compiler, Concrete Syntax Tree, Derivation Tree, Parse Tree, Syntax Tree

What is Parse Tree

A parse tree represents the syntactic structure of a string according to some context-free grammar. It describes the syntax of the input language. A parse tree does not use distinct symbol shapes for different types of constituents. The basis to construct a parse tree is phrase structure grammars or dependency grammars. It is possible to generate parse trees for natural language sentences and when processing programming languages.

Moreover, a phrase marker is a linguistic expression marked as to its phrase structure. A tree or a bracketed expression represents it. Applying phrase structure rules to parse tree generates phrase markers. A set of possible parse trees for a syntactically ambiguous sentence is a parse forest.

What is Syntax Tree

A syntax tree describes the abstract syntactic structure of source code written in a programming language. It focuses on the rules rather than elements such as braces, semicolons that terminate statements in some languages. Also, it is a hierarchy with the elements of programming statements divided into several sections. The nodes of the tree signify a construct occurring in the source code. It does not represent every detail in the real syntax; instead, it shows the structural based and content-based details. Subsequent processing such as contextual analysis adds extra information to the syntax tree.

Figure 2: Syntax tree for the Euclidean algorithm

Syntax tree helps to determine the accuracy of the compiler. If the syntax tree contains an error, the compiler displays an error message. Program analysis and program transformation are some other uses of the syntax tree.

Difference Between Parse Tree and Syntax Tree

Definition

A parse tree is an ordered, rooted tree that represents the syntactic structure of a string according to some context-free grammar. A syntax tree, on the other hand, is a tree representation of the abstract syntactic structure of source code written in a programming language. Thus, this is the main difference between parse tree and syntax tree. 

Synonyms

Parsing tree, derivation tree, and concrete syntax tree are some other names for parse tree while abstract syntax tree is another name for the syntax tree.

Functionality

Moreover, parse tree contains records of the rules (tokens) to match input texts while syntax tree contains records of the syntax of programming language. Hence, this is another major difference between parse tree and syntax tree.

Conclusion

The main difference between parse tree and syntax tree is that parse tree is a hierarchical structure that represents the derivation of the grammar to obtain input strings while syntax tree is a way of representing the syntax of a programming language as a hierarchical tree similar structure.

Reference:

1. “Parse Tree.” Wikipedia, Wikimedia Foundation, 27 Dec. 2018, Available here.
2. “Abstract Syntax Tree.” Wikipedia, Wikimedia Foundation, 27 Sept. 2018, Available here.
3. “What Is an Abstract Syntax Tree (AST)? – Definition from Techopedia.” Techopedia.com, Available here.

Image Courtesy:

1. “Abstract syntax tree for Euclidean algorithm” By Dcoetzee – Own work (CC0) via Commons Wikimedia
2. “Python add5 parse” By Lulu of the Lotus-Eaters at English Wikipedia – Transferred from en.wikipedia to Commons (Public Domain) via Commons Wikimedia