描述语法和语义

语法以及词义的属性在计算机语言编译的过程中发挥到了一个强有力的作用,本章节介绍了四种关于语法和词义的合成属性,另外介绍了BNF和EBNF以及他们的表现形式,此外Parse-Translator作为计算机编译器的一个有效的应用做了介绍。
展开查看详情

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