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 elseparts 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 ]
