Writing a scanner and parser in Ada

Writing a scanner and parser in Ada

[Yves Cloutier]

Hi there, 

I'm new to Ada, but not to programming.

I'd like to know if there are any examples of how to write a scanner and parser in Ada.

I have a pet project where I have a DSL that I want to use as input, scan, parse, then output as Groff code.

I've done a working prototype in Perl, but have been putting off writing it in a real :) programming language.

I'd rather not touch C. I started a skeleton in D but I've always wanted to put some effort into learning Ada.  From what I've seen it seems like a strong and mature language, but the very small number of books out there (and most only covering until Ada95) have made it a bit offputting. But lets see what I can do anyways!

Re: Writing a scanner and parser in Ada

[Robert Eachus]

On Saturday, December 23, 2017 at 8:15:05 PM UTC-5, Yves Cloutier wrote:
> Hi there, 
> 
> I'm new to Ada, but not to programming.
> 
> I'd like to know if there are any examples of how to write a scanner and parser in Ada.

Welcome!

You don't really need to worry about learning Ada, and even Ada 83 texts will get you started.  Going beyond Ada 95 really requires reading this newsgroup or the equivalent.  What has been going on is providing support for specialized areas of programming.  (Some of the extensions like the container library are more general.)  For example, if you don't deal with complex numbers, you can pretty much skip Annex G.  (Well, if you need accuracy bounds for trig functions they are there as well.)

There are plenty of books out there on software engineering, or on various subfields like proofs of correctness.  If you want to do that in Ada, you probably want to download some SPARK documentation.  But SPARK is essentially an Ada subset plus a prover, and all that is integrated into GNAT.

As for parsing examples, you can get the GNAT source code, and I think it still uses a recursive descent parser.  I may be able to dig up a simple calculator program I wrote mostly to check the (fixed-point) arithmetic and numeric I/O on our compiler.  Again recursive descent about two pages.

If you want to get into other types of parsing, I was one of two people who supported and extended the LALR(k) tool on Multics.  Parsing seems to be one of those areas which was solved once, and all the experts are now retired.  Not as dumb as it seems.  Writing a recursive descent (LL(1)) compiler is fairly easy even without supporting tools.  If you do have tools?  Look-ahead LR (LALR) allows for better recovery from syntax errors, but there is no particular reason today to design a language which cannot be parsed by an LL(1) parser.

Re: Writing a scanner and parser in Ada

[Dmitry A. Kazakov]

On 2017-12-24 02:15, Yves Cloutier wrote:

> I'd like to know if there are any examples of how to write a scanner
> and parser in Ada.

Table-driven parser:

    http://www.dmitry-kazakov.de/ada/components.htm#Parsers_etc

> I have a pet project where I have a DSL that I want to use as input,
> scan, parse, then output as Groff code.

Normally for a domain-specific language you would do all that in a 
single step: match source against current table, descent/ascent and/or 
generate code, repeat.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Writing a scanner and parser in Ada

[Tero Koskinen]

Hi,

Yves Cloutier wrote:
> Hi there,
>
> I'm new to Ada, but not to programming.
>
> I'd like to know if there are any examples of how to write a scanner and parser in Ada.

I have some parsers available at
https://bitbucket.org/tkoskine/oboe/src/751154a47626928267b225b0028ee44c0002d116/src/oberon-parser.adb?at=default&fileviewer=file-view-default

and
https://bitbucket.org/tkoskine/jdaughter/src/308afa955ad6d7209100a27f8926cd66e63bed90/src/json-parser.adb?at=default&fileviewer=file-view-default

First one is parser for Oberon programming language and second one is 
JSON parser.

They aren't fully complete, but give you some examples how to write 
parsers in Ada (without using any external libraries).

Yours,
  Tero

Re: Writing a scanner and parser in Ada

[Niklas Holsti]

On 17-12-24 11:08 , Dmitry A. Kazakov wrote:
> On 2017-12-24 02:15, Yves Cloutier wrote:
>
>> I'd like to know if there are any examples of how to write a scanner
>> and parser in Ada.
>
> Table-driven parser:
>
>    http://www.dmitry-kazakov.de/ada/components.htm#Parsers_etc

Another useful tool is OpenToken:

http://stephe-leake.org/ada/opentoken.html

Quote: "OpenToken is a facility for performing token analysis and 
parsing within the Ada language. It supports two modes of parser 
programming; code generation similar to yacc, and Ada packages to 
construct the grammar and parse tables directly at run-time."

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: Writing a scanner and parser in Ada

[Lucretia]

On Sunday, 24 December 2017 01:15:05 UTC, Yves Cloutier  wrote:
> Hi there, 
> 
> I'm new to Ada, but not to programming.
> 
> I'd like to know if there are any examples of how to write a scanner and parser in Ada.

If you've ever done this in another language the principle is exactly the same, just the syntax is different.

https://github.com/stcarrez/ayacc
https://github.com/stcarrez/aflex

Will get you going using lex/yacc ports.

Re: Writing a scanner and parser in Ada

[Yves Cloutier]

On Saturday, December 23, 2017 at 11:07:37 PM UTC-5, Robert Eachus wrote:
> On Saturday, December 23, 2017 at 8:15:05 PM UTC-5, Yves Cloutier wrote:
> > Hi there, 
> > 
> > I'm new to Ada, but not to programming.
> > 
> > I'd like to know if there are any examples of how to write a scanner and parser in Ada.
> 
> Welcome!
> 
> You don't really need to worry about learning Ada, and even Ada 83 texts will get you started.  Going beyond Ada 95 really requires reading this newsgroup or the equivalent.  What has been going on is providing support for specialized areas of programming.  (Some of the extensions like the container library are more general.)  For example, if you don't deal with complex numbers, you can pretty much skip Annex G.  (Well, if you need accuracy bounds for trig functions they are there as well.)
> 
> There are plenty of books out there on software engineering, or on various subfields like proofs of correctness.  If you want to do that in Ada, you probably want to download some SPARK documentation.  But SPARK is essentially an Ada subset plus a prover, and all that is integrated into GNAT.
> 
> As for parsing examples, you can get the GNAT source code, and I think it still uses a recursive descent parser.  I may be able to dig up a simple calculator program I wrote mostly to check the (fixed-point) arithmetic and numeric I/O on our compiler.  Again recursive descent about two pages.
> 
> If you want to get into other types of parsing, I was one of two people who supported and extended the LALR(k) tool on Multics.  Parsing seems to be one of those areas which was solved once, and all the experts are now retired.  Not as dumb as it seems.  Writing a recursive descent (LL(1)) compiler is fairly easy even without supporting tools.  If you do have tools?  Look-ahead LR (LALR) allows for better recovery from syntax errors, but there is no particular reason today to design a language which cannot be parsed by an LL(1) parser.

Hi Robert, thanks for the warm welcome.

I've actually ordered Ada As a Second Language (15$ from abebooks.com) and Programming in Ada: A First Course.

I have Ada 95: Problem Solving and Program Design but right from the first chapter it makes reference to compiling code that's on the disk for using code that's already been done. Of course I don't have the disk ;(

I also ordered Compiler Engineering Using PASCAL, and thought I could follow that but try to code in Ada instead of Pascal.

Writing a full blown compiler is something I eventually want to do, but here is the approach I want to take:

1. use my DSL as an exercise in scanning/parsing/code generation. Target code being Groff. My DSL: https://www.dropbox.com/sh/d5emub0yza1r14r/AAA-f9MPmAQRuK_pX5GirrQoa?dl=0
2. Use this experience to implement a transpiler. Maybe parsing Oberon and generating code in another language.
3. Then finally extending this to generate native code.

A few other folks have provided some useful guidance below and I'll check those out too.

Re: Writing a scanner and parser in Ada

[Yves Cloutier]

On Sunday, December 24, 2017 at 4:08:56 AM UTC-5, Dmitry A. Kazakov wrote:
> On 2017-12-24 02:15, Yves Cloutier wrote:
> 
> > I'd like to know if there are any examples of how to write a scanner
> > and parser in Ada.
> 
> Table-driven parser:
> 
>     http://www.dmitry-kazakov.de/ada/components.htm#Parsers_etc
> 
> > I have a pet project where I have a DSL that I want to use as input,
> > scan, parse, then output as Groff code.
> 
> Normally for a domain-specific language you would do all that in a 
> single step: match source against current table, descent/ascent and/or 
> generate code, repeat.
> 
> -- 
> Regards,
> Dmitry A. Kazakov
> http://www.dmitry-kazakov.de

Hi Dimitry,

Yes my Perl version does all that in 1 pass, but one of the things I want to do is have it generate for different targets.  Groff was my initial one.  I wan't creating any kind of AST but I think I'll want to do that in my rewrite to make things simpler and allow for generating for other targets like maybe Latex, or epub etc...

I'll have a look, thanks for the link!

Re: Writing a scanner and parser in Ada

[Yves Cloutier]

On Sunday, December 24, 2017 at 9:40:42 AM UTC-5, Tero Koskinen wrote:
> Hi,
> 
> Yves Cloutier wrote:
> > Hi there,
> >
> > I'm new to Ada, but not to programming.
> >
> > I'd like to know if there are any examples of how to write a scanner and parser in Ada.
> 
> I have some parsers available at
> https://bitbucket.org/tkoskine/oboe/src/751154a47626928267b225b0028ee44c0002d116/src/oberon-parser.adb?at=default&fileviewer=file-view-default
> 
> and
> https://bitbucket.org/tkoskine/jdaughter/src/308afa955ad6d7209100a27f8926cd66e63bed90/src/json-parser.adb?at=default&fileviewer=file-view-default
> 
> First one is parser for Oberon programming language and second one is 
> JSON parser.
> 
> They aren't fully complete, but give you some examples how to write 
> parsers in Ada (without using any external libraries).
> 
> Yours,
>   Tero

Super, thanks Tero!

Re: Writing a scanner and parser in Ada

[Yves Cloutier]

On Sunday, December 24, 2017 at 10:09:06 AM UTC-5, Niklas Holsti wrote:
> On 17-12-24 11:08 , Dmitry A. Kazakov wrote:
> > On 2017-12-24 02:15, Yves Cloutier wrote:
> >
> >> I'd like to know if there are any examples of how to write a scanner
> >> and parser in Ada.
> >
> > Table-driven parser:
> >
> >    http://www.dmitry-kazakov.de/ada/components.htm#Parsers_etc
> 
> Another useful tool is OpenToken:
> 
> http://stephe-leake.org/ada/opentoken.html
> 
> Quote: "OpenToken is a facility for performing token analysis and 
> parsing within the Ada language. It supports two modes of parser 
> programming; code generation similar to yacc, and Ada packages to 
> construct the grammar and parse tables directly at run-time."
> 
> -- 
> Niklas Holsti
> Tidorum Ltd
> niklas holsti tidorum fi
>        .      @       .

Niklas, this looks interesting, I definitely look at this too.  Wow, so many options

Re: Writing a scanner and parser in Ada

[Dmitry A. Kazakov]

On 2017-12-25 17:35, Yves Cloutier wrote:

> Yes my Perl version does all that in 1 pass, but one of the things I
> want to do is have it generate for different targets. Groff was my
> initial one. I wan't creating any kind of AST but I think I'll want to
> do that in my rewrite to make things simpler and allow for generating
> for other targets like maybe Latex, or epub etc...

You don't need AST for that. Simply define code generator interface 
(tagged) with abstract operations generating pieces of code. For each 
target have a derived type implementing these operations. Pass a 
class-wide Target object as a parameter to the parser. If the actual is 
of Groff_Target the result is groff etc.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Writing a scanner and parser in Ada

[Yves Cloutier]

On Monday, December 25, 2017 at 12:08:38 PM UTC-5, Dmitry A. Kazakov wrote:
> On 2017-12-25 17:35, Yves Cloutier wrote:
> 
> > Yes my Perl version does all that in 1 pass, but one of the things I
> > want to do is have it generate for different targets. Groff was my
> > initial one. I wan't creating any kind of AST but I think I'll want to
> > do that in my rewrite to make things simpler and allow for generating
> > for other targets like maybe Latex, or epub etc...
> 
> You don't need AST for that. Simply define code generator interface 
> (tagged) with abstract operations generating pieces of code. For each 
> target have a derived type implementing these operations. Pass a 
> class-wide Target object as a parameter to the parser. If the actual is 
> of Groff_Target the result is groff etc.
> 
> -- 
> Regards,
> Dmitry A. Kazakov
> http://www.dmitry-kazakov.de

haha I'm quite new to Ada so most of what you just explained I don't quite understand.  But will get there. Baby steps.

I see that you created a SNOBOL-like pattern matcher.  This looks really useful for processing text.

Re: Writing a scanner and parser in Ada

[Dmitry A. Kazakov]

On 2017-12-25 19:57, Yves Cloutier wrote:
> On Monday, December 25, 2017 at 12:08:38 PM UTC-5, Dmitry A. Kazakov wrote:
>> On 2017-12-25 17:35, Yves Cloutier wrote:
>>
>>> Yes my Perl version does all that in 1 pass, but one of the things I
>>> want to do is have it generate for different targets. Groff was my
>>> initial one. I wan't creating any kind of AST but I think I'll want to
>>> do that in my rewrite to make things simpler and allow for generating
>>> for other targets like maybe Latex, or epub etc...
>>
>> You don't need AST for that. Simply define code generator interface
>> (tagged) with abstract operations generating pieces of code. For each
>> target have a derived type implementing these operations. Pass a
>> class-wide Target object as a parameter to the parser. If the actual is
>> of Groff_Target the result is groff etc.
>>
> haha I'm quite new to Ada so most of what you just explained I don't
> quite understand. But will get there. Baby steps.

It is not that complicated when you get into Ada's OO model. The idea is 
that you abstract away code generator (as well as the code source) fro 
the parser. Then you can use the same parser with all back-ends and all 
types of sources (file, string, stream, text-buffer etc)

> I see that you created a SNOBOL-like pattern matcher. This looks
> really useful for processing text.

Not really. Pattern matching is rarely useful. There are few cases like 
searching and skipping parts of text, partial and error-tolerant parsing 
(like in text coloring). But even then simple wildcard patterns (like * 
and %) often work better because they are easier to understand.

The rationale is this. More powerful the formal language of patterns is, 
more difficult it becomes for the user to foresee and understand what 
the pattern will match and what not. Regular expressions are already too 
complex. SNOBOL patterns are even more powerful, so that anything beyond 
trivial quickly becomes not understandable.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Writing a scanner and parser in Ada

[Shark8]

On Monday, December 25, 2017 at 12:19:29 PM UTC-7, Dmitry A. Kazakov wrote:
> 
> The rationale is this. More powerful the formal language of patterns is, 
> more difficult it becomes for the user to foresee and understand what 
> the pattern will match and what not. Regular expressions are already too 
> complex. SNOBOL patterns are even more powerful, so that anything beyond 
> trivial quickly becomes not understandable.


I'm not sure that's true. Chapter 7 of "A Snobol4 Tutorial" from snobol4.org -- http://www.snobol4.org/docs/burks/tutorial/ch7.htm -- has as its first example matching a list.

------------------------------------------------
Let's consider a simple example. We want to write a pattern to test for a list. We'll define a list as being one or more numbers separated by comma, and enclosed by parentheses. Use CODE.SNO to try this definition:
    ?       ITEM = SPAN('0123456789')
    ?       LIST = POS(0) '(' ITEM  ARBNO(',' ITEM) ')' RPOS(0)
    ?       '(12,345,6)' LIST
    Success
    ?       '(12,,34)' LIST
    Failure

ARBNO is retried and extended until its subsequent, ')', finally matches. POS(0) and RPOS(0) force the pattern to be applied to the entire subject string. 
Alternation may be used within ARBNO's argument.
------------------------------------------------

The above seems quite straightforward, and IMO, easier to comprehend than an equivalent regular expression. Especially because breaking out of the realm of regular languages simply by making the definition recursive [LISTs that can contain LISTs] can be achieved simply by appending " | *LIST" to the definition of ITEM.

So, IMO, SNOBOL itself proves as a counterexample to your claim.

Re: Writing a scanner and parser in Ada

[Dmitry A. Kazakov]

On 2017-12-26 19:06, Shark8 wrote:

> Let's consider a simple example. We want to write a pattern to test 
> for a list. We'll define a list as being one or more numbers
> separated by comma, and enclosed by parentheses.

Toy examples prove nothing.

> The above seems quite straightforward, and IMO, easier to comprehend
> than an equivalent regular expression.
Yes SNOBOL is easier to understand than regular expressions, because it 
was designed as programming language. Regular expressions were not.

> So, IMO, SNOBOL itself proves as a counterexample to your claim.

No, it does not prove that. Griswold et all give in their book an 
example of SNOBOL parser written in SNOBOL. Compare that with a parser 
written in Ada.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Writing a scanner and parser in Ada

[Dmitry A. Kazakov]

On 2017-12-26 19:06, Shark8 wrote:

> Let's consider a simple example. We want to write a pattern to test 
> for a list. We'll define a list as being one or more numbers
> separated by comma, and enclosed by parentheses. Use CODE.SNO to try
> this definition:
>      ?       ITEM = SPAN('0123456789')
>      ?       LIST = POS(0) '(' ITEM  ARBNO(',' ITEM) ')' RPOS(0)
>      ?       '(12,345,6)' LIST
>      Success
>      ?       '(12,,34)' LIST
>      Failure
> 
> ARBNO is retried and extended until its subsequent, ')', finally 
> matches. POS(0) and RPOS(0) force the pattern to be applied to the
> entire subject string.

I forgot to show the pattern in my syntax:

   '(' digit $digit $(',' digit $digit) ')' END

digit matches '0'..'9'. '$' is an eager repeater similar to 'ARBNO', so 
$digit is a sequence of digits, maybe empty. digit $digit is a sequence 
of at least one digit. END matches line end. Matching is always 
anchored, using SNOBOL terms.

BTW, one could consider adding a 'FENCE' or two to prevent backtracking 
because, and this is the reason why the pattern is that simple, the 
matching could never give back anything it already matched.

It is a kind of problem if you have patterns successfully matching empty 
strings that are put under a repeater. You may run into an infinite loop 
with backtracking.

As I said it is a toy example which is far easier and more importantly 
*safer* to write in Ada. And the result will be more readable and far 
more maintainable in the future.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de