Skip to content
grammarware edited this page Jan 19, 2013 · 5 revisions

The grammar is rewritten by local transformations such that the language generated by the grammar (or the denotation according to any other semantics for that matter) is preserved. The known rewriting rules affect the use of selectors and regular expression operators: e.g., any symbol will always generate the same set of strings that the same symbol wrapped in a selector.

There are two expression arguments: one to be matched, and another one that replaces the matched expression. One of them must be in a “massage-equality relation” to the other.

The scope of the transformation can be limited.

Syntax

massage:
        expression expression in::scope?

If (x, y) represents sequential composition of symbols x and y, and (x; y) represents a choice with x and y as alternatives, then the following algebraic laws define the massage- equality relation:

![massage-equality](https://github.com/grammarware/slps/raw/master/topics/documents/wiki/massage-laws.png)

Associativity rules for massage:

![associativity](https://github.com/grammarware/slps/raw/master/topics/documents/wiki/associativity.png)

Example

Distributivity rules for optionality modifier such as these:

![distributivity](https://github.com/grammarware/slps/raw/master/topics/documents/wiki/distributivity.png)

are not explicitly covered by massage since it is possible to emulate them with a sequence of abovementioned patterns of massage, as well as with factor and similar transformations. Let us take the last formula as an example of a massaging that takes several steps to complete. The input BGF is:

foo:
        (bar | qux)?

After performing these transformation steps:

massage(
 (bar | qux)?,
 ((bar | qux) | ε));
massage(
 ε,
 (bar::ε | qux::ε));
factor(
 ((bar | qux) | (bar::ε | qux::ε)),
 ((bar | bar::ε) | (qux | qux::ε)));
anonymize(
 foo:
        (bar | <bar::ε>)
        (qux | qux::ε)
);
massage(
 (bar | ε),
 bar?);
anonymize(
 foo:
        bar?
        (qux | <qux::ε>)
);
massage(
 (qux | ε),
 qux?);

The result will be:

foo:
        bar?
        qux?

The selectors and anonymize commands are necessary because otherwise the choice of two epsilons would be removed automatically during the normalisation phase. The rest of distributivity laws are expressed quite similarly to this example.

Relevant files

See also

  • Massage is a part of XBGF

Contributors

Clone this wiki locally