From lojban-out@lojban.org Thu Jul 13 07:41:51 2006 Return-Path: X-Sender: lojban-out@lojban.org X-Apparently-To: lojban@yahoogroups.com Received: (qmail 44900 invoked from network); 13 Jul 2006 14:12:41 -0000 Received: from unknown (66.218.66.217) by m26.grp.scd.yahoo.com with QMQP; 13 Jul 2006 14:12:41 -0000 Received: from unknown (HELO chain.digitalkingdom.org) (64.81.49.134) by mta2.grp.scd.yahoo.com with SMTP; 13 Jul 2006 14:12:37 -0000 Received: from lojban-out by chain.digitalkingdom.org with local (Exim 4.62) (envelope-from ) id 1G11vJ-0002p0-BT for lojban@yahoogroups.com; Thu, 13 Jul 2006 07:12:13 -0700 Received: from chain.digitalkingdom.org ([64.81.49.134]) by chain.digitalkingdom.org with esmtp (Exim 4.62) (envelope-from ) id 1G11tX-0002ni-KF; Thu, 13 Jul 2006 07:10:25 -0700 Received: with ECARTIS (v1.0.0; list lojban-list); Thu, 13 Jul 2006 07:10:15 -0700 (PDT) Received: from nobody by chain.digitalkingdom.org with local (Exim 4.62) (envelope-from ) id 1G11t3-0002mP-Nk for lojban-list-real@lojban.org; Thu, 13 Jul 2006 07:09:53 -0700 Received: from py-out-1112.google.com ([64.233.166.180]) by chain.digitalkingdom.org with esmtp (Exim 4.62) (envelope-from ) id 1G11t1-0002mH-Pf for lojban-list@lojban.org; Thu, 13 Jul 2006 07:09:53 -0700 Received: by py-out-1112.google.com with SMTP id x31so257800pye for ; Thu, 13 Jul 2006 07:09:50 -0700 (PDT) Received: by 10.35.34.18 with SMTP id m18mr807012pyj; Thu, 13 Jul 2006 07:09:50 -0700 (PDT) Received: by 10.35.14.17 with HTTP; Thu, 13 Jul 2006 07:09:49 -0700 (PDT) Message-ID: <925d17560607130709u3fef60c5ubd8f638c795685c0@mail.gmail.com> Date: Thu, 13 Jul 2006 11:09:49 -0300 In-Reply-To: <20060713025542.GH18359@chain.digitalkingdom.org> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <20060713003616.GD18359@chain.digitalkingdom.org> <20060713013545.GF18359@chain.digitalkingdom.org> <20060713025542.GH18359@chain.digitalkingdom.org> X-Spam-Score: -2.5 (--) X-archive-position: 12174 X-ecartis-version: Ecartis v1.0.0 Errors-to: lojban-list-bounce@lojban.org X-original-sender: jjllambias@gmail.com X-list: lojban-list X-Spam-Score: -2.5 (--) To: lojban@yahoogroups.com X-Originating-IP: 64.81.49.134 X-eGroups-Msg-Info: 1:0:0:0 X-eGroups-From: "=?ISO-8859-1?Q?Jorge_Llamb=EDas?=" From: "=?ISO-8859-1?Q?Jorge_Llamb=EDas?=" Reply-To: jjllambias@gmail.com Subject: [lojban] Re: Is Lojban a CFG? (was Re: [lojban-beginners] Re: Enumerating in Lojban) X-Yahoo-Group-Post: member; u=116389790; y=EPJIGbUbORgUy_A0cSEGXv9TwbPQx-LOUP1ap3v-CgzRFzmQpQ X-Yahoo-Profile: lojban_out X-Yahoo-Message-Num: 26601 Tell me see if I have this right. A CFG is a formal grammar with *production* rules of the form X -> x, (for example sumti -> LE BRIVLA), that tell us how to produce the construct on the left from the expression on the right. A PEG is a formal grammar with *parsing* rules of the form X <- x, (for example sumti <- LE BRIVLA), that tell us how to parse/interpret the expression on the right. In other words, a CFG is what the speaker needs (I want to produce a sumti, how can I construct it?) and a PEG is what the listener needs (I'm given the expression {LE BRIVLA}, how do I interpret it?) Now, the nice thing about a CFG is that the speaker, in order to produce grammatical output, If they want to produce a sumti they need only look at the production rule for "sumti". That's what context-free means. The nice thing about a PEG is that the listener, given any grammatical string, is guaranteed that it can only be parsed in one way. There is no risk of there being more than one way of parsing it. If I'm not mistaken, for any CFG, there is a PEG that will accept all and only the strings generated by that CFG. If that's correct, then what Jonathan wants (a CFG for Lojban) is compatible with what Robin wants (a PEG for Lojban). At least in principle, because maybe the required PEG might be way too complicated to write. Or maybe not, we can at least try. I think this is, simplifying, the kind of thing we would need the PEG to do in order to handle the {li pa pa pa pa moi} example: Current PEG rules: sentence <- sumti* selbri sumti* selbri <- number MOI sumti <- LI number LOhO? number <- PA+ Possible modification to make it context-free: sentence <- sumti* selbri sumti* selbri <- moi-number MOI sumti <- LI li-number LOhO? li-number <- PA (PA !MOI)* moi-number <- PA+ But I don't know how hard it would be to modify the whole PEG so that it fully corresponds to a CFG. (Disclaimer: I'm not completely sure all of the above is right, I'm not an expert on any of this.) mu'o mi'e xorxes To unsubscribe from this list, send mail to lojban-list-request@lojban.org with the subject unsubscribe, or go to http://www.lojban.org/lsg2/, or if you're really stuck, send mail to secretary@lojban.org for help.