程序代写 CSE 10

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