Re: GDB/MI Output Syntax ambiguity

[Bob Rossi <bob at brasko dot net>]

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