Re: help with simple grammar please

[Thomas Troeger]

On Sun, Aug 25, 2002 at 03:06:47AM -0400, Bernd Prager wrote:
> Hi,
> 

[...]

> -------- snip --------------------
> word: >one<
> word: >two<
> expression: (single word >two<)
> sentence: (word >(null)< expression >one two)<)
> expression: (sentence >(null)<)
> -------- snip --------------------
> 
> I was expecting something like:
> -------- snip --------------------
> word: >one<
> expression: (single word >one<)
> word: >two<
> expression: (single word >two<)
> sentence: (word >one< expression >two<)
> expression (sentence >(one two)<)
> -------- snip --------------------
> 
> I don't understand this. Where is my error in reasoning?
> Can anybody help me?
> Thanks,
> -- B.

Hello,

About the unexpected output you get while parsing '(one two)':

If you're a little familiar with LR(1) or LALR(1) parsing, the
following explanation for the output might help you on:

I transformed the grammar in the following fashion:
E := W | S ;
W := w ;
S := ( W E ) ;

Below you see: the canonical collection, an LR(1) parse table (LALR
is similar, but with a compacted table), and an example parse of an
input string (input = '( w w )', which corresponds to '(one two)').

LR(1) Zustandsgraph:
Zustand 0
[E := . W , #]
[E := . S , #]
[W := . w , #]
[S := . ( W E ) , #]
'S' --> 1
'W' --> 2
'(' --> 3
'w' --> 4
Zustand 1
[E := S . , #]
Zustand 2
[E := W . , #]
Zustand 3
[W := . w , (]
[W := . w , w]
/* in state 3, there are two possibilities to continue.
   to decide which one to use, we need to read the lookahead.
         for input '( one *two )', we shift here (to 6) */
[S := ( . W E ) , #]
'W' --> 5
'w' --> 6
Zustand 4
[W := w . , #]
Zustand 5
[E := . W , )]
[E := . S , )]
[W := . w , )]
[S := . ( W E ) , )]
[S := ( W . E ) , #]
'E' --> 7
'S' --> 8
'W' --> 9
'(' --> 10
'w' --> 11
Zustand 6
[W := w . , (]
[W := w . , w]
Zustand 7
[S := ( W E . ) , #]
')' --> 12
Zustand 8
[E := S . , )]
Zustand 9
[E := W . , )]
Zustand 10
[W := . w , (]
[W := . w , w]
[S := ( . W E ) , )]
'W' --> 13
'w' --> 6
Zustand 11
[W := w . , )]
Zustand 12
[S := ( W E ) . , #]
Zustand 13
[E := . W , )]
[E := . S , )]
[W := . w , )]
[S := . ( W E ) , )]
[S := ( W . E ) , )]
'E' --> 14
'S' --> 8
'W' --> 9
'(' --> 10
'w' --> 11
Zustand 14
[S := ( W E . ) , )]
')' --> 15
Zustand 15
[S := ( W E ) . , )]

LR(1) Table
       E   S   W   (   )   w   #
   0   .  G1  G2  S3   .  S4   .
   1   .   .   .   .   .   .  R1
   2   .   .   .   .   .   .  R0
   3   .   .  G5   .   .  S6   .
   4   .   .   .   .   .   .  R2
   5  G7  G8  G9 S10   . S11   .
   6   .   .   .  R2   .  R2   .
   7   .   .   .   . S12   .   .
   8   .   .   .   .  R1   .   .
   9   .   .   .   .  R0   .   .
  10   .   . G13   .   .  S6   .
  11   .   .   .   .  R2   .   .
  12   .   .   .   .   .   .  R3
  13 G14  G8  G9 S10   . S11   .
  14   .   .   .   . S15   .   .
  15   .   .   .   .  R3   .   .

Runde 1
Stack: 0 
Band : ( w w ) #
shift 3

Runde 2
Stack: 0 3 
Band : w w ) #
shift 6

Runde 3
Stack: 0 3 6 
Band : w ) #
reduce 2: W := w ;
/* this gives the first output line with >one< */
/* > word: >one< */
goto 5

Runde 4
Stack: 0 3 5 
Band : w ) #
shift 11

Runde 5
Stack: 0 3 5 11 
Band : ) #
reduce 2: W := w ;
/* this gives the second output line with >two< */
/* > word: >two< */
goto 9

Runde 6
Stack: 0 3 5 9 
Band : ) #
reduce 0: E := W ;
/* > expression: (single word >two<) */
goto 7

Runde 7
Stack: 0 3 5 7 
Band : ) #
shift 12

Runde 8
Stack: 0 3 5 7 12 
Band : #
reduce 3: S := ( W E ) ;
/* > sentence: (word >(one)< expression >two<) */
goto 1

Runde 9
Stack: 0 1 
Band : #
reduce 1: E := S ;
/* > expression: (sentence >(one)<) */
Wort in Sprache.

I hope this helps :-)

mfg.

--tst.

-- 
/"\
\ / ASCII Ribbon Campaign
 X  Against HTML Mail
/ \