Skip to main content

3 posts tagged with "polynomials"

View All Tags

· 9 min read

Parsing polynomials with F# and FParsec

Parsing a polynomial expression is a simple but interesting example of parsing. We need to handle operator precedence and associativity, for example * has a higher precedence than + and the exponentiation is right associative x^y^z=x^(y^z) while subtraction is left associative x-y-z=(x-y)-z. Moreover a straighforward definition of the grammar is left recursive and a recursive descent parser does not allow to parse such grammar. We need to arrange our grammar in order to avoid the left recursion.

· 4 min read


Using a Pratt parser I aim to parse expressions like this x^2+y^2-1, x=1, y=1 and xy, x=2, y=3. Parsing mathematical expressions it's not hard but it already contains some interesting behaviour such as associativity between operators x+y*z is equal to x+(y*z) and not (x+y)*z. For no particular reason I decided to put the variable assignments after the polynomial. The expression x^2+y^2-1, x=1, y=1 is to be interpreted as you would with this pseudo code

· 5 min read


Update April 2020, hey! I updated this article and the corresponding repo check it out here

In the last couple of months I've been reading and studying about compilers and languages and for everyone doing something like that it's very easy to meet Antlr at a certain point. What is antlr?