EBNF: A Notation to Describe Syntax - Donald Bren School ...

1 Chapter 1 ebnf : A Notation toDescribe SyntaxPrecise language is not the problem. Clear language is the FeynmanChapter Objectives Learn the four control forms in ebnf Learn to read and understand ebnf descriptions Learn to prove a symbol is legal according to an ebnf description Learn to determine if ebnf descriptions are equivalent Learn to write ebnf descriptions from specifications and exemplars Learn the difference between Syntax and semantics Learn the correspondence between ebnf rules and Syntax charts Learn to understand the meaning of and use recursive ebnf

2 IntroductionEBNF is a Notation for formally describing Syntax : how to write the linguisticWe will use ebnf to Describe thesyntax of Pythonfeatures in a language. We will study ebnf in this chapter and then use itthroughout the rest of this book to Describe Python s Syntax formally. Butthere is a more compelling reason to begin our study of programming withEBNF: it is a microcosm of programming , the control forms in ebnf rules are strongly similar to the the basicWriting ebnf descriptions issimilar to writing programscontrol structures in Python: sequence; decision, repetition, and recursion;also similar is the ability to name descriptions and reuse these names to buildmore complex structures.

3 There is also a strong similarity between the processof writing descriptions in ebnf and writing programs in Python: we mustsynthesize a candidate solution and then analyze it to determine whether itis correct and simple. Finally, studying ebnf introduces a level of formalitythat we will employ throughout our study of programming and Language and SyntaxIn the middle 1950s, computer scientists began to design high level program-John Backus helped developedthe FORTRAN and ALGOL lan-guages1 CHAPTER 1.

4 ebnf : A Notation TO Describe SYNTAX2ming languages and build their compilers. The first two major successes wereFORTRAN (FORmula TRAN slator), developed by the IBM corporation in theUnited States, and ALGOL (ALGO rithmic Language), sponsored by a consor-tium of North American and European countries. John Backus led the effort todevelop FORTRAN. He then became a member of the ALGOL design commit-tee, where he studied the problem of describing the Syntax of these programminglanguages simply and invented a Notation (based on the work of logician Emil Post) that wasBackus developed a Notation todescribe Syntax ; Peter Naur thenpopularized its use: they are theB and N in ebnf simple, precise, and powerful enough to Describe the Syntax of any program-ming language.

5 Using this Notation , a programmer or compiler can determinewhether a program is syntactically correct: whether it adheres to the grammarand punctuation rules of the programming language. Peter Naur, as editorof the ALGOL report, popularized this Notation by using it to Describe thecomplete Syntax of ALGOL. In their honor, this Notation is called Backus Naur Form (BNF). This book uses Extended Backus Naur Form ( ebnf ) todescribe Python Syntax , because using it results in more compact a parallel development, the linguist Noam Chomsky began work on a harderAt the same time, linguist NoamChomsky developed notations todescribe the Syntax of naturallanguagesproblem: describing the syntactic structure of natural languages, such as En-glish.

6 He developed four different notations that Describe languages of increas-ing complexity; they are numbered type 3 (least powerful) up through 0 (mostpowerful) in the Chomsky hierarchy. The power of Chomsky s type 2 notationis equivalent to ebnf . The languages in Chomsky s hierarchy, along with themachines that recognize them, are studied in computer science, mathematics,and linguistics under the topics of formal language and automata ebnf Rules and DescriptionsAn ebnf description is an unordered list of ebnf rules.

7 Each ebnf ruleEBNF descriptions comprises alist of ebnf rules of the form:LHS RHShas three parts: a left hand side (LHS), a right-hand side (RHS), and the character separating these two sides; read this symbol as is defined as . TheLHS is oneitalicizedword (possibly with underscores) written in lower case; itnames the ebnf rule. The RHS supplies a description of this name. It caninclude names, characters (standing for themselves), and combinations of thefour control forms explained in Table : Control Forms of Right Hand SidesSequenceItems appear left to right; their order in items are separated by a|(stroke); one item ischosen from this list of alternatives; their order is optional item is enclosed between [ and ] (square brackets);the item can be either included or repeatable item is enclosed between{and}(curly braces).

8 The item can be repeatedzeroor more times; yes, we can choseto repeat itemszerotimes, a fact beginners often rules can include these six characters with special meanings: ,|, [, ],Special characters standing forthemselves in ebnf rules appearin boxes{, and}. If we want to put any of these special characters standing for themselfCHAPTER 1. ebnf : A Notation TO Describe SYNTAX3in a RHS, we put it in a box: so|means alternative but|means the strokecharacter. Any other non-italicized characters that appear in a RHS stand An ebnf Description of IntegersThe following ebnf rules Describe how to write simple RHSAn ebnf description:integerillustrates every control form available in Description:integerdigit 0|1|2|3|4|5|6|7|8|9integer [+|-]digit{digit}We can paraphrase the meanings of these rules in do these ebnf rulesmean?

9 We can paraphrase theirmeaning in English Adigitis defined as one of the ten alternative characters0through9. Anintegeris defined as a sequence of three items: an optional sign (if itis included, it must be one of the alternatives+or-), followed by anydigit, followed by a repetition of zero or moredigits, where each digit isindependently chosen from the list of alternatives in RHS ofintegercombines all the control forms in ebnf : sequence, option,choice, and repetition. We will see longer, more complicated ebnf descriptions,but their rules always use just these four control make ebnf descriptions easier to read and understand, we align theirWe adopt a few simple conven-tions for typesetting ebnf rulesand descriptionsrule names, the , and their rule definitions.

10 Sometimes we put extra spacesin a RHS, to make it easier to read; such spaces do not change the meaning ofthe rule. We can write the special charactertto require a space in an ebnf rule. Although the rules in ebnf descriptions are unordered, we will adopt theconvention writing them in in order of increasing complexity: the RHS of laterrules often refer to the names of earlier ones, as doesinteger. The last ebnf rule names the main syntactic structure being described: in this Proving Symbols Match ebnf RulesNow that we know how to read an ebnf description, we must learn how toA language lawyer can provewhether a symbol is legal or il-legal according to an ebnf de-scriptioninterpret its meaning like a language lawyer.