Cómo escribir un analizador de descenso recursivo desde cero?

Question

Como ejercicio puramente académico, estoy escribiendo un analizador de descenso recursivo desde cero, sin usar ANTLR o lex/yacc.

Estoy escribiendo una función simple que convierte expresiones matemáticas en su equivalente AST. Tengo el siguiente:

// 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 

Así, tokenize "10 * (4 + 5) - 1" devuelve la siguiente cadena de componentes léxicos:

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

En este punto, me gustaría correlacionar el flujo de contadores a su AST con respecto a la prioridad de los operadores:

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

Sin embargo, estoy dibujando un espacio en blanco. Nunca he escrito un analizador sintáctico desde cero, y no sé ni siquiera en principio cómo comenzar.

¿Cómo convierto un flujo de tokens a su representante AST?

Answer 1

¿Conoce las gramáticas del lenguaje?

Suponiendo que sí, que tienen una gramática con reglas a lo largo de las líneas

... 
addTerm := mulTerm addOp addTerm 
     | mulTerm 

addOp := XPlus | XMinus 

mulTerm := litOrParen mulOp mulTerm 
     | litOrParen 
... 

que termina por convertirse en un código como (la escritura de código en el navegador, no compilado)

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 
... 

Esperemos que ver la idea básica. Esto supone una secuencia token mutable global que permite tanto 'peek at next token' como 'consuma next token'.

Answer 2

Si recuerdo de clases de la universidad la idea era construir árboles de expresión como:

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

continuación, una vez que tenga la construcción de su árbol completamente por lo que obtener algo como:

  exp 
     exp op  exp 
    5  +  and so on 

entonces ejecuta su árbol completo a través de otro programa que desciende recursivamente en el árbol calculando expresiones hasta que tenga una respuesta. Si su analizador no comprende el árbol, tiene un error de sintaxis. Espero que ayude.