Say we have some BNF rules for example:

$$A ::= B C$$ $$Dx ::= ExFx$$ $$x ::= y$$

So we might start with $Dx$ and apply rule 2 to get $Ex Fx$ and then apply rule 3 to get $Ey Fy$. But starting with $Dy$ we can't get anything. Unless...

What if we extend the BNF rules to let the rules apply to other rules. Then we could take rule 3 and apply it to rule 2 (interpreted as a string) to get a new rule:

$$Dy ::= EyFy$$

My question is, if we allow such creation of new rules like this. What kind of grammar do we end up with? What is the name of it? Is it equivalent to church lambda calculus?

Using these rules we could express the grammar where the quantity matches the noun and determiner like this:

$$amount ::= singular|plural \\ NP(amount) ::= det(amount)\ \ noun(amount) \\ det(singular) ::= a | one \\ det(plural) ::= some | two | three \\ noun(singular) ::= cat | dog \\ noun(plural) ::= cats| dogs $$

From which we would get $some\ cats$ and $one\ dog$ for example.


1 Answer 1


There seem to be several levels of such grammars.

If the number of possible $y$ is finite, then each $By$ can be coded as a separate variable (like $B_y$) and your grammar is basically a "compressed" context-free grammar.

In case of an infinite number of values the $y$ can behave like stacks of symbols (which can be pushed, popped and copied to other variables) a possible formalism is that of indexed grammars.

Even more is possible with attribute grammars, where the attributes can be operated on (you can add for instance the attributes of children). Moreover the values can be passed either up or down the derivation tree (synthesized or inherited).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.