<p>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, <code>first * second;</code> in C in and C++ can mean both &quot;<em>declare a pointer to the type <code>first</code> named <code>second</code></em>&quot; and &quot;<em>multiply the variables <code>first</code> and <code>second</code> and discard the result</em>&quot;, depending on the context.</p>
<p>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) <code>enable</code> and <code>disable</code> can be both verbs (mnemonics) and adverbs. The sentence <code>enable interrupt</code> is parsed as (S-expression) <code>(enable interrupt)</code>, and <code>enable</code> is a verb there, but the sentence <code>returni enable</code> is parsed as <code>(returni enable)</code>, and <code>enable</code> is an adverb here. In the parser in my <a href="https://flatassembler.github.io/PicoBlaze/PicoBlaze" rel="nofollow noreferrer">PicoBlaze Simulator in JavaScript</a>, I made <a href="https://github.com/FlatAssembler/PicoBlaze_Simulator_in_JS/blob/c62ed83a05ebb5adb5d11e312ea3fc6569403302/parser.js#L59" rel="nofollow noreferrer">an exception</a> so that if the length of the array is equal to 1, and if the first element is either <code>enable</code> or <code>disable</code>, the parsing stops and returns what it has made thus far (to the recursive function that called it).</p>
<p>So, is the PicoBlaze assembly language context-sensitive because of that?</p>

<parsing><grammar><context-free-grammar>
Is PicoBlaze assembly language a context-sensitive language?
CC BY-SA 4.0
2023-06-27T14:02:37.877Z
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.
pxeger
CC BY-SA 4.0
2023-06-27T16:25:40.810Z
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.
kaya3
CC BY-SA 4.0
2023-08-11T00:39:35.913Z
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.
Chris Dodd
<p>Strictly, yes, since any context-free language is <em>also</em> 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.</p>
<p>We could define a CFG for the subset of the language you describe like this:</p>
<pre class="lang-none prettyprint-override"><code>VERB := &quot;returni&quot; | &quot;enable&quot; | &quot;disable&quot;
NOUN := &quot;interrupt&quot;

SENTENCE := VERB ADVERB | VERB NOUN
</code></pre>
<p>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 <code>(returni (enable interrupt))</code>?), but that's not an issue either. You could instead have something like</p>
<pre class="lang-none prettyprint-override"><code>VERB_OTHER := &quot;returni&quot; | ...
VERB := VERB_OTHER | &quot;enable&quot; | &quot;disable&quot;

SENTENCE_OTHER := VERB_OTHER ADVERB | VERB_OTHER NOUN | VERB_OTHER SENTENCE_OTHER
SENTENCE := VERB ADVERB | VERB NOUN | VERB SENTENCE_OTHER
</code></pre>
<p>to make this case explicit: &quot;enable&quot; 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.</p>
<p>During <em>lexing</em>, you don't know whether <code>enable</code> will be an adverb or a verb. This is the big issue of the C &quot;lexer hack&quot; situation with <code>(A)*B</code>, 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.</p>
<hr />
<p>The term &quot;context-sensitive&quot; is a bit misleading, and doesn't refer to what we might casually think of as &quot;context&quot;. 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.</p>
<p>What makes a language context-sensitive and not context-free is necessarily having grammar rules that look like this: <span class="math-container">$\alpha A \beta \rightarrow \alpha \gamma \beta$</span> . There are <em>multiple symbols</em> on the left-hand side, and the &quot;context&quot; 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.</p>

CC BY-SA 4.0
2023-06-27T23:00:53.540Z
2023-08-10T23:33:06.710Z
2023-08-10T23:33:06.710Z
Michael Homer
# Is PicoBlaze assembly language a context-sensitive language?
Posted by: username_0 on 2023-06-27
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](https://flatassembler.github.io/PicoBlaze/PicoBlaze), I made [an exception](https://github.com/FlatAssembler/PicoBlaze_Simulator_in_JS/blob/c62ed83a05ebb5adb5d11e312ea3fc6569403302/parser.js#L59) 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?
**Tags:** parsing grammar context-free-grammar
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_3**: 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.  
---
## 1 answers
### Answer by username_4 on 2023-06-27. Score: 5 | Accepted answer
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.
---
