PEG: Cosa c'è di sbagliato nella mia grammatica per l'istruzione if?

Question

Sto implementando un linguaggio simile a OCaml usando rust-peg e il mio parser ha un bug. Ho definito la grammatica dell'istruzione if, ma non funziona.

Immagino che l'input del test case sia analizzato come Apply(Apply(Apply(Apply(f, then), 2) else), 4). Voglio dire, "then"viene analizzato come Ident, non come parola chiave.

Non ho idea di correggere questa grammatica dell'espressione applicata. Hai qualche idea?

#[derive(Clone, PartialEq, Eq, Debug)]
pub enum Expression {
    Number(i64),
    If {
        cond: Box<Expression>,
        conseq: Box<Expression>,
        alt: Box<Expression>,
    },
    Ident(String),
    Apply(Box<Expression>, Box<Expression>),
}

use peg::parser;
use toplevel::expression;
use Expression::*;

parser! {
pub grammar toplevel() for str {

    rule _() = [' ' | '\n']*

    pub rule expression() -> Expression
        = expr()

    rule expr() -> Expression
        = if_expr()
        / apply_expr()

    rule if_expr() -> Expression
        = "if" _ cond:expr() _ "then" _ conseq:expr() _ "else" _ alt:expr() {
            Expression::If {
                cond: Box::new(cond),
                conseq: Box::new(conseq),
                alt: Box::new(alt)
            }
        }

    rule apply_expr() -> Expression
        = e1:atom() _ e2:atom() { Apply(Box::new(e1), Box::new(e2)) }
        / atom()

    rule atom() -> Expression
        = number()
        / id:ident() { Ident(id) }

    rule number() -> Expression
        = n:$(['0'..='9']+) { Expression::Number(n.parse().unwrap()) }

    rule ident() -> String
        = id:$(['a'..='z' | 'A'..='Z']['a'..='z' | 'A'..='Z' | '0'..='9']*) { id.to_string() }
}}

fn main() {
    assert_eq!(expression("1"), Ok(Number(1)));
    assert_eq!(
        expression("myFunc 10"),
        Ok(Apply(
            Box::new(Ident("myFunc".to_string())),
            Box::new(Number(10))
        ))
    );

    // failed
    assert_eq!(
        expression("if f then 2 else 3"),
        Ok(If {
            cond: Box::new(Ident("f".to_string())),
            conseq: Box::new(Number(2)),
            alt: Box::new(Number(3))
        })
    );
}

thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `Err(ParseError { location: LineCol { line: 1, column: 11, offset: 10 }, expected: ExpectedSet { expected: {"\"then\"", "\' \' | \'\\n\'"} } })`,
 right: `Ok(If { cond: Ident("f"), conseq: Number(2), alt: Number(3) })`', src/main.rs:64:5

Answer 1

PEG usa la scelta ordinata. Ciò significa che quando scrivi R = A / Bper qualche regola R, se in una posizione Aviene analizzata con successo, non ci proverà maiB , anche se la scelta di Aporta a problemi in seguito. Questa è la differenza fondamentale con le grammatiche senza contesto e spesso viene trascurata.

In particolare, quando scrivi apply = atom atom / atom, se è possibile analizzare due atomi di seguito, non tenterà mai di analizzarne solo uno, anche se ciò significa che il resto non ha senso in seguito.

Combina questo con il fatto che thene elsesono identificatori perfettamente validi nella tua grammatica, ottieni il problema che vedi.