Introduction

Construction of parsing tables using CYK (Cocke–Younger–Kasami) algorithm for CNF grammars.

Supported grammars

  • A -> A c | A a d | b d | ϵ
    (All tokens must be separated by space characters)
  • A -> A c
       | A a d
       | b d
       | ϵ
  • S -> A a | b
    A -> A c | S d | ϵ
  • (Copy ϵ to input if needed)

Example

  • Grammar:
    S -> A B | B C
    A -> B A | a
    B -> C C | b
    C -> A B | a
  • Input: b b a b a a