Ваша основная проблема в том, что у вас неправильный высокоуровневый дизайн для вашего синтаксического анализатора.
Ваш текущий дизайн состоит в том, что выражение может быть:
- Выражение (a "подвыражение ", так сказать) между круглыми скобками (здесь нет проблем)
- Число (здесь нет проблем)
- Вызов с параметрами, который является идентификатором, за которым следует пробелсписок выражений (это основная часть проблемы)
- вызов без параметров, который является единым идентификатором (это способствует возникновению проблемы)
просмотр выражения 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 с одним параметром, который является вызовом x спараметр y.
Как это исправить?Ну, вы можете попробовать поменять местами порядок 3 и 4, чтобы перед вызовом с параметрами проверялся вызов функции без параметров (что могло бы x y анализировать как x. Но это не получится, потому что foo x yбудет соответствовать просто foo. Таким образом, размещение правила 4 перед правилом 3 здесь не работает.
Реальное решение состоит в том, чтобы разделить правила для выражения на два уровня. «Внутренний» уровень, которыйЯ назову «значение», может быть:
- Выражение в скобках
- Число
- Вызов функции без параметров
И «внешний» уровень, правила синтаксического анализа для выражений, будет выглядеть так:
- Вызов функции с параметрами, каждый из которых значения , not выражения
- Значение
Обратите внимание, что эти уровни синтаксического анализа являются взаимно рекурсивными, поэтому вам необходимо использовать createParserForwardedToRef в своей реализации.Давайте посмотрим, как foo x y будет проанализирован с этим дизайном:
First, foo анализирует как идентификатор, поэтому проверьте, может ли это быть вызов функции с параметрами.x анализирует как значение?Да, согласно правилу 3 ценностей.И y анализирует как значение?Да, согласно правилу 3 ценностей.Итак, foo x y анализирует как вызов функции.
А что насчет funcWithoutParameters?Это не выполнит правило 1 выражений, потому что за ним не следует список параметров.Таким образом, он будет проверен для правила 2 выражений, а затем совпадет с правилом 3 значений.
Хорошо, базовая проверка работоспособности псевдокода работает, поэтому давайте превратим это в код.Но сначала я упомяну о проблеме other в вашем парсере, о которой я еще не упомянул: вы не понимаете, что синтаксический анализатор FParsec spaces также соответствует символам новой строки .Поэтому, когда вы оборачиваете свой expression парсер в bws («между пробелами»), он также будет использовать новые строки после текста, который он анализирует.Поэтому, когда вы анализируете что-то вроде:
foo a b
inc c
* suiteOf expression видит список a b inc c и превращает все это в параметры для foo.В моем коде ниже я провел различие между парсером spaces в FParsec (который включает в себя новые строки) и парсером, который анализирует только горизонтальные пробелы * (пробел и табуляция, но не новая строка), используя каждый в соответствующем месте.В следующем коде реализован дизайн, о котором я упоминал в этом ответе, и его вывод выглядит мне правильно для всех написанных вами тестовых выражений:
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"
PS Я использовал следующий оператор, предложенный 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)
Это очень помогает, когда вы пытаетесь выяснить, почему ваш анализатор не выполняет то, что вы ожидаете.