Sig: Recuperación de Errores Sup: Análisis Sintáctico Ascendente en Ant: Definición Dirigida por la Con:
Ind:
Ind:
%token D S
%%
p: ds ';' ss | ss ;
ds: D ';' ds
| D
;
ss: S ';' ss | S ;
%%
illustrates a typical LALR conflict due to a bad grammar design.
Ds seguida de la lista de Ss
[~/jison/jison-decs-sts(master)]$ pwd -P /Users/casiano/local/src/javascript/PLgrado/jison/jison-decs-sts
[~/jison/jison-decs-sts(master)]$ git remote -v origin git@github.com:crguezl/jison-decs-sts.git (fetch) origin git@github.com:crguezl/jison-decs-sts.git (push)
La siguiente gramática no es LR(1).
[~/srcPLgrado/jison/jison-nolr]$ cat confusingsolvedppcr.y
%%
A:
B 'c' 'd'
| E 'c' 'f'
;
B:
'x' 'y'
;
E:
'x' 'y'
;
%%
Encuentre una gramática sin conflictos equivalente a la anterior.
[~/jison/jison-nolr(master)]$ pwd -P /Users/casiano/local/src/javascript/PLgrado/jison/jison-nolr
[~/jison/jison-nolr(master)]$ git remote -v origin git@github.com:crguezl/jison-nolr.git (fetch) origin git@github.com:crguezl/jison-nolr.git (push)
{ a^n b^n c^m : n >= 0, m >= 0 } U { a^n b^m c^m : n >= 0, m >= 0 }
Esto es: Concatenaciones de repeticiones
de as seguidas de repeticiones de bs y seguidas de
repeticiones de cs donde el número
de as es igual al número de bs
o bien el número de bs es igual al número de cs.
s: aeqb | beqc ; aeqb: ab cs ; ab: /* empty */ | 'a' ab 'b' ; cs: /* empty */ | cs 'c' ; beqc: as bc ; bc: /* empty */ | 'b' bc 'c' ; as: /* empty */ | as 'a' ;
The symbol aeqb correspond to guess that there are the same number
of as than bs. In the same way, beqc starts the subgrammar
for those phrases where the number of bs is equal to the number
of cs. The usual approach to eliminate the ambiguity by changing
the grammar to an unambiguous one does not work.
[~/jison/jison-ambiguouslanguage(master)]$ pwd -P /Users/casiano/local/src/javascript/PLgrado/jison/jison-ambiguouslanguage
[~/jison/jison-ambiguouslanguage(master)]$ git remote -v origin git@github.com:crguezl/jison-ambiguouslanguage.git (fetch) origin git@github.com:crguezl/jison-ambiguouslanguage.git (push)
[~/srcPLgrado/jison/jison-reducereduceconflict]$ cat reducereduceconflictPPCR2.y
%token ID
%%
def: param_spec return_spec ','
;
param_spec:
type
| name_list ':' type
;
return_spec:
type
| name ':' type
;
type:
ID
;
name:
ID
;
name_list:
name
| name ',' name_list
;
%%
Este es el diagnóstico de Jison:
~/srcPLgrado/jison/jison-reducereduceconflict]$ jison reducereduceconflictPPCR2.y Conflict in grammar: multiple actions possible when lookahead token is ID in state 5 - reduce by rule: name -> ID - reduce by rule: type -> ID Conflict in grammar: multiple actions possible when lookahead token is : in state 5 - reduce by rule: name -> ID - reduce by rule: type -> ID Conflict in grammar: multiple actions possible when lookahead token is , in state 5 - reduce by rule: name -> ID - reduce by rule: type -> ID States with conflicts: State 5 type -> ID . #lookaheads= ID : , name -> ID . #lookaheads= ID : ,Este es el resultado de compilar con
bison -v:
[~/jison/jison-reducereduceconflict(master)]$ bison -v reducereduceconflictPPCR2.y reducereduceconflictPPCR2.y: conflicts: 1 reduce/reduceEl fichero
reducereduceconflictPPCR2.output queda así:
[~/jison/jison-reducereduceconflict(master)]$ cat reducereduceconflictPPCR2.output
State 1 conflicts: 1 reduce/reduce
Grammar
0 $accept: def $end
1 def: param_spec return_spec ','
2 param_spec: type
3 | name_list ':' type
4 return_spec: type
5 | name ':' type
6 type: ID
7 name: ID
8 name_list: name
9 | name ',' name_list
Terminals, with rules where they appear
$end (0) 0
',' (44) 1 9
':' (58) 3 5
error (256)
ID (258) 6 7
Nonterminals, with rules where they appear
$accept (6)
on left: 0
def (7)
on left: 1, on right: 0
param_spec (8)
on left: 2 3, on right: 1
return_spec (9)
on left: 4 5, on right: 1
type (10)
on left: 6, on right: 2 3 4 5
name (11)
on left: 7, on right: 5 8 9
name_list (12)
on left: 8 9, on right: 3 9
state 0
0 $accept: . def $end
ID shift, and go to state 1
def go to state 2
param_spec go to state 3
type go to state 4
name go to state 5
name_list go to state 6
state 1
6 type: ID .
7 name: ID .
',' reduce using rule 6 (type)
',' [reduce using rule 7 (name)]
':' reduce using rule 7 (name)
$default reduce using rule 6 (type)
state 2
0 $accept: def . $end
$end shift, and go to state 7
state 3
1 def: param_spec . return_spec ','
ID shift, and go to state 1
return_spec go to state 8
type go to state 9
name go to state 10
state 4
2 param_spec: type .
$default reduce using rule 2 (param_spec)
state 5
8 name_list: name .
9 | name . ',' name_list
',' shift, and go to state 11
$default reduce using rule 8 (name_list)
state 6
3 param_spec: name_list . ':' type
':' shift, and go to state 12
state 7
0 $accept: def $end .
$default accept
state 8
1 def: param_spec return_spec . ','
',' shift, and go to state 13
state 9
4 return_spec: type .
$default reduce using rule 4 (return_spec)
state 10
5 return_spec: name . ':' type
':' shift, and go to state 14
state 11
9 name_list: name ',' . name_list
ID shift, and go to state 15
name go to state 5
name_list go to state 16
state 12
3 param_spec: name_list ':' . type
ID shift, and go to state 17
type go to state 18
state 13
1 def: param_spec return_spec ',' .
$default reduce using rule 1 (def)
state 14
5 return_spec: name ':' . type
ID shift, and go to state 17
type go to state 19
state 15
7 name: ID .
$default reduce using rule 7 (name)
state 16
9 name_list: name ',' name_list .
$default reduce using rule 9 (name_list)
state 17
6 type: ID .
$default reduce using rule 6 (type)
state 18
3 param_spec: name_list ':' type .
$default reduce using rule 3 (param_spec)
state 19
5 return_spec: name ':' type .
$default reduce using rule 5 (return_spec)
Encuentre una gramática equivalente a la anterior sin conflictos.
return_spec as follows makes the problem go away:
%token BOGUS
...
%%
...
return_spec:
type
| name ':' type
/* This rule is never used. */
| ID BOGUS
;
This corrects the problem because it introduces the possibility of an additional active rule in the context after the ID at the beginning of return_spec. This rule is not active in the corresponding context in a param_spec, so the two contexts receive distinct parser states. As long as the token BOGUS is never generated by yylex, the added rule cannot alter the way actual input is parsed.
In this particular example, there is another way to solve the problem: rewrite the rule for return_spec to use ID directly instead of via name. This also causes the two confusing contexts to have different sets of active rules, because the one for return_spec activates the altered rule for return_spec rather than the one for name.
param_spec:
type
| name_list ':' type
;
return_spec:
type
| ID ':' type
;
[~/jison/jison-reducereduceconflict(master)]$ pwd -P /Users/casiano/local/src/javascript/PLgrado/jison/jison-reducereduceconflict
[~/jison/jison-reducereduceconflict(master)]$ git remote -v origin git@github.com:crguezl/ull-etsii-grado-PL-reducereduce.git (fetch) origin git@github.com:crguezl/ull-etsii-grado-PL-reducereduce.git (push)
Casiano Rodríguez León