Re: Suggestions for dcg_basics (was: Detecting the presence of a pattern in an atom)

2013/10/16 Boris Vassilev <[email protected]>

> There is one small detail about string//1 that bothers me, probably
> because I don't understand how to use it properly:
>
> in its current implementation, it takes as few tokens as possible, and
> takes more on backtracking. So, for a n-token string, it will fail and
> backtrack n-1 times. string_without//2 on the other hand is deterministic.
>
>
I don't know either, I use to put a ! after the (near mandatory) separator.
Related to this, I happened to get exponential parsing time on practical
parsing (some MB of sql dump), and I found to be fairly difficult to debug,
specially when called from phrase_from_file.


> On Wed, Oct 16, 2013 at 2:15 AM, Carlo Capelli <[email protected]>wrote:
>
>> 2013/10/16 Richard A. O'Keefe <[email protected]>
>>
>> > > From: "Richard A. O'Keefe" <[email protected]>
>> > > Subject: Re: [SWIPL] Detecting the presence of a pattern in an atom
>> > > Date: 16 October 2013 11:49:11 AM NZDT
>> > > To: Steve Prior <[email protected]>
>> >
>> > I should also have commented that if you want to take something apart,
>> > it's probably _not_ a good idea to make it an atom in the first place.
>> > >
>> > >
>> > > On 15/10/2013, at 6:18 PM, Steve Prior wrote:
>> > >> Some name and some business name (ABC)
>> > >>
>> > >> I'm trying to get the "ABC".
>> > >>
>> > >> The titles don't have any formal grammar to them, but for starters I
>> > need to see if there is a substring which starts with '(' contains all
>> > upper case letters and ends with ')'.  I suppose it's possible that the
>> > title might contain multiple open/close parens, but I'd expect only one
>> set
>> > to fit the all upper case criterion.
>> > >>
>> > >> It seems a bit much to do a DCG grammar for this
>> > >
>> > >
>> > > Why?
>> > >
>> > > The Quintus library includes more_lists:lit//1.
>> > >
>> > >       lit([])     --> [].
>> > >       lit([X|Xs]) --> [X], lit(Xs).
>> > >
>> > > Adapt that pattern:
>> > >
>> > >       uplit([])     --> [].
>> > >       uplit([X|Xs]) --> [X], {is_upper(X)}, uplit(Xs).
>> > >
>> > > Now put them together:
>> > >
>> > >       extract(Wanted) --> lit(_), "(", uplit(Wanted), ")", !.
>> > >
>> > > There are other ways to do it.
>> > >
>> > > I personally find this _easier_ to write than /\(([A-Z]+)\)/
>> > > where the placement of the backslashes is too easy to get wrong.
>> >
>> > I don't see anything resembling lit//1 in SWI's library(dcg_basics).
>> >
>>
>> There is string//1 in library(dcg/basics), exactly the same.
>>
>> Of course OP's question can be solved by
>>
>>  ?- phrase((string(_), "(", string(S), ")", {forall(member(C,S),
>> code_type(C, upper))} ), "hello (again) (WORLD)", _).
>>
>> S = [87, 79, 82, 76, 68]
>>
>>
>> but I think Michael regex is so handy...
>>
>>
>>
>> > :- module(more_lists, [
>> >         adjust/5,       % Direction x Width x Pad x List -> List
>> >         adjust/6,       % Direction x Width x Pad x List -> List\List
>> >         bnd/2,          % Length x List
>> >         bnd/3,          % Length x List\List
>> >         bnd/4,          % Length x List\List x List
>> >         len/2,          % Length <-> List
>> >         len/3,          % Length <-> List\List
>> >         len/4,          % Length <-> List <-> List\List
>> >         lit/3,          % List <-> List\List
>> >         oneof/3,        % Set x List\List
>> >         oneof/4,        % Set x (Element <-> List\List)
>> >         replist/2,      % Datum x List
>> >         replist/3,      % Datum x Length <-> List
>> >         replist/4,      % Datum x Length <-> List\List
>> >         spaces/2,       % Length <-> List
>> >         spaces/3        % Length <-> List\List
>> >    ]).
>> >
>> > adjust/[5,6] are for generation.
>> > The other things were ultimately inspired by SNOBOL 4.
>> >
>> > %   bnd(+Length, ?List)
>> > %   is true when Length is a non-negative integer and List is a list
>> > %   having at most Length elements.  This can be used to test the
>> > %   length of a list, or it can be used to generate lists up to a
>> > %   given limit.  When used for generation, it will try shorter lists
>> > %   before longer ones.
>> >
>> > %   bnd(+Length, ?S0, ?S)
>> > %   is true when Length is a non-negative integer and the list segment
>> > %   S0\S contains at most Length elements.  This is mostly used to
>> > %   generate segments increasing in length from 0 to Length; in a
>> > %   grammar rule len(3) will match exactly 3 elements, while bnd(3)
>> > %   will match 0, 1, 2, or 3 elements.
>> >
>> > %   bnd(+Length, ?List, ?S0, ?S)
>> > %   is true when bnd(Length, List) & append(List, S, S0), that is,
>> > %   when Length is a non-negative integer, List is the list represented
>> > %   by the segment S0\S, and List (S0\S) has at most Length elements.
>> > %   It is meant for use in grammar rules, where bnd(3,X) will match
>> > %   0..3 elements and return a list of them as X.
>> >
>> > %   len(?Length, ?List)
>> > %   is true when List is a list and Length is a non-negative integer
>> > %   and List has exactly Length elements.  The normal use of this is
>> > %   to find the Length of a given List, but it can be used any way
>> > %   around provided that
>> > %       Length is instantiated, or
>> > %       List   is a proper list.
>> > %   This is identical to length/2 except for the argument order.
>> > %   This predicate is the basis of most things in this module.
>> >
>> > %   len(?Length, ?List0, ?List)
>> > %   is true when append(Part, List, List0) & len(Length, Part)
>> > %   for some list Part.  The idea is to have something we can use
>> > %   in grammar rules.  For example, if we want to recognise
>> > %   phone numbers in the form "(###) ###-####" and don't want the
>> > %   bother of checking that the # characters are digits, we can
>> > %   write
>> > %       phone --> "(", len(3), ") ", len(3), "-", len(4).
>> > %   The code was derived from len/2.
>> >
>> > %   len(?Length, ?Part, ?List0, ?List)
>> > %   is true when append(Part, List, List0) & len(Length, Part).
>> > %   This too is for use in grammar rules.  The difference between
>> > %   len(N) and len(N,X) as non-terminals is that len(N,X) gives
>> > %   us the elements which matched.  This predicate can also be
>> > %   used as a version of append/3 which returns (or is guided by)
>> > %   the length of the Part argument.
>> >
>> > %   lit(?Part, ?List0, ?List)
>> > %   is true when append(Part, List, List0).  It is just append/3 with
>> > %   the last two argument switched so that it can be used in DCGs.
>> >
>> > %   oneof(+Set, ?List0, ?List)
>> > %   is true when List0\List = [X] and X is an element of Set.
>> > %   It should only be used when Set is ground.
>> >
>> > %   oneof(+Set, ?Element, ?List0, ?List)
>> > %   is true when List0\List = [Element] and Element is an element of
>> Set.
>> > %   It should only be used when Set is ground.
>> >
>> > %   replist(?Datum, +List)
>> > %   is true when List is a list all of whose elements equal Datum.
>> > %   It will terminate if either List is a proper list or it is a
>> > %   partial list one of whose known elements does not unify with
>> > %   Datum.  If called with List a variable, it will enumerate
>> > %   successively longer Lists.
>> >
>> > %   replist(?Datum, ?Length, ?List)
>> > %   is true when replist(List, Datum) & length(List, Length).
>> > %   Note that the parameters are the wrong way around for this to
>> > %   be part of the library(length) family.
>> >
>> > %   replist(?Datum, ?Length, ?List0, ?List)
>> > %   is true when append(Part, List, List0) & replist(Datum, Length,
>> Part)
>> > %   for some list Part.  The idea is to have a version of replist/3 that
>> > %   we can use in grammar rules, e.g.
>> > %       ... -> ..., replist(0'*, 20), ...
>> > %   Note that there is no replist(Datum, Length, Part, List0, List) to
>> > %   give us back the elements which matched.  We can rebuild the Part
>> > %   by calling replist/3.
>> >
>> > Actually, that could have been programmed:
>> >
>> > replist(Datum, Length, Part, List0, List) :-
>> >     replist(Datum, Length, List0, List),
>> >     replist(Datum, Length, Part).
>> >
>> > %   spaces(?Length, ?Chars)
>> > %   is true when Chars is a list of Length blanks.
>> > %   This is a special case of replist/3.
>> >
>> > %   spaces(?Length, ?Chars0, ?Chars)
>> > %   is true when append(Spaces, Chars, Chars0) & spaces(Length, Spaces)
>> > %   for some list Spaces.  This is for use in grammar rules.
>> > %   It is a special case of replist/4.
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > _______________________________________________
>> > SWI-Prolog mailing list
>> > [email protected]
>> > https://lists.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog
>> >
>> -------------- next part --------------
>> HTML attachment scrubbed and removed
>>
>> _______________________________________________
>> SWI-Prolog mailing list
>> [email protected]
>> https://lists.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog
>>
>
>
-------------- next part --------------
HTML attachment scrubbed and removed