Hacker News Reader

Comment by tptacek | Hacker News Reader

So, just to kick this off: I wrote an eBPF disassembler and (half-hearted) emulator in Rust and I also found it a pleasant language to do parsing-type stuff in. But: I think the author cuts against their argument when they manage to necessitate a macro less than 1/6th of the way into their case study. A macro isn't quite code-gen, but it also doesn't quite feel like working idiomatically within the language, either.

Again: not throwing shade. I think this is a place where Rust is genuinely quite strong.

View on HN

How can one define an infinite grammar in Rust?

E.g., a context-free rule S ::= abc|aabbcc|aaabbbccc|... can effectively parse a^Nb^Nc^N which is an example of context-sensitive grammar.

This is a simple example, but something like that can be seen in practice. One example is when language allows definition of operators.

So, how does Rust handle that?

In Haskell I think it's something like:

    {-# LANGUAGE OverloadedStrings #-}
    import Data.Attoparsec.Text
    import qualified Data.Text as T

    type ParseError = String

    csgParse :: T.Text -> Either ParseError Int
    csgParse = eitherResult . parse parser where
    parser = do
        as <- many' $ char 'a'
        let n = length as
        count n $ char 'b'
        count n $ char 'c'
        char '\n'
        return n

    ghci> csgParse "aaabbbccc\n"
    Right 3

The question comes from Haskell, yes: https://byorgey.wordpress.com/2012/01/05/parsing-context-sen...

You used monadic parser, monadic parsers are known to be able to parse context-sensitive grammars. But, they hide the fact that they are combiinators, implemented with closures beneath them. For example, that "count n $ char 'b'" can be as complex as parsing a set of statements containing expressions with an operator specified (symbol, fixity, precedence) earlier in code.

In Haskell, it is easy - parameterize your expression grammar with operators, apply them, parse text. This will work even with Applicative parsers, even unextended.

But in Rust? I haven't seen how it can be done.

I tried winnow as suggested elsewhere in this thread, this is what it may look like:

    use winnow::combinator::{ repeat };
    use winnow::token::take_while;
    use winnow::prelude::*;

    pub fn csg_parse(input: &mut &str) -> PResult<usize> {
        let a: &str = take_while(0.., 'a').parse_next(input)?;
        let n: usize = a.len();
        repeat(n, "b").parse_next(input)?;
        repeat(n, "c").parse_next(input)?;
        '\n'.parse_next(input)?;
        return Ok(n);
    }

    #[cfg(test)]
    mod test {
        use super::*;

        #[test]
        fn parses_examples() {
            assert_eq!(Ok(0), csg_parse(&mut "\n"));
            assert_eq!(Ok(3), csg_parse(&mut "aaabbbccc\n"));

            assert!(csg_parse(&mut "abcc\n").is_err());
            assert!(csg_parse(&mut "abbcc\n").is_err());
            assert!(csg_parse(&mut "aabc\n").is_err());
            assert!(csg_parse(&mut "aabbc\n").is_err());
            assert!(csg_parse(&mut "def\n").is_err());
        }
    }

So you are directly express context-sensitivity instead of approximating it with infinite context-free grammar.

Okay, good enough.

Using parser combinator library "nom", this should probably do what you'd want:

    fn parse_abc(input: &str, n: usize) -> IResult<&str, (Vec<char>, Vec<char>, Vec<char>)> {
      let (input, result) = tuple(( many_m_n(n, n, char('a')),
                                  many_m_n(n, n, char('b')),
                                  many_m_n(n, n, char('c'))
                            ))(input)?;
      Ok((input, result)) 
    }

It parses (the beginning of) the input, ensuring `n` repetitions of 'a', 'b', and 'c'. Parse errors are reported through the return type, and the remaining characters are returned for the application to deal with as it sees fit.

https://play.rust-lang.org/?version=stable&mode=debug&editio...

> this should probably do what you'd want

If you have to specify N, no, it doesn't

Link us your eBPF disassembler if you can. Sounds cool.

It's not. If you wrote one, it'd be more interesting than mine.

Reply on news.ycombinator.com