Analisi dei numeri in FParsec

Question

Ho iniziato a imparare FParsec. Ha un modo molto flessibile di analizzare i numeri; Posso fornire una serie di formati numerici voglio usare:

type Number = 
    | Numeral of int 
    | Decimal of float 
    | Hexadecimal of int 
    | Binary of int 

let numberFormat = NumberLiteralOptions.AllowFraction 
        ||| NumberLiteralOptions.AllowHexadecimal 
        ||| NumberLiteralOptions.AllowBinary 

let pnumber = 
    numberLiteral numberFormat "number" 
    |>> fun num -> if num.IsHexadecimal then Hexadecimal (int num.String) 
        elif num.IsBinary then Binary (int num.String) 
        elif num.IsInteger then Numeral (int num.String) 
        else Decimal (float num.String) 

Tuttavia, la lingua che sto cercando di analizzare è un po 'strano. Un numero potrebbe essere numerale (non negativo int), decimale (non negativo float), esadecimale (con il prefisso #x) o binari (con il prefisso #b):

numeral: 0, 2 
decimal: 0.2, 2.0 
hexadecimal: #xA04, #x611ff 
binary: #b100, #b001 

Adesso devo fare parsing due volte da sostituendo # da 0 (se necessario) per fare uso di pnumber:

let number: Parser<_, unit> = 
    let isDotOrDigit c = isDigit c || c = '.' 
    let numOrDec = many1Satisfy2 isDigit isDotOrDigit 
    let hexOrBin = skipChar '#' >>. manyChars (letter <|> digit) |>> sprintf "0%s" 
    let str = spaces >>. numOrDec <|> hexOrBin 
    str |>> fun s -> match run pnumber s with 
        | Success(result, _, _) -> result 
        | Failure(errorMsg, _, _) -> failwith errorMsg 

Che è un modo migliore di analizzare in questo caso? O come posso alterare il CharStream di FParsec per rendere l'analisi condizionale più semplice?

Answer 1

I numeri di analisi possono essere piuttosto complicati se si desidera generare buoni messaggi di errore e verificare correttamente la presenza di overflow.

La seguente è una semplice implementazione FParsec del vostro numero di parser:

let numeralOrDecimal : Parser<_, unit> = 
    // note: doesn't parse a float exponent suffix 
    numberLiteral NumberLiteralOptions.AllowFraction "number" 
    |>> fun num -> 
      // raises an exception on overflow 
      if num.IsInteger then Numeral(int num.String) 
      else Decimal(float num.String) 

let hexNumber =  
    pstring "#x" >>. many1SatisfyL isHex "hex digit" 
    |>> fun hexStr -> 
      // raises an exception on overflow 
      Hexadecimal(System.Convert.ToInt32(hexStr, 16)) 

let binaryNumber =  
    pstring "#b" >>. many1SatisfyL (fun c -> c = '0' || c = '1') "binary digit" 
    |>> fun hexStr -> 
      // raises an exception on overflow 
      Binary(System.Convert.ToInt32(hexStr, 2)) 


let number = 
    choiceL [numeralOrDecimal 
      hexNumber 
      binaryNumber] 
      "number literal" 

Generazione di buoni messaggi di errore sul overflow complicherebbe questa implementazione un po ', come si farebbe in posizione ideale anche bisogno di fare marcia indietro dopo l'errore, in modo che la posizione dell'errore termina all'inizio del numero letterale (vedere i documenti numberLiteral per un esempio).

Un modo semplice per gestire con garbo possibile eccezione di overflow è quello di utilizzare un po 'di combinatore gestione delle eccezioni come la seguente:

let mayThrow (p: Parser<'t,'u>) : Parser<'t,'u> = 
    fun stream -> 
     let state = stream.State   
     try 
      p stream 
     with e -> // catching all exceptions is somewhat dangerous 
      stream.BacktrackTo(state) 
      Reply(FatalError, messageError e.Message) 

È quindi possibile scrivere

let number = mayThrow (choiceL [...] "number literal") 

io non sono sicuro di quello che intendeva dire con "alterare il CharStream di FParsec per rendere più semplice l'analisi condizionale", ma nell'esempio seguente viene illustrato come scrivere un'implementazione di basso livello che utilizza solo i metodi CharStream direttamente.

type NumberStyles = System.Globalization.NumberStyles 
let invariantCulture = System.Globalization.CultureInfo.InvariantCulture 

let number: Parser<Number, unit> = 
    let expectedNumber = expected "number" 
    let inline isBinary c = c = '0' || c = '1' 
    let inline hex2int c = (int c &&& 15) + (int c >>> 6)*9 

    let hexStringToInt (str: string) = // does no argument or overflow checking   
     let mutable n = 0 
     for c in str do 
      n <- n*16 + hex2int c 
     n  

    let binStringToInt (str: string) = // does no argument or overflow checking 
     let mutable n = 0 
     for c in str do 
      n <- n*2 + (int c - int '0') 
     n 

    let findIndexOfFirstNonNull (str: string) = 
     let mutable i = 0 
     while i < str.Length && str.[i] = '0' do 
      i <- i + 1 
     i 

    let isHexFun = id isHex // tricks the compiler into caching the function object 
    let isDigitFun = id isDigit 
    let isBinaryFun = id isBinary 

    fun stream -> 
    let start = stream.IndexToken 
    let cs = stream.Peek2()   
    match cs.Char0, cs.Char1 with 
    | '#', 'x' -> 
     stream.Skip(2) 
     let str = stream.ReadCharsOrNewlinesWhile(isHexFun, false) 
     if str.Length <> 0 then 
      let i = findIndexOfFirstNonNull str 
      let length = str.Length - i 
      if length < 8 || (length = 8 && str.[i] <= '7') then 
       Reply(Hexadecimal(hexStringToInt str)) 
      else 
       stream.Seek(start) 
       Reply(Error, messageError "hex number literal is too large for 32-bit int") 
     else 
      Reply(Error, expected "hex digit") 

    | '#', 'b' -> 
     stream.Skip(2) 
     let str = stream.ReadCharsOrNewlinesWhile(isBinaryFun, false) 
     if str.Length <> 0 then 
      let i = findIndexOfFirstNonNull str 
      let length = str.Length - i 
      if length < 32 then 
       Reply(Binary(binStringToInt str)) 
      else 
       stream.Seek(start) 
       Reply(Error, messageError "binary number literal is too large for 32-bit int") 
     else 
      Reply(Error, expected "binary digit") 

    | c, _ -> 
     if not (isDigit c) then Reply(Error, expectedNumber) 
     else 
      stream.SkipCharsOrNewlinesWhile(isDigitFun) |> ignore 
      if stream.Skip('.') then 
       let n2 = stream.SkipCharsOrNewlinesWhile(isDigitFun) 
       if n2 <> 0 then 
        // we don't parse any exponent, as in the other example 
        let mutable result = 0. 
        if System.Double.TryParse(stream.ReadFrom(start), 
               NumberStyles.AllowDecimalPoint, 
               invariantCulture, 
               &result) 
        then Reply(Decimal(result)) 
        else 
         stream.Seek(start) 
         Reply(Error, messageError "decimal literal is larger than System.Double.MaxValue")      
       else 
        Reply(Error, expected "digit") 
      else 
       let decimalString = stream.ReadFrom(start) 
       let mutable result = 0 
       if System.Int32.TryParse(stream.ReadFrom(start), 
             NumberStyles.None, 
             invariantCulture, 
             &result) 
       then Reply(Numeral(result)) 
       else 
        stream.Seek(start) 
        Reply(Error, messageError "decimal number literal is too large for 32-bit int") 

Mentre questa implementazione analizza esagono e numeri binari senza l'aiuto di metodi di sistema, alla fine delega il parsing di numeri decimali ai metodi Int32.TryParse e Double.TryParse.

Come ho detto: è disordinato.