Mathematica 9 is now available

Wolfram Library Archive

All Collections Articles Books Conference Proceedings
Courseware Demos MathSource Technical Notes
Title Downloads

Recognition and Parsing of Context-free Grammars

Jaime Rangel-Mondragón
Organization: Universidad Autonoma de Querétaro
Department: Facultad de Informatica
Old MathSource #

Revision date


The aim of this work is to provide functions to manipulate the language generated by a given context-free grammar and solve the problem of recognition, i.e., to find out whether a given word w is an element of the language generated by a CFG, and the problem of parsing a word that has been recognised, i.e., to find the actual chain of derivations giving rise to w.

The work is divided into three parts. The first part comprises functions that allow us to input a CFG using its Backus-Naur form and generate all bounded derivations of a given word. The second part develops the Cocke-Kasami-Younger algorithm requiring grammars in Chomsky normal form. The third part follows Michael Harrison´s version of Earley´s algorithm to recognize and obtain the right parsing of words on arbitrary CFG.

Examples follow each of the functions comprising this work.

*Applied Mathematics > Computer Science

Context-free grammars, Chomsky Normal Form, CKY algorithm, Early Algorithm, Parsing
Downloads Download Wolfram CDF Player

CFG.nb (56.9 KB) - Mathematica Notebook