Context sensitive generation in prolog

Question

I am interested in generating elements of a context sensitive language as described by Chomsky, as described in Chomsky Classification of Grammars under the section "Type - 1 Grammar".

(Basically, similar to a standard context-free grammar, but allowing multiple symbols on the left side of a production rule, including terminals).

I know about definite clause grammars in Prolog, but I don't see an obvious mapping between those and Chomsky's context sensitive languages. Is there a "universal" way to use the DCG framework to describe production rules with multiple symbols on the left side, or do I need an ad hoc approach for each individual language?

There is an example of how to do this on Wikipedia of all places, but for this to be a legitimate question on S.O., you have to have a concrete problem you're trying to solve. — Daniel Lyons
Of interest: Chomsky hierarchy - Type 1 - Production rules - αAβ → αγβ — Guy Coder

false false · Accepted Answer · 2019-02-05T14:45:25

Context on the right-hand side can be encoded directly using a semicontext:

nt1, "context" --> nt2, "context".

For context on the left-hand side, there is no obvious direct encoding. Most often arguments to the non-terminals are used.

Context sensitive generation in prolog

1 Answers