Re: GDB/MI Output Syntax ambiguity

Michael Chastain
2004-08-24T03:56:26Z

[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