TrimReductions Property

Applies To

History

This feature was added in version 1.0 Beta 20 of the GOLD Parser Engine.

Description

The TrimReductions property is used to indicate whether the GOLD Engine will automatically remove unneeded reductions from the parse tree.

Although each rule is necessary to define the grammar, not all rules contain terminal symbols. As a result, when the system creates a reduction for that rule, it does not contain any of the actual data being parsed. In some cases, this reduction is not needed in the parse tree since it only represents a single point on a branch. In particular, reductions which contain a single nonterminal can be eliminated from the tree without changing its meaning.

When the TrimReductions property is set to True, those rules with the following format will be automatically trimmed from the parse tree.

The behavior of the TrimReductions property can best be demonstrated with a simple example. For this example, the following grammar will be used:

"Start Symbol" = <Expression>

ID = {Letter}{AlphaNumeric}*

<Expression> ::= <Mult Exp> '+' <Expression>
               | <Mult Exp> '-' <Expression>
               | <Mult Exp>

<Mult Exp>   ::= <Negate Exp> '*' <Mult Exp>
               | <Negate Exp> '/' <Mult Exp>
               | <Negate Exp>

<Negate Exp> ::= '-' <Value>
               | <Value>

<Value>      ::= ID
               | '(' <Expression> ')'

This grammar defines the operator precedence used in most programming languages for arithmetic.

If the source text

a + b * c

is parsed by the system with the TrimReductions property set to False, the parser will produce the following parse tree. The tree represents the source text broken down precisely using the grammar's rules.

For many grammars, such as those with a large number of operator precedence levels, the parse tree can quickly become complex.

With the TrimReductions property set to True, the system will eliminate reductions where the rule contains a single nonterminal.

In the chart on the right, the highlighted reductions will be trimmed from the parse tree.

This is performed 'behind-the-scene' and is invisible to the developer. The gpMsgReduction message will not generated for these trimmed reductions.

The resulting parse tree will contain far fewer reductions, but will not match the grammar verbatim.

For instance, the <Mult Exp> rule contains the nonterminals <Negate Exp> and <Mult Exp>, but the reduction itself contains two <Value> rules instead.

Depending on how you plan to write your compiler or interpreter, it is important to keep this in mind.