CFG File Format (.cfg) CS 444, Winter
A .cfg file is a text file representing a context-free grammar.
The grammar must be augmented in the following sense:
there must be exactly one production rule expanding the start symbol,
and the right-hand-side of the rule must contain three symbols: a
beginning-of-input terminal symbol followed by a non-terminal symbol
followed by an end-of-input terminal symbol. The beginning-of-input
and end-of-input terminal symbols must not appear in any other rule.
Context-free Grammar Representation
The context-free grammar representation has four components, in order:
- t, a positive integer giving the number of terminal symbols in the grammar, followed
by t lines, each containing the name of a distinct terminal symbol. Each terminal symbol may
be any string of one or more printable ascii characters, excluding white space.
- n, a positive integer giving the number of nonterminal symbols in the grammar, followed
by n lines, each containing the name of a distinct nonterminal symbol. Each nonterminal
symbol may be any string of one or more printable ascii characters, and must not be the same as any terminal symbol.
- A single line giving the name of the start symbol, which must be one of the nonterminal symbols
- r, a positive integer giving the number of production rules in the grammar, followed by r lines, each denoting a rule consisting of:
- The left-hand-side (LHS) of the rule; a nonterminal symbol
- The right-hand-side (RHS) of the rule; zero or more terminal
or nonterminal symbols separated from each other, and from the LHS by a
S BOF expr EOF
expr expr - term
term ( expr )