Syntax
•	Syntax vs. Semantics
•	Translation steps
•	Extended Backus-Naur Form (EBNF)
Syntax vs. Semantics
•	Syntax: Is the statement of the correct form?
•	Semantics: What does the statement do?
•	Ex: x = -5.2;  // correct syntax, but semantics might be wrong
•	Which should a translator check first, syntax or semantics?
Steps for compilation
•	Start with program as file of characters
•	Maintain information in tables
•	Lexical analysis
•	Syntactic analysis (Parsing)
Lexical vs. Syntactic rules
•	Lexical rules: how symbols of the language can be combined. Ex:
•	English: words include letters and hyphens (no *, %, $, etc.)
•	C++: variable name starts with a letter or '_', = cannot have a space between  and =, spaces between statements are ignored
Lexical vs. Syntactic rules
•	Syntactic rules: how the words can be combined
•	ex: (a < b) is OK, but (a < b < c) is not
•	ex: Pascal if-then-else vs. Java if-else
Lexemes vs. tokens
•	(Sebesta) the category is the token, the actual string is the lexeme
•	English: tokens are the parts-of-speech, like noun or adjective
•	Programming: tokens include identifier, number, double-quote
Steps for compilation
•	Semantic analysis
•	Optimization
•	Code generation
•	Linking
•	end with (usu. executable) code
Interpreter modules
•	Read – need complete expression, but complete program not necessary
•	Evaluate -- still need to check syntax first
•	Print – every expression must have a value (no void)
•	And repeat
Motivation for EBNF
•	What are some of the problems with trying to use C++/Java to define the syntax of a programming language?
•	What notation did your English teacher use to teach you grammar?
EBNF
•	(extended) Backus-Naur Form
•	notation for defining grammar of a language
•	metalanguage = language for defining languages
•	each grammar includes:
•	terminals -- symbols/words in the language
EBNF
•	nonterminals -- a unit representing a grammatically correct sequence of terminals
•	usually one nonterminal is considered the "start" symbol
•	productions -- the valid ways a nonterminal could be replaced by terminals and other nonterminals
EBNF (continued)
•	ex: English
•	<sentence> -> <noun-part> <verb-part> .
•	<noun-part> -> <noun> | <adj> <noun>
•	[::= often replaces ->]
•	sentence would be start symbol
•	e for empty string
EBNF (continued)
•	nonterminals (surrounded by < > )
•	| means "or"
•	{ } used for grouping
•	Above defines BNF -- Extended BNF added following notation for convenience
EBNF (continued)
•	* to indicate 0 or more of something, 
•	+ 1 or more: 
•	ex: 
•	<posInteger> -> <digit>+
•	<digit> -> 0 | 1 | 2 | ... | 9
Lisp in EBNF
•	<expression> -> <atom> | <list>
•	<atom> -> <number> | <name> | <string> | <operator>
•	<list> -> (<expression>*)
•	close to complete -- compare with C++
Derivations
•	Correct syntax: possible to find derivation from start symbol to program
•	derivation = set of steps 
•	each step replaces one nonterminal by right side of a production
Examples
•	67 for posinteger grammar
•	<posInteger> => <digit>+ {2 digits} => 6 <digit> => 67
•	(+ 2 5) for Lisp grammar
•	<expression> => <list> 
•	=> (<expression>*) {3 expressions}
•	=> (<atom> <expression> <expression>)
Examples (cont'd)
•	=> (<operator> <expression> <expression>)
•	=> (+ <expression> <expression>)
•	=> (+ <number> <expression>)
•	=> (+ 2 <expression>)
•	=> (+ 2 <number>)
•	=> (+ 2 5)
Limitations of EBNF
•	Too many rules will lead to a parser that is very large
•	less efficient, harder to get right
•	Some things just cannot be done
•	Context-sensitive features, like type-checking, require additional programming (no efficient parser exists)