Programming Languages andCompilers (CS 421)Elsa L Gunter2112 SC, UIUChttp://www.cs.uiuc.edu/class/fa06/cs421/Based in part on slides by Mattox Beckman, as updatedby Vikram Adve and Gul AghaElsa L. GunterGrammars• Grammars are formal descriptions ofwhich strings over a given character setare in a particular language• Language designers write grammar• Language implementers use grammarto know what programs to accept• Language users use grammar to knowhow to write legitimate programsElsa L. GunterTypes of Formal LanguageDescriptions• Regular expressions, regular grammars• Context-free grammars, BNFgrammars, syntax diagrams• Finite state automata• Whole family more of grammars andautomata – covered in automata theoryElsa L. GunterSample Grammar• Language: Parenthesized sums of 0’sand 1’s• <Sum> ::= 0• <Sum >::= 1• <Sum> ::= <Sum> + <Sum>• <Sum> ::= (<Sum>)Elsa L. GunterBNF Grammars• Start with a set of characters,a,b,c,…– We call these terminals• Add a set of different characters,X,Y,Z,…– We call these nonterminals• One special nonterminal S calledstart symbolElsa L. GunterBNF Grammars• BNF rules (aka productions) have form X ::= y where X is any nonterminal and y is astring of terminals and nonterminals• BNF grammar is a set of BNF rulessuch that every nonterminal appears onthe left of some ruleElsa L. GunterSample Grammar• Terminals: 0 1 + ( )• Nonterminals: <Sum>• Start symbol = <Sum>• <Sum> ::= 0• <Sum >::= 1• <Sum> ::= <Sum> + <Sum>• <Sum> ::= (<Sum>)• Can be abbreviated as <Sum> ::= 0 | 1 | <Sum> + <Sum> | (<Sum>)Elsa L. GunterBNF Deriviations• Given rulesX::= yZw and Z::=vwe may replace Z by v to sayX => yZw => yvw• Derivation called right-most ifalways replace the right-most non-terminalElsa L. GunterBNF Derivations• Start with the start symbol:<Sum> =>Elsa L. GunterBNF Derivations• Pick a non-terminal<Sum> =>Elsa L. Gunter• Pick a rule and substitute:– <Sum> ::= <Sum> + <Sum><Sum> => <Sum> + <Sum >BNF DerivationsElsa L. Gunter• Pick a non-terminal:<Sum> => <Sum> + <Sum >BNF DerivationsElsa L. Gunter• Pick a rule and substitute:– <Sum> ::= ( <Sum> )<Sum> => <Sum> + <Sum > => ( <Sum> ) + <Sum>BNF DerivationsElsa L. Gunter• Pick a non-terminal:<Sum> => <Sum> + <Sum > => ( <Sum> ) + <Sum>BNF DerivationsElsa L. Gunter• Pick a rule and substitute:– <Sum> ::= <Sum> + <Sum><Sum> => <Sum> + <Sum > => ( <Sum> ) + <Sum> => ( <Sum> + <Sum> ) + <Sum>BNF DerivationsElsa L. Gunter• Pick a non-terminal:<Sum> => <Sum> + <Sum > => ( <Sum> ) + <Sum> => ( <Sum> + <Sum> ) + <Sum>BNF DerivationsElsa L. Gunter• Pick a non-terminal:<Sum> => <Sum> + <Sum > => ( <Sum> ) + <Sum> => ( <Sum> + <Sum> ) + <Sum>BNF DerivationsElsa L. Gunter• Pick a rule and substitute:– <Sum >::= 1<Sum> => <Sum> + <Sum > => ( <Sum> ) + <Sum> => ( <Sum> + <Sum> ) + <Sum> => ( <Sum> + 1 ) + <Sum>BNF DerivationsElsa L. Gunter• Pick a non-terminal:<Sum> => <Sum> + <Sum > => ( <Sum> ) + <Sum> => ( <Sum> + <Sum> ) + <Sum> => ( <Sum> + 1 ) + <Sum>BNF DerivationsElsa L. Gunter• Pick a rule and substitute:– <Sum >::= 0<Sum> => <Sum> + <Sum > => ( <Sum> ) + <Sum> => ( <Sum> + <Sum> ) + <Sum> => ( <Sum> + 1 ) + <Sum> => ( <Sum> + 1 ) + 0BNF DerivationsElsa L. Gunter• Pick a non-terminal:<Sum> => <Sum> + <Sum > => ( <Sum> ) + <Sum> => ( <Sum> + <Sum> ) + <Sum> => ( <Sum> + 1 ) + <Sum> => ( <Sum> + 1 ) + 0BNF DerivationsElsa L. Gunter• Pick a rule and substitute– <Sum> ::= 0<Sum> => <Sum> + <Sum > => ( <Sum> ) + <Sum> => ( <Sum> + <Sum> ) + <Sum> => ( <Sum> + 1 ) + <Sum> => ( <Sum> + 1 ) 0 => ( 0 + 1 ) + 0BNF DerivationsElsa L. Gunter• ( 0 + 1 ) + 0 is generated by grammar<Sum> => <Sum> + <Sum > => ( <Sum> ) + <Sum> => ( <Sum> + <Sum> ) + <Sum> => ( <Sum> + 1 ) + <Sum> => ( <Sum> + 1 ) + 0 => ( 0 + 1 ) + 0BNF DerivationsElsa L. GunterYour Turn:<Sum> ::= 0 | 1 | <Sum> + <Sum> | (<Sum>)<Sum> =>Elsa L. GunterBNF Semantics• The meaning of a BNF grammar isthe set of all strings consisting onlyof terminals that can be derivedfrom the Start symbolElsa L. GunterExtended BNF Grammars• Alternatives: allow rules of from X::=y|z– Abbreviates X::= y, X::= z• Options: X::=y[v]z– Abbreviates X::=yvz, X::=yz• Repetition: X::=y{v}*z– Can be eliminated by adding newnonterminal V and rules X::=yz,X::=yVz, V::=v, V::=vVElsa L. GunterRegular Grammars• Subclass of BNF• Only rules of form<nonterminal>::=<terminal><nonterminal>or <nonterminal>::=<terminal>• Defines same class of languages as regularexpressions• Important for writing lexers (programs thatconvert strings of characters into strings oftokens)Elsa L. GunterExample• Regular grammar:<Balanced> ::= ε<Balanced> ::= 0<OneAndMore><Balanced> ::= 1<ZeroAndMore><OneAndMore> ::= 1<Balanced><ZeroAndMore> ::= 0<Balanced>• Generates even length strings whereevery initial substring of even length hassame number of 0’s as 1’sElsa L. Gunter• Graphical representation of derivation• Each node labeled with either non-terminal or terminal• If node is labeled with a terminal, then itis a leaf (no sub-trees)• If node is labeled with a terminal, then ithas one branch for each character inthe right-hand side of rule used tosubstitute for itParse TreesElsa L. GunterExample• Consider grammar: <exp> ::= <factor> | <factor> + <factor> <factor> ::= <bin> | <bin> * <exp> <bin> ::= 0 | 1• Problem: Build parse tree for 1 * 1 + 0as an <exp>Elsa L. GunterExample cont.• 1 * 1 + 0: <exp><exp> is the start symbol for this parsetreeElsa L. GunterExample cont.• 1 * 1 + 0: <exp> <factor>Use rule: <exp> ::= <factor>Elsa L. GunterExample cont.• 1 * 1 + 0: <exp> <factor> <bin> * <exp>Use rule: <factor> ::= <bin> * <exp>Elsa L. GunterExample cont.• 1 * 1 + 0: <exp> <factor> <bin> * <exp> 1 <factor> + <factor>Use rules: <bin> ::= 1 and <exp> ::= <factor> + <factor>Elsa L. GunterExample cont.• 1 * 1 + 0: <exp>
View Full Document
Unlocking...