Skip to content
/ CYK Public

Validator for context free grammars that returns the resulting cyk table as LaTeX after bringing it into Chomsky normal form.

Notifications You must be signed in to change notification settings

lupeterm/CYK

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Context-Free Grammar Interpreter

This package takes a CF grammar $G$ and a word $w$ as an input, transforms $G$ into Chomsky normal form and performs the Cocke-Younger-Kasami-algorithm (CYK) to evaluate whether the word can be created by the grammar or not.

Table of Contents

  • Requirements
  • Usage
  • Example

Usage

  1. Requirements

    • Windows user (my condolences) need to download and install miktex.
  2. Installation

    • Inside a virtual environment, simply run pip install -e ..
  3. Execute Program

    • Call the module directly via cyk. Run with --help to see available options.
  4. Enter Grammar

    • Enter the members of the grammar in order with following syntax:
Member Syntax/Input Output
Symbols $S, B, C...$ ${S, B, C}$
Terminal Symbols $a, b, c...$ ${a, b, c}$
Rules per Symbol (e.g. $S$) $B, a$, \E ${S \to B \ | \ a \ | \ \varepsilon \ | \ ...}$
Starting Symbol $S$ $S$
  • The grammar may also be entered through an external file with following regulations:
Empty lines in the file will be ignored.
Order of lines Grammar member Rules Example
1 Symbols upper case letters S, A, B
2 Terminal Symbols lower case letters a, b
3 Starting Symbol part of symbols S
4 to x Rules per Symbol first character of the line is the symbol S -> AB, AA
4 to x Rules per Symbol '->' may be inserted for better clarity A -> BA; a
4 to x Rules per Symbol applying rules are stated after the symbol B -> b
Notice that the notation for epsilon is \E. 
Also note that the LaTeX table will go out of bound for long words. 
  1. Enter Word

    → Enter the word, nothing fancy to it.

  2. Open PDF

    → Open the .pdf file using evince or your favourite pdf viewer.

Example

  • Input:

  • Grammar in CNF:

  • Finished CYK-Table of $w = aaccca$:

Next Steps:

  • implement elimination of starting symbol from right sides. ✔️
  • implement a desktop UI (because why not)
  • maybe implement picture/screenshot input support?
  • create PD automata from new rules and visualize it

About

Validator for context free grammars that returns the resulting cyk table as LaTeX after bringing it into Chomsky normal form.

Topics

Resources

Stars

Watchers

Forks

Packages

No packages published

Languages