* Re: GDB/MI Output Syntax ambiguity
2004-08-23 21:03 Bob Rossi
2004-08-23 21:09 ` Daniel Jacobowitz
@ 2004-08-24 3:56 ` Michael Chastain
2004-08-24 12:36 ` Bob Rossi
1 sibling, 1 reply; 9+ messages in thread
From: Michael Chastain @ 2004-08-24 3:56 UTC (permalink / raw)
To: bob; +Cc: gdb
[Shout out to Paul Hilfinger, who was my professor in compiler class,
Spring 1983, UC Berkeley!]
The grammar in gdb.info from gdb 6.2 has stuff like (foo)* and [bar] and is
not quite low-level enough for bison input.
I made a grammar out of it by expanding the (foo)* and [bar] stuff
with rules. Appended is my grammar as I typed it in.
bison likes my grammar just fine on my system, with no shift-reduce
conflicts. I tried four different versions of yacc and bison:
bison 1.35-4-rh, the vendor bison on red hat linux 8
bison 1.875
yacc on netbsd 1.6
yacc on dec osf4.0g
Possibilities are:
(A) My grammar is more tractable than yours.
(B) You have a weird bison.
(C) I have several different weird bisons and yaccs.
I think (A) is likely and the others are long shots.
I played around with the list recursive productions in my grammar,
like this one:
out_of_band_record_list: ;
out_of_band_record_list: out_of_band_record_list out_of_band_record ;
This is the good kind of recursion. When I change it to the bad kind
of recursion:
out_of_band_record_list: ;
out_of_band_record_list: out_of_band_record out_of_band_record_list ;
... then I get two shift/reduce conflicts (with bison 1.35-4-rh). The
first conflict is the same conflict you have, with state 0 input TOKEN,
and the second conflict is in the out_of_band_record_list rule with
input TOKEN.
So, I bet it's some devil in the details of your grammar when you
translated from the augmented BNF with (foo)*[bar] to plain BNF for
bison.
Have a look at my grammar, see how it differs from yours. If you want,
mail me your grammar and your y.output file (the file with all the state
tables from "bison -v"), and I bet I could find the glitch.
=== mi1.y
%token TOKEN
%token STRING
%token CR
%token LF
%token C_STRING
%start output
%%
output: out_of_band_record_list result_record_opt "(gdb)" nl ;
result_record_opt: ;
result_record_opt: token_opt "^" result_class comma_result_list nl ;
out_of_band_record_list: ;
out_of_band_record_list: out_of_band_record_list out_of_band_record ;
out_of_band_record: async_record ;
out_of_band_record: stream_record ;
async_record: exec_async_output ;
async_record: status_async_output ;
async_record: notify_async_output ;
exec_async_output: token_opt "*" async_output ;
status_async_output: token_opt "+" async_output ;
notify_async_output: token_opt "=" async_output ;
async_output: async_class comma_result_list nl ;
result_class: "done" ;
result_class: "running" ;
result_class: "connected" ;
result_class: "error" ;
result_class: "exit" ;
async_class: "stopped" ;
comma_result_list: ;
comma_result_list: comma_result_list "," result ;
comma_value_list: ;
comma_value_list: comma_value_list "," value ;
result: variable "=" value ;
variable: STRING ;
value: const ;
value: tuple ;
value: list ;
const: C_STRING ;
tuple: "{}" ;
tuple: "{" result comma_result_list "}" ;
list: "[]" ;
list: "[" value comma_value_list "]" ;
list: "[" result comma_result_list "]" ;
stream_record: console_stream_output ;
stream_record: target_stream_output ;
stream_record: log_stream_output ;
console_stream_output: "~" C_STRING ;
target_stream_output: "@" C_STRING ;
log_stream_output: "&" C_STRING ;
nl : CR ;
nl : CR LF ;
token_opt: TOKEN ;
token_opt: ;
%%
=== mi1.output
Grammar
Number, Line, Rule
1 10 output -> out_of_band_record_list result_record_opt "(gdb)" nl
2 12 result_record_opt -> /* empty */
3 13 result_record_opt -> token_opt "^" result_class comma_result_list nl
4 15 out_of_band_record_list -> /* empty */
5 16 out_of_band_record_list -> out_of_band_record_list out_of_band_record
6 18 out_of_band_record -> async_record
7 19 out_of_band_record -> stream_record
8 21 async_record -> exec_async_output
9 22 async_record -> status_async_output
10 23 async_record -> notify_async_output
11 25 exec_async_output -> token_opt "*" async_output
12 26 status_async_output -> token_opt "+" async_output
13 27 notify_async_output -> token_opt "=" async_output
14 29 async_output -> async_class comma_result_list nl
15 31 result_class -> "done"
16 32 result_class -> "running"
17 33 result_class -> "connected"
18 34 result_class -> "error"
19 35 result_class -> "exit"
20 37 async_class -> "stopped"
21 39 comma_result_list -> /* empty */
22 40 comma_result_list -> comma_result_list "," result
23 42 comma_value_list -> /* empty */
24 43 comma_value_list -> comma_value_list "," value
25 45 result -> variable "=" value
26 47 variable -> STRING
27 49 value -> const
28 50 value -> tuple
29 51 value -> list
30 53 const -> C_STRING
31 55 tuple -> "{}"
32 56 tuple -> "{" result comma_result_list "}"
33 58 list -> "[]"
34 59 list -> "[" value comma_value_list "]"
35 60 list -> "[" result comma_result_list "]"
36 62 stream_record -> console_stream_output
37 63 stream_record -> target_stream_output
38 64 stream_record -> log_stream_output
39 66 console_stream_output -> "~" C_STRING
40 68 target_stream_output -> "@" C_STRING
41 70 log_stream_output -> "&" C_STRING
42 72 nl -> CR
43 73 nl -> CR LF
44 75 token_opt -> TOKEN
45 76 token_opt -> /* empty */
Terminals, with rules where they appear
$ (-1)
error (256)
TOKEN (257) 44
STRING (258) 26
CR (259) 42 43
LF (260) 43
C_STRING (261) 30 39 40 41
"(gdb)" (262) 1
"^" (263) 3
"*" (264) 11
"+" (265) 12
"=" (266) 13 25
"done" (267) 15
"running" (268) 16
"connected" (269) 17
"error" (270) 18
"exit" (271) 19
"stopped" (272) 20
"," (273) 22 24
"{}" (274) 31
"{" (275) 32
"}" (276) 32
"[]" (277) 33
"[" (278) 34 35
"]" (279) 34 35
"~" (280) 39
"@" (281) 40
"&" (282) 41
Nonterminals, with rules where they appear
output (29)
on left: 1
result_record_opt (30)
on left: 2 3, on right: 1
out_of_band_record_list (31)
on left: 4 5, on right: 1 5
out_of_band_record (32)
on left: 6 7, on right: 5
async_record (33)
on left: 8 9 10, on right: 6
exec_async_output (34)
on left: 11, on right: 8
status_async_output (35)
on left: 12, on right: 9
notify_async_output (36)
on left: 13, on right: 10
async_output (37)
on left: 14, on right: 11 12 13
result_class (38)
on left: 15 16 17 18 19, on right: 3
async_class (39)
on left: 20, on right: 14
comma_result_list (40)
on left: 21 22, on right: 3 14 22 32 35
comma_value_list (41)
on left: 23 24, on right: 24 34
result (42)
on left: 25, on right: 22 32 35
variable (43)
on left: 26, on right: 25
value (44)
on left: 27 28 29, on right: 24 25 34
const (45)
on left: 30, on right: 27
tuple (46)
on left: 31 32, on right: 28
list (47)
on left: 33 34 35, on right: 29
stream_record (48)
on left: 36 37 38, on right: 7
console_stream_output (49)
on left: 39, on right: 36
target_stream_output (50)
on left: 40, on right: 37
log_stream_output (51)
on left: 41, on right: 38
nl (52)
on left: 42 43, on right: 1 3 14
token_opt (53)
on left: 44 45, on right: 3 11 12 13
state 0
$default reduce using rule 4 (out_of_band_record_list)
output go to state 68
out_of_band_record_list go to state 1
state 1
output -> out_of_band_record_list . result_record_opt "(gdb)" nl (rule 1)
out_of_band_record_list -> out_of_band_record_list . out_of_band_record (rule 5)
TOKEN shift, and go to state 2
"~" shift, and go to state 3
"@" shift, and go to state 4
"&" shift, and go to state 5
"(gdb)" reduce using rule 2 (result_record_opt)
$default reduce using rule 45 (token_opt)
result_record_opt go to state 6
out_of_band_record go to state 7
async_record go to state 8
exec_async_output go to state 9
status_async_output go to state 10
notify_async_output go to state 11
stream_record go to state 12
console_stream_output go to state 13
target_stream_output go to state 14
log_stream_output go to state 15
token_opt go to state 16
state 2
token_opt -> TOKEN . (rule 44)
$default reduce using rule 44 (token_opt)
state 3
console_stream_output -> "~" . C_STRING (rule 39)
C_STRING shift, and go to state 17
state 4
target_stream_output -> "@" . C_STRING (rule 40)
C_STRING shift, and go to state 18
state 5
log_stream_output -> "&" . C_STRING (rule 41)
C_STRING shift, and go to state 19
state 6
output -> out_of_band_record_list result_record_opt . "(gdb)" nl (rule 1)
"(gdb)" shift, and go to state 20
state 7
out_of_band_record_list -> out_of_band_record_list out_of_band_record . (rule 5)
$default reduce using rule 5 (out_of_band_record_list)
state 8
out_of_band_record -> async_record . (rule 6)
$default reduce using rule 6 (out_of_band_record)
state 9
async_record -> exec_async_output . (rule 8)
$default reduce using rule 8 (async_record)
state 10
async_record -> status_async_output . (rule 9)
$default reduce using rule 9 (async_record)
state 11
async_record -> notify_async_output . (rule 10)
$default reduce using rule 10 (async_record)
state 12
out_of_band_record -> stream_record . (rule 7)
$default reduce using rule 7 (out_of_band_record)
state 13
stream_record -> console_stream_output . (rule 36)
$default reduce using rule 36 (stream_record)
state 14
stream_record -> target_stream_output . (rule 37)
$default reduce using rule 37 (stream_record)
state 15
stream_record -> log_stream_output . (rule 38)
$default reduce using rule 38 (stream_record)
state 16
result_record_opt -> token_opt . "^" result_class comma_result_list nl (rule 3)
exec_async_output -> token_opt . "*" async_output (rule 11)
status_async_output -> token_opt . "+" async_output (rule 12)
notify_async_output -> token_opt . "=" async_output (rule 13)
"^" shift, and go to state 21
"*" shift, and go to state 22
"+" shift, and go to state 23
"=" shift, and go to state 24
state 17
console_stream_output -> "~" C_STRING . (rule 39)
$default reduce using rule 39 (console_stream_output)
state 18
target_stream_output -> "@" C_STRING . (rule 40)
$default reduce using rule 40 (target_stream_output)
state 19
log_stream_output -> "&" C_STRING . (rule 41)
$default reduce using rule 41 (log_stream_output)
state 20
output -> out_of_band_record_list result_record_opt "(gdb)" . nl (rule 1)
CR shift, and go to state 25
nl go to state 26
state 21
result_record_opt -> token_opt "^" . result_class comma_result_list nl (rule 3)
"done" shift, and go to state 27
"running" shift, and go to state 28
"connected" shift, and go to state 29
"error" shift, and go to state 30
"exit" shift, and go to state 31
result_class go to state 32
state 22
exec_async_output -> token_opt "*" . async_output (rule 11)
"stopped" shift, and go to state 33
async_output go to state 34
async_class go to state 35
state 23
status_async_output -> token_opt "+" . async_output (rule 12)
"stopped" shift, and go to state 33
async_output go to state 36
async_class go to state 35
state 24
notify_async_output -> token_opt "=" . async_output (rule 13)
"stopped" shift, and go to state 33
async_output go to state 37
async_class go to state 35
state 25
nl -> CR . (rule 42)
nl -> CR . LF (rule 43)
LF shift, and go to state 38
$default reduce using rule 42 (nl)
state 26
output -> out_of_band_record_list result_record_opt "(gdb)" nl . (rule 1)
$default reduce using rule 1 (output)
state 27
result_class -> "done" . (rule 15)
$default reduce using rule 15 (result_class)
state 28
result_class -> "running" . (rule 16)
$default reduce using rule 16 (result_class)
state 29
result_class -> "connected" . (rule 17)
$default reduce using rule 17 (result_class)
state 30
result_class -> "error" . (rule 18)
$default reduce using rule 18 (result_class)
state 31
result_class -> "exit" . (rule 19)
$default reduce using rule 19 (result_class)
state 32
result_record_opt -> token_opt "^" result_class . comma_result_list nl (rule 3)
$default reduce using rule 21 (comma_result_list)
comma_result_list go to state 39
state 33
async_class -> "stopped" . (rule 20)
$default reduce using rule 20 (async_class)
state 34
exec_async_output -> token_opt "*" async_output . (rule 11)
$default reduce using rule 11 (exec_async_output)
state 35
async_output -> async_class . comma_result_list nl (rule 14)
$default reduce using rule 21 (comma_result_list)
comma_result_list go to state 40
state 36
status_async_output -> token_opt "+" async_output . (rule 12)
$default reduce using rule 12 (status_async_output)
state 37
notify_async_output -> token_opt "=" async_output . (rule 13)
$default reduce using rule 13 (notify_async_output)
state 38
nl -> CR LF . (rule 43)
$default reduce using rule 43 (nl)
state 39
result_record_opt -> token_opt "^" result_class comma_result_list . nl (rule 3)
comma_result_list -> comma_result_list . "," result (rule 22)
CR shift, and go to state 25
"," shift, and go to state 41
nl go to state 42
state 40
async_output -> async_class comma_result_list . nl (rule 14)
comma_result_list -> comma_result_list . "," result (rule 22)
CR shift, and go to state 25
"," shift, and go to state 41
nl go to state 43
state 41
comma_result_list -> comma_result_list "," . result (rule 22)
STRING shift, and go to state 44
result go to state 45
variable go to state 46
state 42
result_record_opt -> token_opt "^" result_class comma_result_list nl . (rule 3)
$default reduce using rule 3 (result_record_opt)
state 43
async_output -> async_class comma_result_list nl . (rule 14)
$default reduce using rule 14 (async_output)
state 44
variable -> STRING . (rule 26)
$default reduce using rule 26 (variable)
state 45
comma_result_list -> comma_result_list "," result . (rule 22)
$default reduce using rule 22 (comma_result_list)
state 46
result -> variable . "=" value (rule 25)
"=" shift, and go to state 47
state 47
result -> variable "=" . value (rule 25)
C_STRING shift, and go to state 48
"{}" shift, and go to state 49
"{" shift, and go to state 50
"[]" shift, and go to state 51
"[" shift, and go to state 52
value go to state 53
const go to state 54
tuple go to state 55
list go to state 56
state 48
const -> C_STRING . (rule 30)
$default reduce using rule 30 (const)
state 49
tuple -> "{}" . (rule 31)
$default reduce using rule 31 (tuple)
state 50
tuple -> "{" . result comma_result_list "}" (rule 32)
STRING shift, and go to state 44
result go to state 57
variable go to state 46
state 51
list -> "[]" . (rule 33)
$default reduce using rule 33 (list)
state 52
list -> "[" . value comma_value_list "]" (rule 34)
list -> "[" . result comma_result_list "]" (rule 35)
STRING shift, and go to state 44
C_STRING shift, and go to state 48
"{}" shift, and go to state 49
"{" shift, and go to state 50
"[]" shift, and go to state 51
"[" shift, and go to state 52
result go to state 58
variable go to state 46
value go to state 59
const go to state 54
tuple go to state 55
list go to state 56
state 53
result -> variable "=" value . (rule 25)
$default reduce using rule 25 (result)
state 54
value -> const . (rule 27)
$default reduce using rule 27 (value)
state 55
value -> tuple . (rule 28)
$default reduce using rule 28 (value)
state 56
value -> list . (rule 29)
$default reduce using rule 29 (value)
state 57
tuple -> "{" result . comma_result_list "}" (rule 32)
$default reduce using rule 21 (comma_result_list)
comma_result_list go to state 60
state 58
list -> "[" result . comma_result_list "]" (rule 35)
$default reduce using rule 21 (comma_result_list)
comma_result_list go to state 61
state 59
list -> "[" value . comma_value_list "]" (rule 34)
$default reduce using rule 23 (comma_value_list)
comma_value_list go to state 62
state 60
comma_result_list -> comma_result_list . "," result (rule 22)
tuple -> "{" result comma_result_list . "}" (rule 32)
"," shift, and go to state 41
"}" shift, and go to state 63
state 61
comma_result_list -> comma_result_list . "," result (rule 22)
list -> "[" result comma_result_list . "]" (rule 35)
"," shift, and go to state 41
"]" shift, and go to state 64
state 62
comma_value_list -> comma_value_list . "," value (rule 24)
list -> "[" value comma_value_list . "]" (rule 34)
"," shift, and go to state 65
"]" shift, and go to state 66
state 63
tuple -> "{" result comma_result_list "}" . (rule 32)
$default reduce using rule 32 (tuple)
state 64
list -> "[" result comma_result_list "]" . (rule 35)
$default reduce using rule 35 (list)
state 65
comma_value_list -> comma_value_list "," . value (rule 24)
C_STRING shift, and go to state 48
"{}" shift, and go to state 49
"{" shift, and go to state 50
"[]" shift, and go to state 51
"[" shift, and go to state 52
value go to state 67
const go to state 54
tuple go to state 55
list go to state 56
state 66
list -> "[" value comma_value_list "]" . (rule 34)
$default reduce using rule 34 (list)
state 67
comma_value_list -> comma_value_list "," value . (rule 24)
$default reduce using rule 24 (comma_value_list)
state 68
$ go to state 69
state 69
$ go to state 70
state 70
$default accept
^ permalink raw reply [flat|nested] 9+ messages in thread