In parsing theory, what is the opposite of “derive”?

Question

Suppose you have a grammar such as this:

S → A

A → E "=" E

In this example, S derives the sequence (E "=" E). However, what is the opposite of this? That is, what is an appropriate word to fill in the blank:

"The sequence (E "=" E) ______ S."

If we were to borrow the antonym from calculus, one could say that (E "=" E) integrates S, but that doesn't seem right.

Answer 1

I don't believe that there is, strictly speaking, such an antonym. Instead, they are both referred to as derivation. More specifically, what you describe in the question is called "top-down" parsing, whereas the reverse is known as "bottom-up" parsing.

In contrast to top-down parsing, wherein parsing begins from the start symbol and applies derivations until the entire input string is determined, bottom-up parsing starts from the input string and uses derivations in the opposite direction, stopping when it ultimately derives the starting symbol.

Also see: http://lambda.uta.edu/cse5317/notes/node12.html

However, I have seen the opposite of derivation referred to as reduction. Perhaps that's the term that you were thinking of?

(So maybe that formal logic course I took in college was finally good for something after all?)