Charty in Scheme / Racket
© 2005-2012 by Damir Cavar

Charty in Scheme was initially developed back in 2006 for the ESSLLI course on programming in Scheme. I used it in many classes and courses later on. Back then I used PLT-Scheme. The current version is written in Racket 5.x.

Check out the Racket version with GUI on the SNLTK pages.

It is an implementation of an Early Parser, using an agenda for ambiguous paths, and it is tracking parses for the generation of trees or bracketed analyses of structurally ambiguous sentences. Charty is meant to be embedded, meaning, there is no specific GUI or front-end to it. (There is a GUI front-end, and it might be soon published here).

Charty reads context-free grammars (CFGs) without restrictions on the right-hand side, i.e. the left-hand side is restricted to one symbol only, while the right-hand side can be any combination of symbols or terminals. The grammars can of course contain recursion.

Charty is published under the GNU Lesser General Public License Version 3.

Racket Scheme code Files:
Example grammars:

How to use

I assume that you have the current version of Racket installed on your computer. Check the version by issuing the command

racket -v

in a command-line interface (assuming you are using on Mac OS X, or the Terminal on Linux).

Place the code files in some folder together with the grammars.

The grammar file is a plain text file. It can be edited with any plain text editor, e.g. Notepad or Notepad++ on Microsoft Windows, jEdit, Vim or Emacs (Aquamacs) on Mac OS X or Linux systems. The grammar files are expected to be encoded in UTF-8. The line ending is irrelevant, i.e. it can be a Windows or a Unix one. The rules are simple CFG rules with one left-hand side symbol, and any combination of symbols and terminals in the right-hand side:

NP -> Art Adj N

The file can contain comments that are introduced with a #, as in the following two lines:

# Grammar:
S -> NP VP # simple sentence rule

The simple grammar parser does not support markup for optionality, using round brackets for example, neither regular expression operators. The symbols can contain all symbols except of #, = or >. Symbols cannot start with -, but they can contain -, so the following symbols are permitted:


Rules contain a left-hand side and a right-hand side. The separating character sequence can be:


as well as similar combinations of minus or equal characters followed by a larger character.

You can define your own rules and experiment with the grammar. The grammars could be phrase structure rules as the examples above, or grammars of the following type, for example right linear grammars:

X -> a Y
Y -> b
Y -> b Z
Z -> a Y

The Charty script accepts several parameters. The parameter -h explains some of them briefly. Try the following commands in the command line tool:

./charty.rkt -h


racket ./charty.rkt -h

You can make the charty.rkt script executable with this command:

chmod +c charty.rkt

Obligatory parameters are:




An example call of the parser might look like this:

./charty.rkt -g PSG1.txt -s “John loves Mary”

Important is to surround the input sentence with double quotes, as shown in the command above.

Optional parameters are:

-v or --verbose for the verbose mode, i.e. the chart and the individual edge-formation steps are printed to the screen. The default is, the parser does not print out any edge formation steps or the final chart.

-l or --latex to return the Qtree style Tree syntax for LaTeX typesetting (see also). The -l or --latex flag will be added in the next script release!

Using the example grammars of the package, the command line parameters and the corresponding output are:

./charty.rkt -g psg2.txt -s "a b" -l

Parse: 1 of 2
\Tree [.X a [.Y b ] ]
Parse: 2 of 2
\Tree [.Z a [.Y b ] ]

./charty.rkt -g PSG1.txt -s "John loves Mary"

Parse 1: (S (NP (N John)) (VP (V loves) (NP (N Mary))))

./charty.rkt -g PSG1.txt -i "John loves Mary" -v

Init new edge: (0 1 1 N (John) ())
Init new edge: (1 2 1 V (loves) ())
Init new edge: (2 3 1 N (Mary) ())
RI new edge: (0 1 1 NP (N) (0))
RI new edge: (1 2 1 VP (V NP) (1))
RI new edge: (1 2 1 VP (V) (1))
RI new edge: (1 2 1 VP (V PP) (1))
RI new edge: (1 2 1 VP (V NP PP) (1))
RI new edge: (2 3 1 NP (N) (2))
FR new edge: (1 3 2 VP (V NP) (1 8))
FR new edge: (1 3 2 VP (V NP PP) (1 8))
RI new edge: (0 1 1 S (NP VP) (3))
RI new edge: (0 1 1 NP (NP N) (3))
RI new edge: (2 3 1 S (NP VP) (8))
RI new edge: (2 3 1 NP (NP N) (8))
FR new edge: (0 2 2 S (NP VP) (3 5))
FR new edge: (0 3 2 S (NP VP) (3 9))
Parse 1: (S (NP (N John)) (VP (V loves) (NP (N Mary))))

./charty.rkt -g PSG1.txt -s "she killed the man with the tie"

Parse 1: (S (NP (N she)) (VP (V killed) (NP (Art the) (N man) (PP (P with) (NP (Art the) (N tie))))))
Parse 2: (S (NP (N she)) (VP (V killed) (NP (Art the) (N man)) (PP (P with) (NP (Art the) (N tie)))))

The last two trees can be visualized with LaTeX and Qtree (see instructions about how to use LatexIt on Mac OS X for that):

Parse: 1 of 2
Parse: 2 of 2