Ошибка в примере грамматики для Fsyacc? - PullRequest
Новая
       24

Ошибка в примере грамматики для Fsyacc?

1 голос
/ 15 января 2011

Поэтому я пытаюсь написать компилятор на F # и изучаю инструменты Fslex и Fsyacc, которые поставляются с F # powerpack. Есть пример проекта, в котором рассматриваются внешние инструменты сборки, которые я пытался понять. Его можно скачать здесь . Пример компилируется и запускается для меня, но я думаю, что в грамматике есть небольшая ошибка. Я говорю тонко, потому что грамматика выглядит аналогично тому, что я видел в книге Дракона для разбора выражений, и у меня нет опыта, чтобы определить это.

Вход «4 * 5 + 3» правильно оценен до 23.

Вход 4 * 5-3, однако, генерирует ошибку разбора. Это ошибка в коде, сгенерированном Fsyacc.

Буду признателен за помощь в лучшем понимании проблемы, чтобы я был лучше информирован и имел больше уверенности в Fsyacc Я разместил файл * .fsy ниже. 

// This is the type of the data produced by a successful reduction of the 'start'
// symbol:
%type < Ast.Equation > start

%%

// These are the rules of the grammar along with the F# code of the 
// actions executed as rules are reduced.  In this case the actions 
// produce data using F# data construction terms.
start: Prog { Equation($1) }

Prog:
    | Expr EOF                  { $1 }

Expr: 
    | Expr PLUS  Term           { Plus($1, $3)  }
    | Expr MINUS Term           { Minus($1, $3) }
    | Term                      { Term($1)      }

Term:
    | Term ASTER Factor         { Times($1, $3)  }
    | Term SLASH Factor         { Divide($1, $3) }
    | Factor                    { Factor($1)     }

Factor:
    | FLOAT                     { Float($1)  }
    | INT32                     { Integer($1) }
    | LPAREN Expr RPAREN        { ParenEx($2) }

А вот определение для типа данных AST 

namespace Ast
open System

type Factor =
    | Float   of Double
    | Integer of Int32
    | ParenEx of Expr

and Term =
    | Times  of Term * Factor
    | Divide of Term * Factor
    | Factor of Factor

and Expr =
    | Plus  of Expr * Term
    | Minus of Expr * Term
    | Term  of Term

and Equation =
    | Equation of Expr

EDIT

Я также опубликовал определение лексера и код для управления синтаксическим анализатором, чтобы помочь понять ошибку. 

{
module Lexer
open System
open Parser
open Microsoft.FSharp.Text.Lexing

let lexeme lexbuf =
    LexBuffer<char>.LexemeString lexbuf
}

// These are some regular expression definitions
let digit = ['0'-'9']
let whitespace = [' ' '\t' ]
let 

newline = ('\n' | '\r' '\n')

rule tokenize = parse
| whitespace    { tokenize lexbuf }
| newline       { tokenize lexbuf }
// Operators
| "+"           { PLUS }
| "-"           { MINUS }
| "*"           { ASTER }
| "/"           { SLASH }
// Misc
| "("           { LPAREN }
| ")"           { RPAREN }
// Numberic constants
| ['-']?digit+                                  { INT32 (Int32.Parse(lexeme lexbuf)) }
| ['-']?digit+('.'digit+)?(['e''E']digit+)?     { FLOAT (Double.Parse(lexeme lexbuf)) }
// EOF
| eof   { EOF }

Наконец, код для управления анализатором. 

    // This project type requires the F# PowerPack at http://fsharppowerpack.codeplex.com/releases
    // Learn more about F# at http://fsharp.net
    // Original project template by Jomo Fisher based on work of Brian McNamara, Don Syme and Matt Valerio
    // This posting is provided "AS IS" with no warranties, and confers no rights.

    open System
    open Microsoft.FSharp.Text.Lexing

    open Ast
    open Lexer
    open Parser

    /// Evaluate a factor
    let rec evalFactor factor =
        match factor with
        | Float x   -> x
        | Integer x -> float x
        | ParenEx x -> evalExpr x

    /// Evaluate a term
    and evalTerm term =
        match term with
        | Times (term1, term2)  -> (evalTerm term1) * (evalTerm term2)
        | Divide (term1, term2)  -> (evalTerm term1) / (evalTerm term2)
        | Factor fact         -> evalFactor fact

    /// Evaluate an expression
    and evalExpr expr =
        match expr with
        | Plus (expr1, expr2)  -> (evalExpr expr1) + (evalExpr expr2)
        | Minus (expr1, expr2)  -> (evalExpr expr1) - (evalExpr expr2)
        | Term term          -> evalTerm term

    /// Evaluate an equation
    and evalEquation eq =
        match eq with
        | Equation expr -> evalExpr expr

    printfn "Calculator"

    let rec readAndProcess() =
        printf ":"
        match Console.ReadLine() with
        | "quit" -> ()
        | expr ->
            try
                printfn "Lexing [%s]" expr
                let lexbuff = LexBuffer<char>.FromString(expr)

                printfn "Parsing..."
                let equation = Parser.start Lexer.tokenize lexbuff

                printfn "Evaluating Equation..."
                let result = evalEquation equation

                printfn "

Result: %s" (result.ToString())

        with ex ->
            printfn "Unhandled Exception: %s" ex.Message

        readAndProcess()

readAndProcess()

EDIT: дополнительный минус в лексере был проблемой. После удаления образец работает как положено.

1 Ответ

3 голосов
/ 15 января 2011

Я только взглянул, похоже, лексер, возможно, лечит 

// Numberic constants 
| ['-']?digit+                                  { INT32 (Int32.Parse(lexeme lexbuf)) } 
etc

знак минус здесь 

4*5-3

как унарная часть константы "-3", а не как двоичный минус. Поэтому я согласен, что это ошибка в образце. Я бы избавился от необязательного минуса в лексере и добавил бы правило в синтаксический анализатор в соответствии с фактором, например, например. "МИНУС ИНТ32".

Просто набросок того, как это исправить, надеюсь, это поможет вам, или вы получите еще один более подробный ответ с полным кодом.

...