Feature Unification

Features are simply name,value pairs of alphanumeric strings, which are properties of a grammar symbol. In the grammar, feature list (or vector) is represented as "[" (name "=" value)("," name "=" value)* "]"

e.g. [case=acc,pers=1,numb=plur]

Consider a sample grammar where each production has an associated feature:

A -> a  [cnt=1]
A -> aa [cnt=2]
B -> b  [cnt=1]
B -> bb [cnt=2]

If we define start production as:

S -> A B

The following inputs are recogized correctly:

a b
aa bb

while the following inputs cannot be recogized, as features [cnt=1] and [cnt=2] cannot be unified:

a bb
aa b

Features are propaged bottom-up, so the symbol S also acquires the feature "cnt". The parse tree for input "a b" would be:

S(
#1[cnt=1]
    A(
    #2[cnt=1]
        a
    )
    B(
    #4[cnt=1]
        b
    )
)

In order to disable propagation of these features we can add empty parameters to one or both symbol:

S -> A() B()

In this scenario, features of A and B are not propagated into S, i.e. S has an empty feature list [], and all following inputs are recognized:

a b
aa bb
a bb
aa b

It is also possible top have selective propagation of some features:

S -> A(cnt) B
A -> a  [cnt=1,type=a]
A -> aa [cnt=2,type=a]
B -> b  [cnt=1,type=b]
B -> bb [cnt=2,type=b]

In this scenario, only feature "cnt" is propagated from A into S, but not "type", otherwise A would not unify with B. It can recognize the following inputs:

a b
aa bb

The parse tree for input "a b" would be:

S(
#1[cnt=1,type=b]
    A(
    #2[cnt=1,type=a]
        a
    )
    B(
    #4[cnt=1,type=b]
        b
    )
)

Sometimes we want only symbols with specific features, which is feature enforcement:

S -> X(type=a,cnt) X(type=b,cnt)
X -> a  [cnt=1,type=a]
X -> aa [cnt=2,type=a]
X -> b  [cnt=1,type=b]
X -> bb [cnt=2,type=b]

again recognizes the following inputs:

a b
aa bb

The parse tree for input "a b" would be:

S(
#1[cnt=1]
    X(
    #2[cnt=1,type=a]
        a
    )
    X(
    #4[cnt=1,type=b]
        b
    )
)

In summary, there are following kinds of bottom-up feature propagation:

1. Unrestricted Propagation: S -> A B

2. No Propagation: S -> A() B

3. Selective Propagation: S ->A(cnt,type) B

4. Enforcement: S -> A(cnt=1,type=a) B

5. Combined: S -> A(cnt,type=a) B