O'Reilly logo

Compilers: Principles and Practice by Himanshu B. Dave, Parag H. Dave

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

A.5 Context-free Languages, CFG and Push-down Automata

Context-free Languages (CFL) have structures which cannot be specified by regular expressions. Most of the computer programming languages are of this type. The grammar which can specify a CFL is called Context-free Grammar (CFG) and acceptor for such a language is called Push-down Automata (PDA).

A.5.1 Context-free Language

We consider first an example:

Palindrome language PAL over ∑ = {a, b} can be defined as:

  1. λ, a, bPAL
  2. SPAL, aSa, bSbPAL
  3. no other string in PAL unless it can be obtained by applying (1) and (2).

Typical strings in PAL are: a, b, aa, bb, aaa, aba, bab, image,…

We can ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required