1CMSC 330: Organization of Programming LanguagesContext-Free GrammarsCMSC 330 2Reminders / Announcements• Project 2 was posted on Sep. 24• Class participation is part of your grade2CMSC 330 3Motivation• Programs are just strings of text– But they’re strings that have a certain structure• 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, an if, a goto, etc.• An expression may be assignment, addition, subtraction, etc• We want to solve two problems– We want to describe programming languages precisely– We need to describe more than the regular languages• Recall that regular expressions , DFAs, and NFAs are limited in their expressivenessCMSC 330 4Program structureSyntax• What a program looks like• BNF (context free grammars) - a useful notation for describing syntax.Semantics• Execution behavior3CMSC 330 5Context-Free Grammars (CFGs)• A way of generating sets of strings or languages• They subsume regular expressions (and DFAsand NFAs)– There is a CFG that generates any regular language– (But regular expressions are a better notation for languages which are regular.)• They can be used to describe programming languages– They (mostly) describe the parsing processCMSC 330 6Simple ExampleS → 0|1|0S|1S|ε• This is the same as the regular expression (0|1)*• But CFGs can do a lot more!4CMSC 330 7Formal Definition• A context-free grammar G is a 4-tuple:– – a finite set of terminal or 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 –S N – the start symbolCMSC 330 8Informal Definition of Acceptance• A string is accepted by a CFG if there is some path that can be followed starting at the start state which generates the stringExample:S → 0|1|0S|1S|ε0101:S →0S →01S →010S →01015CMSC 330 9Example: Arithmetic Expressions (Limited)•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.CMSC 330 10Formal Description of Example• Formally, the grammar we just showed is– = { +, -, *, (, ), a, b, c }– N = { E }– P = { E a, E b, E c, E E-E, E E+E,E E*E, E (E)}–S = E6CMSC 330 11Notational Shortcuts• If not specified, assume the left-hand side of the first listed production is the start symbol• Usually productions with the same left-hand sides are combined with |• If a production has an empty right-hand side it means CMSC 330 12Backus-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• 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 19627CMSC 330 13Uniqueness of Grammars• Grammars are not unique. Different grammars can generate the same set of strings.• The following grammar generates the same set of strings as the previous grammar:E E+T | E-T | TT T*P | PP (E) | a | b | cCMSC 330 14Another Example Grammar•S aS | TT bT | UU cU | What are some strings in the language?8CMSC 330 15PracticeTry to make a grammar which accepts…•0*|1*•anbnGive some example strings from this language:•S →0|1SWhat language is it?CMSC 330 16Sentential FormsA sentential form is a string of terminals and nonterminals produced from the start symbolInductively:– 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 9CMSC 330 17Derivations• is used to indicate a derivation of one step• +is used to indicate a derivation of one or more steps• *indicates a derivation of zero or more stepsExample:S → 0|1|0S|1S|ε0101:S 0S 01S 010S 0101S +0101S *SCMSC 330 18Language Generated by GrammarA slightly more formal definition…• The language defined by a CFG is the set of all sentential forms made up of only terminals.Example:S → 0|1|0S|1S|εIn language: Not in language:01, 000, 11, ε … 0S, a, 11S, …10CMSC 330 19ExampleS aS | TT bT | UU cU | • A derivation:–S aS aT aU acU ac• Abbreviated as S +ac•SoS, aS, aT, aU, acU, ac are all sentential forms for this grammar–S T U • Is there any derivation–S +ccc ? S +Sa ?–S +bab ? S +bU ?CMSC 330 20The Language Generated by a CFG• The language generated by a grammar G isL(G) = { | * and S + }– (where S is the start symbol of the grammar and is the alphabet for that grammar)• I.e., all sentential forms with only terminals• I.e., all strings over that can be derived from the start symbol via one or more productions11CMSC 330 21Example (cont’d)S aS | TT bT | UU cU | • Generates what language?• Do other grammars generate this language?S ABCA aA | B bB | C cC | – So grammars are not uniqueCMSC 330 22Parse Trees•A parse tree shows how a string is produced by a grammar– The root node is the start symbol– Each interior node is a nonterminal– Children of node are symbols on r.h.s of production applied to that nonterminal– Leaves are all terminal symbols• Reading the leaves left-to-right shows the string corresponding to the tree12CMSC 330 23ExampleS aS | TT bT | UU cU | S aS aT aU acU acCMSC 330 24Parse Trees for Expressions•A parse tree shows the structure of an expression as it corresponds to a grammarE a | b | c | d | E+E | E-E | E*E | (E)a
View Full Document
Unlocking...