1.Chapter 5: Syntax Directed Translation Prof. Steven A. Demurjian Computer Science & Engineering Department The University of Connecticut 371 Fairfield Way, Unit 2155 Storrs, CT 06269-3155 steve@engr.uconn.edu http://www.engr.uconn.edu/~steve (860) 486 - 4818 Material for course thanks to: Laurent Michel Aggelos Kiayias Robert LeBarre

2.Overview Review Supporting Concepts (Extended) Backus Naur Form Parse Tree and Schedule Explore Basic Concepts/Examples of Attribute Grammars Synthesized and Inherited Attributes Actions as Direct Effect of Parsing Examine more Complex Examples Attribute Grammars and Yacc – Jump to Slide Set Constructing Syntax Trees During Parsing Translation is Two-Pass: First Pass: Construct Tree using Attribute Grammar Second Pass: Evaluate Tree (Perform Translation) Concluding Remarks

3.Excerpts from Various Presentations BNF/EBNF and Attribute Grammars Chapter 3: Describing Syntax and Semantics Concepts of Programming Languages, 11E R. Sebesta Lecture 11: Semantic Analysis(Section 4.1- 4.4) Felix Hernandez-Campos at UNC Chapel Hill http://www.cs.unca.edu/~bruce/Fall02/csci431/slides/lect11.ppt Syntax Directed Translation http://www3.cs.stonybrook.edu/~cse304/Fall09/Lectures/attributes-handout.pdf

4.Chapter 3 Describing Syntax and Semantics

5.BNF Fundamentals (continued) Nonterminals are often enclosed in angle brackets Examples of BNF rules: <ident_list> → identifier | identifier, <ident_list> <if_stmt> → if <logic_expr> then <stmt> Grammar: a finite non-empty set of rules A start symbol is a special element of the nonterminals of a grammar Copyright © 2015 Pearson. All rights reserved. 1- 5

6.Copyright © 2015 Pearson. All rights reserved. 1- 6 BNF Rules An abstraction (or nonterminal symbol) can have more than one RHS <stmt>  <single_stmt> | begin <stmt_list> end

7.Copyright © 2015 Pearson. All rights reserved. 1- 7 Describing Lists Syntactic lists are described using recursion <ident_list>  ident | ident, <ident_list> A derivation is a repeated application of rules, starting with the start symbol and ending with a sentence (all terminal symbols)

8.Copyright © 2015 Pearson. All rights reserved. 1- 8 Extended BNF Optional parts are placed in brackets [ ] <proc_call> -> ident [(<expr_list>)] Alternative parts of RHSs are placed inside parentheses and separated via vertical bars <term> → <term> (+|-) const Repetitions (0 or more) are placed inside braces { } <ident> → letter {letter|digit}

9.Copyright © 2015 Pearson. All rights reserved. 1- 9 BNF and EBNF BNF <expr>  <expr> + <term> | <expr> - <term> | <term> <term>  <term> * <factor> | <term> / <factor> | <factor> EBNF <expr>  <term> {(+ | -) <term>} <term>  <factor> {(* | /) <factor>}

10.Copyright © 2015 Pearson. All rights reserved. 1- 10 Recent Variations in EBNF Alternative RHSs are put on separate lines Use of a colon instead of => Use of opt for optional parts Use of oneof for choices

11.BNF and EBNF Essentially Backus Naur Form for Regular Expressions that we have Utilized to Date Extension - Reminiscent of regular expressions EBNF Extended Backus Naur Form What is it? A way to specify a high-level grammar Grammar is Independent of parsing algorithm Richer than “plain grammars” Human friendly [highly readable]

12.Optional and Alternative Sections E → id ( A ) → id A → integer → id E → id [ ( A ) ] A → integer → id Optional Part! E → id [ ( A ) ] A → ( integer | id ) E → id [ ( A ) ] A → integer → id Simplifying for Alternatives

13.Kleene Closure Simplifies Grammar by Eliminating Epsilon Rules E → id [ ( [ Args ] ) ] Args → E [ , Args ]* E → id [ ( Args ) ] Args → E Rest → ε Rest → , E Rest → ε foo() foo(x) foo(x,y) foo(x,y,z) foo(w,x,y,z)

14.Positive Closure For having at least 1 occurrence L → S + S → if .... → while .... → repeat .... L → S L’ L’ → S L’ → ε S → if .... → while .... → repeat ....

15.C-- EBNF Style

16.C-- EBNF Style

17.Pascal BNF

18.Pascal BNF

19.Pascal BNF

20.Pascal BNF

21.Pascal BNF – Graphical Form

22.Pascal BNF – Graphical Form

23.Pascal BNF – Graphical Form

24.Pascal BNF – Graphical Form

25.Pascal BNF – Graphical Form

26.Pascal BNF – Graphical Form

27.Pascal BNF – Graphical Form

28.Pascal BNF – Graphical Form

29.Pascal BNF – Graphical Form