CODEWITHSUNDEEP
prologdcgcontext-sensitive-grammardcg-semicontext
lightning
lightning

Reputation: 409

Context sensitive generation in prolog

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?

Upvotes: 4

Views: 262

Answers (1)

false
false

Reputation: 10102

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.

Upvotes: 2

Related Questions