Is PicoBlaze assembly language a context-sensitive language?

Question

I know one example of context-sensitivity in programming languages is the so-called typedef problem. Basically, the words can be different types, and that influences how a sentence may be parsed. For example, first * second; in C in and C++ can mean both "declare a pointer to the type first named second" and "multiply the variables first and second and discard the result", depending on the context.

There is a problem with parsing PicoBlaze assembly language, but I don't know if it is analogous. Namely, in PicoBlaze assembly, the words (tokens) enable and disable can be both verbs (mnemonics) and adverbs. The sentence enable interrupt is parsed as (S-expression) (enable interrupt), and enable is a verb there, but the sentence returni enable is parsed as (returni enable), and enable is an adverb here. In the parser in my PicoBlaze Simulator in JavaScript, I made an exception so that if the length of the array is equal to 1, and if the first element is either enable or disable, the parsing stops and returns what it has made thus far (to the recursive function that called it).

So, is the PicoBlaze assembly language context-sensitive because of that?

Answer 1

Strictly, yes, since any context-free language is also a context-sensitive language (the terminology is not ideal...), but in the sense of whether you need something beyond a CFG to represent it, no.

We could define a CFG for the subset of the language you describe like this:

VERB := "returni" | "enable" | "disable"
NOUN := "interrupt"

SENTENCE := VERB ADVERB | VERB NOUN

This is fine, describes the language without issue, and only generates valid sentences of it. I think the real system is a little more complex (it would otherwise recurse (returni (enable interrupt))?), but that's not an issue either. You could instead have something like

VERB_OTHER := "returni" | ...
VERB := VERB_OTHER | "enable" | "disable"

SENTENCE_OTHER := VERB_OTHER ADVERB | VERB_OTHER NOUN | VERB_OTHER SENTENCE_OTHER
SENTENCE := VERB ADVERB | VERB NOUN | VERB SENTENCE_OTHER

to make this case explicit: "enable" is not part of the verbs used in SENTENCE_OTHER, so as an argument it can only be an adverb and won't accept a further argument.

During lexing, you don't know whether enable will be an adverb or a verb. This is the big issue of the C "lexer hack" situation with (A)*B, but it doesn't seem to be an issue here because you only need to know it's an identifier. In any case, assigning lexical or grammatical classes to parts of the input isn't what these language classes are about — they only deal with deciding whether a string is part of the language or not. Your parser handles that, and special-casing rare situations is a legitimate approach to use there.

---

The term "context-sensitive" is a bit misleading, and doesn't refer to what we might casually think of as "context". Even while parsing a context-free language, the parser will know which derivation(s) it's in, which is determined by what it's seen so far and feels like context, but isn't for this purpose.

What makes a language context-sensitive and not context-free is necessarily having grammar rules that look like this: $\alpha A \beta \rightarrow \alpha \gamma \beta$ . There are multiple symbols on the left-hand side, and the "context" around a terminal is represented by the Greek symbols there. A context-free language is one you can write with always only a single nonterminal on the left (and which can be accepted by a pushdown automata, and a number of other formal equivalences). This is the case here from what we've seen so far, and for most programming languages just because they are much more readily parseable than non-context-free languages.