解析一个函数的调用 - FParsec
Parser the call of a function - FParsec
我尝试解析一个函数的调用，这里是变体：
add 8 2
add x y
add (inc x) (dec y)
funcWithoutArgs
根据我在代码中分配分析器的方式，也许还有它们的编码方式，我会遇到错误，以及成功但不需要的分析。
例如，这个：
add 4 7
returns 以下 AST：
[Call ("foo",[Number 4]);
Number 7]
因此他只接受第一个参数。
当我这样做时：
foo x y
他把这个 AST 发给我：
[Call ("foo",[Call ("x",[Call ("y",[])])])]
这不是我想要的，因为在这里，每个参数都会调用下一个参数。
另一个例子，当我这样做时：
foo x y
inc x
我得到：
[Call ("foo",[Call ("x",[Call ("y",[Call ("inc",[Call ("x",[])])])])])]
它的作用与上面相同，但还会调用该行后面的代码。当我向我的分析器请求换行时（见代码），它向我发送了这个：
[Call ("foo",[]); Call ("x",[]); Call ("y",[]); Call ("inc",[]); Call ("x",[])]
即使在括号中也不起作用:
foo (x) (y)
给予：
[Call ("foo",[]); Call ("x",[]); Call ("y",[])]
并且：
add (inc x) (dec y)
给予：
Error in Ln: 1 Col: 1
Note: The error occurred on an empty line.
The parser backtracked after:
Error in Ln: 2 Col: 5
add (inc x) (dec y)
^
Expecting: end of input or integer number (32-bit, signed)
The parser backtracked after:
Error in Ln: 2 Col: 10
add (inc x) (dec y)
^
Expecting: ')'
[]
简而言之，我的函数调用分析器不能正常工作。每次我改变一些东西，比如一条新线，一次尝试，或者一个不同的层次结构，有些东西不起作用......
你知道如何解决这个非常烦人的问题吗？
这是使用的最小功能代码：
open FParsec
// Ast
type Expression =
| Number of int
| Call of string * Expression list
type Program = Expression list
// Tools
let private bws p =
spaces >>? p .>>? spaces
let private suiteOf p =
sepEndBy p spaces1
let inline private betweenParentheses p label =
between (pstring "(") (pstring ")") p
<?> (label + " between parentheses")
let private identifier =
many1Satisfy2 isLetter (fun c -> isLetter c)
// Expressions
let rec private call = parse {
let! call = pipe2 (spaces >>? identifier) (spaces >>? parameters)
(fun id parameters -> Call(id, parameters)) // .>>? newline
return call
}
and private parameters = suiteOf expression
and private callFuncWithoutArgs =
identifier |>> fun id -> Call(id, [])
and private number = pint32 |>> Number
and private betweenParenthesesExpression =
parse { let! ex = betweenParentheses expression "expression"
return ex }
and private expression =
bws (attempt betweenParenthesesExpression <|>
attempt number <|>
attempt call <|>
callFuncWithoutArgs)
// -------------------------------
let parse code =
let parser = many expression .>>? eof
match run parser code with
| Success(result, _, _) -> result
| Failure(msg, _, _) ->
printfn "%s" msg
[]
System.Console.Clear()
parse @"
add 4 7
foo x y
inc x
foo (x) (y)
add (inc x) (dec y)
" |> printfn "%A"
您的主要问题是您的解析器的高级设计有误。
你现在的设计是一个表达式可以是：
- 括号之间的表达式（可以说是 "sub-expression"（这里没问题）
- 一个数字（这里没问题）
- 带参数的调用，它是一个标识符，后跟 space 分隔的表达式列表（这是问题的主要部分）
- 不带参数的调用，它是单个标识符（这会导致问题）
看看表达式 foo x y，让我们按照解析器的顺序应用这些规则。没有括号并且 foo 不是数字，所以它不是 3 就是 4。首先我们尝试 3。foo 后跟 x y：x y 是否解析为一种表达？为什么，是的，它确实如此：它解析为带参数的调用，其中 x 是函数，y 是参数。由于 x y 匹配 3，它根据规则 3 进行解析而不检查规则 4，因此 foo x y 匹配类似于 foo (x y) 将：使用单个参数调用 foo，这是使用参数 y.
调用 x
如何解决这个问题？好吧，您可以尝试交换 3 和 4 的顺序，以便在调用带参数的函数调用之前检查不带参数的函数调用（这会使 x y 解析为 x。但那会失败，因为 foo x y 会像 foo 一样匹配。所以将规则 4 放在规则 3 之前在这里不起作用。
真正的解决方案是将表达式的规则拆分为两个级别。 "inner" 级别，我称之为 "value"，可能是：
- 括号中的表达式
- 一个数
- 不带参数的函数调用
"outer" 级别，表达式的解析规则，将是：
- 一个函数调用，带个参数，都是值，不是表达式
- 一个值
请注意，这些解析级别是相互递归的，因此您需要在实现中使用 createParserForwardedToRef。让我们看看 foo x y 将如何使用此设计进行解析：
首先，foo 解析为标识符，因此检查它是否可能是带参数的函数调用。 x 是否解析为一个值？是的，根据价值观规则 3。 y 是否解析为一个值？是的，根据价值观规则 3。所以 foo x y 解析为函数调用。
现在funcWithoutParameters呢？它会失败表达式的规则 1，因为它后面没有参数列表。所以它会检查表达式的规则 2，然后它会根据值的规则 3 进行匹配。
好的，伪代码的基本健全性检查有效，所以让我们把它变成代码。但首先，我会提到你的解析器中的 other 问题，我还没有提到，那就是你没有意识到 FParsec spaces 解析器 also matches newlines。因此，当您将 expression 解析器包装在 bws ("between whitespace") 中时，它还会在解析的文本后使用换行符。因此，当您解析类似以下内容时：
foo a b
inc c
suiteOf expression 看到列表 a b inc c 并将所有这些转换为 foo 的参数。在我下面的代码中，我区分了 FParsec 的 spaces 解析器（包括换行符）和解析器 only horizontal whitespace (space和制表符但不是换行符），在适当的地方使用每个。下面的代码实现了我在这个答案中提到的设计，它的输出对我来说对于你写的所有测试表达式来说都是正确的：
open FParsec
// Ast
type Expression =
| Number of int
| Call of string * Expression list
type Program = Expression list
// Tools
let private justSpaces = skipMany (pchar ' ' <|> pchar '\t')
let private justSpaces1 = skipMany1 (pchar ' ' <|> pchar '\t')
let private bws p =
spaces >>? p .>>? spaces
let private suiteOf p =
sepEndBy1 p (justSpaces1)
let inline private betweenParentheses p label =
between (pstring "(") (pstring ")") p
<?> (label + " between parentheses")
let private identifier =
many1Satisfy2 isLetter (fun c -> isLetter c)
// Expressions
let private expression, expressionImpl = createParserForwardedToRef()
let private betweenParenthesesExpression =
parse { let! ex = betweenParentheses expression "expression"
return ex }
let private callFuncWithoutArgs =
(identifier |>> fun id -> Call(id, []))
let private number = pint32 |>> Number
let private value =
justSpaces >>? (attempt betweenParenthesesExpression <|>
attempt number <|>
callFuncWithoutArgs)
let private parameters = suiteOf value
let rec private callImpl = parse {
let! call = pipe2 (justSpaces >>? identifier) (justSpaces >>? parameters)
(fun id parameters -> Call(id, parameters))
return call }
let call = callImpl
expressionImpl.Value <-
bws (attempt call <|>
value)
// -------------------------------
let parse code =
let parser = many expression .>>? (spaces >>. eof)
match run parser code with
| Success(result, _, _) -> result
| Failure(msg, _, _) ->
printfn "%s" msg
[]
System.Console.Clear()
parse @"
add 4 7
foo x y
inc x
foo (x) (y)
add (inc x) (dec y)
" |> printfn "%A"
P.S。我使用了 http://www.quanttec.com/fparsec/users-guide/debugging-a-parser.html 建议的以下运算符来极大地帮助我跟踪问题：
let (<!>) (p: Parser<_,_>) label : Parser<_,_> =
fun stream ->
printfn "%A: Entering %s" stream.Position label
let reply = p stream
printfn "%A: Leaving %s (%A)" stream.Position label reply.Status
reply
用法：将let parseFoo = ...变成let parseFoo = ... <!> "foo"。然后您将在控制台中获得调试输出流，如下所示：
(Ln: 2, Col: 20): Entering expression
(Ln: 3, Col: 1): Entering call
(Ln: 3, Col: 5): Entering parameters
(Ln: 3, Col: 5): Entering bwParens
(Ln: 3, Col: 5): Leaving bwParens (Error)
(Ln: 3, Col: 5): Entering number
(Ln: 3, Col: 6): Leaving number (Ok)
(Ln: 3, Col: 7): Entering bwParens
(Ln: 3, Col: 7): Leaving bwParens (Error)
(Ln: 3, Col: 7): Entering number
(Ln: 3, Col: 8): Leaving number (Ok)
(Ln: 3, Col: 8): Leaving parameters (Ok)
(Ln: 3, Col: 8): Leaving call (Ok)
(Ln: 3, Col: 8): Leaving expression (Ok)
当您试图弄清楚为什么您的解析器没有按照您的预期运行时，这会很有帮助。
我尝试解析一个函数的调用，这里是变体：
add 8 2
add x y
add (inc x) (dec y)
funcWithoutArgs
根据我在代码中分配分析器的方式，也许还有它们的编码方式，我会遇到错误，以及成功但不需要的分析。 例如，这个：
add 4 7
returns 以下 AST：
[Call ("foo",[Number 4]);
Number 7]
因此他只接受第一个参数。
当我这样做时：
foo x y
他把这个 AST 发给我：
[Call ("foo",[Call ("x",[Call ("y",[])])])]
这不是我想要的，因为在这里，每个参数都会调用下一个参数。
另一个例子，当我这样做时：
foo x y
inc x
我得到：
[Call ("foo",[Call ("x",[Call ("y",[Call ("inc",[Call ("x",[])])])])])]
它的作用与上面相同，但还会调用该行后面的代码。当我向我的分析器请求换行时（见代码），它向我发送了这个：
[Call ("foo",[]); Call ("x",[]); Call ("y",[]); Call ("inc",[]); Call ("x",[])]
即使在括号中也不起作用:
foo (x) (y)
给予：
[Call ("foo",[]); Call ("x",[]); Call ("y",[])]
并且：
add (inc x) (dec y)
给予：
Error in Ln: 1 Col: 1
Note: The error occurred on an empty line.
The parser backtracked after:
Error in Ln: 2 Col: 5
add (inc x) (dec y)
^
Expecting: end of input or integer number (32-bit, signed)
The parser backtracked after:
Error in Ln: 2 Col: 10
add (inc x) (dec y)
^
Expecting: ')'
[]
简而言之，我的函数调用分析器不能正常工作。每次我改变一些东西，比如一条新线，一次尝试，或者一个不同的层次结构，有些东西不起作用...... 你知道如何解决这个非常烦人的问题吗？
这是使用的最小功能代码：
open FParsec
// Ast
type Expression =
| Number of int
| Call of string * Expression list
type Program = Expression list
// Tools
let private bws p =
spaces >>? p .>>? spaces
let private suiteOf p =
sepEndBy p spaces1
let inline private betweenParentheses p label =
between (pstring "(") (pstring ")") p
<?> (label + " between parentheses")
let private identifier =
many1Satisfy2 isLetter (fun c -> isLetter c)
// Expressions
let rec private call = parse {
let! call = pipe2 (spaces >>? identifier) (spaces >>? parameters)
(fun id parameters -> Call(id, parameters)) // .>>? newline
return call
}
and private parameters = suiteOf expression
and private callFuncWithoutArgs =
identifier |>> fun id -> Call(id, [])
and private number = pint32 |>> Number
and private betweenParenthesesExpression =
parse { let! ex = betweenParentheses expression "expression"
return ex }
and private expression =
bws (attempt betweenParenthesesExpression <|>
attempt number <|>
attempt call <|>
callFuncWithoutArgs)
// -------------------------------
let parse code =
let parser = many expression .>>? eof
match run parser code with
| Success(result, _, _) -> result
| Failure(msg, _, _) ->
printfn "%s" msg
[]
System.Console.Clear()
parse @"
add 4 7
foo x y
inc x
foo (x) (y)
add (inc x) (dec y)
" |> printfn "%A"
您的主要问题是您的解析器的高级设计有误。
你现在的设计是一个表达式可以是：
- 括号之间的表达式（可以说是 "sub-expression"（这里没问题）
- 一个数字（这里没问题）
- 带参数的调用，它是一个标识符，后跟 space 分隔的表达式列表（这是问题的主要部分）
- 不带参数的调用，它是单个标识符（这会导致问题）
看看表达式 foo x y，让我们按照解析器的顺序应用这些规则。没有括号并且 foo 不是数字，所以它不是 3 就是 4。首先我们尝试 3。foo 后跟 x y：x y 是否解析为一种表达？为什么，是的，它确实如此：它解析为带参数的调用，其中 x 是函数，y 是参数。由于 x y 匹配 3，它根据规则 3 进行解析而不检查规则 4，因此 foo x y 匹配类似于 foo (x y) 将：使用单个参数调用 foo，这是使用参数 y.
x
如何解决这个问题？好吧，您可以尝试交换 3 和 4 的顺序，以便在调用带参数的函数调用之前检查不带参数的函数调用（这会使 x y 解析为 x。但那会失败，因为 foo x y 会像 foo 一样匹配。所以将规则 4 放在规则 3 之前在这里不起作用。
真正的解决方案是将表达式的规则拆分为两个级别。 "inner" 级别，我称之为 "value"，可能是：
- 括号中的表达式
- 一个数
- 不带参数的函数调用
"outer" 级别，表达式的解析规则，将是：
- 一个函数调用，带个参数，都是值，不是表达式
- 一个值
请注意，这些解析级别是相互递归的，因此您需要在实现中使用 createParserForwardedToRef。让我们看看 foo x y 将如何使用此设计进行解析：
首先，foo 解析为标识符，因此检查它是否可能是带参数的函数调用。 x 是否解析为一个值？是的，根据价值观规则 3。 y 是否解析为一个值？是的，根据价值观规则 3。所以 foo x y 解析为函数调用。
现在funcWithoutParameters呢？它会失败表达式的规则 1，因为它后面没有参数列表。所以它会检查表达式的规则 2，然后它会根据值的规则 3 进行匹配。
好的，伪代码的基本健全性检查有效，所以让我们把它变成代码。但首先，我会提到你的解析器中的 other 问题，我还没有提到，那就是你没有意识到 FParsec spaces 解析器 also matches newlines。因此，当您将 expression 解析器包装在 bws ("between whitespace") 中时，它还会在解析的文本后使用换行符。因此，当您解析类似以下内容时：
foo a b
inc c
suiteOf expression 看到列表 a b inc c 并将所有这些转换为 foo 的参数。在我下面的代码中，我区分了 FParsec 的 spaces 解析器（包括换行符）和解析器 only horizontal whitespace (space和制表符但不是换行符），在适当的地方使用每个。下面的代码实现了我在这个答案中提到的设计，它的输出对我来说对于你写的所有测试表达式来说都是正确的：
open FParsec
// Ast
type Expression =
| Number of int
| Call of string * Expression list
type Program = Expression list
// Tools
let private justSpaces = skipMany (pchar ' ' <|> pchar '\t')
let private justSpaces1 = skipMany1 (pchar ' ' <|> pchar '\t')
let private bws p =
spaces >>? p .>>? spaces
let private suiteOf p =
sepEndBy1 p (justSpaces1)
let inline private betweenParentheses p label =
between (pstring "(") (pstring ")") p
<?> (label + " between parentheses")
let private identifier =
many1Satisfy2 isLetter (fun c -> isLetter c)
// Expressions
let private expression, expressionImpl = createParserForwardedToRef()
let private betweenParenthesesExpression =
parse { let! ex = betweenParentheses expression "expression"
return ex }
let private callFuncWithoutArgs =
(identifier |>> fun id -> Call(id, []))
let private number = pint32 |>> Number
let private value =
justSpaces >>? (attempt betweenParenthesesExpression <|>
attempt number <|>
callFuncWithoutArgs)
let private parameters = suiteOf value
let rec private callImpl = parse {
let! call = pipe2 (justSpaces >>? identifier) (justSpaces >>? parameters)
(fun id parameters -> Call(id, parameters))
return call }
let call = callImpl
expressionImpl.Value <-
bws (attempt call <|>
value)
// -------------------------------
let parse code =
let parser = many expression .>>? (spaces >>. eof)
match run parser code with
| Success(result, _, _) -> result
| Failure(msg, _, _) ->
printfn "%s" msg
[]
System.Console.Clear()
parse @"
add 4 7
foo x y
inc x
foo (x) (y)
add (inc x) (dec y)
" |> printfn "%A"
P.S。我使用了 http://www.quanttec.com/fparsec/users-guide/debugging-a-parser.html 建议的以下运算符来极大地帮助我跟踪问题：
let (<!>) (p: Parser<_,_>) label : Parser<_,_> =
fun stream ->
printfn "%A: Entering %s" stream.Position label
let reply = p stream
printfn "%A: Leaving %s (%A)" stream.Position label reply.Status
reply
用法：将let parseFoo = ...变成let parseFoo = ... <!> "foo"。然后您将在控制台中获得调试输出流，如下所示：
(Ln: 2, Col: 20): Entering expression
(Ln: 3, Col: 1): Entering call
(Ln: 3, Col: 5): Entering parameters
(Ln: 3, Col: 5): Entering bwParens
(Ln: 3, Col: 5): Leaving bwParens (Error)
(Ln: 3, Col: 5): Entering number
(Ln: 3, Col: 6): Leaving number (Ok)
(Ln: 3, Col: 7): Entering bwParens
(Ln: 3, Col: 7): Leaving bwParens (Error)
(Ln: 3, Col: 7): Entering number
(Ln: 3, Col: 8): Leaving number (Ok)
(Ln: 3, Col: 8): Leaving parameters (Ok)
(Ln: 3, Col: 8): Leaving call (Ok)
(Ln: 3, Col: 8): Leaving expression (Ok)
当您试图弄清楚为什么您的解析器没有按照您的预期运行时，这会很有帮助。