Scribd
Upload
6 views11 pages

Module3 Lecture1 ContextFreeGrammar

Context Free Grammar (CFG) is a formal grammar used to generate strings in a formal language, defined by four tuples: V (non-terminal symbols), T (terminal symbols), P (production rules), and S (start symbol). CFG specifies how a sentence can be derived from a distinguished symbol through a set of productions, which can be interpreted as rewrite rules. Parsing techniques, such as top-down and bottom-up parsing, are used to determine how sentences can be generated from the grammar.

Uploaded by

Sachin Kumar N
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views11 pages

Module3 Lecture1 ContextFreeGrammar

Context Free Grammar (CFG) is a formal grammar used to generate strings in a formal language, defined by four tuples: V (non-terminal symbols), T (terminal symbols), P (production rules), and S (start symbol). CFG specifies how a sentence can be derived from a distinguished symbol through a set of productions, which can be interpreted as rewrite rules. Parsing techniques, such as top-down and bottom-up parsing, are used to determine how sentences can be generated from the grammar.

Uploaded by

Sachin Kumar N
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Context Free Grammar

Context Free Grammars

 Context free grammar is a formal grammar which is used to


generate all possible strings in a given formal language.
 Context free grammar G can be defined by four tuples as:
G= (V, T, P, S)
 Where,
 G describes the grammar
 T describes a finite set of terminal symbols.
 V describes a finite set of non-terminal symbols
 P describes a set of production rules
 S is the start symbol.
Context Free Grammars

 A context-free grammar (CFG) is a formal system that describes a


language by specifying how any legal text can be derived from a
distinguished symbol called the axiom, or sentence symbol.

 It consists of a set of productions, each of which states that a given


symbol can be replaced by a given sequence of symbols.

 An alternative shorter explanation of CFG is that CFG specifies


rewrite rules for how a symbol can be replaced by a series of
symbols and words.

 Parsing tries to determine how a sentence can be generated from a


grammar.
Context Free Grammars
Components of a Natural Language: Types of Words

Content Words: Identifies a part Function Words: Glues words,


of the world phrases together

 Nouns: person, place, or thing  Determiners: indicate specific


(child, room, hammer) object (a, the, that)

 Adjectives: properties of objects  Quantifiers: how many are


(tall, dark, pretty) identified (all, some, none)

 Verbs: actions, relationships  Prepositions: relates phrases


(edit, load, debug, link) (at, on, of, about)

 Adverbs: properties of verbs  Connectives: connect words,


(slowly, frequently, nally) phrases (and, but, when)
Lexicon for a language, say, L0 (ATS)
Grammar for L0
Context Free Grammars
SMC Example: Sue, mouse & the cat

Parse tree 1 (Parse tree is also known as derivation tree) Parse tree 2
Context Free Grammars
SMC Example: Top-down parsing (A)

 Top-down parsing starts with the S symbol and


tries to rewrite it into the sentence.
Context Free Grammars
SMC Example: Bottom-up parsing (A)

 Bottom-up parsing starts with the words and


tries to find symbols that generate them.
Context Free Grammars
SMC Example: Top-down parsing (B) - using parse tree
Context Free Grammars
SMC Example: Bottom-up parsing (B) - using parse tree

You might also like