Parse tree

Let’s see another example of parse tree. As another example, consider the following grammar:
S ::= ( L )| a

L ::= L , S | S

Under this grammar, the parse tree of the sentence (a,((a, a), a)) is:

S
/ | \
( L )
/ | \
L , S
| / | \
S ( L )
| / | \
a L , S
| |
S a
/ | \
( L )
/ | \
L , S
| |
S a
|
a

Automata Step by Step

This post is connected to the previous post. So if you have not read that post, please give few minutes in reading that post.

Parsing:

Parsing (more formally syntax analysis) is the process of analyzing a sequence of tokens to determine its grammatical structure with respect to a given formal grammar. A parser is the component of a compiler that carries out this task.

Parsing transforms input text into a data structure, usually a tree, which is suitable for later processing and which captures the implied hierarchy of the input. Lexical analysis creates tokens from a sequence of input characters and it is these tokens that are processed by a parser to build a data structure such as parse tree or abstract syntax trees.

Can you guess what the next question is? Yes, you are right. Next question is what the Formal Grammar is.