EECS 395Programming LanguagesWinter 2010Instructor: Robby Findler1Course Detailshttp://www.eecs.northwestern.edu/~robby/courses/395-2010-winter/(or google “findler” and follow the links)2Programming Language ConceptsThis course teaches concepts in two ways:By implementing interpretersnew concept ! new interpreterBy using Scheme and variantswe don’t assume that you already know Scheme3Interpreters vs CompilersAn interpreter takes a program and produces a resultDrSchemex86 processordesktop calculatorbashAlgebra student4Interpreters vs CompilersAn interpreter takes a program and produces a resultDrSchemex86 processordesktop calculatorbashAlgebra studentA compiler takes a program and produces a programDrSchemex86 processorgccjavac5Interpreters vs CompilersAn interpreter takes a program and produces a resultGood for understandingprogram behavior, easyto implementDrSchemex86 processordesktop calculatorbashAlgebra studentA compiler takes a program and produces a programGood for speed, morecomplex (come backnext quarter)DrSchemex86 processorgccjavac6Interpreters vs CompilersAn interpreter takes a program and produces a resultGood for understandingprogram behavior, easyto implementDrSchemex86 processordesktop calculatorbashAlgebra studentA compiler takes a program and produces a programGood for speed, morecomplex (come backnext quarter)DrSchemex86 processorgccjavacSo, what’s a program?7A Grammar for Algebra ProgramsA grammar of Algebra in BNF (Backus-Naur Form):prog ::= defn* exprdefn ::= id(id) = exprexpr ::= (expr + expr)| (expr - expr)| id(expr)| id| numid ::= a variable name: f, x, y, z, ...num ::= a number: 1, 42, 17, ...8A Grammar for Algebra ProgramsA grammar of Algebra in BNF (Backus-Naur Form):prog ::= defn* exprdefn ::= id(id) = exprexpr ::= (expr + expr)| (expr - expr)| id(expr)| id| numid ::= a variable name: f, x, y, z, ...num ::= a number: 1, 42, 17, ...Each meta-variable, such as prog, defines a set9Using a BNF Grammarid ::= a variable name: f, x, y, z, ...num ::= a number: 1, 42, 17, ...The set id is the set of all variable namesThe set num is the set of all numbers10Using a BNF Grammarid ::= a variable name: f, x, y, z, ...num ::= a number: 1, 42, 17, ...The set id is the set of all variable namesThe set num is the set of all numbersTo make an example member of num, simply pickan element from the set11Using a BNF Grammarid ::= a variable name: f, x, y, z, ...num ::= a number: 1, 42, 17, ...The set id is the set of all variable namesThe set num is the set of all numbersTo make an example member of num, simply pickan element from the set2 " num298 " num12Using a BNF Grammarexpr ::= (expr + expr)| (expr - expr)| id(expr)| id| numThe set expr is defined in terms of other sets13Using a BNF Grammarexpr ::= (expr + expr)| (expr - expr)| id(expr)| id| numTo make an example expr:choose one case in the grammarpick an example for each meta-variablecombine the examples with literal text14Using a BNF Grammarexpr ::= (expr + expr)| (expr - expr)| id(expr)| id| numTo make an example expr:choose one case in the grammarpick an example for each meta-variablecombine the examples with literal text15Using a BNF Grammarexpr ::= (expr + expr)| (expr - expr)| id(expr)| id| numTo make an example expr:choose one case in the grammarpick an example for each meta-variable7 " numcombine the examples with literal text16Using a BNF Grammarexpr ::= (expr + expr)| (expr - expr)| id(expr)| id| numTo make an example expr:choose one case in the grammarpick an example for each meta-variable7 " numcombine the examples with literal text7 " expr17Using a BNF Grammarexpr ::= (expr + expr)| (expr - expr)| id(expr)| id| numTo make an example expr:choose one case in the grammarpick an example for each meta-variablecombine the examples with literal text18Using a BNF Grammarexpr ::= (expr + expr)| (expr - expr)| id(expr)| id| numTo make an example expr:choose one case in the grammarpick an example for each meta-variablef " idcombine the examples with literal text19Using a BNF Grammarexpr ::= (expr + expr)| (expr - expr)| id(expr)| id| numTo make an example expr:choose one case in the grammarpick an example for each meta-variablef " id 7 " exprcombine the examples with literal text20Using a BNF Grammarexpr ::= (expr + expr)| (expr - expr)| id(expr)| id| numTo make an example expr:choose one case in the grammarpick an example for each meta-variablef " id 7 " exprcombine the examples with literal textf(7) " expr21Using a BNF Grammarexpr ::= (expr + expr)| (expr - expr)| id(expr)| id| numTo make an example expr:choose one case in the grammarpick an example for each meta-variablef " id f(7) " exprcombine the examples with literal text22Using a BNF Grammarexpr ::= (expr + expr)| (expr - expr)| id(expr)| id| numTo make an example expr:choose one case in the grammarpick an example for each meta-variablef " id f(7) " exprcombine the examples with literal textf(f(7)) " expr23Using a BNF Grammarprog ::= defn* exprdefn ::= id(id) = exprf(x) = (x + 1) " defn24Using a BNF Grammarprog ::= defn* exprdefn ::= id(id) = exprf(x) = (x + 1) " defnTo make a prog pick some number of defns(x + y) " progf(x) = (x + 1)g(y) = f((y - 2))g(7) " prog25Programming LanguageA programming language is defined by• a grammar for programs• rules for evaluating any program to produce