teaching ebnf first in cs 1
This paper is a guided tour through the first day of a CS 1 course. It discusses teaching Extended Backus-Naur Form (EBNF) as the first topicnot to facilitate presenting the syntax of a programming language, but because EBNF is a microcosm of programming. With no prerequisites, students are introduced to a variety of fundamental concepts in programming: formal systems, abstraction, control structures, equivalence of descriptions, the difference between syntax and semantics, and the relative power of recursion versus iteration. As a non-numeric formal system, EBNF provides a small but concrete context in which to study all these topics. EBNF descriptions include abstraction (named rules) and the four fundamental control structures (sequence, decision, repetition, and recursion). Because there are no data or parameters in EBNF, it is easy to sidestep tricky issues surrounding variables, scope, assignment statements, and parameter modes. Describing entitles in EBNF is similar to describing computations in a programming language. Students learn to read a description and analyze whether it generates/matches candidate symbols; then they learn to synthesize descriptions from English specifications, augmented by legal and illegal exemplars of symbols. All these concepts can be covered in one lecture, establishing a high level of formality early in the course, while foreshadowing actual programming language features and techniques to be covered later. Of course, learning EBNF also facilitates presenting the syntax of a programming language concisely during the rest of the course.
teaching paper present program programming language student concept formalism systems abstraction control structure semantic power recursion iter context rules sequence data variability assignment learning read feature relation