Trim Reductions Feature

Description

The "Trim Reductions" feature is designed to simplify the parse tree by removing unneeded reductions. In particular, reductions which contain a single nonterminal can be eliminated from the tree without changing its meaning.

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.

This feature is particularly useful if the parse tree is going to be analyzed based on its "content" rather than the structure of the language.

Essentially, "Trim Reductions" will affect those rules with the following format:

Example

The behavior of 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, the system will produce the following 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 "Trim Reductions", 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 can be performed 'behind-the-scene' and made invisible to the developer.

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.