DOC PREVIEW
UMD CMSC 330 - Context-Free Grammars

This preview shows page 1-2-20-21 out of 21 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CMSC 330: Organization of Programming Languages Context-Free Grammars CMSC 330 2 Motivation •! Programs are just strings of text –! But they’re strings that have a certain structure •! Informal description of syntax 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 an expression, if, goto, etc. –! An expression may be assignment, addition, subtraction, etc Motivation (cont’d) •! 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 •! Instead, we’ll use context-free grammars –! These are almost enough for C, C++, Java CMSC 330 3 CMSC 330 4 Context 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 ! " •! Grammar is same as regular expression (0|1)* –! Generates / accepts the same set of stringsCMSC 330 5 Context-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 process CMSC 330 6 Formal 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 # •! Can think of productions as rewriting rules –! S 󲶽 N – the start symbol CMSC 330 7 Backus-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 1962 CMSC 330 8 Informal 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 parsingCMSC 330 9 Derivations •! 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 !* S CMSC 330 10 Practice •! Try to make a grammar which accepts –! 0*|1* – 0n1n where n $ 0 – 0n1m where m % n •! Give some example strings from this language –! S ! 0 | 1S •! 0, 10, 110, 1110, 11110, … –! What language is it? •! 1*0 S # A | B A # 0A | & B # 1B | & S # 0S1 | & S # 0S1 | 0S & CMSC 330 11 Example S # aS | T T # bT | U U # cU | & •! A derivation: –! S ! aS ! aT ! aU ! acU ! ac •! Abbreviated as S !+ ac –! S ! T ! U ! & •! Is there any derivation –! S !+ ccc ? S !+ Sa ? –! S !+ bab ? S !+ bU ? CMSC 330 12 Example (cont’d) S # aS | T T # bT | U U # cU | & •! Generates what language? •! Do other grammars generate this language? S # ABC A # aA | & B # bB | & C # cC | & –! So grammars are not uniqueCMSC 330 13 Example: 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 + d)} •! Example strings not in the language –! d, c(a), a+, b**c, etc. CMSC 330 14 Example, Formally •! Formally, the grammar we just showed is ! = { +, -, *, (, ), a, b, c } // terminals N = { E } // nonterminals P = { E # a, E # b, E # c, // productions E # E-E, E # E+E, E # E*E, E # (E) } S = E // start symbol CMSC 330 15 Uniqueness of Grammars •! Grammars are not unique –! Different grammars can generate same set of strings •! Following grammar generates the same set of strings as the previous grammar: E # E+T | E-T | T T # T*P | P P # (E) | a | b | c CMSC 330 16 Notational 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 symb A # aA | b // A # b | // A # "CMSC 330 17 Sentential Forms and Derivations •! A sentential form is a string of terminals and nonterminals produced from that start symbol •! Inductively –! The start symbol is a sentential form for a grammar –! 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, …


View Full Document

UMD CMSC 330 - Context-Free Grammars

Documents in this Course
Exam #1

Exam #1

6 pages

Quiz #1

Quiz #1

2 pages

Midterm 2

Midterm 2

12 pages

Exam #2

Exam #2

7 pages

Ocaml

Ocaml

7 pages

Parsing

Parsing

38 pages

Threads

Threads

12 pages

Ruby

Ruby

7 pages

Quiz #3

Quiz #3

2 pages

Threads

Threads

7 pages

Quiz #4

Quiz #4

2 pages

Exam #2

Exam #2

6 pages

Exam #1

Exam #1

6 pages

Threads

Threads

34 pages

Quiz #4

Quiz #4

2 pages

Threads

Threads

26 pages

Exam #2

Exam #2

9 pages

Exam #2

Exam #2

6 pages

Load more
Download Context-Free Grammars
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Context-Free Grammars and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Context-Free Grammars 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?