parser combinator library

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

parser combinator library

Bernd K.
Hello,

Eight years ago someone asked whether there is a parser combinator library for free pascal, nothing like that existed at that time and also does not seem to exist up to the present day.

While I was reading about parser combinators in functional programming languages (during my 42nd attempt to learn Haskell) I thought to myself why not try to implement something like that in Object Pascal, just so see how far we can push the boundaries of this imperative object oriented language.

This is what I have come up with so far:
https://github.com/prof7bit/fpc_parser_combinators

Since we don't have lambdas I choose the next closest approach to emulate them with object instances instead. This leads to a lot of boiler plate in the definition of the elementary parsers and combinators but fortunately it can all be hidden away in the library and the usage of the combinators looks quite neat:

 // define the grammar
  EXPR      := Num or _PARENS;
  MULFUNC   := Sym('mul') and EXPR and EXPR;
  ADDFUNC   := Sym('add') and EXPR and EXPR;
  INNER     := MULFUNC or ADDFUNC or Num;
  PARENS    := Sym('(') and INNER and Sym(')');


Please also note the unorthodox usage of and/or operators to invoke the combinators :-)

Please post improvements or variations of this theme, especially I am interested in how to properly build up a syntax tree in the most generic and reusable manner, this is something I have not yet completely understood (because I am myself still quite unfamiliar with this whole parsing business) currently all my parsers only return arrays of strings that I can optionally post-process with an optional hook function after a parser has completed.

Bernd

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: parser combinator library

leledumbo
Administrator
This post has NOT been accepted by the mailing list yet.
> This is what I have come up with so far:
> https://github.com/prof7bit/fpc_parser_combinators
>
> Since we don't have lambdas I choose the next closest approach to emulate
> them with object instances instead. This leads to a lot of boiler plate in
> the definition of the elementary parsers and combinators but fortunately it
> can all be hidden away in the library and the usage of the combinators
> looks quite neat:
>
>  // define the grammar
>   EXPR      := Num or _PARENS;
>   MULFUNC   := Sym('mul') and EXPR and EXPR;
>   ADDFUNC   := Sym('add') and EXPR and EXPR;
>   INNER     := MULFUNC or ADDFUNC or Num;
>   PARENS    := Sym('(') and INNER and Sym(')');
>
> Please also note the unorthodox usage of and/or operators to invoke the
> combinators :-)

Wow! I never thought of making such a library in an OO way. I was also looking for this for Object Pascal when I learned Haskell in college, but I'm still a huge fan of purely handwritten recursive descent parser as I found Haskell's parsec somewhat limited in error handling, which is super flexible in recursive descent parser.

Your abstraction using operator overloading is nice and easily reflect the grammar, I salute you for this.

> Please post improvements or variations of this theme, especially I am
> interested in how to properly build up a syntax tree in the most generic
> and reusable manner, this is something I have not yet completely understood
> (because I am myself still quite unfamiliar with this whole parsing
> business) currently all my parsers only return arrays of strings that I can
> optionally post-process with an optional hook function after a parser has
> completed.

I don't think there's a really good way to implement generic syntax tree. At best I can think of is:

type
  PNode = ^TNode;
 
  PNodeList = ^TNodeList;
  TNodeList = record
    Node: PNode;
    Next: PNodeList;
  end;

  TNode = record
    Token: TToken; // I always store this for generating exact error location information, not a must if you don't want to provide one
    Kind: String; // or Integer if you like
    Value: String; // no better data type for holding generic value, I guess
    Children: PNodeList;
  end;

Now you need to define how Kind, Value and Children forms a node, which would be quite error prone in my experience, compared to having limited predefined set of Kind, with Value and Children (and not necessarily them) defined by each specific node variant as variant record fields. You can generate the nodes in your hook function.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: parser combinator library

noreply
In reply to this post by Bernd K.
On 2017-02-24 15:00, Bernd wrote:

> Hello,
>
> Eight years ago someone asked whether there is a parser combinator
> library for free pascal, nothing like that existed at that time and
> also does not seem to exist up to the present day.
>
> While I was reading about parser combinators in functional programming
> languages (during my 42nd attempt to learn Haskell) I thought to
> myself why not try to implement something like that in Object Pascal,
> just so see how far we can push the boundaries of this imperative
> object oriented language.
>
> This is what I have come up with so far:
> https://github.com/prof7bit/fpc_parser_combinators
>
> Since we don't have lambdas I choose the next closest approach to
> emulate them with object instances instead. This leads to a lot of
> boiler plate in the definition of the elementary parsers and
> combinators but fortunately it can all be hidden away in the library
> and the usage of the combinators looks quite neat:
>
>  // define the grammar
>   EXPR      := Num or _PARENS;
>   MULFUNC   := Sym('mul') and EXPR and EXPR;
>   ADDFUNC   := Sym('add') and EXPR and EXPR;
>   INNER     := MULFUNC or ADDFUNC or Num;
>   PARENS    := Sym('(') and INNER and Sym(')');
>
> Please also note the unorthodox usage of and/or operators to invoke
> the combinators :-)

Cool! Parsing is my favourite area of computing science..

And my 42 attempt at learning haskell I gave up because it seemed not to
be able to do a simple char by char parser like any procedural language
can do...

But, now that you've mentioned this, my interest has peaked in both
Object Pascal and Haskell.

>
> Please post improvements or variations of this theme, especially I am
> interested in how to properly build up a syntax tree in the most
> generic and reusable manner, this is something I have not yet
> completely understood (because I am myself still quite unfamiliar with
> this whole parsing business) currently all my parsers only return
> arrays of strings that I can optionally post-process with an optional
> hook function after a parser has completed.

I think parsing is still something computing science has to study more.
There are many undiscovered techniques. The biggest issue I have seen is
large long case statements where you start duplicating code in the case
statement. Rob Pike has done some work on this, but I've had little time
to research his solution proposed.
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Loading...