ASTs and Syntax Analysis in Compilers and Interpreters

Slide Note

Dive into the world of Abstract Syntax Trees (ASTs) and syntax analysis in the context of compilers and interpreters. Explore how ASTs are built, the role of syntax analyzers, and the process of semantic evaluation. Discover the key concepts involved in parsing and understanding program structures using ASTs.

mack686 Follow

Uploaded on Mar 08, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

Creative Commons License CS2 in Java Peer Instruction Materials by Cynthia Lee is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. Based on a work at http://peerinstruction4cs.org. Permissions beyond the scope of this license may be available at http://peerinstruction4cs.org. CSE 12 Basic Data Structures Cynthia Bailey Lee Some slides and figures adapted from Paul Kube s CSE 12

2 Today s Topics 1. ASTs

READING QUIZ! A node in the parse tree corresponds to what? A. one symbol in the BNF grammer B. a transition from one FFT to the next C. the index of the symbol in a string

READING QUIZ! A parse tree where non-essential nodes are not included is called what? A. An Abstract Syntax Tree B. A Generic Parse Tree C. A Universal Interpreter D. All of the above

READING QUIZ! A map ADT is useful when you want store, retrieve and manipulate data based on keys associated with pieces of data. In relation to parsing, one application is... A. a distance table B. a difference table C. a symbol table D. a sequence table

Compilers and interpreters

Compilers and Interpreters One of the most important kinds of programs are programs that read other programs and translate them into action Compilers and interpreters They both have two main steps in their processing Syntax analyzer Semantic evaluator

Compilers and Interpreters Syntax analyzer: Recursively builds up an AST Semantic evaluator: Takes an AST and does the calculation by traversing the tree

Syntax Analyzer Building Abstract Syntax Trees

Syntax Analyzer: parse() method static Assmt parse(java.lang.String s) So we take a string and need to produce a tree node (the example above produces Assmt, but could be other kinds of nodes)

Our sample grammar <A> := | <C> := <ident> = <A> <C> := <C> + <D> | <C> - <D> | <D> <D> := <D> * <M> | <D> / <M> | <M> <M> := <ident> | <const> | (<A>) <ident> := w | x | y | z <const> := 0 | 1 | 2 | 3 | 4

<A> := | <C> := <ident> = <A> <C> := <C> + <D> | <C> - <D> | <D> <D> := <D> * <M> | <D> / <M> | <M> <M> := <ident> | <const> | (<A>) <ident> := w | x | y | z <const> := 0 | 1 | 2 | 3 | 4 Sample derivation 2 <A> => <C> => <D> => <M> => <const> => 2

<A> := | <C> := <ident> = <A> <C> := <C> + <D> | <C> - <D> | <D> <D> := <D> * <M> | <D> / <M> | <M> <M> := <ident> | <const> | (<A>) <ident> := w | x | y | z <const> := 0 | 1 | 2 | 3 | 4 You turn! 2 + w + 3 Which of the following steps can NOT follow immediately after the other in a derivation? A. <C> => <C> + <D> B. <C> + <D> + 3 => <D> + <D> + 3 C. <M> + <D> + 3 => <const> + <M> + 3 D. 2 + <ident> + 3 => 2 + w + 3 E. Other/none/more

<A> := | <C> := <ident> = <A> <C> := <C> + <D> | <C> - <D> | <D> <D> := <D> * <M> | <D> / <M> | <M> <M> := <ident> | <const> | (<A>) <ident> := w | x | y | z <const> := 0 | 1 | 2 | 3 | 4 Solution 2 + w + 3 <A> => <C> => <C> + <D> => <C> + <M> => <C> + <const> => <C> + 3 => <C> + <D> + 3 => <D> + <D> + 3 => <M> + <D> + 3 => <M> + <M> + 3 => <const> + <M> + 3 => <const> + <ident> + 3 => 2 + <ident> + 3 => 2 + w + 3

<A> := | <C> := <ident> = <A> <C> := <C> + <D> | <C> - <D> | <D> <D> := <D> * <M> | <D> / <M> | <M> <M> := <ident> | <const> | (<A>) <ident> := w | x | y | z <const> := 0 | 1 | 2 | 3 | 4 Your turn! 2 + w * 3

So we can do parse() on paper how do we do it in code?? static Assmt parse(java.lang.String s) So we take a string and need to produce a tree node (the example above produces Assmt, but could be other kinds of nodes)

Semantic Evaluator Traversing Abstract Syntax Trees

Semantic Evaluator This is really just a traversal of the tree We have been talking about the visit operation as being something like print the this node s data variable But here it will be to evaluate the expression

Which kind of traversal? (and WHY?) A. Pre-order: 1. visit self 2. Traverse left 3. Traverse right B. In-order: 1. Traverse left 2. visit self 3. Traverse right C. Post-order: 1. Traverse left 2. Traverse right 3. visit self