Abstract Syntax Trees
27 February 2019 OSU CSE 1
Abstract Syntax Tree
Copyright By PowCoder代写 加微信 powcoder
• An abstract syntax tree (AST) is a tree
model of an entire program or a certain “program structure” (e.g., a statement or an expression in a Java program)
• An AST is “abstract” in the sense that some of the actual characters used in the “concrete” program text do not appear in the AST
27 February 2019 OSU CSE 2
Example: A Java Statement
while (k < 7) {
k 7 foo k k
27 February 2019
Example: A Java Statement
while (k < 7) {
foo(k); k++;
You should see the connections! (This may
not be an actual Java AST, however; it is just an
illustration of the idea.) k 27 February 2019 OSU CSE
Example: A BL Statement
WHILE true DO move
infect END WHILE
WHILE TRUE
27 February 2019
CALL infect
Example: A BL Statement
WHILE true DO move
infect END WHILE
You should see the connections! (This is an
WHILE TRUE
actual AST for BL; notice it uses a different “design”.)
27 February 2019 OSU CSE
CALL infect
BL Statement Kinds
instruction IF test THEN
IF test THEN
WHILE test DO
27 February 2019
BL Statement Kinds
instruction IF test THEN IF test THEN
WHILE test DO
END IF ELSE
Any sequence of zero or
more statements nested in
an IF or WHILE construct
is called a block.
27 February 2019 OSU CSE
CALL Statement
BL Example
CALL turnleft
27 February 2019 OSU CSE 9
IF Statement
BL Example
IF next-is-enemy THEN turnleft
move END IF
IF NEXT_IS_ENEMY
CALL turnleft
27 February 2019 OSU CSE 10
IF_ELSE Statement
BL Example
IF next-is-enemy THEN turnleft
IF_ELSE NEXT_IS_ENEMY
CALL CALL turnleft move
27 February 2019 OSU CSE 11
WHILE Statement
BL Example
WHILE next-is-enemy DO turnleft
move END WHILE
WHILE NEXT_IS_ENEMY
CALL turnleft
27 February 2019 OSU CSE 12
Why BLOCK?
• Draw the AST for this BL code with and
without the intermediate notion of BLOCK: IF next-is-empty THEN
turnright ELSE
infect END IF
27 February 2019
OSU CSE 13
Why BLOCK?
If it’s not clear, draw the
• Draw the AST for this code with and
AST for this code with
without the intermediate notion of BLOCK:
IF next-is-empty THEN move
turnright ELSE
infect END IF
infect END IF
27 February 2019
OSU CSE 14
and without BLOCK: IF next-is-empty THEN
AST Node Labels
• An AST for BL is a tree of ... what?
• Each node has some of the following:
– The kind of statement (e.g., BLOCK, WHILE)
– The test condition (e.g., NEXT_IS_EMPTY, TRUE)
– The call of an instruction (e.g., infect, move), realizing that this may be an instruction defined elsewhere in the program (e.g., FindObstacle in an earlier BL example)
27 February 2019 OSU CSE 15
This mathematical 3-tuple of AST Node Labels
information (of which either test or call might be relevant, depending on the
• An AST for BL is a tree of ... what? kind) will be called a
STATEMENT_LABEL.
• Each node has some of the following:
– The kind of statement (e.g., BLOCK, WHILE) – The test condition (e.g., NEXT_IS_EMPTY,
– The call of an instruction (e.g., infect, move), realizing that this may be an instruction defined elsewhere in the program (e.g., FindObstacle in an earlier BL example)
27 February 2019 OSU CSE 16
AST Node Labels The mathematical model of an AST for
a BL statement is therefore a
• An AST for BL is a tree of ... what?
tree of STATEMENT_LABEL.
• Each node has some of the following:
– The kind of statement (e.g., BLOCK, WHILE) – The test condition (e.g., NEXT_IS_EMPTY,
– The call of an instruction (e.g., infect, move), realizing that this may be an instruction defined elsewhere in the program (e.g., FindObstacle in an earlier BL example)
27 February 2019 OSU CSE 17
• Wikipedia: Abstract Syntax Tree
– http://en.wikipedia.org/wiki/Abstract_syntax_tree
27 February 2019 OSU CSE 18
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com