Recursive parsing types

[numToStr]

Hi,

I am trying to parse emmylua types but couldn't figure out how to recursively parse union and array types. For Example:

fun(a: string, b: string|number, c: string[], d: number[][])
table<string, string|number>[]
table<string, string[]>[]

Besides that, I was able to parse other nested types like functions and tables.

fun(a: string, b: fun(c: string)): table<string, number>
table<string, fun(a: string, b: table<string, boolean>))

I came up with this code so far

use chumsky::{
    prelude::Simple,
    primitive::{choice, just},
    recursive::recursive,
    text::{ident, TextParser},
    Parser,
};

// Source: https://github.com/sumneko/lua-language-server/wiki/Annotations#documenting-types
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub enum Ty {
    Nil,
    Unknown,
    Boolean,
    String,
    Number,
    Integer,
    Function,
    Thread,
    Userdata,
    Lightuserdata,
    Union(Vec<Ty>),
    Array(Box<Ty>),
    Table(Option<(Box<Ty>, Box<Ty>)>),
    Fun(Vec<(String, Ty)>, Option<Box<Ty>>),
}

recursive(|inner| {
    let comma = just(',').padded();
    let colon = just(':').padded();

    choice((
        just("any").to(Ty::Unknown),
        just("unknown").to(Ty::Unknown),
        just("nil").to(Ty::Nil),
        just("boolean").to(Ty::Boolean),
        just("string").to(Ty::String),
        just("number").to(Ty::Number),
        just("integer").to(Ty::Integer),
        just("function").to(Ty::Function),
        just("thread").to(Ty::Thread),
        just("userdata").to(Ty::Userdata),
        just("lightuserdata").to(Ty::Lightuserdata),
        just("fun")
            .ignore_then(
                ident()
                    .padded()
                    .then_ignore(colon)
                    .then(inner.clone())
                    .separated_by(comma)
                    .allow_trailing()
                    .delimited_by(just('('), just(')')),
            )
            .then(colon.ignore_then(inner.clone().map(Box::new)).or_not())
            .map(|(param, ret)| Ty::Fun(param, ret)),
        just("table")
            .ignore_then(
                just('<')
                    .ignore_then(inner.clone().map(Box::new))
                    .then_ignore(comma)
                    .then(inner.clone().map(Box::new))
                    .then_ignore(just('>'))
                    .or_not(),
            )
            .map(Ty::Table),
        // This produces stackoverflow :(
        // inner
        //     .clone()
        //     .then_ignore(just('|'))
        //     .chain(inner.clone().separated_by(just('|')))
        //     .map(Ty::Union),
        // inner
        //     .clone()
        //     .then_ignore(just('[').then(just(']')))
        //     .map(|x| Ty::Array(Box::new(x))),
    ))
})

I would appreciate it If you could guide me on how parse union and array types recursively :)

[zesterer]

You can think of the array notation as being a postfix unary operator. You'd do well to split the definition of your type syntax into 'atoms' (self-delimiting types) and other operators, as when parsing expressions (I find it easier to think of type syntax as being 'type-level expressions'). Then, array access can look something like this:

let atom = ... ;

let array = atom
    .then(just("[]").repeated())
    .foldl(|ty, _| Type::Array(ty));

[numToStr]

@zesterer Thanks for the suggestion, it worked. Now I am able to parse array types. But I was wondering how to parse nested unions. I tried on my own to tackle it but no success.

string|string[]|boolean
fun(a: string, b: string[], c: string|string[]|boolean)

Now my code looks like this:

recursive(|inner| {
    let comma = just(',').padded();
    let colon = just(':').padded();

    fn array(
        p: impl Parser<char, Ty, Error = Simple<char>>,
    ) -> impl Parser<char, Ty, Error = Simple<char>> {
        p.then(just("[]").repeated())
            .foldl(|arr, _| Ty::Array(Box::new(arr)))
    }

    let any = just("any").to(Ty::Unknown);
    let unknown = just("unknown").to(Ty::Unknown);
    let nil = just("nil").to(Ty::Nil);
    let boolean = just("boolean").to(Ty::Boolean);
    let string = just("string").to(Ty::String);
    let num = just("number").to(Ty::Number);
    let int = just("integer").to(Ty::Integer);
    let function = just("function").to(Ty::Function);
    let thread = just("thread").to(Ty::Thread);
    let userdata = just("userdata").to(Ty::Userdata);
    let lightuserdata = just("lightuserdata").to(Ty::Lightuserdata);

    let fun = just("fun")
        .ignore_then(
            ident()
                .padded()
                .then_ignore(colon)
                .then(inner.clone())
                .separated_by(comma)
                .allow_trailing()
                .delimited_by(just('('), just(')')),
        )
        .then(colon.ignore_then(inner.clone().map(Box::new)).or_not())
        .map(|(param, ret)| Ty::Fun(param, ret));

    let table = just("table")
        .ignore_then(
            just('<')
                .ignore_then(inner.clone().map(Box::new))
                .then_ignore(comma)
                .then(inner.clone().map(Box::new))
                .then_ignore(just('>'))
                .or_not(),
        )
        .map(Ty::Table);

    choice((
        array(any),
        array(unknown),
        array(nil),
        array(boolean),
        array(string),
        array(num),
        array(int),
        array(function),
        array(thread),
        array(userdata),
        array(lightuserdata),
        array(fun),
        array(table),
    ))
})

[zesterer]

That's... a choice. I think it's a mistake to have this big choice at the bottom, it's basically saying "all of these things have equal precedence" when that's not true! In your example, the array operator ([]) clearly has much higher precedence (i.e: it binds to the thing on its left more strongly) than the union operator (|).

I really think it's worth taking a look at the tutorial, specifically the sections on parsing unary and binary operators as they explain how to structure parsers for grammars that have operators and precedence rules between them (your array syntax is basically just a type-level unary operator, and your union syntax is just a type-level binary operator).

[numToStr]

I'll surely read the tutorial and restructure my parser. Thanks for taking your time and explaining things to me.