unofficial mirror of guile-user@gnu.org 
 help / color / mirror / Atom feed
* Re: Re: parse-result (Catonano)
       [not found] <mailman.109.1547658023.1050.guile-user@gnu.org>
@ 2019-01-16 20:31 ` Zelphir Kaltstahl
  2019-01-16 21:47   ` tomas
  2019-01-17  7:16   ` swedebugia
  2019-01-16 20:34 ` Tangerine Edition penultimate report: how I voted, how you're, voting (John Cowan) Zelphir Kaltstahl
  1 sibling, 2 replies; 13+ messages in thread
From: Zelphir Kaltstahl @ 2019-01-16 20:31 UTC (permalink / raw)
  To: catonano@gmail.com >> Catonano; +Cc: Guile User

Perhaps I should put a link into the source code whenever I follow a
tutorial. Sorry for the confusion!

I am also only following Amirouche Boubekki's tutorial ; ) Good that you
already found it.

There is a paper about parser combinators (which I did not completely
implement, because I had a bug somewhere, where I did not find it at
some point), about parser combinators:
http://www.cs.nott.ac.uk/~pszgmh/monparsing.pdf

It takes some time to get used to the Gopher code syntax, but from the
part of the paper, that I read, it is quite clever stuff, all this
parser combinator stuff.

I am still unsure about the theoretical CS stuff: What kind of parsers
one can possibly write with parser combinators? Which language class is
that? I have language X can I parse it completely using parser
combinators? etc. Theoretical CS and the proofs were not my strongest area.

On 1/16/19 6:00 PM, guile-user-request@gnu.org wrote:
> Ok I found this
>
> https://hyperdev.fr/blog/getting-started-with-guile-parser-combinators.html



^ permalink raw reply	[flat|nested] 13+ messages in thread

* Re: Tangerine Edition penultimate report: how I voted, how you're, voting (John Cowan)
       [not found] <mailman.109.1547658023.1050.guile-user@gnu.org>
  2019-01-16 20:31 ` Re: parse-result (Catonano) Zelphir Kaltstahl
@ 2019-01-16 20:34 ` Zelphir Kaltstahl
  2019-01-20  2:24   ` John Cowan
  1 sibling, 1 reply; 13+ messages in thread
From: Zelphir Kaltstahl @ 2019-01-16 20:34 UTC (permalink / raw)
  To: guile-user

On 1/16/19 6:00 PM, guile-user-request@gnu.org wrote:
> Message: 2
> Date: Wed, 16 Jan 2019 09:27:50 -0500
> From: John Cowan <cowan@ccil.org>
> To: scheme-reports-wg1@googlegroups.com,
> 	scheme-reports-wg2@googlegroups.com, 	chicken chicken
> 	<chicken-users@nongnu.org>, chibi-scheme@googlegroups.com,
> 	gambit-list@iro.umontreal.ca, guile-user <guile-user@gnu.org>,
> 	srfi-160@srfi.schemers.org
> Subject: Tangerine Edition penultimate report: how I voted, how you're
> 	voting
> Message-ID:
> 	<CAD2gp_SVHEqhz1wYifeKYJGf6B+74121M6zmXARwsm_KZwd3cQ@mail.gmail.com>
> Content-Type: text/plain; charset="UTF-8"
>
> Well, there are two weeks to go on the Tangerine Edition ballot (cutoff is
> 12 noon UTC on Saturday, February 2).  So far, 18 people have voted,
> including me.  For the Red Edition we had 30 voters, so I hope some of you
> who haven't voted yet will take an interest and give us your views.
> Remember that you don't have to vote on all issues: choosing "No vote" is
> equivalent to abstaining, which does not affect the outcome, as votes are
> decided by a majority of the votes cast.
>
> As in the Red Edition, the choice of string library (issue #1) has been the
> most controversial.  There was no majority vote cast in the Red Edition, so
> the issue is being reballoted.  Currently, the index-based SRFI 152, which
> is meant to be a simple basic string library, holds a majority position,
> but only by a single vote.  There is a strong minority for the original
> SRFI 13, which is a superset (with a few deviations) of 152.  SRFI 130,
> which is cursor-based, has only a single vote.  Three write-in votes were
> cast for SRFI 140, which I excluded from Tangerine because it provides
> adjustable-length strings.  These, like all other features that can't be
> implemented (at least minimally) on top of R7RS-small, have been postponed
> to the Green Edition.  I voted for SRFI 152.
>
> Issue #4, supplementing the Red Edition's SRFI 127 generators with their
> dual, accumulators, is substantially beating the alternatives of status quo
> and no library.  Issue #6 is about bitwise operations on integers, and the
> comprehensive SRFI 151 is dominating the R6RS alternative.  The same thing
> is happening with fixnums (issue #7) and flonums (issue #8), where SRFIs
> 143 and 144, both supersets of R6RS, are getting more support than the R6RS
> alternatives. SRFI 160 is a superset of SRFI 4 that provides homogeneous
> vectors (issue #10), and it too is winning, though by a lesser margin.
> Surprising to me is that for the combinator-based formatting library (issue
> #11), the combinator-based SRFI 159 is in a majority position over SRFI 48,
> the traditional template-based (as in Common Lisp) alternative.
> Essentially all the remaining issues are yes/no/abstain, and yes is
> dominant all down the line, though a little less so for ratios (issue #13)
> and exact complex numbers (issue #16).  I voted with the majority for all
> of these except exact complex numbers.
>
> So what is happening is that people are voting for more rather than less,
> as with the Red Edition.  This encourages me that I'm going in a sensible
> direction with the large language.
>
> -- John Cowan http://vrici.lojban.org/~cowan cowan@ccil.org It was
> dreary and wearisome. Cold clammy winter still held sway in this
> forsaken country. The only green was the scum of livid weed on the
> dark greasy surfaces of the sullen waters. Dead grasses and rotting
> reeds loomed up in the mists like ragged shadows of long-forgotten
> summers. --LOTR, "The Passage of the Marshes"
I am not sure I have a sufficiently informed opinion about SRFIs and
such things. How experienced should a person be, as to not simply vote
for something that superficially might sound great, but actually isn't
so good and screw up the voting?



^ permalink raw reply	[flat|nested] 13+ messages in thread

* Re: Re: parse-result (Catonano)
  2019-01-16 20:31 ` Re: parse-result (Catonano) Zelphir Kaltstahl
@ 2019-01-16 21:47   ` tomas
  2019-01-17  7:16   ` swedebugia
  1 sibling, 0 replies; 13+ messages in thread
From: tomas @ 2019-01-16 21:47 UTC (permalink / raw)
  To: guile-user

[-- Attachment #1: Type: text/plain, Size: 755 bytes --]

On Wed, Jan 16, 2019 at 09:31:13PM +0100, Zelphir Kaltstahl wrote:
> Perhaps I should put a link into the source code whenever I follow a
> tutorial. Sorry for the confusion!

[...]

> I am still unsure about the theoretical CS stuff: What kind of parsers
> one can possibly write with parser combinators? Which language class is
> that? I have language X can I parse it completely using parser
> combinators? etc. Theoretical CS and the proofs were not my strongest area.

AFAIK they implement recursive descent parsers [1], i.e. they are good for
LL languages (LL(k) if there is a way to "peek ahead").

Thus they aren't as powerful as table based parsers -- but easier to grok.

Cheers

[1] https://en.wikipedia.org/wiki/Recursive_descent_parsers
-- t

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

^ permalink raw reply	[flat|nested] 13+ messages in thread

* Re: Re: parse-result (Catonano)
  2019-01-16 20:31 ` Re: parse-result (Catonano) Zelphir Kaltstahl
  2019-01-16 21:47   ` tomas
@ 2019-01-17  7:16   ` swedebugia
  2019-01-17  7:43     ` Re parse-result Zelphir Kaltstahl
  1 sibling, 1 reply; 13+ messages in thread
From: swedebugia @ 2019-01-17  7:16 UTC (permalink / raw)
  To: Zelphir Kaltstahl, catonano@gmail.com >> Catonano; +Cc: Guile User

[-- Attachment #1: Type: text/plain, Size: 1447 bytes --]

   Zelphir Kaltstahl <zelphirkaltstahl@gmail.com> skrev: (16 januari 2019
   21:31:13 CET)

Perhaps I should put a link into the source code whenever I follow a
tutorial. Sorry for the confusion!
I am also only following Amirouche Boubekki's tutorial ; ) Good that you
already found it.
There is a paper about parser combinators (which I did not completely
implement, because I had a bug somewhere, where I did not find it at
some point), about parser combinators:
http://www.cs.nott.ac.uk/~pszgmh/monparsing.pdf
It takes some time to get used to the Gopher code syntax, but from the
part of the paper, that I read, it is quite clever stuff, all this
parser combinator stuff.
I am still unsure about the theoretical CS stuff: What kind of parsers
one can possibly write with parser combinators? Which language class is
that? I have language X can I parse it completely using parser
combinators? etc. Theoretical CS and the proofs were not my strongest area.
On 1/16/19 6:00 PM, guile-user-request@gnu.org wrote:

     Ok I found this
     [1]https://hyperdev.fr/blog/getting-started-with-guile-parser-combin
     ators.html

   Hi.
   Have you looked at the PEG parser recently added to guile? It does
   everything the combinators do with an added compressor.
   Its quite powerful and seems to work well.
   --
   Sent from my pa 0/00!p for Android.

References

   1. https://hyperdev.fr/blog/getting-started-with-guile-parser-combinators.html

[-- Attachment #2: pEpkey.asc --]
[-- Type: application/pgp-keys, Size: 3825 bytes --]

^ permalink raw reply	[flat|nested] 13+ messages in thread

* Re: Re parse-result
  2019-01-17  7:16   ` swedebugia
@ 2019-01-17  7:43     ` Zelphir Kaltstahl
  2019-01-17  9:56       ` swedebugia
                         ` (2 more replies)
  0 siblings, 3 replies; 13+ messages in thread
From: Zelphir Kaltstahl @ 2019-01-17  7:43 UTC (permalink / raw)
  To: swedebugia, catonano@gmail.com >> Catonano; +Cc: Guile User


On 1/17/19 8:16 AM, swedebugia wrote:
> Zelphir Kaltstahl <zelphirkaltstahl@gmail.com> skrev: (16 januari 2019
> 21:31:13 CET)
>
>     Perhaps I should put a link into the source code whenever I follow a
>     tutorial. Sorry for the confusion!
>
>     I am also only following Amirouche Boubekki's tutorial ; ) Good that you
>     already found it.
>
>     There is a paper about parser combinators (which I did not completely
>     implement, because I had a bug somewhere, where I did not find it at
>     some point), about parser combinators:
>     http://www.cs.nott.ac.uk/~pszgmh/monparsing.pdf
>
>     It takes some time to get used to the Gopher code syntax, but from the
>     part of the paper, that I read, it is quite clever stuff, all this
>     parser combinator stuff.
>
>     I am still unsure about the theoretical CS stuff: What kind of parsers
>     one can possibly write with parser combinators? Which language class is
>     that? I have language X can I parse it completely using parser
>     combinators? etc. Theoretical CS and the proofs were not my strongest area.
>
>     On 1/16/19 6:00 PM, guile-user-request@gnu.org wrote:
>
>         Ok I found this
>         https://hyperdev.fr/blog/getting-started-with-guile-parser-combinators.html
>
>
>
>
> Hi.
> Have you looked at the PEG parser recently added to guile? It does
> everything the combinators do with an added compressor.
> Its quite powerful and seems to work well.
> -- 
> Sent from my p≡p for Android.

Hi Swedebugia,

I did not notice a PEG parser has been added. How did you notice this?
Maybe there is another blog for new additions to Guile?

Do you know a good text, which explains differences between the
different approaches to parsing? For example, what is the difference
between PEG parsing and parser combinators? There seems to be a whole
jungle of approaches to parsing out there, including parser generators,
which I believe take a grammar of certain kind and produce a parser from
that. I am never sure what languages I can parse using what approach.

Thanks anyways!

Regards,

Zelphir



^ permalink raw reply	[flat|nested] 13+ messages in thread

* Re: Re parse-result
  2019-01-17  7:43     ` Re parse-result Zelphir Kaltstahl
@ 2019-01-17  9:56       ` swedebugia
  2019-01-17 10:49       ` tomas
  2019-01-17 19:47       ` John Cowan
  2 siblings, 0 replies; 13+ messages in thread
From: swedebugia @ 2019-01-17  9:56 UTC (permalink / raw)
  To: Zelphir Kaltstahl; +Cc: Guile User

    Hi Swedebugia,

    I did not notice a PEG parser has been added. How did you notice this?
    Maybe there is another blog for new additions to Guile?

    Do you know a good text, which explains differences between the
    different approaches to parsing? For example, what is the difference
    between PEG parsing and parser combinators? There seems to be a whole
    jungle of approaches to parsing out there, including parser generators,
    which I believe take a grammar of certain kind and produce a parser from
    that. I am never sure what languages I can parse using what approach.

    Thanks anyways!

I heard about the PEG addition from Ricardo who mentioned it in
guix-devel. It also is one of very few features who got a nice tutorial
in the guile manual which I read a lot in.

Unfortunately I don't know a good comparison, but I believe PEG is somewhat
superior to guile-parser-combinators.



^ permalink raw reply	[flat|nested] 13+ messages in thread

* Re: Re parse-result
  2019-01-17  7:43     ` Re parse-result Zelphir Kaltstahl
  2019-01-17  9:56       ` swedebugia
@ 2019-01-17 10:49       ` tomas
  2019-01-19 13:23         ` Zelphir Kaltstahl
  2019-01-17 19:47       ` John Cowan
  2 siblings, 1 reply; 13+ messages in thread
From: tomas @ 2019-01-17 10:49 UTC (permalink / raw)
  To: Zelphir Kaltstahl; +Cc: Guile User

[-- Attachment #1: Type: text/plain, Size: 2245 bytes --]

On Thu, Jan 17, 2019 at 08:43:01AM +0100, Zelphir Kaltstahl wrote:

> >     I am still unsure about the theoretical CS stuff: What kind of parsers
> >     one can possibly write with parser combinators [...]

[...]

> > Have you looked at the PEG parser recently added to guile? It does
> > everything the combinators do with an added compressor.
> > Its quite powerful and seems to work well.
> > -- 
> > Sent from my p≡p for Android.
> 
> Hi Swedebugia,
> 
> I did not notice a PEG parser has been added. How did you notice this?
> Maybe there is another blog for new additions to Guile?
> 
> Do you know a good text, which explains differences between the
> different approaches to parsing? For example, what is the difference
> between PEG parsing and parser combinators? There seems to be a whole
> jungle of approaches to parsing out there, including parser generators,
> which I believe take a grammar of certain kind and produce a parser from
> that. I am never sure what languages I can parse using what approach.

I repeat myself, but I can only recommend the Wikipedia articles on that
topic. I'd start with the Chomsky hierarchy, which provides a nice map
for the terrain:

  https://en.wikipedia.org/wiki/Chomsky_hierarchy

At its bottom there is a transcluded template which gives an overview
of the kinds of languages out there and the types of "machines". You
can jump directly to that template:

  https://en.wikipedia.org/wiki/Template:Formal_languages_and_grammars

which is full of links :-)

PEGs are a bit of a freak within the Chomsky hierarchy, strictly
superior than regular languages (Type-3, think regexps) but inferior
to parsers doing fully general context-free (Type-2), like Earley
and CYK (which are worst-case about n^3 in the input's size).

OTOH, PEGs can be exponential in time (or in space, if you use
memoizing ("Packrat" parser) in some pathological cases.

Here you can read about thw relationship between PEGs and recursive
descent parsers (which those combinator thingies are, after all):

  https://en.wikipedia.org/wiki/Parsing_expression_grammar#Implementing_parsers_from_parsing_expression_grammars

Enjoy the landscape...

Cheers
-- tomás

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

^ permalink raw reply	[flat|nested] 13+ messages in thread

* Re: Re parse-result
  2019-01-17  7:43     ` Re parse-result Zelphir Kaltstahl
  2019-01-17  9:56       ` swedebugia
  2019-01-17 10:49       ` tomas
@ 2019-01-17 19:47       ` John Cowan
  2 siblings, 0 replies; 13+ messages in thread
From: John Cowan @ 2019-01-17 19:47 UTC (permalink / raw)
  To: Zelphir Kaltstahl; +Cc: Guile User

On Thu, Jan 17, 2019 at 2:56 AM Zelphir Kaltstahl <
zelphirkaltstahl@gmail.com> wrote:

For example, what is the difference
> between PEG parsing and parser combinators?
>

Both of them do top-down parsing (try to match the top-level grammar rule,
which is
done by trying to match the lower-level rules which make it up, and so on
until we
get down to single tokens.  They differ in the amount of lookahead that's
provided.

Parser combinators are a facade over recursive-descent parsing, where you
write
a procedure corresponding to each rule in the parser, and you can only look
ahead
one token to guide parsing.  This is known as LL(1) parsing. It's very easy
to write
these procedures, so you don't really need an engine like yacc to do the
job.
One character of lookahead isn't usually enough, so there is a lower-level
lexer
that uses (typically) regular expressions to aggregate things like numbers
and
identifiers into single parsing tokens.

PEG parsing allows *infinite* lookahead, all the way to the end of the
input.
However, it memoizes the results of parsing to avoid reparsing repeatedly.
To make this possible, alternatives are ordered: instead of rules like A |
B,
where the first token has to be enough to tell you if you have an A or a B,
you have rules like A / B, which means "assume it's an A, and only if it
fails, assume it's a B".  If A and B overlap, non-PEG parsing has to treat
A | B as a grammar ambiguity and recover, but A / B is never ambiguous.

-- 
John Cowan          http://vrici.lojban.org/~cowan        cowan@ccil.org
You cannot enter here.  Go back to the abyss prepared for you!  Go back!
Fall into the nothingness that awaits you and your Master.  Go! --Gandalf


^ permalink raw reply	[flat|nested] 13+ messages in thread

* Re: Re parse-result
  2019-01-17 10:49       ` tomas
@ 2019-01-19 13:23         ` Zelphir Kaltstahl
  2019-01-20  8:32           ` tomas
  0 siblings, 1 reply; 13+ messages in thread
From: Zelphir Kaltstahl @ 2019-01-19 13:23 UTC (permalink / raw)
  To: tomas; +Cc: Guile User


On 1/17/19 11:49 AM, tomas@tuxteam.de wrote:
> On Thu, Jan 17, 2019 at 08:43:01AM +0100, Zelphir Kaltstahl wrote:
>
>>>     I am still unsure about the theoretical CS stuff: What kind of parsers
>>>     one can possibly write with parser combinators [...]
> [...]
>
>>> Have you looked at the PEG parser recently added to guile? It does
>>> everything the combinators do with an added compressor.
>>> Its quite powerful and seems to work well.
>>> -- 
>>> Sent from my p≡p for Android.
>> Hi Swedebugia,
>>
>> I did not notice a PEG parser has been added. How did you notice this?
>> Maybe there is another blog for new additions to Guile?
>>
>> Do you know a good text, which explains differences between the
>> different approaches to parsing? For example, what is the difference
>> between PEG parsing and parser combinators? There seems to be a whole
>> jungle of approaches to parsing out there, including parser generators,
>> which I believe take a grammar of certain kind and produce a parser from
>> that. I am never sure what languages I can parse using what approach.
> I repeat myself, but I can only recommend the Wikipedia articles on that
> topic. I'd start with the Chomsky hierarchy, which provides a nice map
> for the terrain:
>
>   https://en.wikipedia.org/wiki/Chomsky_hierarchy
>
> At its bottom there is a transcluded template which gives an overview
> of the kinds of languages out there and the types of "machines". You
> can jump directly to that template:
>
>   https://en.wikipedia.org/wiki/Template:Formal_languages_and_grammars
>
> which is full of links :-)
>
> PEGs are a bit of a freak within the Chomsky hierarchy, strictly
> superior than regular languages (Type-3, think regexps) but inferior
> to parsers doing fully general context-free (Type-2), like Earley
> and CYK (which are worst-case about n^3 in the input's size).
>
> OTOH, PEGs can be exponential in time (or in space, if you use
> memoizing ("Packrat" parser) in some pathological cases.
>
> Here you can read about thw relationship between PEGs and recursive
> descent parsers (which those combinator thingies are, after all):
>
>   https://en.wikipedia.org/wiki/Parsing_expression_grammar#Implementing_parsers_from_parsing_expression_grammars
>
> Enjoy the landscape...
>
> Cheers
> -- tomás

Thanks tomás!

I know the Chomsky Hierarchy exists for languages and I remember there
was some thing called pumping lemma, which I forgot how to use years ago
anyway and I usually find online proofs difficult to follow, because
they lack the usual "explain for stupid" thoughts, that one has, when
thinking about these things. My best bet for applying such a thing would
be to search through old documents from university and hope that
somewhere I wrote down all the thoughts in very detailed manner,
including treatment of every little "but what if …?" thought. But this
is also only to prove that a language is not regular, if I recall
correctly. I think in a practical setting (for example: "I want to write
a parser for ReStructuredText! Can I use parser combinators?") the
problem is, figuring out whether the real language is in a specific
class of languages and then understanding, whether or not the parsing
tool I want to use is able to parse such language.

Is it trial and error in the end?

Here is an example of such a case from some time ago, when I wanted to
do some parsing in Rust, because I could not use ReStructuredText in a
Rust project: https://github.com/flying-sheep/rust-rst/issues/4 (This
one actually mentions PEG parsing.)

Anyway, maybe I can fresh up my knowledge a little through the articles
you linked.

Regards,

Zelphir




^ permalink raw reply	[flat|nested] 13+ messages in thread

* Re: Tangerine Edition penultimate report: how I voted, how you're, voting (John Cowan)
  2019-01-16 20:34 ` Tangerine Edition penultimate report: how I voted, how you're, voting (John Cowan) Zelphir Kaltstahl
@ 2019-01-20  2:24   ` John Cowan
  2019-01-20 12:02     ` Arne Babenhauserheide
  0 siblings, 1 reply; 13+ messages in thread
From: John Cowan @ 2019-01-20  2:24 UTC (permalink / raw)
  To: Zelphir Kaltstahl; +Cc: guile-user

On Wed, Jan 16, 2019 at 3:34 PM Zelphir Kaltstahl <
zelphirkaltstahl@gmail.com> wrote:

I am not sure I have a sufficiently informed opinion about SRFIs and
> such things. How experienced should a person be, as to not simply vote
> for something that superficially might sound great, but actually isn't
>
so good and screw up the voting?



It's like any other decision with imperfect information: you look it over
and give it your
best shot based on what makes sense to you.  "Prediction is very difficult,
especially about the future."

-- 
John Cowan          http://vrici.lojban.org/~cowan        cowan@ccil.org
Nobody expects the RESTifarian Inquisition!  Our chief weapon is
surprise ... surprise and tedium  ... tedium and surprise ....
Our two weapons are tedium and surprise ... and ruthless disregard
for unpleasant facts....  Our three weapons are tedium, surprise, and
ruthless disregard ... and an almost fanatical devotion to Roy Fielding....


^ permalink raw reply	[flat|nested] 13+ messages in thread

* Re: Re parse-result
  2019-01-19 13:23         ` Zelphir Kaltstahl
@ 2019-01-20  8:32           ` tomas
  2019-01-20 11:35             ` Zelphir Kaltstahl
  0 siblings, 1 reply; 13+ messages in thread
From: tomas @ 2019-01-20  8:32 UTC (permalink / raw)
  To: Zelphir Kaltstahl; +Cc: Guile User

[-- Attachment #1: Type: text/plain, Size: 3258 bytes --]

On Sat, Jan 19, 2019 at 02:23:58PM +0100, Zelphir Kaltstahl wrote:
> 
> On 1/17/19 11:49 AM, tomas@tuxteam.de wrote:

[...]

> Thanks tomás!
> 
> I know the Chomsky Hierarchy exists for languages and I remember there
> was some thing called pumping lemma, which I forgot how to use years ago
> anyway and I usually find online proofs difficult to follow, because
> they lack the usual "explain for stupid" thoughts, that one has, when
> thinking about these things.

The one "explain for stupid" I made up for me is that whenever the
grammar is too simple, the language becomes boring and starts to
"repeat itself".

>                              My best bet for applying such a thing would
> be to search through old documents from university [...] But this
> is also only to prove that a language is not regular, if I recall
> correctly.

There's one for regular languages and one for context-free. The
"repeating itself" in CFGs is a bit more elaborate (it's pairs
that repeat, think parentheses :-) but the gist is similar.

> I think in a practical setting (for example: "I want to write
> a parser for ReStructuredText! Can I use parser combinators?") the
> problem is, figuring out whether the real language is in a specific
> class of languages and then understanding, whether or not the parsing
> tool I want to use is able to parse such language.

First you gotta have a grammar. There's a lot of fudging in that
part (you can shift things to or from the "semantic part": e.g.
you might want to express in your grammar that a variable has to
have a "previous" declaration, but nobody in her right mind tries
to do that).

Then you have to look at the grammar and see whether it is
context-free. As above, you can try to fudge things a bit to
"make it so" -- after all, you have a (nearly, the tape and
your patience being limited) Turing-complete beast under your
belt.

In practice, most libraries and tools cheat, so most regular
expression machines offer things which take them beyond regular
languages (and you pay the price in possibly exponential run
time, but us programming folks love that risk ;-) -- and most
(sub-) CFG machineries cheat in similar ways, but that makes
them interesting.

> Is it trial and error in the end?

That's our trade it seems :-) Have a look at this one:

  https://en.wikipedia.org/wiki/Context-free_language#Decidability

to get a "feel" on how fractal-y the limits are.

OTOH -- all inputs being finite, all languages are regular,
given enough time and storage :-)

> Here is an example of such a case from some time ago, when I wanted to
> do some parsing in Rust, because I could not use ReStructuredText in a
> Rust project: https://github.com/flying-sheep/rust-rst/issues/4 (This
> one actually mentions PEG parsing.)

Thanks, and I promise I'll be having a look at this one. I just
Should Be Doing Something Different (TM) at the moment, so it
might take a couple of days.

It just happens that I am doing some parsing stuff at the moment
(an archeological language, using Python, alas, and their pyparsing
combinator library. I'd rather play with Guile, but perhaps I can
learn things to steal them later ;-)

Cheers
-- t

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

^ permalink raw reply	[flat|nested] 13+ messages in thread

* Re: Re: Re parse-result
  2019-01-20  8:32           ` tomas
@ 2019-01-20 11:35             ` Zelphir Kaltstahl
  0 siblings, 0 replies; 13+ messages in thread
From: Zelphir Kaltstahl @ 2019-01-20 11:35 UTC (permalink / raw)
  To: tomas; +Cc: Guile User

Hey tomás,

On 1/20/19 9:32 AM, tomas@tuxteam.de wrote:
>>                              My best bet for applying such a thing would
>> be to search through old documents from university [...] But this
>> is also only to prove that a language is not regular, if I recall
>> correctly.
> There's one for regular languages and one for context-free. The
> "repeating itself" in CFGs is a bit more elaborate (it's pairs
> that repeat, think parentheses :-) but the gist is similar.

Ah right, I forgot that there was one for CFGs too! I think I never
learned that one though. Neither Ogden's (which at least I have heard
of) or Parikh's.

>> I think in a practical setting (for example: "I want to write
>> a parser for ReStructuredText! Can I use parser combinators?") the
>> problem is, figuring out whether the real language is in a specific
>> class of languages and then understanding, whether or not the parsing
>> tool I want to use is able to parse such language.
> First you gotta have a grammar. There's a lot of fudging in that
> part (you can shift things to or from the "semantic part": e.g.
> you might want to express in your grammar that a variable has to
> have a "previous" declaration, but nobody in her right mind tries
> to do that).

Yes, I imagine that to be difficult to express in a grammar. On the
other hand, I know that (for example's sake) ReStructuredText has
arbitrary document internal references, so the sink or target of the
reference needs to be defined somewhere, possibly far away from the
reference itself. I think I am beginning to understand, why the
reference implementation of RST is more "rolled their own" instead of
visibly based on a grammar.

> Then you have to look at the grammar and see whether it is
> context-free. As above, you can try to fudge things a bit to
> "make it so" -- after all, you have a (nearly, the tape and
> your patience being limited) Turing-complete beast under your
> belt.

I was afraid someone would tell me I have to figure out the grammar
first, in order to judge the language class. :D

> In practice, most libraries and tools cheat, so most regular
> expression machines offer things which take them beyond regular
> languages (and you pay the price in possibly exponential run
> time, but us programming folks love that risk ;-) -- and most
> (sub-) CFG machineries cheat in similar ways, but that makes
> them interesting.
>> Is it trial and error in the end?
> That's our trade it seems :-) Have a look at this one:
>
>   https://en.wikipedia.org/wiki/Context-free_language#Decidability
>
> to get a "feel" on how fractal-y the limits are.
I always wonder how people know that their parsing approach will be
sufficient. So maybe they do not and simply try it with their favorite
parsing tool.
> OTOH -- all inputs being finite, all languages are regular,
> given enough time and storage :-)
I never thought about it like this. This is kind of funny actually. I
wonder what a "theoretical CS" teaching person would say to that. Maybe
that you still don't know ahead of time (parsing) exactly how long your
input is and that it therefore seems infeasible to construct a correct
grammar for that regular language, so in practice this does not help
you, when looking for a "correct" result.
>> Here is an example of such a case from some time ago, when I wanted to
>> do some parsing in Rust, because I could not use ReStructuredText in a
>> Rust project: https://github.com/flying-sheep/rust-rst/issues/4 (This
>> one actually mentions PEG parsing.)
> Thanks, and I promise I'll be having a look at this one. I just
> Should Be Doing Something Different (TM) at the moment, so it
> might take a couple of days.
>
> It just happens that I am doing some parsing stuff at the moment
> (an archeological language, using Python, alas, and their pyparsing
> combinator library. I'd rather play with Guile, but perhaps I can
> learn things to steal them later ;-)
>
> Cheers
> -- t

I did not mean to ask here for anyone to solve that one. Really only an
example of where I got stuck because of not knowing things and then
losing motivation.

Anyway, thank you for your reply!

Regards,

Zelphir




^ permalink raw reply	[flat|nested] 13+ messages in thread

* Re: Tangerine Edition penultimate report: how I voted, how you're, voting (John Cowan)
  2019-01-20  2:24   ` John Cowan
@ 2019-01-20 12:02     ` Arne Babenhauserheide
  0 siblings, 0 replies; 13+ messages in thread
From: Arne Babenhauserheide @ 2019-01-20 12:02 UTC (permalink / raw)
  To: John Cowan; +Cc: guile-user, Zelphir Kaltstahl

[-- Attachment #1: Type: text/plain, Size: 1052 bytes --]


John Cowan <cowan@ccil.org> writes:

> On Wed, Jan 16, 2019 at 3:34 PM Zelphir Kaltstahl <
> zelphirkaltstahl@gmail.com> wrote:
>
> I am not sure I have a sufficiently informed opinion about SRFIs and
>> such things. How experienced should a person be, as to not simply vote
>> for something that superficially might sound great, but actually isn't
>>
> so good and screw up the voting?
>
> It's like any other decision with imperfect information: you look it over
> and give it your
> best shot based on what makes sense to you.  "Prediction is very difficult,
> especially about the future."

I read the SRFIs, with special focus on the procedures they define, and
took my best guess.

I cannot actually give them the realworld testing they deserve. That’s
something I could only do for the old SRFIs, namely 1, 9, 11, 27, 37,
42, 43, 60, 64, and 119.

Those are the ones I already used (based on grepping the imports in my
projects).

Best wishes,
Arne
--
Unpolitisch sein
heißt politisch sein
ohne es zu merken

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 1076 bytes --]

^ permalink raw reply	[flat|nested] 13+ messages in thread

end of thread, other threads:[~2019-01-20 12:02 UTC | newest]

Thread overview: 13+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
     [not found] <mailman.109.1547658023.1050.guile-user@gnu.org>
2019-01-16 20:31 ` Re: parse-result (Catonano) Zelphir Kaltstahl
2019-01-16 21:47   ` tomas
2019-01-17  7:16   ` swedebugia
2019-01-17  7:43     ` Re parse-result Zelphir Kaltstahl
2019-01-17  9:56       ` swedebugia
2019-01-17 10:49       ` tomas
2019-01-19 13:23         ` Zelphir Kaltstahl
2019-01-20  8:32           ` tomas
2019-01-20 11:35             ` Zelphir Kaltstahl
2019-01-17 19:47       ` John Cowan
2019-01-16 20:34 ` Tangerine Edition penultimate report: how I voted, how you're, voting (John Cowan) Zelphir Kaltstahl
2019-01-20  2:24   ` John Cowan
2019-01-20 12:02     ` Arne Babenhauserheide

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).