Re: Shift reduce errors due to embedded actions

[Axel Kittenberger]

On Wednesday 10 October 2001 20:58, Hans Aberg wrote:
> At 20:20 +0200 2001/10/10, Axel Kittenberger wrote:
> >> LR(n) grammars can be rewritten as LR(1) grammars, but I do not know how
> >> that works when out when having to take actios into account.
> >
> >Oh, this is possible?
>
> And even LR(0) if each sentence is assumed to be followed by an end marker;
> see J.E.Hopcroft & J.D.Ullman, "Introduction to Automata Theory, Languages
> and Computation", Addison-Wesley (1979).
> 
> Note that LR(n) grammars are still context independent, and I get the
> feeling you try to plug in a context dependent grammar. The usual way out
> of it is to have a look-up table with the type of each name, and then let
> the lexer return that type to the Bison generated parser.
>

Well as I was able to write the grammar only with rules with all only having 
one token on the left side this is per definition a context free grammar. (I 
guess called a level 3 grammar or so) context sensitive grammars have more 
than one token on the left side like :

S -> 'a' S Q
S -> 'a' 'b' 'c'
'b' Q 'c' -> 'b' 'b' 'c' 'c'
'c' Q -> 'Q' 'c'

Which is a context sensitive grammar, that cannot be handeled by bison, or LR 
or LL parsers. at all Oh well I didn't think of it of course :o) It's an 
example I got out of a book and descripes a ruleset to generate words which 
follow a^n b^n c^n like abc, aabbcc, aaabbbccc, ...

> The stuff above is probably known to C compiler writers (check in say the
> newsgroups comp.compilers, comp.lang.c.moderated, or some).

Well I think I know today why they decided to create arrays in C like this
cork a[5]; 
and not like java, or I also intend to do
cork[5] a;

> If
>   cork[5] = 3;
> appears first, it is an error, as "cork" has not been declared. So the
> lexer checks the lookup table, and finds that "cork" is not there, and
> returns say "undeclared_name". If the name is on the table, it will tell
> its type, say "array_name". Then the grammar may look something like
>   declaration:
>     type_name "[" number "]" undeclared_name ";" { /* action */ }
>     ...
>
>   assignment:
>     array_name "[" number "]" "=" ...

Well but this implies you cannot hava a type and a variable with the same 
name, not that I ever considered this an desirable fact, but at least from 
the grammar this could be possible it just wonders me that no matter how I 
tried I did not manage to squeeze it into bison without producing 
reduce/reduce conflicts.

> At least the C++ ANSI standard (can be bought at ANSI for $18 or something)
> has an appendix with the C++ grammar, where one can get ideas on how to
> create such grammars.

I think if seen somewhere a C grammar on the web, and also there is g++ :o) 
but as said this certain problem does not arise in C++ as arrays are declared 
after the variable not as part of the type, java could be more interesting, 
but what I tried it forbids the same, no "types" (classes) and variables with 
the same name, however this is some time ago I'm no longer certain, will have 
to try again.

- Axel