Geek asks and answers

How is this grammar LR (1), but not SLR (1)?

I have the following grammar, which, as I was told, is LR (1), but not SLR (1):

S :: = a A | b A c | dc | bda

A :: = d

I do not understand why this is so. How would you prove it?

+6
source share
4 answers

I do not have enough reputation to comment on the answer above, and I was a bit late for this question, but ...

I saw this grammar as an example elsewhere, and the OP actually sealed it. Must be:

S :: = A a | b A c | d s | b d

A :: = d

S - "A a", "a A".

FOLLOWS A {$, a, c}, 8 SLR.

+12

- LR (1) SLR (1) . / / , , .

SLR (1). -, LR (0) . :

(1)
S -> .aA
S -> .bAc
S -> .dc
S -> .bda

(2)
S -> a.A
A -> .d

(3)
S -> aA.

(4)
A -> d.

(5)
S -> b.Ac
S -> b.da
A -> .d

(6)
S -> bA.c

(7)
S -> bAc.

(8)
S -> bd.a
A -> d.

(9)
S -> bda.

(10)
S -> d.c

(11)
S -> dc.

, FOLLOW . :

FOLLOW(S) = { $ }
FOLLOW(A) = { $, c }

, LR (0) SLR (1):

(1)
S -> .aA    [ $ ]
S -> .bAc   [ $ ]
S -> .dc    [ $ ]
S -> .bda   [ $ ]

(2)
S -> a.A    [ $ ]
A -> .d     [ $, c ]

(3)
S -> aA.    [ $ ]

(4)
A -> d.     [ $, c ]

(5)
S -> b.Ac   [ $ ]
S -> b.da   [ $ ]
A -> .d     [ $, c ]

(6)
S -> bA.c   [ $ ]

(7)
S -> bAc.   [ $ ]

(8)
S -> bd.a   [ $ ]
A -> d.     [ $, c ]

(9)
S -> bda.   [ $ ]

(10)
S -> d.c    [ $ ]

(11)
S -> dc.    [ $ ]

, ! / - (8), , a, - $. , SLR (1). SLR (1) LR (1), , SLR (1) LR (1).

, !

+10

- first- CFG, LR (0), SLR (1) LR (1). .

, , , ( , ). :

http://smlweb.cpsc.ucalgary.ca/

:

S -> a A | b A c | d c | b d a.
A -> d.

, , : - SLR (1). ( -1 ).

, , SLR (1), LR (1).

+1

1) - LL (1) LALR (1) .

2) , , LALR (1).

3) ( ), SLR (1).

4) They say that the grammar is LR (1), because it does not have a conflict in the parsing table or the ACTION / GOTO table, and we all know that when a conflict occurs in LR (1), we combine the data and get LALR.

LR (0) OR SLR OR SLR (1) are the same

LR (1) OR CLR are the same

LALR OR LALR (1) are the same

Parameter (1) determines the type of internal efficiency of the parser.

thank you.

0
source

More articles:


All Articles