Back to Questions
1.9k
views8
comments
FParsec: How do I build a parser that succeeds based on an if statement, but fails on the else clause?
f#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

    let identStart c = isAsciiLetter c || c = '_'
    let identContinue c = isAsciiLetter c || isDigit c || c = '_'
    let identOptions = 
        IdentifierOptions(
            isAsciiIdStart = identStart,
            isAsciiIdContinue = identContinue,
            normalization = nf.FormKC,
            normalizeBeforeValidation = true)
 
    let ident = identifier identOptions
    let lookup (registry : IRegistry<_>, text : string) =
        let result = registry.Find(text)
        result
 
    let verb = ident .>> ws |>> 
        fun i ->
            let registry = manager.GetVerbRegistry()
            let lexeme = lookup(registry, i)
            lexeme
 
    let pverb = verb |>> fun lexeme ->
        if lexeme.IsVerb then
            lexeme |> Expr.Verb
        else 
            Error // <-- throw some error that signifies that this parser didnt work
 
    let pverbs = verb |>> fun lexeme ->
        if lexeme.IsVerbs then
            lexeme |> Expr.Verbs
        else 
            Error // <-- throw some error that signifies that this parser didnt work

I only want fail without consuming input if it doesnt match the condition. However, instead of building the matching out of raw parsers,
in this case I want to do a lookup that tells me if the input is 'in; the grammar. Thanks for any help or hints anyone can provide... ;)

Scott

.

Do you mean something like

1
2
3
4
5
6
7
8
9
10
11

let If predicate (p: Parser<_,_>) : Parser<_,_> =    
    fun stream ->
        let state = stream.State
        let reply = p stream
        if reply.Status <> Ok || predicate reply.Result then reply        
        else
            stream.BacktrackTo(state) 
            Reply(Error, NoErrorMessages)


let pverb = verb |> If lexeme.IsVerb

?

By on 8/16/2011 12:27 PM ()

oooh- That is super fancy and most definitely what I am looking for. It does look similar to some of your examples in the documentation, but I wasn't sure how to translate my desire into fparsec code. Thanks again for your prompt help and fabulous project. I am really liking programming my parser in fparsec!

Thanks,

Scott

By on 8/16/2011 3:16 PM ()

bummer- that didn't work. It seems that my verb binding is really returning a Parser<Lexeme, UserState> instead of just a Lexeme. Stranger still when I try your code that you posted it failes because it thinks the lexeme you are passing to the If binding is an object rather than a Lexeme. Is there something else I can try?

Thanks,

Scott

By on 8/16/2011 11:48 PM ()

Could you provide a minimal complete example that I can try to make work?

By on 8/17/2011 1:03 AM ()

// C# Language Class Library

// Lexeme.cs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Poc.Language
{
	public class Lexeme<TItem>
		where TItem : Verb
	{
		public Lexeme(int dot, params TItem[] items)
		{
			Dot = dot;
			_Items = items;
		}

		public bool IsMatched
		{
			get
			{
				return _Items != null && _Items.Length > 0 ? _Items.Any(item => item.IsMatched(Dot)) : false;
			}
		}

		public int Dot { get; set; }
		public TItem Item { get { return _Items != null && _Items.Length > 0 ? _Items[0] : null; } }
		public TItem[] Items { get { return _Items; } }
		private TItem[] _Items;
	}

}

// Manager.cs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Poc.Language
{
	public class Manager
	{
		public Manager()
		{
			Verb open = new Verb("open");
			Verb set = new Verb("set");
			Verb delete = new Verb("delete");

			var verbs = new Registry<Verb>();
			verbs.Register(new Verb[] { open, set, delete });
			_VerbRegistry = verbs;

		}

		public Lexeme<Verb> FindVerb(string name)
		{
			return _VerbRegistry.Find(name);
		}

 

		public Registry<Verb> GetVerbRegistry() { 
return _VerbRegistry; 
}
		private Registry<Verb> _VerbRegistry;
	}
}

// Registry.cs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Poc.Language
{
	public class Registry<TItem>
		where TItem : Verb
	{
		public Registry(params TItem[] items)
		{
			Register(items);
		}

		public void Register(params TItem[] items)
		{
			_Items.AddRange(items);
		}

		public void Unregister(params TItem[] items)
		{
			items.ToList().ForEach(item => _Items.Remove(item));
		}

		public Lexeme<TItem> Find(string text)
		{
			Lexeme<TItem> lexeme = null;
			if (string.IsNullOrWhiteSpace(text))
			{
				int dot = text.Length;
				var items = _Items.Where(item => item.Name.Length >= dot && item.Name.Substring(0, dot).Equals(text)).ToArray();
				lexeme = new Lexeme<TItem>(dot, items);
			}
			return lexeme;
		}

		private List<TItem> _Items = new List<TItem>();
	}

}

// Verb.cs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Poc.Language
{
	public class Verb
	{
		public Verb() : this(null) { }
		public Verb(string name) { Name = name; }
		public string Name { get; internal set; }
		public bool IsMatched(int dot)
		{
			if (0 <= dot && dot < Name.Length)
				return false;
			return true;
		}
	}
}

// F# Parser Class Library (include ref to Language.dll)

// Ast.fs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

namespace Poc.Parser
open System
open FParsec
open Poc.Language

type UserState = unit
type Parser<'t> = Parser<'t, UserState>
type Ident = string

type Expr = 
    | Var of Ident
    | Int of int
    | Float of float32
    | Double of double
    | String of string
    | Oper of Expr * Expr list
    | Verb of Lexeme<Verb>
    | Verbs of Lexeme<Verb>

// Parser.fs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163

namespace Poc.Parser
open System
open System.Collections.Generic
open FParsec
open FParsec.Primitives
open FParsec.CharParsers
open Poc.Language

type nf = System.Text.NormalizationForm

type Parser() =
    let manager = new Manager()
    let ws : Parser<_> = spaces
    let ch c = skipChar c >>. ws
    let str s = pstring s .>> ws

    let lparen = ch '('
    let rparen = ch ')'
    let tab = pchar '\t'
    let space = pchar ' '
    let comma = pchar ','
    let period = pchar '.'
    let newline = pchar '\n'
    let underscore = pchar '_'

    let identStart c = isAsciiLetter c || c = '_'
    let identContinue c = isAsciiLetter c || isDigit c || c = '_'
    let identOptions = 
        IdentifierOptions(
            isAsciiIdStart = identStart,
            isAsciiIdContinue = identContinue,
            normalization = nf.FormKC,
            normalizeBeforeValidation = true)
 
    let ident = identifier identOptions
    let pident = ident |>> Expr.Var
 
    let stringStart c = isAsciiLetter c || isDigit c || c = '_'
    let stringContinue c = isAsciiLetter c || isDigit c || c = '_' || c = ' '
    let stringOptions =
        IdentifierOptions(
            isAsciiIdStart = stringStart,
            isAsciiIdContinue = stringContinue,
            normalization = nf.FormKC,
            normalizeBeforeValidation = true)
 
    let string = identifier stringOptions
    let pstring = string |>> Expr.String

    let aoc2str aoc = new System.String(Array.ofList aoc)

    // -?[0-9]+(\.[0-9]*)?([eE][+-]?[0-9]+)?
    let numberFormat =  NumberLiteralOptions.AllowMinusSign
                    ||| NumberLiteralOptions.AllowFraction
                    ||| NumberLiteralOptions.AllowExponent
                    ||| NumberLiteralOptions.AllowSuffix

    let number =
        numberLiteral numberFormat "number"
        |>> fun nl ->
            if nl.IsInteger then Expr.Int (int32 nl.String)
            elif nl.IsDecimal && Char.ToLower(nl.SuffixChar1) = 'f' then Expr.Float (float32 nl.String)
            else Expr.Double (double nl.String)

    let opp = new OperatorPrecedenceParser<_,_,_>()
    let exprNoComma = opp.ExpressionParser

    let var = sepBy1 exprNoComma (ch ',') |>> (List.reduce (fun acc e -> Oper(Var ",", [acc;e])))
    let vars = many var
    let parenExpr = between lparen rparen var

    let prim = choice [parenExpr;pident;number;pstring]

    let argList = sepBy exprNoComma (ch ',')
    let oper = between lparen rparen argList |>> (fun args fct -> Oper(fct, args))

    let simpleExpr = pipe2 prim (many oper) (fun prim ops -> List.fold (fun acc elt -> elt acc) prim ops)

    do opp.TermParser <- simpleExpr

    let precedence1 = 
        [
            ["*"; "/"; "%"], Associativity.Left
            ["+"; "-"], Associativity.Left
            ["<<"; ">>"], Associativity.Left
            ["<"; ">"; "<="; ">="], Associativity.Left
            ["=="; "!="], Associativity.Left
            ["&"], Associativity.Left
            ["^"], Associativity.Left
            ["|"], Associativity.Left
            ["&&"], Associativity.Left
            ["^^"], Associativity.Left
            ["||"], Associativity.Left
        ]

    let precedence2 = 
        [
            ["="; "+="; "-="; "*="; "/="; "%="; "<<="; ">>="; "&="; "^="; "|="], Associativity.Right
        ]

    // Add all the operators in the OperatorParser
    let makeOperator =
      // we start with operators with highest priority, then we decrement the counter.
        let precCounter = ref 20 //(we have at most 20 different priorities)
        let addInfix li =
            for ops, assoc in li do
                decr precCounter
                for op in ops do
                    opp.AddOperator(InfixOperator(op, ws, !precCounter, assoc, fun x y -> Oper(Var op, [x; y])))

        let addPrefix() =
            decr precCounter
            for op in ["++"; "--"; "+"; "-"; "~"; "!"] do
                opp.AddOperator(PrefixOperator(op, ws, !precCounter, true, fun x -> Oper(Var op, [x])))

        let addPostfix() =
            decr precCounter
            for op in ["++"; "--"] do
                // the '$' prefix in the name is a trick to distinguish ++a from a++ in the AST
                opp.AddOperator(PostfixOperator(op, ws, !precCounter, true, fun x -> Oper(Var ("$"+op), [x])))

        addPostfix()
        addPrefix()
        addInfix precedence1
        decr precCounter
        opp.AddOperator(TernaryOperator("?", ws, ":", ws, !precCounter, Associativity.Right, fun x y z -> Oper(Var "?:", [x;y;z])))
        addInfix precedence2

    let lookup (registry : Registry<_>, text : string) =
        let result = registry.Find(text)
        result

    let If predicate (parser : Parser<_,_>) : Parser<_,_> = 
        fun stream ->
            let state = stream.State
            let reply = parser stream
            if reply.Status <> Ok || predicate reply.Result then reply
            else
                stream.BacktrackTo(state)
                Reply(Error, NoErrorMessages)

    let verb = ident .>> ws |>> 
        fun i ->
            let registry = manager.GetVerbRegistry()
            let lexeme = lookup(registry, i)
            lexeme

    let pverb = verb |>> Expr.Verb // <-- wrong
    let pverb = verb |> If lexeme.IsMatched |> Expr.Verb // <-- based on your suggestion
    let pverbs = verb |> If !lexeme.IsMatched |> Expr.Verbs 

    let run parser (input : string) =
        runParserOnString parser () "" input

    let parseVerb = ws >>. pverb .>> eof

    member this.ParseVerb(input : string) =
        let result = run parseVerb input
        match result with
        | Success(v,_,_) -> v
        | Failure(msg,_,_) ->
            System.Console.WriteLine(msg)
            exit 1

// C# Console Application (include refs to Language.dll and Parser.dll)

// Program.cs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using Poc.Language;
using Poc.Parser;
 
namespace ParserProofOfConcept2
{
	class Program
	{
		static void Main(string[] args)
		{
			Parser parser = new Parser();
			var result = parser.ParseVerb("ope");
		}
	}
}
By on 8/17/2011 11:42 PM ()

This is the absolute minimal set of code that represents what I am doing, with the lone exception that you could combine all of the cs class definitions into one file. I am assuming if you want to do that the way I have broken it up won't stop you. ;)

Thanks for taking the time to look at it, Stephan

-Scott

By on 8/17/2011 11:44 PM ()

There's a simple error in my previous answer.

Does maybe

1

let pverb = verb |> If (fun lexeme -> lexeme.IsVerb) |>> Expr.Verb

work for you?

I didn't have time to look at your whole example.

By on 8/18/2011 9:50 AM ()

That did it and gave me some ideas on how to solve my problem...

Thanks,

Scott

By on 8/21/2011 12:22 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper