Modularized Context-Free Grammars
Shuly Wintner
Given two context-free grammars (CFGs), $G_1$ and $G_2$, the language
generated by the union of the grammars is \textit{not} the union of
the languages generated by each grammar: $L(G_1 \cup G_2) \neq L(G_1)
\cup L(G_2)$. In order to account for modularity of grammars, another
way of defining the meaning of grammars is needed. This paper adapts
results from the semantics of logic programming languages to CFGs. We
discuss alternative approaches for defining the denotation of a
grammar, culminating in one which we show to be both compositional and
fully-abstract. We then show how grammar modules can be defined such
that their semantics retains these desirable properties.