Doc request: what exactly is afterStringParser in expression parser?

[amir734jj]

In the expression parser, is there is documentation on what exactly is afterStringParser?

/// <summary>Adds a postfix operator to the OPP.</summary>
/// <footer><a href="https://www.google.com/search?q=FParsec.CSharp.Operators%603.AddPostfix">`Operators.AddPostfix` on google.com</a></footer>
public Operators<TUserState, TTerm, TAfterString> AddPostfix(
  string operatorString,
  int precedence,
  FSharpFunc<CharStream<TUserState>, Reply<TAfterString>> afterStringParser, // <------
  Func<TTerm, TTerm> map)
{
  return this.AddPostfix(operatorString, precedence, false, afterStringParser, map);
}

I am trying to abuse it to parse left recursive grammar?

<Expression> : <FunctionCall> | <Variable> | <Expression>.<FunctionCall>

For example, foo() and bar.foo() and foo().bar()

[bert2]

The FParsec docs give a few usage examples. Does that help?

[amir734jj]

@bert2 The documentation was helpful. Thank you. I wish there was an overloaded method to AddPostfix that would take a function for afterStringParser. Similar to WithTerms(term => ... ) which we can use to recursively construct the parser

Please feel free to close this issue.

[bert2]

Hi @amir734jj! I'm not sure I entirely understand what you are asking. Could you show some code of the OOP API you have in mind from a usage perspective?

[amir734jj]

I am not sure exactly about the types but something like this:

static FSharpFunc<CharStream<Unit>, Reply<Token>> Variable(
    FSharpFunc<CharStream<Unit>, Reply<Token>> expressionRec)
{
   throw new NotImplementedException();
}

static FSharpFunc<CharStream<Unit>, Reply<Token>> FunctionCall(
    FSharpFunc<CharStream<Unit>, Reply<Token>> expressionRec)
{
   throw new NotImplementedException();
}

var expressionP = new OPPBuilder<Unit, Token, Unit>()
    .WithOperators(ops => ops
        .AddPrefix("-", 5, WS, token => new NegateToken(token))
        .AddPrefix("!", 5, WS, token => new NotToken(token))
        .AddInfix("+", 10, WS, (x, y) => new AddToken(x, y))
        .AddInfix("-", 10, WS, (x, y) => new SubtractToken(x, y))
        .AddInfix("*", 20, WS, (x, y) => new MultiplyToken(x, y))
        .AddInfix("/", 20, WS, (x, y) => new DivideToken(x, y))
        .AddInfix("==", 30, WS, (x, y) => new EqualsToken(x, y))
        .AddInfix("!=", 30, WS, (x, y) => new NotEqualsToken(x, y))
        // Notice afterStringParser is a function that takes recursive expression parser as input
        .AddPostfix(".", 10, term => Choice(Variable(term), FunctionCall(term)), x => new AccessToken(x))
    )
    .WithTerms(term => Choice(
        Declaration(term),
        Instantiation(term),
        Conditional(term),
        While(term),
        Assignment(term),
        Block(term),
        Atomic(term),
        FunctionCall(term),
        Variable(term),
        Wrap('(', term, ')')
      )
    )
    .Build()
    .ExpressionParser
    .Label("operator");

[bert2]

Hey @amir734jj, sorry for the late reply.

At a glance it seems to me that the . operator should be implemented using AddInfix(). Probably with maximum precedence and left-associative.

But I never tried that myself, so I might be overlooking something.

[bert2]

Alternatively you could use Rec(). The ExpressionParser property of the OPP is the term parser.

So if you init expressionP with null and later re-assign it as you did in your example, then you could use the following operator definition:

.AddPostfix(".", 10, Choice(Variable(Rec(() => expressionP)), FunctionCall(Rec(() => expressionP)), x => new AccessToken(x))

Creating an infix operator still seems like the better option to me, though.

[amir734jj]

It worked! Thank you so much

@bert2 infix with high precedence worked flawlessly.

[amir734jj]

@bert2 sorry for asking too many questions. I am trying to implement a toy language using your parser :)

I am wondering what do you think I should use for this case of expression?

 <Expr> match { 
      case null => <Expr> 
      case x:Any => <Expr> 
    }

The infix expression doesn't make sense here. My code results in StackOverflow because its left recursive

            static FSharpFunc<CharStream<Unit>, Reply<Token>> Match(
                FSharpFunc<CharStream<Unit>, Reply<Token>> expressionRec)
            {
                var typeMatch = Name().AndLTry(WS).AndLTry(CharP(':')).AndLTry(WS).AndTry(Name()).AndLTry(WS)
                    .AndLTry(StringP("=>")).AndLTry(WS).AndTry(expressionRec)
                    .Map(x => new ArmToken(x.Item1.Item1, x.Item1.Item2, x.Item2));

                var nullMatch = Skip("null").AndTry_(WS).AndTry_(StringP("=>")).AndTry_(WS).AndRTry(expressionRec)
                    .Map(x => new ArmToken("null", "Any", x));

                var arm = Skip("case").AndTry_(WS1)
                    .AndRTry(Choice(typeMatch, nullMatch));

                var arms = SepBy('{', arm, '}', SkipNewline, canEndWithSep: true);
                
                var matchP = expressionRec.AndLTry(WS1).AndLTry(StringP("match"))
                    .AndLTry(WS)
                    .AndTry(arms)
                    .Label("match")
                    .Map(x => (Token)new Match(x.Item1, x.Item2.AsValueSemantics()));

                return SkipWs(matchP);
            }
            
            FSharpFunc<CharStream<Unit>, Reply<Token>> expressionP = null;
            var expressionRec = Rec(() => expressionP);
            
            expressionP = new OPPBuilder<Unit, Token, Unit>()
                .WithOperators(ops => ops
                    .AddPrefix("-", 5, WS, token => new NegateToken(token))
                    .AddPrefix("!", 5, WS, token => new NotToken(token))
                    .AddInfix("+", 10, WS, (x, y) => new AddToken(x, y))
                    .AddInfix("-", 10, WS, (x, y) => new SubtractToken(x, y))
                    .AddInfix("*", 20, WS, (x, y) => new MultiplyToken(x, y))
                    .AddInfix("/", 20, WS, (x, y) => new DivideToken(x, y))
                    .AddInfix("==", 30, WS, (x, y) => new EqualsToken(x, y))
                    .AddInfix("!=", 30, WS, (x, y) => new NotEqualsToken(x, y))
                    .AddInfix("<=", 30, WS, (x, y) => new LessThanEqualsToken(x, y))
                    .AddInfix("<", 30, WS, (x, y) => new LessThanToken(x, y))
                    .AddInfix(".", 40, WS, (x, y) => new AccessToken(x, Guard(y, y is VariableToken or FunctionCallToken)))
                )
                .WithTerms(term => Choice(
                        Native(term),
                        Declaration(term),
                        Instantiation(term),
                        Conditional(term),
                        While(term),
                        Assignment(term),
                        Block(term),
                        Atomic(term),
                        FunctionCall(term),
                        Variable(term),
                        Wrap('(', term, ')')
                        Match(expressionRec)
                    )
                )
                .Build()
                .ExpressionParser
                .Label("operator");

[bert2]

Don't worry 😊

Generally your approach seems fine to me. I did it similarly in the script parser example.

I can't see where the recursive loop might be, but try making the language easier too parse. For instance match <Expr> {...} or maybe even match <Expr> with {...} will require a lot less backtracking with AndTry() etc. Then you can move it way up in the list of term Choices, allowing the parser to rule it out as soon as possible.

[amir734jj]

match <Expr> with { ... } is so much nicer. I used that instead. Thank you so much

[bert2]

I tried around in LINQPad a bit. I'm parsing a very simplified version of your grammar, but with the same infinite recursion problem. The parser can parse programs like:

42

1 match {
  case 0 => -1,
  case 1 => -1
}

1 match {
  case 0 => -1,
  case 1 => 2 match { case 0 => 2, case 2 => -1 }
}

This is the parser/AST definition:

interface IExpr { }
record IntVal(int value) : IExpr;
record Arm(IntVal caseValue, IExpr caseResult);
record Match(IExpr toMatch, Arm[] arms) : IExpr;

void Main() {
    FSharpFunc<CharStream<Unit>, Reply<IExpr>>? allExprs = null;
    FSharpFunc<CharStream<Unit>, Reply<IExpr>>? allExprsExceptMatch = null;

    var intVal = Int.Map(v => new IntVal(v));

    var matchArm = Skip("case").AndR(WS1)
        .And(intVal).And(WS1)
        .And(Skip("=>")).And(WS)
        .And(Rec(() => allExprs))
        .Map((v, r) => new Arm(v, r));

    var matchExpr = Rec(() => allExprsExceptMatch) // don't try to parse a match expr here
                                                   // by using `allExprsExceptMatch`
        .And(WS1).And(Skip("match")).And(WS)
        .And(Between(
            CharP('{').And(WS),
            Many1(matchArm, CharP(',').And(WS)).And(WS),
            CharP('}')))
        .Map((toMatch, arms) => new Match(toMatch, arms.ToArray()));

    allExprsExceptMatch = Choice(
        intVal.Map(x => (IExpr)x)
        /* all your other parsers */);

    allExprs =
        Try(allExprsExceptMatch                           // attempt to parse anything, but if
            .And(NotFollowedBy(WS1.And_(Skip("match"))))) // it's a match expr we fail and backtrack
        .Or(matchExpr.Map(x => (IExpr)x));

    allExprs
        .Run("2 match { case 0 => 1, case 2 => -1 }")
        .GetResult()
        .Dump();
}

Note how the general parser that you want to use recursively has been split up into two: one for all your parsers except the match expression and one for the final parser combines all your parsers.

Not sure if this is a feasible approach in your scenario. But generally I'd opt for making the grammar less ambiguous to save me some major headaches 😄

[amir734jj]

@bert2 I have a different question. I am wondering is there a way to drop the user state?

I am trying to parser any string that doesn't contain those invalid chars AND it's not one of the reserved words.

            var invalidChars = new[]
                { ':', '"', ' ', '{', '}', '=', '(', ')', '\n', ';', ',', '*', '!', '.', '<' };
            var reservedKeyword = new[]
            {
                "match", "while", "with", "class", "extends", "if", "else", "case", "def", "null", "var", "new",
                "native"
            };

            FSharpFunc<CharStream<Unit>, Reply<string>> nameP = Many1CharsU<string>(x => !invalidChars.Contains(x))
                .AndL(UserStateSatisfies<string>(x => !reservedKeyword.Contains(x)))
                .AndL(UpdateUserState<Unit>(x => Unit))  // <--  how to drop the user state and use Unit instead (this line doesn't type check)
                .Label("name");

[bert2]

Hi @amir734jj, I don't think you need user state in this scenario. Have you seen this example of a similar identifier parser already?

[amir734jj]

Thank you so much. It worked.

[amir734jj]

@bert2 I promise this is the last question :)

I can't implement a match, there is probably some small mistake somewhere.

<Expr>         = <Atomic>
               ;

<Arm>          = case null '=>' <Expr>
               | case <Name> ':' <Name> '=>' <Expr>
               ;
             
<Arms>         = '{' (<Arm> ,)+ <Arm> '}' | '{' <Arm> '}' | '{' '}'
               ;

<Match>       = match <Expr> with <Arms>
               ;

I created this re-producible example:

using System;
using System.Linq;
using FParsec;
using FParsec.CSharp;
using Microsoft.FSharp.Collections;
using Microsoft.FSharp.Core;
using static FParsec.CSharp.PrimitivesCS; // combinator functions
using static FParsec.CSharp.CharParsersCS; // pre-defined parsers

namespace ConsoleApp
{
    class Program
    {   
        private static FSharpFunc<CharStream<Unit>, Reply<string>> Atomic()
        {
            var quotedStringP = Wrap('"', Regex(@"(?:[^\\""]|\\.)*"), '"')
                .Label("string");
            var numberP = Int
                .Label("number")
                .Map(x => x.ToString());
            var boolP = StringP("true").Or(StringP("false"))
                .Lbl("bool");
            var nullP = Skip("null")
                .Label("null")
                .Return("null");

            var atomicP = Choice(nullP, numberP, quotedStringP, boolP).Label("atomic");

            return SkipWs(atomicP);
        }
        
        private static FSharpFunc<CharStream<Unit>, Reply<string>> Name()
        {
            var invalidChars = new[]
                { ':', '"', ' ', '{', '}', '=', '(', ')', '\n', ';', ',', '*', '!', '.', '<', '>' };
            var reservedKeyword = new[]
            {
                "match", "while", "with", "class", "extends", "if", "else", "case", "def", "null", "var", "new",
                "native", "overrides"
            };

            var identifier = Many1Chars(NoneOf(invalidChars))
                .AndTry(id => reservedKeyword.Contains(id) ? Fail<string>("reserved") : Return(id))
                .Label("identifier");
            
            return identifier;
        }

        private static FSharpFunc<CharStream<Unit>, Reply<T>> Wrap<T>(
            char start,
            FSharpFunc<CharStream<Unit>, Reply<T>> p,
            char end)
        {
            var wrapP = Between(SkipWs(CharP(start)), SkipWs(p), SkipWs(CharP(end)));
            return wrapP;
        }

        private static FSharpFunc<CharStream<Unit>, Reply<FSharpList<T>>> SepBy<T>(
            char start,
            FSharpFunc<CharStream<Unit>, Reply<T>> p,
            char end,
            FSharpFunc<CharStream<Unit>, Reply<Unit>> delimiterP)
        {
            var arrItems = Many1(SkipWs(p), sep: delimiterP, canEndWithSep: false);
            var arrayP = Wrap(start, arrItems, end);
            return arrayP;
        }

        private static FSharpFunc<CharStream<Unit>, Reply<T>> SkipWs<T>(
            FSharpFunc<CharStream<Unit>, Reply<T>> p
        )
        {
            return Skip(WS).AndRTry(p).AndLTry(Skip(WS));
        }

        static void Main(string[] args)
        {
            var typeMatch = Name().AndLTry(WS).AndLTry(Skip(':')).AndLTry(WS).AndTry(Name()).AndLTry(WS)
                .AndLTry(Skip("=>")).AndLTry(WS).AndTry(Atomic())
                .Map(x => $"{x.Item1.Item1}:{x.Item1.Item2} => {x.Item2}")
                .Label("typeBranch");
                
            var nullMatch = Skip("null").AndTry_(WS).AndTry_(Skip("=>")).AndTry_(WS).AndRTry(Atomic())
                .Map(x => $"null:Any => {x}")
                .Label("nullBranch");

            var arm = Skip("case").AndTry_(WS1)
                .AndRTry(Choice(typeMatch, nullMatch))
                .Map(x => $"case {x}")
                .Label("arm");
                
            var arms = SepBy('{', arm, '}', Skip(','))
                .Map(x => $"{{ {string.Join(",", x)} }}")
                .Label("arms");

            var matchP = Skip("match").AndTry_(WS1).AndRTry(Atomic()).AndLTry(WS1).AndLTry(Skip("with"))
                .AndLTry(WS)
                .AndTry(arms)
                .Label("match")
                .Map(x => $"match {x.Item1} with {x.Item2}");
            
            var reply = matchP.ParseString("match null with { case null => null }");
            
            Console.WriteLine(reply.IsOk());
            Console.WriteLine(reply.Result);
        }
    }
}

The full code is here

[bert2]

The problem is that SkipWs() is eating away the whitespace you are later expecting between the expression to match and the with keyword.

I checked your repo. If you change the this line to:

var matchP = Skip("match").AndTry_(WS1).AndRTry(expressionRec).AndLTry(WS).AndLTry(Skip("with"))
// Use `WS` instead of `WS1` here -------------------------------------'

Then this test will pass after you change Atomic("null") to Atomic(null) in the assert.

Note that this is just a quickfix. I think it's better to not have that white space skipped. Ideally matchP should validate it's there but that might be hard to achieve, since it's not unusual that expressionRec skips trailing white-space (that's what the afterStringParser is often used for after all). A hacky way to get around that might be something like (untested):

[...].AndR(expressionRec).AndL(PreviousCharSatisfies(char.IsWhiteSpace)).AndL(Skip("with"))

Or just leave it out altogether, since we know the underlying OPP of expressionRec eats trailing white-space and would have consumed the with anyway if the space were missing:

[...].AndR(expressionRec).AndL(Skip("with"))

Some general advice:

• Don't use ParseString() for parsing. Use Run() instead so you get helpful parser error messages. In unit tests I mostly use Run().GetResult() for convenience.
• You are using waaay to much back-tracking with And*Try(). This should only be needed rarely. Back-tracking can cause confusing parser error messages and will decrease the parsing performance. I think skipping comments is a valid use case for back-tracking: try to parse a comment and skip all the whitespace around it; if there is no comment then back-track and don't skip any whitespace, because other parsers might expect it.

[amir734jj]

@bert2 Thank you so much for all the help. I learned so much about using parser combinators. Thank you so much for this awesome library you made :)