Some trouble with macros

So here we go. I have this code

macro_rules! list {
    ($x:expr) => (FunList::new($x));
    ($x:expr, $($y:expr),+) => (
        add($x, list!($($y),+))
    );
}

fn main() {
    let a = list!(1, 2, 3, 4, 5);
    print(&a);
}  

struct FunList<T> {
    val: T,
    next: Option<Box<FunList<T>>>,
}

impl<T> FunList<T> {
    fn new(val: T) -> FunList<T> {
        FunList { val, next: None }
    }
}
fn add<T>(val: T, next: FunList<T>) -> FunList<T> {
    FunList {
        val,
        next: Some(Box::from(next)),
    }
}
fn print<T>(list: &FunList<T>)
where T: std::fmt::Display {
    print!("{}, ", list.val);
    match &list.next {
        None => {},
        Some(val) => print(val.as_ref())
    };
}

And it works good and all but my inner dump_programmer wanted to try to change macro to this just for fun

macro_rules! list {
    ($x:expr) => (FunList::new($x));
    ($($y:expr),+, $x:expr) => (
        add($x, list!($($y),+))
    );
}

I was sure that it will work, but it doesn't and give me this

error: local ambiguity: multiple parsing options: built-in NTs expr ('x') or expr ('y').
 --> src/main.rs:9:22
  |
9 |     let a = list!(1, 2, 3, 4, 5);
  |                      ^

error: aborting due to previous error

error: could not compile `test_crate`

To learn more, run the command again with --verbose.

And I'm interested if I can extract the last element from elements sequence in macro and if yes how and what I made wrong in my example.

It all boils down to left-recursion vs. right-recursion in parsing. If parsing proceeds from left to right (which it mostly does in Rust), then ($y:expr),+, $x:expr has multiple possible interpretations (as the error message tells you). In particular, $y can be bound to 1 or more comma-separated expressions, so $y = 1, $x = 2, $y = (1, 2), $x = 3, $y = (1, 2, 3), $x = 4, etc. are all valid parses of the macro input.


If you have tried implementing a recursive descent parser for a context-free grammar before, you might be aware how naïve recursion leads to infinite recursion when a production rule in the grammar is specified left-recursively. This is a similar (although not identical) issue – in general, left recursion is problematic when trying to parse eagerly from left to right.

You'll have to recurse until there is only a single element. Something like this.

2 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.