Fsyacc的示例语法错误？ [英] Error in example grammar for Fsyacc?

问题描述

因此，我试图在F＃中编写一个编译器，并且一直在查看F＃powerpack附带的Fslex和Fsyacc工具。有一个样例项目，负责处理我一直试图理解的外部构建工具。可以下载此处。这个例子为我编译和运行，但我认为语法中有一个微妙的错误。我说的很微妙，因为语法看起来类似于我在龙书中解析表达式，我没有经验来发现它。

输入4 * 5 + 3正确评估为23。

然而，输入4 * 5-3会生成解析错误。这是Fsyacc生成的代码中的错误。

我将感谢您帮助我们更好地了解问题所在，以便我能更好地了解Fsyacc并更有信心。我已经张贴的* .fsy文件下面。

  //这是成功减少'start'所产生的数据类型
 //符号：
％type< Ast.Equation> start 
 
 %% 
 
 //这些是语法的规则以及
 //执行的操作的F＃代码，因为规则被减少。在这种情况下，操作
 //使用F＃数据构造术语产生数据。 
 start：Prog {Equation（$ 1）} 
 
 Prog：
 | Expr EOF {$ 1} 
 
 Expr：
 | Expr PLUS Term {Plus（$ 1，$ 3）} 
 | Expr MINUS期限{减去（$ 1，$ 3）} 
 |期限{Term（$ 1）} 
 
期限：
 |术语ASTER因子{Times（$ 1，$ 3）} 
 |术语SLASH因子{Divide（$ 1，$ 3）} 
 |因子{因子（$ 1）} 
 
因子：
 | FLOAT {Float（$ 1）} 
 | INT32 {Integer（$ 1）} 
 | LPAREN Expr RPAREN {ParenEx（$ 2）} 
  

这里是AST数据类型的定义

 命名空间Ast 
打开系统
 
类型Factor = 
 |双浮动
 | Int32的整数
 | Expr 
 
的ParenEx和Term = 
 |期限*因子
 |期限*因子
 |因子因子
 
和Expr = 
 |加上Expr * Term 
 |减去减法*项
 |期限
 
和等式= 
 | Expr的方程
  

EDIT

发布了lexer定义和代码来驱动解析器，以帮助理解错误。

  {
模块Lexer 
 open系统
打开解析器
打开Microsoft.FSharp.Text.Lexing 
 
让lexeme lexbuf = 
 LexBuffer< char> .LexemeString lexbuf 
} 
 
 //这些是一些正则表达式定义
 let digit = ['0' - '9'] 
 let whitespace = ['''\t' ] 
 let 
 
 newline =（'\\\
'|'\r''\\\
'）
 
 rule tokenize = parse 
 | whitespace {tokenize lexbuf} 
 | newline {tokenize lexbuf} 
 //运算符
 | +{PLUS} 
 |  - {MINUS} 
 | *{ASTER} 
 | /{SLASH} 
 // Misc 
 | （{LPAREN} 
 |）{RPAREN} 
 //数字常量
 | [' - ']？digit + {INT32（Int32.Parse（lexeme lexbuf））} 
 | [' - ']？digit +（'。'digit +）？（['e''E'] digit +）？ {FLOAT（Double.Parse（lexeme lexbuf））} 
 // EOF 
 | eof {EOF} 
  

最后是驱动解析器的代码。

  //这个项目类型需要F＃PowerPack在http://fsharppowerpack.codeplex.com/releases 
 //了解更多关于F＃在http： //fsharp.net 
 // Jomo Fisher的原始项目模板基于Brian McNamara，Don Syme和Matt Valerio的工作
 //此发布是按原样提供，没有保证，并且不赋予权利。 
 
 open系统
打开Microsoft.FSharp.Text.Lexing 
 
打开Ast 
打开Lexer 
打开解析器
 
 ///评估因子
让rec evalFactor因子= 
匹配因子与
 |浮点x  - > x 
 |整数x  - > float x 
 | ParenEx x  - > evalExpr x 
 
 ///评估术语
和evalTerm term = 
匹配术语与
 |时间（term1，term2） - > （evalTerm term1）*（evalTerm term2）
 | Divide（term1，term2） - > （evalTerm term1）/（evalTerm term2）
 |因子事实> evalFactor fact 
 
 ///评估表达式
和evalExpr expr = 
匹配expr与
 | Plus（expr1，expr2） - > （evalExpr expr1）+（evalExpr expr2）
 |减去（expr1，expr2） - > （evalExpr expr1） - （evalExpr expr2）
 |术语术语> evalTerm term 
 
 ///评估方程
和evalEquation eq = 
匹配eq和
 |等式expr  - > evalExpr expr 
 
 printfnCalculator
 
 let rec readAndProcess（）= 
 printf：
匹配Console.ReadLine b | quit - > （）
 | expr  - > 
 try 
 printfnLexing [％s]expr 
 let lexbuff = LexBuffer< char> .FromString（expr）
 
 printfnParsing ...
 let equation = Parser.start Lexer.tokenize lexbuff 
 
 printfnEvaluating Equation ...
 let result = evalEquation方程
 
 printfn
 
结果：％s（result.ToString（））
 
 with ex  - > 
 printfn未处理的异常：％sex.Message 
 
 readAndProcess（）
 
 readAndProcess（）
  pre> 
 
 
编辑：词法分析器中的可选减号是问题。删除它之后，样例按预期工作。
解决方案
我只看过，看起来lexer可能正在处理
  //数字常量
 | [' - ']？digit + {INT32（Int32.Parse（lexeme lexbuf））} 
 etc 
  
此处的减号
  4 * 5-3 
  
作为一元，是常量-3的一部分，而不是二进制减。所以我同意这是一个错误的样品。我将删除在词法分析器中的可选减号，并在解析器中添加一条规则，沿着因子转到例如。 MINUS INT32。
 
 
 
只是一个如何修复它的草图，希望这将引导你或你会得到另一个更深入的答案与完整的代码。 / p> 
So I am trying to write a compiler in F# and have been looking at the Fslex and Fsyacc tools that come with the F# powerpack. There is a sample project that takes care of the external build tools that I have been trying to understand. It can be downloaded here. The example compiles and runs for me, but I think there is a subtle error in the grammar. I say subtle, because the grammar looks similar to what I have seen in the Dragon book for parsing expressions and I don't have the experience to spot it.

The input "4*5+3" correctly evaluated to 23.

The input 4*5-3, however, generates a parse error. That is an error in the code generated by Fsyacc.

I would appreciate your help in better understanding what the problem so I can be better informed and have more confidence in Fsyacc. I have posted the *.fsy file below. 
// 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) }
And here is the definition for AST data type
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

I have posted the lexer definition and the code to drive the parser as well to help with understanding the error.
{
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 }
Lastly, the code to drive the parser.
    // 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:  The optional minus sign in the lexer was the problem. After removing it the sample works as expected.
解决方案
I have only glanced, it looks like the lexer perhaps is treating
// Numberic constants 
| ['-']?digit+                                  { INT32 (Int32.Parse(lexeme lexbuf)) } 
etc
the minus sign here
4*5-3
as unary, part of the constant "-3" rather than as a binary minus.  So I agree it is an error in the sample.  I would get rid of the optional minus in the lexer, and add a rule in the parser along the lines of Factor going to e.g. "MINUS INT32".

Just a sketch of how to fix it, hopefully this will steer you or you'll get another more in-depth answer with full code.

                        
这篇关于Fsyacc的示例语法错误？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！