Transcription
Context-Free Grammars andLanguagesContext-Free Grammars and Languages – p.1/40
There are languages, such asbe described (specified) by NFAs or REs Limitations of finite automatathat cannotContext-Free Grammars and Languages – p.2/40
There are languages, such asbe described (specified) by NFAs or REs Limitations of finite automatathat cannotContext-free grammars provide a more powerfulmechanism for language specificationContext-Free Grammars and Languages – p.2/40
There are languages, such asbe described (specified) by NFAs or REs Limitations of finite automatathat cannotContext-free grammars provide a more powerfulmechanism for language specificationContext-free grammars can describe features thathave a recursive structure making them useful beyondfinite automataContext-Free Grammars and Languages – p.2/40
Historical notesContext-free grammars were first used to study humanlanguagesContext-Free Grammars and Languages – p.3/40
Historical notesContext-free grammars were first used to study humanlanguagesOne way of understanding the relationship betweensyntactic categories (such as noun, verb, preposition,etc) and their respective phrases leads to naturalrecursionContext-Free Grammars and Languages – p.3/40
Historical notesContext-free grammars were first used to study humanlanguagesOne way of understanding the relationship betweensyntactic categories (such as noun, verb, preposition,etc) and their respective phrases leads to naturalrecursionThis is because noun phrases may occur inside theverb phrases and vice versa.Context-Free Grammars and Languages – p.3/40
NoteContext-free grammars can capture important aspects ofthese relationshipsContext-Free Grammars and Languages – p.4/40
Important applicationContext-free grammars are used as basis for compilerdesign and implementationContext-Free Grammars and Languages – p.5/40
Important applicationContext-free grammars are used as basis for compilerdesign and implementationContext-free grammars are used as specificationmechanisms for programming languagesContext-Free Grammars and Languages – p.5/40
Important applicationContext-free grammars are used as basis for compilerdesign and implementationContext-free grammars are used as specificationmechanisms for programming languagesDesigners of compilers use such grammars toimplement compiler’s components, such a scanners,parsers, and code generatorsContext-Free Grammars and Languages – p.5/40
Important applicationContext-free grammars are used as basis for compilerdesign and implementationContext-free grammars are used as specificationmechanisms for programming languagesDesigners of compilers use such grammars toimplement compiler’s components, such a scanners,parsers, and code generatorsThe implementation of any programming language ispreceded by a context-free grammar that specifies itContext-Free Grammars and Languages – p.5/40
Context-free languagesThe collection of languages specified by context-freegrammars are called context-free languagesContext-Free Grammars and Languages – p.6/40
Context-free languagesThe collection of languages specified by context-freegrammars are called context-free languagesContext-free languages include regular languages andmany othersContext-Free Grammars and Languages – p.6/40
Context-free languagesThe collection of languages specified by context-freegrammars are called context-free languagesContext-free languages include regular languages andmany othersHere we will study the formal concepts of context-freegrammars and context-free languagesContext-Free Grammars and Languages – p.6/40
NotationsAbbreviate the phrase context-free grammar to CFG.Context-Free Grammars and Languages – p.7/40
NotationsAbbreviate the phrase context-free grammar to CFG.Abbreviate the phrase context-free language to CFL.Context-Free Grammars and Languages – p.7/40
NotationsAbbreviate the phrase context-free grammar to CFG.Abbreviate the phrase context-free language to CFL. Abbreviate the concept of a CFG specification rule towherestands for left handthe tuplestands for right hand side.side andContext-Free Grammars and Languages – p.7/40
More on specification rules Theof a specification rule is also called variableand is denoted by capital lettersContext-Free Grammars and Languages – p.8/40
More on specification rules Theof a specification rule is also called variableand is denoted by capital letters Theof a specification rule is also called aspecification pattern and consists of a string ofvariables and constantsContext-Free Grammars and Languages – p.8/40
More on specification rules Theof a specification rule is also called variableand is denoted by capital letters Theof a specification rule is also called aspecification pattern and consists of a string ofvariables and constantsThe variables that occur in a specification pattern arealso called nonterminal symbols; the constants thatoccur in a specification pattern are also called terminalsymbolsContext-Free Grammars and Languages – p.8/40
CFG: InformalA CFG grammar consists of a collection ofspecification rules where one variable is designated asstart symbol or axiomContext-Free Grammars and Languages – p.9/40
CFG: InformalExample: the CFGrules: A CFG grammar consists of a collection ofspecification rules where one variable is designated asstart symbol or axiomhas the following specificationContext-Free Grammars and Languages – p.9/40
CFG: InformalA CFG grammar consists of a collection ofspecification rules where one variable is designated asstart symbol or axiom has the following specification Example: the CFGrules:Context-Free Grammars and Languages – p.9/40
are Nonterminals of CFG Noteandis the axiomContext-Free Grammars and Languages – p.10/40
are andis the axiom Terminals of CFGare Nonterminals of CFG NoteContext-Free Grammars and Languages – p.10/40
More terminologyThe specification rules of a CFG are also calledproductions or substitution rulesContext-Free Grammars and Languages – p.11/40
More terminologyThe specification rules of a CFG are also calledproductions or substitution rulesNonterminals used in the specification rules defining aCFG may be stringsContext-Free Grammars and Languages – p.11/40
More terminologyThe specification rules of a CFG are also calledproductions or substitution rulesNonterminals used in the specification rules defining aCFG may be stringsTerminals in the specification rules defining a CFG areconstant stringsContext-Free Grammars and Languages – p.11/40
TerminalsTerminals used in CFG specification rules areanalogous to the input alphabet of an automatonContext-Free Grammars and Languages – p.12/40
TerminalsTerminals used in CFG specification rules areanalogous to the input alphabet of an automatonExample terminals used in CFG-s are letters of analphabet, numbers, special symbols, and strings ofsuch elements.Context-Free Grammars and Languages – p.12/40
TerminalsTerminals used in CFG specification rules areanalogous to the input alphabet of an automatonExample terminals used in CFG-s are letters of analphabet, numbers, special symbols, and strings ofsuch elements.Strings used to denote terminals in CFG specificationrules are quotedContext-Free Grammars and Languages – p.12/40
Language specificationA CFG is used as a language specification mechanism bygenerating each string of the language in following manner:Context-Free Grammars and Languages – p.13/40
Language specificationA CFG is used as a language specification mechanism bygenerating each string of the language in following manner: 1. Write down the start variable; it is theof one of thespecification rules,the top rule, unless specified otherwiseContext-Free Grammars and Languages – p.13/40
Language specificationA CFG is used as a language specification mechanism bygenerating each string of the language in following manner: 2. Find a variable that is written down and a rule whosevariable. Replace the written down variable with therule 1. Write down the start variable; it is theof one of thespecification rules,the top rule, unless specified otherwiseis thatof thatContext-Free Grammars and Languages – p.13/40
Language specificationA CFG is used as a language specification mechanism bygenerating each string of the language in following manner: 2. Find a variable that is written down and a rule whosevariable. Replace the written down variable with therule 1. Write down the start variable; it is theof one of thespecification rules,the top rule, unless specified otherwiseis thatof that3. Repeat step 2 until no variables remain in the string thusgeneratedContext-Free Grammars and Languages – p.13/40
Using CFGfollows:A0A1 Example string generationwe can generate the string 000#111 as00A11000A111000B111000#111Context-Free Grammars and Languages – p.14/40
Using CFGfollows:A0A1 Example string generationwe can generate the string 000#111 as00A11000A111000B111000#111Note: The sequence of substitutions used to obtain a stringusing a CFG is called a derivation and may be representedby a tree called a derivation tree or a parse treeContext-Free Grammars and Languages – p.14/40
The derivation tree of the string 000#111 using CFGAin Figure 1 Example derivation treeisAAAB000#111Figure 1: Derivation tree for 000#111Context-Free Grammars and Languages – p.15/40
NoteAll strings of terminals generated in this way constitutethe language specified by the grammarContext-Free Grammars and Languages – p.16/40
Note for the language generated by the. Thus,. We writegrammar All strings of terminals generated in this way constitutethe language specified by the grammarContext-Free Grammars and Languages – p.16/40
Note for the language generated by the. Thus,. We writegrammar All strings of terminals generated in this way constitutethe language specified by the grammarThe language generated by a context-free grammar iscalled a Context-Free Language, CFL.Context-Free Grammars and Languages – p.16/40
More notations To distinguish nonterminal from terminal strings weoften enclose nonterminals in angular parentheses,, and terminals in quotes “,".Context-Free Grammars and Languages – p.17/40
More notations To distinguish nonterminal from terminal strings weoften enclose nonterminals in angular parentheses,, and terminals in quotes “,". If two or more rules have the same, as in theand, we may compact themexamplewhere is usedusing the formwith the meaning of an “or".Context-Free Grammars and Languages – p.17/40
Example compactionandmay be written as The rules.Context-Free Grammars and Languages – p.18/40
% # ! " The CFG CFGspecifies a fragment of EnglishContext-Free Grammars and Languages – p.19/40
NoteThe CFGhas ten variables (capitalized and inangular brackets) and 9 terminals (written in thestandard English alphabet) plus a space characterContext-Free Grammars and Languages – p.20/40
NoteThe CFGhas ten variables (capitalized and inangular brackets) and 9 terminals (written in thestandard English alphabet) plus a space characterAlso, the CFGhas 18 rulesContext-Free Grammars and Languages – p.20/40
NoteThe CFGhas ten variables (capitalized and inangular brackets) and 9 terminals (written in thestandard English alphabet) plus a space characterExamples strings that belongs to has 18 rules Also, the CFGare:a boy seesthe boy sees a flowera girl with a flower likes the boyContext-Free Grammars and Languages – p.20/40
Example derivation withContext-Free Grammars and Languages – p.21/40
A context-free grammar is a 4-tuple Formal definition of a CFGwhere:Context-Free Grammars and Languages – p.22/40
1. A context-free grammar is a 4-tuple Formal definition of a CFGwhere:is a finite set of strings called the variables ornonterminalsContext-Free Grammars and Languages – p.22/40
A context-free grammar is a 4-tuple Formal definition of a CFGwhere:is a finite set of strings called the variables ornonterminals2.is a finite set of strings, disjoint fromterminals 1., calledContext-Free Grammars and Languages – p.22/40
Formal definition of a CFGwhere: A context-free grammar is a 4-tuple1.is a finite set of strings called the variables ornonterminals2.is a finite set of strings, disjoint fromterminals3.is a finite set of rules (or specification rules) of the, where,form , calledContext-Free Grammars and Languages – p.22/40
Formal definition of a CFGwhere: A context-free grammar is a 4-tuple1.is a finite set of strings called the variables ornonterminals2.is a finite set of strings, disjoint fromterminals3.is a finite set of rules (or specification rules) of the, where,form4. , calledis the start variable (or grammar axiom)Context-Free Grammars and Languages – p.22/40
whereis: Example CFG grammarContext-Free Grammars and Languages – p.23/40
Direct derivation If(i.e., are strings of variables and(i.e., is a rule of theterminals) andyields, writtengrammar) then we say thatContext-Free Grammars and Languages – p.24/40
Direct derivation is directly derived from We may also say thatusing the rule If(i.e., are strings of variables and(i.e., is a rule of theterminals) andyields, writtengrammar) then we say thatContext-Free Grammars and Languages – p.24/40
Derivationor if a sequenceexists, for, and % % if We writeContext-Free Grammars and Languages – p.25/40
Derivationor if a sequenceexists, for, and% is a derivation of We may also say thatfrom % % if We writeContext-Free Grammars and Languages – p.25/40
is a CFG then the language specified by(or the language of ) is If Language specified byContext-Free Grammars and Languages – p.26/40
NoteOften we specify a grammar by writing down only itsrulesContext-Free Grammars and Languages – p.27/40
NoteOften we specify a grammar by writing down only itsrules We can identify the variables as the symbols thatof the rulesappear only as theContext-Free Grammars and Languages – p.27/40
NoteOften we specify a grammar by writing down only itsrules We can identify the variables as the symbols thatof the rulesappear only as theTerminals are the remaining strings used in the rulesContext-Free Grammars and Languages – p.27/40
More examples of CFGsConsider the grammar:Context-Free Grammars and Languages – p.28/40
More examples of CFGs Consider the grammar:Context-Free Grammars and Languages – p.28/40
More examples of CFGs Consider the grammar:contains strings such as:Context-Free Grammars and Languages – p.28/40
More examples of CFGs Consider the grammar:contains strings such as:abab, aaabbb, aababb;Context-Free Grammars and Languages – p.28/40
More examples of CFGs Consider the grammar:contains strings such as: abab, aaabbb, aababb; Note: if one think atasthen we can see thatis the language of all strings of properly nestedparenthesesContext-Free Grammars and Languages – p.28/40
Arithmetic expressionswhere Consider the grammar:is:Context-Free Grammars and Languages – p.29/40
Arithmetic expressions is: where Consider the grammar:Context-Free Grammars and Languages – p.29/40
Arithmetic expressions is: where Consider the grammar:is the language of arithmetic expressionsContext-Free Grammars and Languages – p.29/40
are represented The variables and constants inby the terminal NoteContext-Free Grammars and Languages – p.30/40
are represented The variables and constants inby the terminal NoteArithmetic operations inare addition,represented by , and multiplication, represented by *Context-Free Grammars and Languages – p.30/40
are represented The variables and constants inby the terminal NoteArithmetic operations inare addition,represented by , and multiplication, represented by *An examples of a derivation usingis in Figure 2Context-Free Grammars and Languages – p.30/40
Example derivation withE E TTTFFaa*FaFigure 2: Derivation tree for a a*aContext-Free Grammars and Languages – p.31/40
Designing CFGsAs with the design of automata, the design of CFGsrequires creativityContext-Free Grammars and Languages – p.32/40
Designing CFGsAs with the design of automata, the design of CFGsrequires creativityCFGs are even trickier to construct than finiteautomata because “we are more accustomed toprogramming a machine than we are to specifyprogramming languages"Context-Free Grammars and Languages – p.32/40
Design techniquesMany CFG are unions of simpler CFGs. Hence thesuggestion is to construct smaller, simpler grammarsfirst and then to join them into a larger grammarContext-Free Grammars and Languages – p.33/40
Design techniquesMany CFG are unions of simpler CFGs. Hence thesuggestion is to construct smaller, simpler grammarsfirst and then to join them into a larger grammar % The mechanism of grammar combination consists ofputting all their rules together and adding the new ruleswhere the variables ,,are the start variables of the individual grammars andis a new variableContext-Free Grammars and Languages – p.33/40
Example grammar design Design a grammar for the languageContext-Free Grammars and Languages – p.34/40
Example grammar design that generates 1. Construct the grammar Design a grammar for the languageContext-Free Grammars and Languages – p.34/40
Example grammar design that generates 2. Construct the grammarthat generates 1. Construct the grammar Design a grammar for the languageContext-Free Grammars and Languages – p.34/40
Example grammar design thus getting 3. Put them together adding the rule that generates 2. Construct the grammar that generates 1. Construct the grammar Design a grammar for the languageContext-Free Grammars and Languages – p.34/40
Second design techniqueConstructing a CFG for a regular language is easy ifone can first construct a DFA for that languageContext-Free Grammars and Languages – p.35/40
Second design techniqueConstructing a CFG for a regular language is easy ifone can first construct a DFA for that languageConversion procedure:Context-Free Grammars and Languages – p.35/40
Second design techniqueConstructing a CFG for a regular language is easy ifone can first construct a DFA for that languagefor each state 1. Make a variable Conversion procedure:of DFAContext-Free Grammars and Languages – p.35/40
Second design techniqueConstructing a CFG for a regular language is easy ifone can first construct a DFA for that language to the CFG if 2. Add the ruletransition in the DFA of DFA for each state 1. Make a variable Conversion procedure:is aContext-Free Grammars and Languages – p.35/40
Second design techniqueConstructing a CFG for a regular language is easy ifone can first construct a DFA for that language ifto the CFG if 3. Add the rule 2. Add the ruletransition in the DFA of DFA for each state 1. Make a variable Conversion procedure:is ais an accept state of the DFAContext-Free Grammars and Languages – p.35/40
Second design techniqueConstructing a CFG for a regular language is easy ifone can first construct a DFA for that language is ais an accept state of the DFA4. If is the start state of the DFA makethe CFG. ifto the CFG if 3. Add the rule 2. Add the ruletransition in the DFA of DFA for each state 1. Make a variable Conversion procedure:the start variable ofContext-Free Grammars and Languages – p.35/40
NoteVerify that CFG constructed by the conversion of a DFA intoa CFG generates the language that the DFA recognizesContext-Free Grammars and Languages – p.36/40
Third design technique Certain CFLs contain strings with two relatedandinsubstrings as areContext-Free Grammars and Languages – p.37/40
Third design technique Certain CFLs contain strings with two relatedandinsubstrings as areExample of relationship: to recognize such a languagea machine would need to remember an unboundedamount of info about one of the substringsContext-Free Grammars and Languages – p.37/40
Note A CFG that handles this situation uses a rule of the formwhich generates strings wherein the portion containing ’s corresponds to the portion containing ’sContext-Free Grammars and Languages – p.38/40
Fourth design techniqueIn a complex language, strings may contain certainstructures that appear recursivelyContext-Free Grammars and Languages – p.39/40
Fourth design techniqueIn a complex language, strings may contain certainstructures that appear recursivelyExample: in arithmetic expressions any time thesymbol a appear, the entire parenthesized expressionmay appear.Context-Free Grammars and Languages – p.39/40
NoteTo achieve this effect one needs to place the variable genin case of erating the structure () in the location of the appear as in rule corresponding to where the structure may recursivelyin case ofContext-Free Grammars and Languages – p.40/40
preceded by a context-free grammar that specifies it Context-Free Grammars and Languages - p.5/40. Important application Context-free grammars are used as basis for compiler design and implementation Context-free grammars are used as specification mechanisms for programming languages
