[SOLVED] CSE 10

Abstract Syntax Trees
27 February 2019 OSU CSE 1

Abstract Syntax Tree

Copyright By Assignmentchef assignmentchef

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 k27 February 2019 Example: A Java Statementwhile (k < 7) {foo(k); k++;You should see the connections! (This maynot be an actual Java AST, however; it is just anillustration of the idea.) k 27 February 2019 OSU CSE Example: A BL StatementWHILE true DO moveinfect END WHILEWHILE TRUE 27 February 2019CALL infect Example: A BL StatementWHILE true DO moveinfect END WHILEYou should see the connections! (This is anWHILE TRUEactual AST for BL; notice it uses a different design.)27 February 2019 OSU CSECALL infect BL Statement Kinds instruction IF test THENIF test THENWHILE test DO 27 February 2019 BL Statement Kinds instruction IF test THEN IF test THENWHILE test DO END IF ELSE Any sequence of zero ormore statements nested inan IF or WHILE constructis called a block.27 February 2019 OSU CSE CALL StatementBL Example CALL turnleft27 February 2019 OSU CSE 9 IF StatementBL ExampleIF next-is-enemy THEN turnleftmove END IF IF NEXT_IS_ENEMY CALL turnleft27 February 2019 OSU CSE 10 IF_ELSE StatementBL ExampleIF next-is-enemy THEN turnleft IF_ELSE NEXT_IS_ENEMY CALL CALL turnleft move27 February 2019 OSU CSE 11 WHILE StatementBL ExampleWHILE next-is-enemy DO turnleftmove END WHILE WHILE NEXT_IS_ENEMY CALL turnleft27 February 2019 OSU CSE 12 Why BLOCK? Draw the AST for this BL code with andwithout the intermediate notion of BLOCK: IF next-is-empty THENturnright ELSEinfect END IF27 February 2019OSU CSE 13 Why BLOCK?If its not clear, draw the Draw the AST for this code with andAST for this code withwithout the intermediate notion of BLOCK:IF next-is-empty THEN moveturnright ELSEinfect END IFinfect END IF27 February 2019OSU CSE 14and 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 15This mathematical 3-tuple of AST Node Labelsinformation (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 aSTATEMENT_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: assignmentchef QQ: 1823890830 Email: [email protected]