Stack Overflow
Stack Overflow

Questions tagged [context-sensitive-grammar]

A context-sensitive grammar is a type of grammar that generates precisely the context-sensitive languages.

Context-sensitive grammars are grammars where each rule has the form

xAy -> xwy

Where A is a nonterminal and x, y, and z are strings of terminals and nonterminals.

56 questions
442
votes
20 answers

Is C++ context-free or context-sensitive?

I often hear claims that C++ is a context-sensitive language. Take the following example: a b(c); Is this a variable definition or a function declaration? That depends on the meaning of the symbol c. If c is a variable, then a b(c); defines a…
fredoverflow
  • 256,549
  • 94
  • 388
  • 662
49
votes
3 answers

Context-free grammars versus context-sensitive grammars?

Can someone explain to me why grammars [context-free grammar and context-sensitive grammar] of this kind accepts a String? What I know is Context-free grammar is a formal grammar in which every production(rewrite) rule is a form of V→w Where V is…
user1004413
  • 2,509
  • 6
  • 23
  • 33
34
votes
3 answers

chomsky hierarchy in plain english

I'm trying to find a plain (i.e. non-formal) explanation of the 4 levels of formal grammars (unrestricted, context-sensitive, context-free, regular) as set out by Chomsky. It's been an age since I studied formal grammars, and the various definitions…
tylerl
  • 30,197
  • 13
  • 80
  • 113
13
votes
2 answers

Parsing Context Sensitive Language

i am reading the Definitive ANTLR reference by Terence Parr, where he says: Semantic predicates are a powerful means of recognizing context-sensitive language structures by allowing runtime information to drive recognition But the examples…
Radi
  • 6,548
  • 18
  • 63
  • 91
12
votes
1 answer

Can a Perl/Java/etc regular expression be written to match decimal (non-)prime numbers?

Related questions/material: How can we match a^n b^n with Java regex? How to determine if a number is a prime with regex? (which deals with unary prime matching, while I'm looking for base ≥ 2; a nice trick nevertheless, and what got me to think…
Sami Liedes
  • 1,084
  • 8
  • 19
7
votes
1 answer

how to parse Context-sensitive grammar?

CSG is similar to CFG but the reduce symbol is multiple. So, can I just use CFG parser to parse CSG with reducing production to multiple terminals or non-terminals? Like 1. S → a bc 2. S → a S B c 3. c B → W B 4. W B → W X 5. W X → B X 6. B X → B…
qdwang
  • 425
  • 1
  • 4
  • 13
7
votes
1 answer

When a keyword means different things in different contexts, is that an example of context sensitivity?

According to this answer => in Scala is a keyword which has two different meanings: 1 to denote a function type: Double => Double and 2 to create a lambda expression: (x: Double): Double => 2*x. How does this relate to formal grammars, i.e. does…
corazza
  • 31,222
  • 37
  • 115
  • 186
6
votes
5 answers

Recursive languages vs context-sensitive languages

In Chomsky's hierarchy, the set of recursive languages is not defined. I know that recursive languages are a subset of recursively enumerable languages and that all recursive languages are decidable. What I'm curious about is how recursive languages…
Martin Konecny
  • 57,827
  • 19
  • 139
  • 159
6
votes
1 answer

how typedef-name - identifier issue is resolved in C?

I've been recently writing parser for language based on C. I'm using CUP (Yacc for Java). I want to implement "The lexer hack" (http://eli.thegreenplace.net/2011/05/02/the-context-sensitivity-of-c%E2%80%99s-grammar-revisited/ or …
Grzes
  • 971
  • 1
  • 13
  • 28
6
votes
1 answer

Can someone give a simple but non-toy example of a context-sensitive grammar?

I'm trying to understand context-sensitive grammars, and I understand why languages like {ww | w is a string} {an bn cn | a,b,c are symbols} are not context free, but what I'd like to know if a language similar to the untyped lambda calculus is…
BlueBomber
  • 282
  • 2
  • 11
5
votes
1 answer

Can a context-sensitive grammar have an empty string?

In one of my cs classes they mentioned that the difference between context-free grammar and context-sensitive grammar is that in CSG, then the left side of the production rule has to be less or equal than the right side. So, one example they gave…
ravelinx
  • 1,557
  • 4
  • 18
  • 26
4
votes
3 answers

Pumping lemma for context-sensitive language?

i have googled on pumping lemma for context sensitive, and it seems to only produce results for context-free language. Pumping lemma only allows to prove a language is context free only? and not context sensitive? Any idea how?
user1004413
  • 2,509
  • 6
  • 23
  • 33
4
votes
1 answer

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…
lightning
  • 389
  • 1
  • 9
4
votes
1 answer

Context-sensitive and turing-complete formal languages

Do you know about any, which can specify context-sensitive grammar? For example * symbol pointer/multiplication ambiguity resolving. I am looking for formal language which will make it possible to resolve such ambiguities. The language, which I am…
user3313119
  • 49
  • 3
3
votes
1 answer

How to use context-sensitive grammar in sentiment analysis?

Is it possible to use context-sensitive grammar in sentiment analysis? If yes, then how? Basically, I want to do some phrase-level analysis.
Hemant
  • 619
  • 2
  • 6
  • 17
1
2 3 4