Как написать парсер рекурсивного спуска с нуля?

Question

В качестве чисто академического упражнения я пишу парсер рекурсивного спуска с нуля - без использования ANTLR или lex / yacc.

Я пишу простую функцию, которая преобразует математические выражения в их эквивалент AST. У меня есть следующее:

// grammar
type expr =
    | Lit of float
    | Add of expr * expr
    | Mul of expr * expr
    | Div of expr * expr
    | Sub of expr * expr

// tokens
type tokens =
    | Num of float
    | LParen | RParen
    | XPlus | XStar | XMinus | XSlash

let tokenize (input : string) =
    Regex.Matches(input.Replace(" ", ""), "\d+|[+/*\-()]")
    |> Seq.cast<Match>
    |> Seq.map (fun x -> x.Value)
    |> Seq.map (function
        | "+" -> XPlus
        | "-" -> XMinus
        | "/" -> XSlash
        | "*" -> XStar
        | "(" -> LParen
        | ")" -> RParen
        | num -> Num(float num))
    |> Seq.to_list

Итак, tokenize "10 * (4 + 5) - 1" возвращает следующий поток токенов:

[Num 10.0; XStar; LParen; Num 4.0; XPlus; Num 5.0; RParen; XMinus; Num 1.0]

На этом этапе я бы хотел отобразить поток токенов в его AST с учетом приоритета оператора:

Sub(
    Mul(
        Lit 10.0
        ,Add(Lit 4.0, Lit 5.0)
       )
    ,Lit 1.0
   )

Однако я рисую пробел. Я никогда не писал парсер с нуля, и даже не знаю, в принципе, с чего начать.

Как преобразовать токен-поток в его репрезентативный AST?

Answer 1

Знаете ли вы о грамматике языка?

Предполагая, что да, у вас есть грамматика с правилами вдоль строк

...
addTerm := mulTerm addOp addTerm
         | mulTerm

addOp   := XPlus | XMinus

mulTerm := litOrParen mulOp mulTerm
         | litOrParen
...

, что в конечном итоге превращается в код (запись кода в браузере, никогда не компилируется)

let rec AddTerm() =
    let mulTerm = MulTerm() // will parse next mul term (error if fails to parse)
    match TryAddOp with  // peek ahead in token stream to try parse
    | None -> mulTerm    // next token was not prefix for addOp rule, stop here
    | Some(ao) ->        // did parse an addOp
         let rhsMulTerm = MulTerm()
         match ao with
         | XPlus -> Add(mulTerm, rhsMulTerm)
         | XMinus -> Sub(mulTerm, rhsMulTerm)
and TryAddOp() =
    let next = tokens.Peek() 
    match next with
    | XPlus | XMinus ->
        tokens.ConsumeNext()
        Some(next)
    | _ -> None
...

Надеюсь, вы видите основную идею. Это предполагает глобальный изменяемый поток токенов, который позволяет «смотреть на следующий токен» и «потреблять следующий токен».

Answer 2

Если я помню из уроков колледжа, идея состояла в том, чтобы построить деревья выражений вроде:

<program> --> <expression> <op> <expression> | <expression>
<expression> --> (<expression>) | <constant>
<op> --> * | - | + | /
<constant> --> <constant><constant> | [0-9]

тогда, когда вы построите свое дерево полностью , вы получите что-то вроде:

            exp
       exp   op     exp
    5        +       and so on

затем вы запускаете ваше законченное дерево через другую программу, которая рекурсивно спускается в выражения вычисления дерева, пока не получите ответ. Если ваш синтаксический анализатор не понимает дерево, у вас есть синтаксическая ошибка. Надеюсь, это поможет.