Re: [LONG] Chomsky grammars
I wrote:
=> || return 0 if $rule !~ m{
=> || ($xTerm*) $xNon_term+ ($xTerm*) # LHS
=> || $xArrow
=> || $1 $xAlphabet* $2 # RHS
=> || }x;
That should be "\1" and "\2" instead of $1 and $2. I should
have caught that before I sent off my email. :-S
Also note that $xTerm, $xNon_term, and $xArrow should only
use non-capturing parentheses, if at all. $xAlphabet should
preferably do the same, as a coding style, although it
doesn't impact this example.
peace, || Rainwater Harvesting in Karnataka:
--{kr.pA} || http://makeashorterlink.com/?J21521932
--
GAAP, n.: the reason for the gaap between the balance sheet and reality.
Re: [LONG] Chomsky grammars
Steffen Mueller writes:
=> [...]
=> CH-1: context-sensitive grammars (all productions are context sensitive:
=> uAv -> urv, where u and v are 1 or more terminals, A one or more
=> non-terminals, and r any combination of terminals and non-terminals.)
=> [...]
=> u is a number of terminals, A and B a number of non-terminals. [...]
=> Of course, one'd check for CH-1 first, but that's not nearly as easy to
=> do. [...]
Since regexps have backtracking built in, won't it be easy to
test each rule as a string, instead of handling the LHS and
RHS separately? The m{}x regexp at the bottom of the
following code seems to capture your definition of CH-1,
although I may be mistaken.
(Of course, &check_CH1 returns 1 for CH-2 and CH-3 grammars,
too. The tests are to be applied in decreasing order, from
CH-3 down to CH-1, as you've described.)
|| # *** Incomplete code follows! ***
||
|| my $xTerm = qr/.../; # Match any terminal.
|| my $xNon_term = qr/.../; # Match any non-terminal.
|| my $xAlphabet = qr/(?:$xTerm|$xNon_term)/; # Match the alphabet.
||
|| # Choose an arrow not matching the alphabet.
|| my $arrow = "->";
|| assert($arrow !~ $xAlphabet);
|| my $xArrow = qr/$arrow/;
||
|| sub check_CH1 {
|| # Receive an array of @productions (as described by OP in
|| # his examples).
|| # Return 1 if every $production is (at most)
|| # context sensitive; 0 otherwise.
|| #
|| # If @rules is available in main::, we can simplify
|| # this function. We can simply receive @rules here,
|| # instead of @productions, and we won't have to
|| # create $rule from each $production.
|| my @productions = @_;
||
|| foreach my $production (@productions) {
|| # Make a rule from $production, by stringifying the
|| # left and right sides.
|| my $rule = join("", @{$production->{left}}, $arrow,
|| @{$production->{right}});
||
|| return 0 if $rule !~ m{
|| ($xTerm*) $xNon_term+ ($xTerm*) # LHS
|| $xArrow
|| $1 $xAlphabet* $2 # RHS
|| }x;
|| }
|| 1;
|| } # &check_CH1
||
|| # *** Incomplete code above! ***
peace, || Rainwater Harvesting in Karnataka:
--{kr.pA} || http://makeashorterlink.com/?J21521932
--
GAAP, n.: the reason for the gaap between the balance sheet and reality.
Re: Proposal: [Was: "... arm wrestling ..."]
Kripa Sundar:
> On my system, whereis(1) doesn't do what I want it to do,
> which is search my $PATH. The following one-liner does this:
>
> || % perl -lwe '$,=" ";for my $x(@ARGV){print "$x:", \
> || map {-e "$_/$x" ? "$_/$x" : ()} split /:/,$ENV{PATH}}' ls cat
Not portable!
% perl -MFile::Spec::Functions -wle 'for $x (@ARGV) { map { print "$x: $y"
if -x ($y=catfile($_,$x))} path() }' cat ls
--
Grr... don't get me started on Wagner. The man couldn't resolve a
dominant seventh to a tonic with two musical dictionaries open to the
word "resolution", and a copy of anything by Muddy Waters.
- Eric the Read, in the monastery.
Re: Iterating down two lists at the same time
On Tue, Oct 29, 2002 at 01:05:12PM -0400, Bernie Cosell wrote:
> I'm cobbling up a bit of code that'll need to do something akin to 'map' on two
> lists at the same time. I'm going to just brute-force it [doing shifts in a
> loop: $left = shift @leftlist; $right = shift @rightlist, with all the usual
> nonsense around to do the right thing when one list is shorter than the other
> [delivering up 'undef's but without warnings, etc] But it feels clumsy.
>>> a=(1, 2, 3)
>>> b=('a', 'b', 'c')
>>> c = map (None, a, b)
>>> c
[(1, 'a'), (2, 'b'), (3, 'c')]
>>>
Oh, Fun With *Perl*. D'oh :-)
For those that are interested,
http://www.python.org/doc/current/lib/built-in-funcs.html
Perl 6's map will be able to do this and more.
Paul
--
Paul Makepeace ... http://paulm.com/
"What is movement? Unconditional Love and Acceptance."
-- http://paulm.com/toys/surrealism/
Re: [LONG] Chomsky grammars
> Being a cs1 student (well Physics actually, but my minor subject is > computer science), I recently learned about Chomsky grammars. One of the > assignments was to classify given grammars as anything between CH-0 and > CH-3. That's not too hard for a human IMO, but somehow quite a few of my > fellow student can't wrap around those concepts. Hence I decided to > write a quick Perl script to classify given grammars. (Yes, I know, I'm > not actually helping anybody understand it that way.) What about a frontend for the code that turns it into a self-study program, giving you the bit, and asking that the user classify it, and select the reasoning, and then telling them whether they were correct or not, or whether they were correct for the right reasons. Joey
[LONG] Chomsky grammars
Hi fwplers,
I suppose this is another one of those borderline fwp posts, but I
wouldn't post if I didn't consider this fwp. And this is not an
assignment. This is fun for me and I hope you consider it somewhat
interesting as well. Sorry for this becoming utterly long.
Being a cs1 student (well Physics actually, but my minor subject is
computer science), I recently learned about Chomsky grammars. One of the
assignments was to classify given grammars as anything between CH-0 and
CH-3. That's not too hard for a human IMO, but somehow quite a few of my
fellow student can't wrap around those concepts. Hence I decided to
write a quick Perl script to classify given grammars. (Yes, I know, I'm
not actually helping anybody understand it that way.)
I first scavenged from a defunct project of mine the routine that parses
simple text files into a list of productions as well as lists of
terminals and non-terminals. (or is it "terminal tokens? It's not like
you could look that up in a conventional dictionary! Well, if you
picture the grammar as a tree, the things I call terminals here are the
leaves, all other nodes are non-terminals. You may know those as
subrules.)
So what you get from this parsing routine is:
An array of tokens that are terminals: @terminals
An array of tokens that are non-terminals (subrules): @nonterminals
An array of productions: (alternatives as in "a A -> B | C c | d" are
split up as separate productions "a A -> B", "a A -> C c", "a A -> d"
because that's what they are in this context.)
Now any one of those productions is represented by a hash of two lists:
(same example, first production)
{ left => ['a', 'A'],
right => ['B'] }
etc.
I wonder whether the definitions of the Chomsky types are taught the
same everywhere, so here's a quick summary:
CH-0: all valid grammars.
CH-1: context-sensitive grammars (all productions are context sensitive:
uAv -> urv, where u and v are 1 or more terminals, A one or more
non-terminals, and r any combination of terminals and non-terminals.)
CH-2: context free grammars. That means: all productions have no
terminals on their left side.
CH-3: regular grammars. All productions must either be left- or
right-linear or temrinating. That means: A -> uB or A -> Bu or A -> B or
A -> u.
u is a number of terminals, A and B a number of non-terminals. This
means that the resulting string may only grow in one direction: left or
right.
All CH-3 grammars are CH-2 grammars, all CH-2's are also CH-1's and
guess what: since all valid grammars are CH-0 grammars, CH-1 grammars
are also of type CH-0.
The program should output the most restricted type for a given grammar.
Okay, here's the beef:
Determining whether a grammar is CH-2 is easy:
(@(non)terminals were mapped into hashes)
For every production:
# Check that all tokens on the left are nonterminals.
foreach my $token ( @{ $production->{left} } ) {
return 0 if exists $nonterminals{$token};
}
CH-3 might be tested for using the following butt-ugly code:
This is applied to all productions until one doesn't comply.
Sorry, it's not quite cut'n'paste, but it needed some cleaning up.
I added some comments and changed some variable names. For posting.
sub is_regular {
my $prod = shift;
# Have previous productions been left- or right-linear?
my $left_right = shift;
# Must be regular if there are no nonterminals on the right.
return 1
unless grep { exists $nonterminals{$_} } @{$prod->{right}};
# Must be regular if there are no terminals on the right.
return 1
unless grep { exists $terminals{$_} } @{$prod->{right}};
# If we have been left-linear previously
if ( $left_right eq 'left' ) {
my $found_terminal = 0;
foreach ( @{$prod->{right}} ) {
# not ch-3 if we find a non-terminal and
# have had a terminal before
return 0
if exists $nonterminals{$_} and $found_terminal;
$found_terminal = 1 if exists $terminals{$_};
}
# If have been right-linear previously
} elsif ( $l_r eq 'right' ) {
my $found_nonterm = 0;
foreach ( @{$prod->{right}} ) {
return 0
if exists $terminals{$_} and $found_nonterm;
$found_nonterm = 1 if exists $nonterminals{$_};
}
# No left- or right-linearity found in
# previous productions.
} else {
# No nonterminals on the left (of the right
# side of the production) yet.
my $found_left = 0;
# Same for the ones on the right...
my $found_right = 0;
my $found_terminal = 0;
foreach ( @{$prod->{right}} ) {
# Found a nonterm on the lefthand side if
# we haven't found a terminal yet.
$found_left = 1
if exists $nonterminals{$_} and
not $found_terminal;
# Must've been on the right if we did
# find a terminal before.
$found_right = 1
if exists $nonterminals{$_} and
$found_terminal;
Re: Iterating down two lists at the same time
> > I'm cobbling up a bit of code that'll need to do something akin to 'map' on two
> > lists at the same time. ...
>
> Footnote: I realized, that while doing 'mapN' is interesting. what I'm actually
> in the midst of implementing is 'foreach' for multiple lists. The template I
> had in mind was something like:
>forall my ($lotsofvariables) (list of listrefs)
> and then it'd alias the vbls in the lotsofvariables [or en masse if there's an
> array, of course] to each parallel entry from the various lists.
>
> I wonder if there's a pretty/elegant way to do that...
Hi,
Pretty? Elegant? In my example, it depends whether you are examining
the point of use... or the implimentation. The principle is to covert:
@array1 = ["a", "b", "c"]
@array2 = ["1", "2", "3"]
into
@result = [ ["a", "1"],
["b", "2"],
["c", "3"] ];
and then iterate over that. Obviously, I called the function magic()
because it's going to seem rather complex and UGLY. Call it pre-mature
optimisation for speed, if you like. Code quality is about 0.1% and
does not reflect normal code quality, guess I wanted more to see if you
liked the approach. Do NOT use *as is*, you definately want to check
you get array-refs on all elements (skipped) since it's VERY easy to
do:
magic @array1, @array2;
and not get what you expected.
My license for this is simple: fix/improve, copy and paste. Oh, and
I don't want my name in your otherwise clean code :)
__PERL CODE__
#!/usr/bin/perl -w
use strict;
use Carp;
# Basic test... iterates over and prints results
my @result = magic(["1", "2", "3"], ["a", "b", "c"], ["x", "y", "z"]);
foreach (@result) {
my ($first, $second, $third) = @{$_};
# Do something with values
print "$first : $second : $third\n";
}
# The UGLY stuff
sub magic {
my @array = @_;
# Check we have only array references
# ... exercise for reader... laziness for me.
# Find length of first array, then check consistency
my $length = $#{$array[0]};
for (@_) {
if ($length != scalar $#{$_}) {
croak "Array lengths don't match";
}
}
# Combine everything, using an eval for speed
my @result;
my $code;
for (0..$#_) {
$code .= "my \@array_$_ = \@{\$array[$_]};\n";
}
$code .= 'for (0..$length) {'."\n".' push @result, [';
for (0..$#_) {
$code .= "\$array_${_}[\$_]";
$code .= ", " unless $#_ == $_;
}
$code .= "];\n}";
eval $code;
return @result;
}
__END__
Jonathan Paton <--- evil programmer
sub point {
(list != array) and see("Programming Perl, pages 72-76.");
}
=
s''! v+v+v+v+ J r e Ph+h+h+h+ !s`\x21`~`g,s`^ . | ~.*``mg,$v=q.
P ! v-v-v-v- u l r e r h-h-h- !12.,@.=m`.`g;do{$.=$2.$1,$.=~s`h
E ! v+v+v+ s k e h+h+ !`2`x,$.=~s`v`31`,print$.[$v+=$.]
R ! v-v- t H a c h h- !}while/([hv])([+-])/g;print"\xA"
L ! A n o t !';$..=$1while/([^!]*)$/mg;eval$.
__
Do You Yahoo!?
Everything you'll ever need on one web page
from News and Sport to Email and Music Charts
http://uk.my.yahoo.com
RE: Naked arm wrestling: Schwern v Damian
-Original Message- From: Meryll Larkin [mailto:alwanza@;oz.net] Sent: Tuesday, October 29, 2002 10:07 AM > anybody ever wonder where all the female Perl > programmers are *raises hand* Hi, I have two X chromosomes and I hack Perl professionally.
Re: Iterating down two lists at the same time
Hmm... I just finished my solution when I saw the mapcar one posted by
Evan. Well, here's mine anyway. It is worse because: 1) it's not a
package, 2) it doesn't support aliased variables (i.e. you can't modify
the incoming arrays like you can with map). But, it does use letters
$a, $b, $c, etc. as Bernie requested. Mine operates on the minimum
number of elements, instead of the maximum, in all of the arrays. Perl6
could do this better with variable aliases.
#!/usr/bin/perl
sub mapn(&@) {
my $coderef = shift;
return () if (@_==0);
my $n = @{$_[0]};
my @result;
foreach my $arg (1 .. $#_) {
$n = @{$_[$arg]} if (@{$_[$arg]} < $n);
}
foreach $i (0..$n-1) {
foreach my $arg (0 .. $#_) {
my $letter = chr(ord('a') + $arg);
$$letter = $_[$arg]->[$i];
}
push @result, &$coderef;
}
@result;
}
my @one = qw(foo bar baz fwip);
my @two = qw(spam ham jam flimflam);
my @tri = qw(1 2 3 4);
my @out = mapn {"$c:$a:$b"} \@one, \@two, \@tri;
print "@out\n";
Chris
Bernie Cosell wrote:
> On 29 Oct 2002 at 13:05, Bernie Cosell wrote:
>
>
>>I'm cobbling up a bit of code that'll need to do something akin to 'map' on two
>>lists at the same time. ...
>
>
> Footnote: I realized, that while doing 'mapN' is interesting. what I'm actually
> in the midst of implementing is 'foreach' for multiple lists. The template I
> had in mind was something like:
>forall my ($lotsofvariables) (list of listrefs)
> and then it'd alias the vbls in the lotsofvariables [or en masse if there's an
> array, of course] to each parallel entry from the various lists.
>
> I wonder if there's a pretty/elegant way to do that...
>
> /bernie\
>
Re: Iterating down two lists at the same time
On Tue, Oct 29, 2002 at 01:05:12 PM, Bernie Cosell wrote:
> I was wondering if there's any fun to be found in elegant/clever ways to
> traverse two lists at the same time... I envisioned something like:
>map2 {stuff} \@list1, \@list2
> where inside the map maybe you had $a and $b aliased appropriately
> or something
> like that. Or perhaps:
>mapn {stuff} list-of-listrefs
> where you aliased $1, $2, $3, ... to the parallel entries from the different
> lists...
Hello Bernie,
You may be interested in mapcar, a module written by Tye on Perlmonks:
http://www.perlmonks.org/index.pl?node_id=44763
http://www.perlmonks.org/index.pl?node_id=44763&displaytype=displaycode
You call the mapcar function as you specified above:
use mapcar;
my @a= qw( foo bar baz );
my @b= qw( qux quux quo );
print mapcar { "@_\n" } \@a, \@b;
__END__
foo qux
bar quux
baz quo
Inside the block that you pass to mapcar, the two elements from
the lists you are traversing are stored in @_.
>From Perlmonks:
mapcar is from lisp. It is like map but works on more than
one list. While map loops setting $_ to successive elements of a
list, mapcar loops setting @_ to successive elements of several
lists (but since you can only pass one list to a subroutine,
mapcar expects a list of references to one or more arrays). Both
map and mapcar collect the values returned by the code block or
subroutine and then return the collected values.
Hope this helps,
-E
Proposal: [Was: "... arm wrestling ..."]
Meryll Larkin writes:
=> [...]
=> The effect these last several emails about naked arm wrestling [...]
=> has produced in me is [...] of "[...] I'm glad I wasn't there."
=> [...]
I heartily second this opinion. Thanks for speaking up!
=> If it had been 5 emails or fewer I probably would have let
=> it go, [...]
Those who want to continue the discussion, please take it
off-list. (Feel free to create <[EMAIL PROTECTED]> for "fun
with naked arm wrestling" fans. :-)
ObPerl:
On my system, whereis(1) doesn't do what I want it to do,
which is search my $PATH. The following one-liner does this:
|| % perl -lwe '$,=" ";for my $x(@ARGV){print "$x:", \
|| map {-e "$_/$x" ? "$_/$x" : ()} split /:/,$ENV{PATH}}' ls cat
|| ls: /depot/local/bin/ls /usr/ucb/ls /bin/ls /usr/bin/ls
|| cat: /bin/cat /usr/bin/cat
|| %
|| % whereis ls cat
|| ls: /usr/bin/ls /usr/ucb/ls
|| cat: /usr/bin/cat
|| %
peace, || Rainwater Harvesting in Karnataka:
--{kr.pA} || http://makeashorterlink.com/?J21521932
--
GAAP, n.: the reason for the gaap between the balance sheet and reality.
Re: Naked arm wrestling: Schwern v Damian
On Tue, Oct 29, 2002 at 10:07:00AM -0800, Meryll Larkin wrote: > > If it had been 5 emails or fewer I probably would have let > it go, but since this thread is showing no signs of dieing, > will someone please let me in on the joke? For what it's worth... At the Y::E auction (to raise money to deal with any shortfall of conference expense, with the balance going to the Perl Foundation), which is usually an odd event anyway due to the auctioneering of one Greg McCarroll, Schwern won a bid for the opportunity to arm wrestle damian for the right to get two opcodes in parrot. Someone in the audience suggested that damian take off his shirt for this. He responded that he'd do it for a bid of 50 euros. It was pledged. Schwern said he'd do the same for the same bid. Again, the condition was met. So, basically, by doing it this way, they raised and extra 100 euros for the Perl Foundation. Just be glad we haven't been discussing the point in the auction where schwern auctioned off his pants. :-) dha -- David H. Adler - <[EMAIL PROTECTED]> - http://www.panix.com/~dha/ "I'll keep him as an insurance policy, since, unfortunately, I can't kill him twice." - Scaroth
Re: Iterating down two lists at the same time
On 29 Oct 2002 at 13:05, Bernie Cosell wrote: > I'm cobbling up a bit of code that'll need to do something akin to 'map' on two > lists at the same time. ... Footnote: I realized, that while doing 'mapN' is interesting. what I'm actually in the midst of implementing is 'foreach' for multiple lists. The template I had in mind was something like: forall my ($lotsofvariables) (list of listrefs) and then it'd alias the vbls in the lotsofvariables [or en masse if there's an array, of course] to each parallel entry from the various lists. I wonder if there's a pretty/elegant way to do that... /bernie\ -- Bernie Cosell Fantasy Farm Fibers mailto:bernie@;fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--
Re: Naked arm wrestling: Schwern v Damian
I hope you guys are having fun because I'm not. The effect these last several emails about naked arm wrestling between Schwern vs Damian (Conway) has produced in me is NOT one of "I wish I had been there" but of "If I had been there I would have been miserable, I'm glad I wasn't there." anybody ever wonder where all the female Perl programmers are There is something about this that I just don't get. Maybe, like the other person who wrote from this list that "Humans can be controlled through their women" it is something HUMAN that I and WOMEN are lacking (since we are obviously not quite human). I enjoy Fun with Perl when it is about coding, but maybe someone should enlighten me as to what is fun about the hero worship and women bashing. If it had been 5 emails or fewer I probably would have let it go, but since this thread is showing no signs of dieing, will someone please let me in on the joke? Meryll Larkin Steffen Mueller wrote: > David H. Adler wrote: > >>On Mon, Oct 28, 2002 at 01:54:53PM +0100, Steffen Mueller wrote: >> >>>David H. Adler wrote: >>> Heh. I survived, and I had to see it in person! :-) >>> >>>People, bow to that man. He sat in the second row! >> >>*Front* row, thank you very much. :-) > > > Hmm, odd. I thought I sat in the third row behind you and Schwern and > Jos Boumans (sp?) in front of you. Doesn't matter, I suppose. > > Steffen > > > -- Meryll Larkin (206) 782-9203 Perl Programmer Web Developer - Linux Apache Admin Seattle, WA, USA
Iterating down two lists at the same time
I'm cobbling up a bit of code that'll need to do something akin to 'map' on two
lists at the same time. I'm going to just brute-force it [doing shifts in a
loop: $left = shift @leftlist; $right = shift @rightlist, with all the usual
nonsense around to do the right thing when one list is shorter than the other
[delivering up 'undef's but without warnings, etc] But it feels clumsy.
I was wondering if there's any fun to be found in elegant/clever ways to
traverse two lists at the same time... I envisioned something like:
map2 {stuff} \@list1, \@list2
where inside the map maybe you had $a and $b aliased appropriately or something
like that. Or perhaps:
mapn {stuff} list-of-listrefs
where you aliased $1, $2, $3, ... to the parallel entries from the different
lists...
/Bernie\
--
Bernie Cosell Fantasy Farm Fibers
mailto:bernie@;fantasyfarm.com Pearisburg, VA
--> Too many people, too few sheep <--
Re: Naked arm wrestling: Schwern v Damian
David H. Adler wrote: > On Mon, Oct 28, 2002 at 01:54:53PM +0100, Steffen Mueller wrote: >> David H. Adler wrote: >>> Heh. I survived, and I had to see it in person! :-) >> >> People, bow to that man. He sat in the second row! > > *Front* row, thank you very much. :-) Hmm, odd. I thought I sat in the third row behind you and Schwern and Jos Boumans (sp?) in front of you. Doesn't matter, I suppose. Steffen
Re: Naked arm wrestling: Schwern v Damian
"Steffen Mueller" <[EMAIL PROTECTED]> writes: > David H. Adler wrote: >> Heh. I survived, and I had to see it in person! :-) > > People, bow to that man. He sat in the second row! > >> Haven't sorted out the pictures from Y::E yet, but will weed them out >> and get them to you someway tomorrow. > > Being the lazy person I am, I did not take any pictures myself, so I > wouldn't mind having a look at yours... Do you think you could arrange > posting them somewhere on the net for all of us? Heh, I've still not scanned my photos from Y::E::19100... really should get 'round to that. Some day. -- Piers "It is a truth universally acknowledged that a language in possession of a rich syntax must be in need of a rewrite." -- Jane Austen?
