|
|
|
|
|
|
 |
 |
|
Recognition and Parsing of Context-free Grammars
|
|
|
|
|
|
| Organization: | Universidad Autonoma de Querétaro |
| Department: | Facultad de Informatica |
|
|
|
|
|
|
0210-665
|
|
|
|
|
|
2000-03-31
|
|
|
|
|
|
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.
|
|
|
|
|
|
|
|
|
|
|
|
Context-free grammars, Chomsky Normal Form, CKY algorithm, Early Algorithm, Parsing
|
|
|
 |
|
|
| CFG.nb (56.9 KB) - Mathematica Notebook |
|
|
|
|
|
|
|
| | | | | |
|
For the newest resources, visit Wolfram Repositories and Archives »
