清华大学：编译原理课件（英文译文）Chapter 3.5 Extended Notations：EBNFand Syntax Diagrams

COMPILER CONSTRUCTION Principles and practice Kenneth C. louden

COMPILER CONSTRUCTION Principles and Practice Kenneth C. Louden

3. Context-Free Grammars and Parsing PART TWO

3. Context-Free Grammars and Parsing PART TWO

Contents PART ONE 3. 1 The Parsing Process 3.2 Context-Free Grammars 3.3 Parse Trees and Abstract 3.4 Ambiguity PART TWO 3.5 Extended NotationS EBNF and Syntax diagrams more 3.6 Formal Properties of Context-Free Languages More 3.7 Syntax of the tiNY Language More

Contents PART ONE 3.1 The Parsing Process 3.2 Context-Free Grammars 3.3 Parse Trees and Abstract 3.4 Ambiguity PART TWO 3.5 Extended Notations: EBNF and Syntax Diagrams [More] 3.6 Formal Properties of Context-Free Languages [More] 3.7 Syntax of the TINY Language [More]

3. 5 Extended notationS: EbnF and Syntax Diagrams

3.5 Extended Notations: EBNF and Syntax Diagrams

3.5.1 EBNF Notation

3.5.1 EBNF Notation

Special notations for Repetitive Constructs Repetition A→Ac|B〔 left recursive),and A>aaB right recursive) where a and Bare arbitrary strings of terminals and non-terminals and In the first rule b does not begin with A and In the second B does not end with a

Special Notations for Repetitive Constructs • Repetition – A → A  |  (left recursive), and – A →  A |  (right recursive) • where  and  are arbitrary strings of terminals and non-terminals, and – In the first rule  does not begin with A and – In the second  does not end with A

Special notations for Repetitive Constructs Notation for repetition as regular expressions use, the asterisk A→Ba,and A→0*B eBNF opts to use curly brackets i. to express repetition A→B{c},and A→{aB The problem with any repetition notation is that it obscures how the parse tree is to be constructed, but, as we have seen, we often do not care

Special Notations for Repetitive Constructs • Notation for repetition as regular expressions use, the asterisk * . A →  * , and A → *  • EBNF opts to use curly brackets {. . .} to express repetition A →  { } , and A → {}  • The problem with any repetition notation is that it obscures how the parse tree is to be constructed, but, as we have seen, we often do not care

Examples Example: The case of statement sequences The grammar as follows, in right recursive orm stmt-Sequence- stmt: stmt-Sequence stmt stnt→S In ebnF this would appear as stmt-sequence->stmt;) stmt(right recursive form) stmt-sequence>stmt i; stmt (left recursive form)

Examples • Example: The case of statement sequences • The grammar as follows, in right recursive form: stmt-Sequence → stmt ; stmt-Sequence | stmt stmt → s • In EBNF this would appear as stmt-sequence → { stmt ; } stmt (right recursive form) stmt-sequence → stmt { ; stmt} (left recursive form)

Examples A more significant problem occurs when the associativity matters exp >exp addo term term exp→)term{ adop term} (imply left associativity) exp,term addopfterm (imply right associativity)

Examples • A more significant problem occurs when the associativity matters exp → exp addop term | term exp → term { addop term } (imply left associativity) exp → {term addop } term (imply right associativity)

Special Notations for Optional Constructs Optional construct are indicated by surrounding them with square brackets【…l The grammar rules for if-statements with optional else parts would be written as follows in EBNF: statement>if-stmt other if-stmt>if (exp )statement else statement I exp→0|1 stmt-sequence stmt; stmt-sequence stmt is written as stmt-sequence> stmt stmt-sequence

Special Notations for Optional Constructs • Optional construct are indicated by surrounding them with square brackets [...]. • The grammar rules for if-statements with optional else￾parts would be written as follows in EBNF: statement → if-stmt | other if-stmt → if ( exp ) statement [ else statement ] exp → 0 | 1 • stmt-sequence → stmt; stmt-sequence | stmt is written as • stmt-sequence → stmt [ ; stmt-sequence ]