GDB/MI Output Syntax ambiguity

GDB/MI Output Syntax ambiguity

[Bob Rossi]

Hi,

I am generating a bottom up parser for 'GDB/MI Output Syntax' using
bison. Unfortunately, I think that I found an ambiguity, which makes it
not easily parsable. Please correct me if I am wrong.

output                  -> ( out-of-band-record )* [ result-record ] "(gdb)" nl
result-record           -> [ token ] "^" result-class ( "," result )* nl
out-of-band-record      -> async-record | stream-record
async-record            -> exec-async-output | status-async-output | notify-asyn
exec-async-output       -> [ token ] "*" async-output
status-async-output     -> [ token ] "+" async-output
notify-async-output     -> [ token ] "=" async-output

I am assuming that the grammar above for 'output' means that there can
be 0 or more 'out-of-band-record', followed by 0 or 1 'result-record',
followed by '(gdb)' and then a newline.

The problem is, when you are parsing 'output', and you get a 'token' as
the first token from the lexer, you don't know if that is part of the 
'out-of-band-record' or if it is part of the 'result-record'. Both of 
these rules optionally start with 'token'.Has anyone actually written a 
recursive descent parser, or generated a parser from bison for GDB/MI's 
output yet, or am I the first?

Help would be greatly appreciated. This is the only shift/reduce
conflict I have in my modified BNF version of the grammar. Other than
this, the grammar looks very well written.

I consider this to be a serious problem so I hope that I am not doing
something incorrectly or am mis-understanding the grammar.

Thanks,
Bob Rossi

Re: GDB/MI Output Syntax ambiguity

[Daniel Jacobowitz]

On Mon, Aug 23, 2004 at 05:03:14PM -0400, Bob Rossi wrote:
> Hi,
> 
> I am generating a bottom up parser for 'GDB/MI Output Syntax' using
> bison. Unfortunately, I think that I found an ambiguity, which makes it
> not easily parsable. Please correct me if I am wrong.
> 
> output                  -> ( out-of-band-record )* [ result-record ] "(gdb)" nl
> result-record           -> [ token ] "^" result-class ( "," result )* nl
> out-of-band-record      -> async-record | stream-record
> async-record            -> exec-async-output | status-async-output | notify-asyn
> exec-async-output       -> [ token ] "*" async-output
> status-async-output     -> [ token ] "+" async-output
> notify-async-output     -> [ token ] "=" async-output
> 
> I am assuming that the grammar above for 'output' means that there can
> be 0 or more 'out-of-band-record', followed by 0 or 1 'result-record',
> followed by '(gdb)' and then a newline.

This is easily solved.  For instance, factor the optional token out of
async-record and result-record, and handle output as:
 output     -> [token] ( out-of-band-record-1 [token] )* [ result-record ] "(gdb)" nl


I'm not sure how faithful to the documented grammar GDB is... but
that's a separate problem.

-- 
Daniel Jacobowitz

Re: GDB/MI Output Syntax ambiguity

[Bob Rossi]

On Mon, Aug 23, 2004 at 05:09:24PM -0400, Daniel Jacobowitz wrote:
> On Mon, Aug 23, 2004 at 05:03:14PM -0400, Bob Rossi wrote:
> > Hi,
> > 
> > I am generating a bottom up parser for 'GDB/MI Output Syntax' using
> > bison. Unfortunately, I think that I found an ambiguity, which makes it
> > not easily parsable. Please correct me if I am wrong.
> > 
> > output                  -> ( out-of-band-record )* [ result-record ] "(gdb)" nl
> > result-record           -> [ token ] "^" result-class ( "," result )* nl
> > out-of-band-record      -> async-record | stream-record
> > async-record            -> exec-async-output | status-async-output | notify-asyn
> > exec-async-output       -> [ token ] "*" async-output
> > status-async-output     -> [ token ] "+" async-output
> > notify-async-output     -> [ token ] "=" async-output
> > 
> > I am assuming that the grammar above for 'output' means that there can
> > be 0 or more 'out-of-band-record', followed by 0 or 1 'result-record',
> > followed by '(gdb)' and then a newline.
> 
> This is easily solved.  For instance, factor the optional token out of
> async-record and result-record, and handle output as:
>  output     -> [token] ( out-of-band-record-1 [token] )* [ result-record ] "(gdb)" nl
> 
> 
> I'm not sure how faithful to the documented grammar GDB is... but
> that's a separate problem.

Thanks! Hopefully it won't be to long before I'm done :)
Bob Rossi

Re: GDB/MI Output Syntax ambiguity

[Bob Rossi]

On Mon, Aug 23, 2004 at 05:09:24PM -0400, Daniel Jacobowitz wrote:
> On Mon, Aug 23, 2004 at 05:03:14PM -0400, Bob Rossi wrote:
> > Hi,
> > 
> > I am generating a bottom up parser for 'GDB/MI Output Syntax' using
> > bison. Unfortunately, I think that I found an ambiguity, which makes it
> > not easily parsable. Please correct me if I am wrong.
> > 
> > output                  -> ( out-of-band-record )* [ result-record ] "(gdb)" nl
> > result-record           -> [ token ] "^" result-class ( "," result )* nl
> > out-of-band-record      -> async-record | stream-record
> > async-record            -> exec-async-output | status-async-output | notify-asyn
> > exec-async-output       -> [ token ] "*" async-output
> > status-async-output     -> [ token ] "+" async-output
> > notify-async-output     -> [ token ] "=" async-output
> > 
> > I am assuming that the grammar above for 'output' means that there can
> > be 0 or more 'out-of-band-record', followed by 0 or 1 'result-record',
> > followed by '(gdb)' and then a newline.
> 
> This is easily solved.  For instance, factor the optional token out of
> async-record and result-record, and handle output as:
>  output     -> [token] ( out-of-band-record-1 [token] )* [ result-record ] "(gdb)" nl
> 
> 
> I'm not sure how faithful to the documented grammar GDB is... but
> that's a separate problem.
> 
> -- 
> Daniel Jacobowitz

I Emailed this directly to Daniel, but it's probably worth it if other
people get to see the problem.

I have a modified BNF that is pretty small, however, this one
grammar problem I can not get passed. Your solution looks close,
however, I don't think it's completly correct.

'possible-token' is the beggining of both 'oob-record-prime' and
'possible-result-record'.  I could move the 'possible-token' from
'result-record' to 'possible-result-record', but I can not move it up to
the 'output' rule, because this would allow a possible token, and then
not a possible result record. That would be illegal for the GDB/MI
output syntax.

I have a feeling this isn't a solvable problem, but I hope it is.

It's been a long time since compiler design :)

output                  -> oob-record-prime possible-result-record "(gdb)" nl
oob-record-prime        -> oob-record-list | epsilon
oob-record-list         -> oob-record-list oob-record | oob-record
possible-result-record  -> result-record | epsilon
result-record           -> possible-token "^" result-class result-list-prime nl
oob-record              -> async-record | stream-record
async-record            -> exec-async-output | status-async-output |
+notify-async-output
exec-async-output       -> possible-token "*" async-output
status-async-output     -> possible-token "+" async-output
notify-async-output     -> possible-token "=" async-output
async-output            -> async-class result-list-prime nl
result-class            -> "done" | "running" | "connected" | "error" | "exit"
async-class             -> "stopped"
result-list-prime       -> result-list | epsilon
result-list             -> result-list "," result | "," result
result                  -> variable "=" value
variable                -> string
value-list-prime        -> value-list | epsilon
value-list              -> value-list "," value | "," value
value                   -> const | tuple | list
const                   -> c-string
tuple                   -> "{}" | "{" result result-list-prime "}"
list                    -> "[]" | "[" value value-list-prime "]" | "[" result
+result-list-prime "]"
stream-record           -> console-stream-output | target-stream-output |
+log-stream-output
console-stream-output   -> "~" c-string
target-stream-output    -> "@" c-string
log-stream-output       -> "&" c-string
nl                      -> CR | CR-LF
possible-token          -> token | epsilon
token                   -> any sequence of digits.

Thanks,
Bob Rossi

Re: GDB/MI Output Syntax ambiguity

[Michael Chastain]

It's been a while since I wrote a yacc grammar, but my inclination
would be to enhance the lexer and distinguish some new terminals:

  TOKEN-UPARROW
  TOKEN-STAR
  TOKEN-PLUS
  TOKEN-EQUALS

Then the grammar goes from LALR(2) to LALR(1), because
result-record can start with TOKEN-UPARROW, which is just
one symbol, rather than token "^", which is two symbols.
That ought to make it yacc-parseable.

That keeps the token numbers in the natural place.

With drow's rule:

 output     -> [token] ( out-of-band-record-1 [token] )* [ result-record ] "(gdb)" nl

This is also LALR(1), but the token symbol is not bundled with
the wrong out-of-band-record-1, so the tree-value-constructing
code gets a little skewed.

But I'm rusty on all this.

Re: GDB/MI Output Syntax ambiguity

[Bob Rossi]

On Mon, Aug 23, 2004 at 05:43:05PM -0400, Michael Chastain wrote:
> It's been a while since I wrote a yacc grammar, but my inclination
> would be to enhance the lexer and distinguish some new terminals:
> 
>   TOKEN-UPARROW
>   TOKEN-STAR
>   TOKEN-PLUS
>   TOKEN-EQUALS
> 
> Then the grammar goes from LALR(2) to LALR(1), because
> result-record can start with TOKEN-UPARROW, which is just
> one symbol, rather than token "^", which is two symbols.
> That ought to make it yacc-parseable.

Yes, this could work. However, was the original grammer meant to be
LALR(2)?

I am going to try to do some Left Factoring to fix the problem but I
don't think it will work. Plus, I don't have to much experience with
this.

Thanks,
Bob Rossi

Re: GDB/MI Output Syntax ambiguity

[Michael Chastain]

[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

Re: GDB/MI Output Syntax ambiguity

[Bob Rossi]

On Mon, Aug 23, 2004 at 11:56:18PM -0400, Michael Chastain wrote:
> [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.

I will compare the grammar more in detail. However, these are the 5
rules I applied to get the MI grammar to not have any left recursions.

1. (out-of-band-record)* ->
    out-of-band-record-prime -> out-of-band-record-list | epsilon
    out-of-band-record-list  -> out-of-band-record-list out-of-band-record | out-of-band-record

2. [result-record]
    possible-result-record -> result-record | epsilon

3. [token]
    possible-token -> token | epsilon

4. ( "," result )*
    result-list-prime -> result-list | epsilon
    result-list       -> result-list "," result | "," result

5. ( "," value )*
    value-list-prime -> value-list | epsilon
    value-list       -> value-list "," value | "," value

Other than that, I think it's all still the same.
I will compare the grammars in more detail today.

Thanks for putting in the great effort!
Bob Rossi

RE: GDB/MI Output Syntax ambiguity

[Xinan Tang]

Hi 

  If it is a shift/reduce conflict, you can ignore it if the shift is
your choice. By default the shift is a default action. If there is
reduce/reduce conflicts, then you need to start to worry.

--Xinan


-----Original Message-----
From: gdb-owner@sources.redhat.com [mailto:gdb-owner@sources.redhat.com]
On Behalf Of Bob Rossi
Sent: Monday, August 23, 2004 1:03 PM
To: gdb@sources.redhat.com
Subject: GDB/MI Output Syntax ambiguity

Hi,

I am generating a bottom up parser for 'GDB/MI Output Syntax' using
bison. Unfortunately, I think that I found an ambiguity, which makes it
not easily parsable. Please correct me if I am wrong.

output                  -> ( out-of-band-record )* [ result-record ]
"(gdb)" nl
result-record           -> [ token ] "^" result-class ( "," result )* nl
out-of-band-record      -> async-record | stream-record
async-record            -> exec-async-output | status-async-output |
notify-asyn
exec-async-output       -> [ token ] "*" async-output
status-async-output     -> [ token ] "+" async-output
notify-async-output     -> [ token ] "=" async-output

I am assuming that the grammar above for 'output' means that there can
be 0 or more 'out-of-band-record', followed by 0 or 1 'result-record',
followed by '(gdb)' and then a newline.

The problem is, when you are parsing 'output', and you get a 'token' as
the first token from the lexer, you don't know if that is part of the 
'out-of-band-record' or if it is part of the 'result-record'. Both of 
these rules optionally start with 'token'.Has anyone actually written a 
recursive descent parser, or generated a parser from bison for GDB/MI's 
output yet, or am I the first?

Help would be greatly appreciated. This is the only shift/reduce
conflict I have in my modified BNF version of the grammar. Other than
this, the grammar looks very well written.

I consider this to be a serious problem so I hope that I am not doing
something incorrectly or am mis-understanding the grammar.

Thanks,
Bob Rossi