Context-free grammars

Context-free grammars

For access to this article, please select a purchase option:

Buy chapter PDF
(plus tax if applicable)
Buy Knowledge Pack
10 chapters for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
Handbook of Mathematical Models for Languages and Computation — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Context-free grammars represent language-generating rewriting systems. Each of their rewriting rules has a single symbol on its left-hand sides. By repeatedly applying these rules, these grammars generate sentences of their languages. This chapter gives a mathematical introduction into context-free grammars. First, Section 6.1 defines their basic versions. Then, Section 6.2 presents several mathematical methods that transform the basic versions so that the transformed versions are as powerful as the original versions but are much easier to handle in theory as well as in practice.

Chapter Contents:

  • 6.1 Mathematical elements of context-free grammars
  • 6.2 Canonical derivations and derivation trees
  • 6.2.1 Leftmost derivations
  • 6.2.2 Rightmost derivations
  • 6.2.3 Derivation trees
  • 6.2.4 Ambiguity
  • 6.3 Useless symbols and their elimination
  • 6.4 Erasing rules and their elimination
  • 6.5 Single rules and their elimination
  • 6.6 Chomsky normal form
  • 6.7 Left recursion and its removal
  • 6.7.1 Direct left recursion and its elimination
  • 6.7.2 Left recursion and its elimination
  • 6.7.3 Right recursion
  • 6.8 Greibach normal form

Inspec keywords: context-free grammars; rewriting systems

Other keywords: rewriting rules; language-generating rewriting systems; context-free grammars

Subjects: Formal languages and computational linguistics

Preview this chapter:
Zoom in

Context-free grammars, Page 1 of 2

| /docserver/preview/fulltext/books/pc/pbpc026e/PBPC026E_ch6-1.gif /docserver/preview/fulltext/books/pc/pbpc026e/PBPC026E_ch6-2.gif

Related content

This is a required field
Please enter a valid email address