4
$\begingroup$

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.

However, there is a problem with parsing PicoBlaze assembly language, which 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 that, if the length of the array is equal to 1, and if the 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?

$\endgroup$
3
  • 2
    $\begingroup$ Correct me if I'm wrong, but it was my understanding that "context-sensitive" only applies to a language in the context of deciding it: i.e., just checking whether or not a string is valid in the language, not about how it gets parsed into a syntax tree or similar. And I'd need more details on the syntax of PicoBlaze assembly to be certain, but it looks to me like the enable/disable problem doesn't make it context-sensitive. $\endgroup$
    – pxeger
    Jun 27, 2023 at 14:02
  • 1
    $\begingroup$ Yes, it seems what you're interested in is not context-sensitivity but ambiguity, i.e. first * second; could be parsed as a statement in two ways, either as Statement → Expression ';' or as Statement → Type Identifier ';'. This isn't context-sensitivity because the left-hand-side of the production rule is just one non-terminal. $\endgroup$
    – kaya3
    Jun 27, 2023 at 16:25
  • $\begingroup$ The typdef problem in C does not actually make the syntax not-context-free, it just makes the syntax ambiguous. Of course, any langauge that allows for programs that are syntactically correct but semantically invalid (due to type checking or other non-syntactic errors) blurs the definition of context-free vs context-sensitive. $\endgroup$
    – Chris Dodd
    Aug 11, 2023 at 0:39

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .