[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: help with simple grammar please
From: |
Thomas Troeger |
Subject: |
Re: help with simple grammar please |
Date: |
Sun, 25 Aug 2002 14:05:02 +0200 |
User-agent: |
Mutt/1.3.25i |
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
/ \