A context-sensitive grammar is a grammar with context-sensitive rules. There are two equivalent formulations of the definition of a context-sensitive grammar rule (cf. Chomsky hierarchy): rules of the form a → b where a and b are strings of alphabet symbols, with the restriction that length(a) <= length(b) rules of the form l X r → l b r where l, r, and b are (possibly empty) strings of alphabet symbols, and X is a non-terminal. l and r are referred to as the left and right context for X → b in the context-sensitive rule. Context-sensitive grammars are more powerful than context-free grammars, but they are much harder to work with.
Vous devez demander un compte pour contribuer à cette page.