1CMSC330Context Free Grammars2Where we are• Programming languages– Ruby– OCaml• Implementing programming languages– Scanner (or lexer)• Uses regular expressions• Finite automata– Parser• Uses context free grammars• Pushdown automata3This lecture• Program syntax– Regular expressions & grammars• Context free grammars (CFGs)– Definition– Derivations (leftmost)– Parse tree– Ambiguity– Associativity & precedence4Motivation for grammars• Programs are just strings of text– But they’re strings that have a certain structure• Informal description of structure of a C program– A C program is a list of declarations and definitions– A function definition contains parameters and a body– A function body is a sequence of statements– A statement is either an expression, a while loop, etc…– An expression may be assignment, addition, etc…5Motivation for Grammars (cont.)• We want to describe program structure precisely• Regular expressions are not enough– No regular expression for balanced pairs of ( )’s• { “( )”, “(( ))”, “((( )))”, “(((( ))))”, … } is not a regular language– Regex “do not have memory”• Need to use context free grammar (CFG)6Context Free Grammar (CFG)• A way of generating sets of strings or languages• Grammar: S → 0S | 1S | ε– Means every S may be replaced by 0S, 1S, or ε– Example• S → 0S // using S → 0S→ 01S // using S → 1S→ 011S // using S → 1S→ 011 // using S → ε• Happens to be the same as regular expression (0|1)*– Generates / accepts the same set of strings7Context-Free Grammars (CFGs)• But CFGs can do a lot more!– S → ( S ) | ε // generates balanced pairs of ( )’s• In fact, CFGs subsume REs, DFAs, NFAs– There is a CFG that generates any regular language– But REs are a better notation for regular languages• CFGs can specify programming language syntax – CFGs (mostly) describe the parsing process8Math alert!9Formal definition• A context-free grammar G is a 4-tuple– – a finite set of terminal (alphabet) symbols• Often written in lowercase– N – a finite, nonempty set of nonterminal symbols• Often written in uppercase• It must be that N = Ø– P – a set of productions of the form N (|N)*• Informally this means that the nonterminal can be replaced by the string of zero or more terminals or nonterminals to the right of the • Can think of productions as rewriting rules– S ∈ N – the start symbol10Backus-Naur Form• Context-free grammar production rules are also called Backus-Naur Form or BNF– A production like A B c D is written in BNF as<A> ::= <B> c <D> (Non-terminals written with angle brackets and ::= instead of )– Often used to describe language syntax• BNF was designed by– John Backus• Chair of the Algol committee in the early 1960s– Peter Naur• Secretary of the committee, who used this notation to describe Algol in 196211Informal Definition of Acceptance• A string is accepted by a CFG if there is– Some sequence of applying productions (rewrites) starting at the start symbol that generates the string• Example– Grammar: S → 0S | 1S | ε– Sequence generating the string 010• S → 0S → 01S → 010S → 010• Terminology– Such a sequence of rewrites is a derivation or parse– Discovering the derivation is called parsing12Derivations• Notation→ indicates a derivation of one step→ + indicates a derivation of one or more steps→ * indicates a derivation of zero or more steps• Example– S → 0S | 1S | ε• For the string 010– S → 0S → 01S → 010S → 010– S → + 010– S → * S13Practice• Try to make a grammar which accepts– 0*|1* – 0n1n where n 0 – 0n1mwhere m n• Give some example strings from this language– S → 0 | 1S• 0, 10, 110, 1110, 11110, …– What language is it?• 1*0S A | BA 0A | B 1B | S 0S1 | S 0S1 | 0S | 14Example: Arithmetic Expressions• E a | b | c | E+E | E-E | E*E | (E)– An expression E is either a letter a, b, or c– Or an E followed by + followed by an E– etc…• This describes (or generates) a set of strings– {a, b, c, a+b, a+a, a*c, a-(b*a), c*(b + a), …}• Example strings not in the language– d, c(a), a+, b**c, etc.15Formal Description of Example• Formally, the grammar we just showed is– = { +, -, *, (, ), a, b, c } // terminals– N = { E } // nonterminals– P = { E a, E b, E c, // productionsE E-E, E E+E, E E*E, E (E)}– S = E // start symbol16Uniqueness of Grammars• Grammars are not unique• Different grammars – Can generate the same set of strings (language)• The following grammar generates the same set of strings as the previous grammarE E+T | E-T | TT T*P | PP (E) | a | b | c17Notational Shortcuts• A production is of the form– left-hand side (LHS) right hand side (RHS)• If not specified– Assume LHS of first listed production is the start symbol• Productions with the same LHS– Are usually combined with |• If a production has an empty RHS– It means the RHS is S ABC // S is start symbolA aA| b // A b| // A ε18Sentential form• Definition– A sentential form is a string of terminals and nonterminals produced from the start symbol• Inductively– The start symbol– If A is a sentential form for a grammar, where (and ∈ (N|)*), and A is a production, then is a sentential form for the grammar• In this case, we say that A derives in one step, which is written as A 19Sentential form example• Given grammar – S → 0S | 1S | ε• Possible derivations– S → 0S → 01S → 010S → 010• S, 0S, 01S, 010S, 010 are sentential forms– S → 1S → 11S → 111S → 111• S, 1S, 11S, 111S, 111 are sentential forms– S → ε• S, ε are sentential forms• In other words– If S → * , then is a sentential form20Language generated by grammar• A slightly more formal definition…– The language defined by a CFG is the set of all sentential forms made up of only terminals• Example– S → 0S | 1S | ε– In language Not in language01, 000, 11, ε … 0S, a, 11S, …21Language Generated by Grammar (cont.)• L(G), the language generated by grammar G isL(G) = { | ∈ * and S →+ }– S is the start symbol of the grammar – is the alphabet for that grammar• In other
View Full Document
Unlocking...