CS 241 - CFG-R (reversed rightmost) File Format (.cfg-r)

A .cfg-r file is a text file representing a context-free grammar followed by several (zero or more) abbreviated reversed right canonical derivations. The format differs from the CFG file format only in that it uses unindented reversed rightmost derivation format.

Context-free Grammar Representation

The context-free grammar representation has four components, in order:

Abbreviated Reversed Right Canonical Derivation(s)

Zero or more derivations immediately follow the context-free grammar. Each derivation is a representation of the parse tree, with each node in the tree represented by a line in the file containing a production rule. (In contrast to the derivations in CFG files, these lines do not begin with any spaces.)

The order and indentation of the lines in the file are defined by the following recursive rules:

Example .cfg-r file (sample.cfg-r)

6
)
(
EOF
BOF
id
-
3
term
S
expr
S
5
term id
term ( expr )
S BOF expr EOF
expr expr - term
expr term
term id
expr term
term id
expr term
term ( expr )
expr expr - term
term id
expr expr - term
S BOF expr EOF