Difference between revisions of "Context-free grammar"

From Conservapedia
Jump to navigation Jump to search
(add cross-reference to Backus-Naur Form)
(start making this article more accessible)
Line 1: Line 1:
−
''An equivalent grammar [[Backus-Naur Form]] is often used for describing the syntax/grammar of programming languages.''
+
:''An equivalent grammar [[Backus-Naur Form]] is often used for describing the syntax/grammar of programming languages.''
  
 +
A '''context-free grammar''' is a formal grammatical system for describing a particular class of language. The basic idea of such a generative grammar is to provide a set of rules which can be used to generate all possible grammatical 'sentences'; these rules must also avoid generating any ungrammatical sentences. A context-free grammar is not powerful enough to describe a natural language such as [[English]], but it is powerful enough to describe nearly all [[programming language]]s.
 +
 +
A context-free grammar is the level 2 grammar in the [[Chomsky hierarchy]] and was first described in 1956 by the linguist [[Noam Chomsky|Chomsky]].
 +
<ref>{{cite journal
 +
| title = Three models for the description of language
 +
| year = 1956
 +
| last = Chomsky
 +
| first = Noam
 +
| journal = IRE Transactions on Information Theory
 +
| volume = 2
 +
| pages = 113–124
 +
| url = http://www.chomsky.info/articles/195609--.pdf
 +
| accessdate = 2012-04-08
 +
}}</ref>
 +
 +
==Example of a very simple context-free grammar==
 +
This very simple example can handle only a tiny subset of English and should not be taken seriously as a guide to English grammar or vocabulary. It is based on an example by David Crystal
 +
<ref>{{cite book
 +
| last = Crystal
 +
| first = David 
 +
| title = The Cambridge Encyclopedia of Language
 +
| publisher = Cambridge University Press
 +
| year = 1987
 +
| isbn = 0-521-42443-7
 +
| pages = page 97
 +
}}</ref> and is a slight extension of an example on slide 9 of this lecture.
 +
<ref>{{cite web
 +
| url = http://www.cs.princeton.edu/~rywang/99f126/slides/16th.pdf
 +
| title = Lecture notes: Formal Languages
 +
| accessdate = 2012-04-07}}
 +
</ref>
 +
 +
''Sentence''  ->  ''NounPhrase'' ''VerbPhrase''        # A ''Sentence'' consists of a ''NounPhrase'' followed by a ''VerbPhrase''
 +
''NounPhrase'' ->  ''Determiner'' ''Noun''              # A ''NounPhrase'' consists of a ''Determiner'' followed by a ''Noun''
 +
''VerbPhrase'' ->  ''Verb'' ''NounPhrase''              # A ''VerbPhrase'' consists of a ''Verb'' followed by a ''NounPhrase''
 +
''Determiner'' ->  '''a''', '''the'''                        # A ''Determiner''  is one of: '''a''' or '''the'''
 +
''Noun''      ->  '''boy''', '''girl''', '''dog'''                # A ''Noun'' is one of: '''boy''' or '''girl''' or '''dog''' 
 +
''Verb''      ->  '''chased''', '''heard''', '''saw'''            # A ''Verb'' is one of: '''chased''' or '''heard''' or '''saw'''
 +
 +
Notation used above:
 +
:The symbol "->" means "can be replaced by". 
 +
:When there are several items on the right hand side separated by commas, just one of these items can be selected.
 +
:The comments preceded by "#" are not part of the generative grammar, but hopefully will help folks understand the example a little better.
 +
 +
By making appropriate substitutions we can generate such sentences as:
 +
:The dog chased a girl.
 +
:The girl heard the dog.
 +
:The boy saw a girl.
 +
 +
The stages in the generation of these examples are as follows:
 +
:''Sentence''
 +
:-> ''NounPhrase'' ''VerbPhrase''
 +
:-> ''Determiner'' ''Noun'' ''Verb'' ''NounPhrase''
 +
:-> ''Determiner'' ''Noun'' ''Verb'' ''Determiner'' ''Noun''
 +
 +
By appropriate selection of words to substitute for ''Determiner'', ''Noun'', and ''Verb'' we can produce the 3 example sentences above.
 +
 +
The simple grammar defines a few words which can be substituted for ''Determiner'', ''Noun'', and ''Verb''. There are two possibilities for ''Determiner'', three for ''Noun'', and three for ''Verb'', with both ''Determiner'' and ''Noun'' appearing twice in the expansion. Hence the total number of grammatical sentences which can be generated by this simple grammar is 108 (= 2 * 3 * 3 * 2 * 3). In this particular case the possible words have been carefully chosen so that all of these 108 sentences also actually mean something.
 +
 +
Note that the use of ''italics'' and '''boldface''' in this example is merely a convenient way of indicating the difference between items which can be expanded further (e.g. concepts such as ''NounPhrase'') and items which can not be expanded further (e.g. words such as '''girl'''). In the linguistic literature, items which can be expanded further are referred to as 'non-terminal' items, while items which can't be expanded further are known as 'terminal' items.
 +
 +
The 'comma' notation for alternatives is a form of shorthand. In some formulations this would be shown as several separate rules, so that:
 +
  ''Determiner'' ->  '''a''', '''the'''
 +
could be shown as two rules:
 +
  ''Determiner'' ->  '''a'''
 +
  ''Determiner'' ->  '''the'''
 +
 +
==Caution==
 +
While a generative grammar may produce sentences which are grammatically correct, there is no certainty that such sentences will actually mean anything. The classic example of such a meaningless sentence is from Chomsky's book
 +
<ref>{{cite book
 +
| last = Chomsky
 +
| first = Noam
 +
| title = Syntactic Structures
 +
| year = 1957
 +
| publisher = Mouton
 +
| location = The Hague/Paris
 +
| pages = page 15
 +
| isbn = 3-11-017279-8
 +
}}</ref> with the grammatically correct sentence:
 +
 +
:"Colorless green ideas sleep furiously."
 +
 +
:This example illustrates the difference between grammar/syntax and meaning/semantics.
 +
 +
Another problem when analysing a sentence is that many English words have multiple meanings, so that there may be more than one way to interpret a sentence. A simple example is the sentence:
 +
:"Time flies."
 +
:Is this an instruction to check how fast flies are flying, or an indication that time appears to be passing quickly?
 +
:A varied and entertaining selection of such ambiguities has been compiled by Jeff Gray.<ref>{{Cite web
 +
| title = Collection of Ambiguous or Inconsistent/Incomplete Statements 
 +
| url = http://www.gray-area.org/Research/Ambig/
 +
| author = Jeff Gray
 +
| accessdate = 2012-04-10
 +
}}</ref>
 +
 +
==Formal definition==
 
A '''Context-Free''' Grammar is a tuple (T, V, S, P);
 
A '''Context-Free''' Grammar is a tuple (T, V, S, P);
 
T is a set of atomic symbols.
 
T is a set of atomic symbols.
Line 7: Line 102:
 
P is a set of productions, each production describes how to produce a variable using a sequence of tokens and variables.
 
P is a set of productions, each production describes how to produce a variable using a sequence of tokens and variables.
  
 +
==Examples==
 
For example, a Context-Free Grammar for the real numbers would be:
 
For example, a Context-Free Grammar for the real numbers would be:
 
:T = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, .}
 
:T = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, .}
Line 25: Line 121:
 
::real-number → part . part
 
::real-number → part . part
 
:}
 
:}
 +
 +
==References==
 +
{{reflist}}
 +
  
 
[[category:linguistics]]
 
[[category:linguistics]]
 
[[Category:Computer Science]]
 
[[Category:Computer Science]]

Revision as of 20:07, May 14, 2012

An equivalent grammar Backus-Naur Form is often used for describing the syntax/grammar of programming languages.

A context-free grammar is a formal grammatical system for describing a particular class of language. The basic idea of such a generative grammar is to provide a set of rules which can be used to generate all possible grammatical 'sentences'; these rules must also avoid generating any ungrammatical sentences. A context-free grammar is not powerful enough to describe a natural language such as English, but it is powerful enough to describe nearly all programming languages.

A context-free grammar is the level 2 grammar in the Chomsky hierarchy and was first described in 1956 by the linguist Chomsky. [1]

Example of a very simple context-free grammar

This very simple example can handle only a tiny subset of English and should not be taken seriously as a guide to English grammar or vocabulary. It is based on an example by David Crystal [2] and is a slight extension of an example on slide 9 of this lecture. [3] 

Sentence   ->  NounPhrase VerbPhrase         # A Sentence consists of a NounPhrase followed by a VerbPhrase
NounPhrase ->  Determiner Noun               # A NounPhrase consists of a Determiner followed by a Noun
VerbPhrase ->  Verb NounPhrase               # A VerbPhrase consists of a Verb followed by a NounPhrase
Determiner ->  a, the                        # A Determiner  is one of: a or the
Noun       ->  boy, girl, dog                # A Noun is one of: boy or girl or dog  
Verb       ->  chased, heard, saw            # A Verb is one of: chased or heard or saw

Notation used above:

The symbol "->" means "can be replaced by".
When there are several items on the right hand side separated by commas, just one of these items can be selected.
The comments preceded by "#" are not part of the generative grammar, but hopefully will help folks understand the example a little better.

By making appropriate substitutions we can generate such sentences as:

The dog chased a girl.
The girl heard the dog.
The boy saw a girl.

The stages in the generation of these examples are as follows:

Sentence
-> NounPhrase VerbPhrase
-> Determiner Noun Verb NounPhrase
-> Determiner Noun Verb Determiner Noun

By appropriate selection of words to substitute for Determiner, Noun, and Verb we can produce the 3 example sentences above.

The simple grammar defines a few words which can be substituted for Determiner, Noun, and Verb. There are two possibilities for Determiner, three for Noun, and three for Verb, with both Determiner and Noun appearing twice in the expansion. Hence the total number of grammatical sentences which can be generated by this simple grammar is 108 (= 2 * 3 * 3 * 2 * 3). In this particular case the possible words have been carefully chosen so that all of these 108 sentences also actually mean something.

Note that the use of italics and boldface in this example is merely a convenient way of indicating the difference between items which can be expanded further (e.g. concepts such as NounPhrase) and items which can not be expanded further (e.g. words such as girl). In the linguistic literature, items which can be expanded further are referred to as 'non-terminal' items, while items which can't be expanded further are known as 'terminal' items.

The 'comma' notation for alternatives is a form of shorthand. In some formulations this would be shown as several separate rules, so that: 

  Determiner ->  a, the

could be shown as two rules: 

  Determiner ->  a
  Determiner ->  the

Caution

While a generative grammar may produce sentences which are grammatically correct, there is no certainty that such sentences will actually mean anything. The classic example of such a meaningless sentence is from Chomsky's book [4] with the grammatically correct sentence:

"Colorless green ideas sleep furiously."
This example illustrates the difference between grammar/syntax and meaning/semantics.

Another problem when analysing a sentence is that many English words have multiple meanings, so that there may be more than one way to interpret a sentence. A simple example is the sentence:

"Time flies."
Is this an instruction to check how fast flies are flying, or an indication that time appears to be passing quickly?
A varied and entertaining selection of such ambiguities has been compiled by Jeff Gray.[5]

Formal definition

A Context-Free Grammar is a tuple (T, V, S, P); T is a set of atomic symbols. V is a set of variables. S is a special start symbol. P is a set of productions, each production describes how to produce a variable using a sequence of tokens and variables.

Examples

For example, a Context-Free Grammar for the real numbers would be:

T = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, .}
V = {real-number, part, digit}
S = real-number
P = { digit → 0
digit → 1
digit → 2
digit → 3
digit → 4
digit → 5
digit → 6
digit → 7
digit → 8
digit → 9
part → digit
part → digit part
real-number → part . part
}

References

  1. ↑ Chomsky, Noam (1956). "Three models for the description of language". IRE Transactions on Information Theory 2: 113–124. http://www.chomsky.info/articles/195609--.pdf. Retrieved 2012-04-08. 
  2. ↑ Crystal, David (1987). The Cambridge Encyclopedia of Language. Cambridge University Press, page 97. ISBN 0-521-42443-7. 
  3. ↑ Lecture notes: Formal Languages. Retrieved on 2012-04-07.
  4. ↑ Chomsky, Noam (1957). Syntactic Structures. The Hague/Paris: Mouton, page 15. ISBN 3-11-017279-8. 
  5. ↑ Jeff Gray. Collection of Ambiguous or Inconsistent/Incomplete Statements. Retrieved on 2012-04-10.
Retrieved from "https://www.conservapedia.com/index.php?title=Context-free_grammar&oldid=981371"