I read the following example in one of my professors notes.
1) we have a SLR(1) Grammar G as following. we use SLR(1) parser generator and generate a parse table S for G. we use LALR(1) parser generator and generate a parse table L for G.
S->AB
A->dAa
A-> lambda (lambda is a string with length=0)
B->aAb
Solution: the number of elements with R (reduce) in S is more than L.
but in one site I read:
2) Suppose T1, T2 is created with SLR(1) and LALR(1) for Grammar G. if G be a SLR(1) Grammar which of the following is TRUE?
a) T1 and T2 has not any difference.
b) total Number of non-error entries in T1 is lower than T2
c) total Number of error entries in T1 is lower than T2
Solution:
The LALR(1) algorithm generates exactly the same states as the SLR(1) algorithm, but it can generate different actions; it is capable of resolving more conflicts than the SLR(1) algorithm. However, if the grammar is SLR(1), both algorithms will produce exactly the same machine (a is right).
any one could describe for me which of them is true?
EDIT: infact my question is why for a given SLR(1) Grammar, the parse table of LALAR(1) and SLR(1) is exactly the same, (error and non-error entries are equal and number of reduce is equal) but for the above grammar, the number of Reduced in S is more than L.
This is easy to check. They have the same number of reductions because there is no conflict in the SLR(1) table. The LALR(1) eliminates conflicts shift-reduce and reduce-reduce but it is the same otherwise.
If possible, can you give what these stand for (i.r., LSLR1 and SLR1). It may help people answer your question. I'm very familiar with Automata Theory and I still will need some more information, so others may need that as well. Also, are what type of grammars are these? Context-free? Regular?
Also are you asking for an explanation between which is right and why? Just double checking!
So, I will try to answer the question of Huimen and giving some background for Daniel. First of all, LR parsers are bottom up parser, i. e. they try to construct the derivation tree starting from the leaves. This is done using a push-down automata, where the stack alphabet is the set the states of an special finite automata, the variables of the grammar and terminal symbols.
Depending on the parsing technique (LR(0), SLR(1), LR(1)) the finite automata is different but this is not interesting for our question right now. What it is interesting, is that the automata used in SLR(1) and LALR(1) are the same.
Bottom up parsing is based in two operations: SHIFT and REDUCE.
To make the pushdown automata, a table is built looking at the stack and one look-ahead symbol (that's why it is called SLR(1) and LALR(1)). In SLR(1), the table is formed by the following rules:
In the entry of the table of symbol q,a
- If the LR(0) finite automata q has a transition with a symbol a to state q1 put in the correspondent position in the table SHIFT:q1
- IF the state is final put in the corresponding entry REDUCE if:
-SLR(1): the lookahead is in the follow of the symbol.
- LALR(1): the lookahead is in a certain "set" that need to be calculated.
But in your example, I think both tables are the same. I can generate both using PLY, do you want me to attach here the tables in Yacc format?
Dear Domingo, i ask 2 questions. i know in general for SLR(1) Grammar the table of LALR(1) and SLR(1) is the same (number of reduces and error entries and non-error entries). but in the 2'nd question i give an SLR(1) grammar and ask why number of reduces be different? (as we mentioned in question 1 there should be the same) !!!! this is my challenge. would you please give me any picture or table as a figure that prove my two questions?
Table for LALR:
Grammar
Rule 0 S' -> S
Rule 1 S -> A B
Rule 2 A -> d A a
Rule 3 A ->
Rule 4 B -> a A b
Terminals, with rules where they appear
a : 2 4
b : 4
d : 2
error :
Nonterminals, with rules where they appear
A : 1 2 4
B : 1
S : 0
Parsing method: LALR
state 0
(0) S' -> . S
(1) S -> . A B
(2) A -> . d A a
(3) A -> .
d shift and go to state 3
a reduce using rule 3 (A -> .)
A shift and go to state 1
S shift and go to state 2
state 1
(1) S -> A . B
(4) B -> . a A b
a shift and go to state 4
B shift and go to state 5
state 2
(0) S' -> S .
state 3
(2) A -> d . A a
(2) A -> . d A a
(3) A -> .
d shift and go to state 3
a reduce using rule 3 (A -> .)
A shift and go to state 6
state 4
(4) B -> a . A b
(2) A -> . d A a
(3) A -> .
d shift and go to state 3
b reduce using rule 3 (A -> .)
A shift and go to state 7
state 5
(1) S -> A B .
$end reduce using rule 1 (S -> A B .)
state 6
(2) A -> d A . a
a shift and go to state 8
state 7
(4) B -> a A . b
b shift and go to state 9
state 8
(2) A -> d A a .
a reduce using rule 2 (A -> d A a .)
b reduce using rule 2 (A -> d A a .)
state 9
(4) B -> a A b .
$end reduce using rule 4 (B -> a A b .)
Grammar
Rule 0 S' -> S
Rule 1 S -> A B
Rule 2 A -> d A a
Rule 3 A ->
Rule 4 B -> a A b
Terminals, with rules where they appear
a : 2 4
b : 4
d : 2
error :
Nonterminals, with rules where they appear
A : 1 2 4
B : 1
S : 0
Parsing method: SLR
state 0
(0) S' -> . S
(1) S -> . A B
(2) A -> . d A a
(3) A -> .
d shift and go to state 3
a reduce using rule 3 (A -> .)
b reduce using rule 3 (A -> .)
A shift and go to state 1
S shift and go to state 2
state 1
(1) S -> A . B
(4) B -> . a A b
a shift and go to state 4
B shift and go to state 5
state 2
(0) S' -> S .
state 3
(2) A -> d . A a
(2) A -> . d A a
(3) A -> .
d shift and go to state 3
a reduce using rule 3 (A -> .)
b reduce using rule 3 (A -> .)
A shift and go to state 6
state 4
(4) B -> a . A b
(2) A -> . d A a
(3) A -> .
d shift and go to state 3
a reduce using rule 3 (A -> .)
b reduce using rule 3 (A -> .)
A shift and go to state 7
state 5
(1) S -> A B .
$end reduce using rule 1 (S -> A B .)
state 6
(2) A -> d A . a
a shift and go to state 8
state 7
(4) B -> a A . b
b shift and go to state 9
state 8
(2) A -> d A a .
a reduce using rule 2 (A -> d A a .)
b reduce using rule 2 (A -> d A a .)
state 9
(4) B -> a A b .
$end reduce using rule 4 (B -> a A b .)
These tables were generated by PLY python, and they look exactly the same.
No, they are not the same. They have an additional entry in state 3 and 4.
They have an additional entry " b reduce using rule 3 (A -> .)"
i confused again would you please add summary for 1) error entries in SLR(1) and LALR(1) 2) non-error entries for SLR(1) and LALR(1) 3) table size in SLR(1) and LALR(1) 4) number of reduces in SLR(1) and LALR(1) for this example ? thanks so much.
Ok, i see it. my last question is, so as i conclude with your works, answer to this question:
Suppose T1, T2 is created with SLR(1) and LALR(1) for Grammar G. if G be a SLR(1) Grammar which of the following is TRUE?
a) T1 and T2 has not any difference.
b) total Number of non-error entries in T1 is lower than T2
c) total Number of error entries in T1 is lower than T2
my professor say (a) is true but you show in another question that (a) is not true? am i right?
thanks.
The difference between SLR und LALR is that with SLR the Reduce A-> is done always, when an element of Follow(A) is the next one in the input.
Follow(a)= {a,b}. b is element of Follow(a) because of rule: B-> a A b. in SLR reduce only use the global function Follow, not the local context.
But in the state 0 the input can not start with b. This would be recognized with LALR, because then LR(1) items are used, with recognize wich terminal can follow the core.
In state 0 we have the following LR(1) items:
(0) S' -> . S, $
(1) S -> . A B, $
(2) A -> . d A a, a
(3) A -> . , a
Therefore A->. is only reduced when an a is following.
When then input is not an Element of the language of the grammar SLR may do some reduce before recognizing the error.
Perhaps my tutorial on compiling theory might help you:
http://inf2.w3.rz.unibw-muenchen.de/Tools/Syntax/english/theoryScreen.pdf
In particular, take a look at the syntax section.
If you want to do experiments yourself, our jaccie tool plus additional documentation can be found at:
http://inf2.w3.rz.unibw-muenchen.de/Tools/Syntax/english/index.html
Happy experimenting!
- Badges
- Science topic
- Similar topics
- Computer Science