The resulting AST should be formulated as a Binary Tree.
;Example - given the simple program (below), stored in a file called while.t, create the list of tokens, using one of the Lexical analyzer [[Compiler/lexical_analyzer|solutions]]
lex < while.t > while.lex
;Run one of the Syntax analyzer [[Compiler/syntax_analyzer|solutions]]:
parse < while.lex > while.ast
;The following table shows the input to lex, lex output, and the AST produced by the parser:
{| class="wikitable"
|-
! Input to lex
! Output from lex, input to parse
! Output from parse
|-
| style="vertical-align:top" |
<syntaxhighlight lang="c">count = 1;
while (count < 10) {
print("count is: ", count, "\n");
count = count + 1;
}</syntaxhighlight>
| style="vertical-align:top" |
<b><pre>
1 1 Identifier count
1 7 Op_assign
1 9 Integer 1
1 10 Semicolon
2 1 Keyword_while
2 7 LeftParen
2 8 Identifier count
2 14 Op_less
2 16 Integer 10
2 18 RightParen
2 20 LeftBrace
3 5 Keyword_print
3 10 LeftParen
3 11 String "count is: "
3 23 Comma
3 25 Identifier count
3 30 Comma
3 32 String "\n"
3 36 RightParen
3 37 Semicolon
4 5 Identifier count
4 11 Op_assign
4 13 Identifier count
4 19 Op_add
4 21 Integer 1
4 22 Semicolon
5 1 RightBrace
6 1 End_of_input
</pre></b>
| style="vertical-align:top" |
<b><pre>
Sequence
Sequence
;
Assign
Identifier count
Integer 1
While
Less
Identifier count
Integer 10
Sequence
Sequence
;
Sequence
Sequence
Sequence
;
Prts
String "count is: "
;
Prti
Identifier count
;
Prts
String "\n"
;
Assign
Identifier count
Add
Identifier count
Integer 1
</pre></b>
|}
;Specifications
;List of node type names:
<pre>
Identifier String Integer Sequence If Prtc Prts Prti While Assign Negate Not Multiply Divide Mod
Add Subtract Less LessEqual Greater GreaterEqual Equal NotEqual And Or
</pre>
In the text below, Null/Empty nodes are represented by ";".
;Non-terminal (internal) nodes:
For Operators, the following nodes should be created:
Multiply Divide Mod Add Subtract Less LessEqual Greater GreaterEqual Equal NotEqual And Or
For each of the above nodes, the left and right sub-nodes are the operands of the
respective operation.
In pseudo S-Expression format:
(Operator expression expression)
Negate, Not
For these node types, the left node is the operand, and the right node is null.
(Operator expression ;)
Sequence - sub-nodes are either statements or Sequences.
If - left node is the expression, the right node is If node, with it's left node being the
if-true statement part, and the right node being the if-false (else) statement part.
(If expression (If statement else-statement))
If there is not an else, the tree becomes:
(If expression (If statement ;))
Prtc
(Prtc (expression) ;)
Prts
(Prts (String "the string") ;)
Prti
(Prti (Integer 12345) ;)
While - left node is the expression, the right node is the statement.
(While expression statement)
Assign - left node is the left-hand side of the assignment, the right node is the
right-hand side of the assignment.
(Assign Identifier expression)
Terminal (leaf) nodes:
Identifier: (Identifier ident_name)
Integer: (Integer 12345)
String: (String "Hello World!")
";": Empty node
;Some simple examples
Sequences denote a list node; they are used to represent a list. semicolon's represent a null node, e.g., the end of this path.
This simple program:
a=11;
Produces the following AST, encoded as a binary tree:
Under each non-leaf node are two '|' lines. The first represents the left sub-node, the second represents the right sub-node:
(1) Sequence
(2) |-- ;
(3) |-- Assign
(4) |-- Identifier: a
(5) |-- Integer: 11
In flattened form:
(1) Sequence
(2) ;
(3) Assign
(4) Identifier a
(5) Integer 11
This program:
a=11;
b=22;
c=33;
Produces the following AST:
( 1) Sequence
( 2) |-- Sequence
( 3) | |-- Sequence
( 4) | | |-- ;
( 5) | | |-- Assign
( 6) | | |-- Identifier: a
( 7) | | |-- Integer: 11
( 8) | |-- Assign
( 9) | |-- Identifier: b
(10) | |-- Integer: 22
(11) |-- Assign
(12) |-- Identifier: c
(13) |-- Integer: 33
In flattened form:
( 1) Sequence
( 2) Sequence
( 3) Sequence
( 4) ;
( 5) Assign
( 6) Identifier a
( 7) Integer 11
( 8) Assign
( 9) Identifier b
(10) Integer 22
(11) Assign
(12) Identifier c
(13) Integer 33
;Pseudo-code for the parser.
Uses [https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm Precedence Climbing] for expression parsing, and
[https://en.wikipedia.org/wiki/Recursive_descent_parser Recursive Descent] for statement parsing. The AST is also built:
<syntaxhighlight lang="python">def expr(p)
if tok is "("
x = paren_expr()
elif tok in ["-", "+", "!"]
gettok()
y = expr(precedence of operator)
if operator was "+"
x = y
else
x = make_node(operator, y)
elif tok is an Identifier
x = make_leaf(Identifier, variable name)
gettok()
elif tok is an Integer constant
x = make_leaf(Integer, integer value)
gettok()
else
error()
while tok is a binary operator and precedence of tok >= p
save_tok = tok
gettok()
q = precedence of save_tok
if save_tok is not right associative
q += 1
x = make_node(Operator save_tok represents, x, expr(q))
return x
def paren_expr()
expect("(")
x = expr(0)
expect(")")
return x
def stmt()
t = NULL
if accept("if")
e = paren_expr()
s = stmt()
t = make_node(If, e, make_node(If, s, accept("else") ? stmt() : NULL))
elif accept("putc")
t = make_node(Prtc, paren_expr())
expect(";")
elif accept("print")
expect("(")
repeat
if tok is a string
e = make_node(Prts, make_leaf(String, the string))
gettok()
else
e = make_node(Prti, expr(0))
t = make_node(Sequence, t, e)
until not accept(",")
expect(")")
expect(";")
elif tok is ";"
gettok()
elif tok is an Identifier
v = make_leaf(Identifier, variable name)
gettok()
expect("=")
t = make_node(Assign, v, expr(0))
expect(";")
elif accept("while")
e = paren_expr()
t = make_node(While, e, stmt()
elif accept("{")
while tok not equal "}" and tok not equal end-of-file
t = make_node(Sequence, t, stmt())
expect("}")
elif tok is end-of-file
pass
else
error()
return t
def parse()
t = NULL
gettok()
repeat
t = make_node(Sequence, t, stmt())
until tok is end-of-file
return t</syntaxhighlight>
;Once the AST is built, it should be output in a [[Flatten_a_list|flattened format.]] This can be as simple as the following:
<syntaxhighlight lang="python">def prt_ast(t)
if t == NULL
print(";\n")
else
print(t.node_type)
if t.node_type in [Identifier, Integer, String] # leaf node
print the value of the Ident, Integer or String, "\n"
else
print("\n")
prt_ast(t.left)
prt_ast(t.right)</syntaxhighlight>
;If the AST is correctly built, loading it into a subsequent program should be as simple as:
<syntaxhighlight lang="python">def load_ast()
line = readline()
# Each line has at least one token
line_list = tokenize the line, respecting double quotes
text = line_list[0] # first token is always the node type
if text == ";" # a terminal node
return NULL
node_type = text # could convert to internal form if desired
