search

rust-bakery / nom

Rust parser combinator framework
MIT License
9.51k stars 805 forks source link

Arithmetic expression example #32

Closed Geal closed 9 years ago

Geal commented 9 years ago

Parsing expressions such as 1 + 2 * 3 is a common parsing example, there should be some code to show it in nom

emberian commented 9 years ago

I'm trying to write a generic Pratt parser using Nom, and arriving at difficulty. Since parsers must be a function (I think?) and not something implementing a trait, there is nowhere for the parser to store the state on token precedence.

emberian commented 9 years ago

I'm honestly not even sure how you would use Nom in the traditional context of parsing a context-free language.

Geal commented 9 years ago

I am not sure a Pratt parser would be easy to build in nom, since it uses parser combinators, a whole other paradigm. They are usually able to parse any context free language, but operator precedence is harder to encode than with Pratt's.

Usually, if there's some state above the parser, I either use another mutable argument in the function, or I have a higher level state machine. It suits well for file/network format parsing with an API on top.

If you want specifically to write a Pratt parser, that could be the focus of a new project. Or a new part of nom :) If you could give me examples of things you are trying to parse, I would be happy to fix nom and make it easier to parse them.

I can get back to you on this tomorrow, I have to sleep now.

Geal commented 9 years ago

ok, so, I gave it some thought. It would be possible to use nom as a lexer, and let a Pratt parser handle precedence.

I have been thinking for some time about adding multiple parsing systems over nom, like GLL, LL, etc. Hammer is an example of parser combinators used with different parsing backends.

Geal commented 9 years ago

There is now an example of arithmetic expression parsing, although not based on a Pratt parser. Parser combinators embed the precedence rules in the way functions refer to each other.

lazarljubenovic commented 1 year ago

This is the first result when you Google "rust nom pratt parse". Has anything changed since 2015? I was hoping to find a recipe for “you can write your expression rule as a Pratt parser (by hand), and then this is how you integrate it into nom for the rest of the grammar“.

epage commented 1 year ago

FYI #1690 is the issue for tracking the status of built-in Pratt Parser support.