pLERO is the pattern Language of Extended Refactoring Operators. Through pLERO it is possible to define patterns for grammar refactoring or other transformations, applicable to grammars expressed in BNF. That is, pLERO is a language for defining parameterless operators of a problem class.

Pattern description consists of a set of transformation rules, while each rule comprises predicate describing the shape of a grammar's production rules, and transformation defining how production rules matched against predicate should be changed.

Predicate and transformation are expressed in similar fashion by formalism of meta-production rules. Each meta-production rule defines structure of some subset of a grammar's production rules. Predicate is specified by exactly one meta-production rule matched against grammar's production rules, while transformation is described by set of meta-production rules defining shape of production rules to be included in grammar during refactoring process.

Each meta-production rule can be divided in two parts, namely, left side of meta-production rule and right side of meta-production rule. Left side of meta-production rule specifies nonterminal on the left side of a grammar's production rule, while right side of meta-production rule specifies sequence of symbols that can be found on the right side of a grammar's production rules. Left side of meta-production rule is some pattern variable, while right side of meta-production rule is concatenation of pattern variables.

Pattern variable specifies homogenous sequence of symbols in a grammar's production rules, consisting of variable prefix and name. Variable prefix describes possible matched symbols and their number, while variable name is identifier of this sequence. The prefix can be t for terminals, n for nonterminals, and s for both terminals and nonterminals. The letter specifying the symbol type can be followed by the asterisk * denoting the variable can match a sequence of symbols instead of a single symbol. For instance, the most generic variable type has prefix s* that can match any sequence of symbols. Variable prefix and name are separated by dot ”.”. After the dot, the variable name follows, e.g. s*.symbols.

Pattern variable on the left side of meta-production rule may only have prefix n not followed by asterisk, denoting exactly one nonterminal. Each pattern variable on the right side of meta-production rule can have arbitrary valid prefix.

Each specification of refactoring pattern in pLERO must comply with the same template which allows specification of global pattern variables denoting same symbol sequences in all transformation rules of a pattern during entire refactoring process.

pattern [pattern_name] {
    variables:
        [prefix1 ].[variable_name1 ],
        [prefix2 ].[variable_name2 ],
        ...
        [prefixn ].[variable_namen ];
    new symbols:
        [prefixI ].[variable_nameI ],
        [prefixII ].[variable_nameII ],
        ...
        [prefixN ].[variable_nameN ];
    [transformation_rule1 ];
    [transformation_rule2 ];
    ...
    [transformation_rulen ];
}

The template also enables to specify new nonterminal symbols, which need to be generated for the use in production of new production rules. Notion of individual transformation rules must also follow specific template:

predicate -> transformation

While variables may consist of all the possible prefixes, new variables may not; more specifically they cannot consist of partially deterministic constructs such as * or s, and in current version of pLERO only n is allowed. Reason for this is that these constructs do not specify unambiguous concatenation of symbols and though it is not possible to generate definite sequence of symbols on their basis. Moreover new variables may be used only in meta-production rules contained within transformation part of transformation rule, and their use in predicate is prohibited. Reason for this is that new variables correspond with sequences of symbols that occur only in refactored grammar, and not in the original grammar.

In order to apply transformation provided by refactoring pattern on some context-free grammar it is first necessary to match this grammar against this pattern. Process of pattern matching has two purposes:

• Determining if a grammar is transformable by a pattern
• Determining which pattern variable represents which sequence of symbols within production rules of a grammar

To each assignment of specific sequence of symbols to particular pattern variable we refer as to variable binding and to each variable representing definite sequence of symbols we refer as to bound variable.

Variables are bound during the matching of the rule and used in the replacement construction process. Global variables keep their value after they are bound during the first successful match. Other variables (to which we refer as to local variables) are bound only during the application of a rule and cleaned before the next matching.

The matching of a predicate against a grammar production is successful if all the pattern variables can be bound to a part of the production and no unmatched symbols are left. Variables can match only some type of symbols, based on their prefix. Simple variables must match exactly one symbol of a specified type, while sequence variables can match any number of symbols (including zero).

For instance, the predicate n.1 ::= n.2 s*.1 t.1 would match production A ::= B 'c' 'd' 'e' , resulting in bindings n.1 = A, n.2 = B, s*. = ” 'c' 'd' , t.1 = 'e' , and also B ::= D 'f' , n.1 = B, n.2 = D, s*. is empty, t.1 = 'f' . Since it does not start with a nonterminal, it would not match C ::= 'd' 'e' 'f' .

If the pattern n.1 ::= s*.1 n.2 s*.2 is matched against the production A ::= B C D, the resulting binding would be n.1 = A, s*.1 is empty, n.2 = B, and s*.2 = C D.

The matching of sequences is non-greedy. This means that short sequences are performed first during the matching. The process continues while the entire production is matched.

However, there are some cases in which conflicts in matching of predicate against production can arise, e.g. conflict always occurs if predicate contains two consecutive sequences of arbitrary symbols (s*.A s*.B). In this case, we have adopted first-match found resolution strategy.

Each transformation rule of refactoring pattern describes structure of some production rules and specifies new production rules that should replace this production rule. Predicate is a concatenation of pattern variables, which can match a sequence of production rule symbols and then represent these symbols in the transformation.

If a variable of the same type and name is present in a transformation rule, it will represent the same sequence of symbols in all its occurrences. In the transformation, meta-production rules have to consist only of the variables occurring on the predicate side of the transformation rule or in global variables. After the predicate matches any grammar production, its variables are bound to parts of the production and the replacement productions are constructed on the basis of transformation patterns.

If applied to a grammar, all transformation rules of a pattern are traversed in the order of their specification. Predicate is then matched against all the unprocessed productions of the original grammar. If the match is successful, replacement production is constructed and the production is replaced in the grammar.

Order of specification of transformation rules within a pattern is important, for it serves as conflict resolution mechanism in case when there are multiple predicates that can be matched against one production rule.