[SOLVED] 程序代写 CSE 10

Abstract Syntax Trees
27 February 2019 OSU CSE 1

Abstract Syntax Tree

Copyright By PowCoder代写加微信 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 it’s 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]