Context Free Grammars Definition of a grammar G

 Context Free Grammars  Definition of a grammar G

Context Free Grammars Definition of a grammar G Deriving strings and defining L(G) Context-Free Language definition 1 Context-Free Grammars Definition 2 Definition A context-free grammar G = (V, , S, P)

V: finite set of variables (nonterminals) : finite set of characters (terminals) S: start variable element of V role is similar to that of q0 for an FSA or NFA P: finite set of grammar rules or production rules Syntax of a production variable string of variables and terminals 3 English Context-Free Grammar ECFG = (V, , S, P)

V = {, , , ... } people sometimes use < > to delimit variables In this course, we generally will use capital letters to denote variables = {a, b, c, ..., z, ;, ,, ., ...} S = P = { ,

, ...} 4 {aibi | i>0} CFG ABG = (V, , S, P)

V = {S} = {a, b} S=S P = {S aSb, S ab} or S aSb | ab second format saves some space 5 Context-Free Grammars Deriving strings, defining L(G), and defining context-free languages 6

Defining , ==> notation First: notation This is used to define the productions of a grammar S aSb | ab Second: ==>G notation This is used to denote the application of a production rule from a grammar G S ==>ABG aSb ==>ABG aaSbb ==>ABG aaabbb We say that string S derives string aSb (in one step) We say that string aSb derives string aaSbb (in one step) We say that string aaSbb derives string aaabbb (in one step)

We often omit the grammar subscript when the intended grammar is unambiguous 7 Defining ==> continued Third: ==>kG notation This is used to denote k applications of production rules from a grammar G S ==>2ABG aaSbb We say that string S derives string aaSbb in two steps aSb ==>2ABG aaabbb

We say that string aSb derives string aaabbb in two steps We often omit the grammar subscript when the intended grammar is unambiguous 8 Defining ==> continued Fourth: ==>*G notation This is used to denote 0 or more applications of production rules from a grammar G S ==>*ABG S We say that string S derives string S in 0 or more steps

S ==>*ABG aaSbb We say that string S derives string aaSbb in 0 or more steps aSb ==>*ABG aaSbb We say that string aSb derives string aaSbb in 0 or more steps aSb ==>*ABG aaabbb We say that string aSb derives string aaabbb in 0 or more steps We often omit the grammar subscript when the intended grammar is unambiguous 9

Defining derivations * Derivation of a string x The complete step by step derivation of a string x from the start variable S Key fact: each step in a derivation makes only one application of a production rule from G Example: Derivation of string aaabbb using ABG S ==>ABG aSb ==>ABG aaSbb ==>ABG aaabbb Example 2: AG= (V, , S, P) where P = S SS | a Deriving string aaa S ==> SS ==> Sa ==> SSa ==> aSa ==> aaa

10 Defining L(G) * Generating strings If S ==>G* x, then grammar G generates string x Note G generates strings which contain terminals and nonterminals aSb contains nonterminals and terminals S contains only nonterminals aaabbb contains only terminals L(G)

The set of strings over generated by grammar G Note we only consider terminal strings generated by G {aibi | i > 0} = L(ABG) {ai | i > 0} = L(AG) 11 Context-Free Languages * Context-Free Languages A language L is a context-free language (CFL) iff Results so far

{ai | i > 0} is a CFL One CFG G such that L(G) = this language is AG Note this language is also regular {aibi | i > 0} is a CFL One CFG G such that L(G) = this language is ABG Note this language is NOT regular 12 Example Let BAL = the set of strings over {(,)} in which the parentheses are balanced Prove that BAL is a CFL

To prove this, you need to come up with a CFG BALG such that L(BALG) = BAL BALG = (V, , S, P) V = {S} = {(, )} S=S P=?

Give derivations of ((( ))) and ( )(( )) with your grammar 13 Implications Given that the language of balanced parentheses is a CFL, what implications does this have for compiler design? What programming language structures can be captured by CFG? 14

Recently Viewed Presentations

  • Hamburger Helper Essay Presentation

    Hamburger Helper Essay Presentation

    The Hamburger Method in Action- Through the Meat Grinder. Introduction and Thesis. Introduction: 1) A broad topic statement that is creative- ... Each new paragraph should have a topic sentence which supports your Thesis Statement. The sentences in the paragraph...
  • Homeostasis and Transport - Quia

    Homeostasis and Transport - Quia

    Homeostasis and Transport Concentration The amount of solute in a solution. Often measured as a percentage. Deciding factor as to where particles move. Passive Transport Movement of particles that does not require energy.
  • Roof Component Parts - bcsc.k12.in.us

    Roof Component Parts - bcsc.k12.in.us

    Presentation 19: RAFTER AND ROOF COMPONENT PARTS Gable Roof Gable Roof Roof Framing Terms Roof Framing Terms Rafter Parts Ridge Cut Bird's Mouth and Tail Bird's Mouth and Tail Projection vs. Overhang Rafter Parts Rafter Parts Rafter Parts Conclusions Gable...
  • NERC Critical Infrastructure Protection (CIP)

    NERC Critical Infrastructure Protection (CIP)

    Audit Preparation - Compliance Levels Compliant (C) - means the entity meets the full intent of the requirements and is beginning to maintain required "data," "documents," "documentation," "logs," and "records" Auditably Compliant (AC) - means the entity meets the full...
  • Benefits - UBC CTLT

    Benefits - UBC CTLT

    Survey (n=505, response 22%) Indepth Interviews 8 withdrawers 8 completers Authors: Boop, Morris, Finnegan (2005) Successful completers Felt "membership" in the course. Understood course layout, expectations, assignments. Faculty feedback was important. Clarity about course was important.
  • Competency: 206.00 Draw Wall Sections Objective 206.01 Identify

    Competency: 206.00 Draw Wall Sections Objective 206.01 Identify

    Competency: 206.00 Draw Wall Sections Objective 206.01 Identify terms and definitions related to wall sections. Wall Sections & Details Terms & Definitions Anchor bolt - threaded rod inserted in masonry construction to anchor sill plate to foundation Blocking - Framing...
  • Failure Mode and Effect Analysis (FMEA)

    Failure Mode and Effect Analysis (FMEA)

    FMEA Team FMEA methodology is a team effort where the responsible engineer involves who? FMEA Documentation Class Assignment !!!!! Divide up into four groups (N,S,E and W) Stages of FMEA Specifying Possibilities Functions Possible Failure Modes Root Causes Effects Detection/Prevention...
  • Company Name - AIRM

    Company Name - AIRM

    Green House Gas. KSS is unique in so far as it is the only Fire Suppression Company in Ireland that has all the approval as required for Waste Regulation by the EPA, Locals Authority, F-GAS and the National TFS Office...