Sender: lojban@googlegroups.com
Received-SPF: pass (google.com: domain of rdentato@gmail.com designates 2a00:1450:400c:c0c::236 as permitted sender) client-ip=2a00:1450:400c:c0c::236;
MIME-Version: 1.0
In-Reply-To: <CAO7bV+iM4CKHZoV5syG-hJis0x6-K8A91gV7jXMftzNxDNr44g@mail.gmail.com>
References: <ef141db1-9811-4d44-8458-972ddffdd883@googlegroups.com>
 <78156dc5-1fb3-4e9d-992c-a8f30facc4fd@googlegroups.com> <SY3PR01MB0873C992D556B090F308980EEB510@SY3PR01MB0873.ausprd01.prod.outlook.com>
 <CACf3dPnmCuGXQtxQOOrP9T9pDthhthx3rnoCdaFoai+fM8M6Wg@mail.gmail.com>
 <SY3PR01MB08733806D926A36CF1726EB0EB560@SY3PR01MB0873.ausprd01.prod.outlook.com>
 <CACf3dPncGvkjQjbxL4MV_omG0R-e66V1CDcZFrt2hVU8iYWf0w@mail.gmail.com>
 <963393d6-a9f1-4232-be13-b4ee76eb69e1@googlegroups.com> <e7d4a3d5-4cd9-435d-bd3f-90c011172a10@googlegroups.com>
 <A9240133-B357-4747-941D-BF28F3CCAE8C@free.fr> <eb1c7ed2-ec39-476d-b9dc-11f835e9623c@googlegroups.com>
 <ae9b9cae-0420-475b-a0e8-8efb3452ef1e@googlegroups.com> <7d063690-0550-45d6-9779-3334ac8e17b5@googlegroups.com>
 <e3a723d2-8b62-4338-bc8a-147f03d6d3f4@googlegroups.com> <CAO7bV+gTit=DupXY_yb1XhaoW=0+zyetZFP5i+0C+HWz+T_8Hg@mail.gmail.com>
 <85ecf653-49c8-457c-8397-d80fc0c3a8ea@googlegroups.com> <CAAQ0imMT=Y-Twy2PXzAaW8hWyvaugdLAxXam11B-1A2BsWANUQ@mail.gmail.com>
 <d9cfa229-07e3-4ffb-a9eb-b2a42597d9b3@googlegroups.com> <CAO7bV+hVaTn9ZdTz37aizNeQ7UochwamSuEpfp5xLimPASMMeQ@mail.gmail.com>
 <CAAQ0imMsJ8vhuCnixsN-arEzhf5gEF9nRe5CAS2Q+YZDRSDfvA@mail.gmail.com>
 <CAO7bV+jbzJEnHSYn_omxhx7LUzsnVZmWumnGE8wApO_3Z1Odwg@mail.gmail.com>
 <CAAQ0imNGztbTDwXBnbNGvPVpwThzJOY+XWOGnA9X1=nJ8froXQ@mail.gmail.com> <CAO7bV+iM4CKHZoV5syG-hJis0x6-K8A91gV7jXMftzNxDNr44g@mail.gmail.com>
From: Remo Dentato <rdentato@gmail.com>
Date: Wed, 22 Nov 2017 12:38:24 +0100
Message-ID: <CAAQ0imOc-ADJ0VdFQ1XkJ+_3537ZA1h-YxX6b9K5XuY6YUP2XA@mail.gmail.com>
Subject: Re: [lojban] Re: CLL and modern Lojban
To: lojban <lojban@googlegroups.com>
Content-Type: multipart/alternative; boundary="f403045cf798eb77c3055e90c167"
Reply-To: lojban@googlegroups.com
Precedence: list
Mailing-list: list lojban@googlegroups.com; contact lojban+owners@googlegroups.com
X-Spam_score: -4.1
X-Spam_score_int: -40
X-Spam_bar: ----

--f403045cf798eb77c3055e90c167
Content-Type: text/plain; charset="UTF-8"

On Wed, Nov 22, 2017 at 10:29 AM, Gleki Arxokuna <gleki.is.my.name@gmail.com
> wrote:

> PEG has no tools to check for ambiguity, it simply does not support it,
> it's another grammar with its own drawbacks. It can't be compared to YACC,
> it's just another class of grammars.
>
> If you want tools resolving ambiguity then having tools not more powerful
> than PEG or CFG is not enough.
>


Since the absence of syntactic ambiguity is one of (my) requirement for
Lojban, let me understand better.

In CFG the source of ambiguity is the at any given moment in parsing one
can choos which alternative path to follow.
So, for example, the following CFG grammar is ambiguous:

E = E '+' E | E '-' E | N
N = '0' | '1' | ... | '9'

because the string "4+3-9" may result in two different parse tree:

         E                 E
       / | \             / | \
      E  +  E           E  -  E
      |   / | \       / | \   |
      4  E  -  E     E  +  E  9
         |     |     |     |
         3     9     4     3

The corresponding PEG would be:

E = E '+' E / E '-' E | N
N = '0' / '1' / ... / '9'

And there is only parse tree for "4+3+9"
         E
       / | \
      E  +  E
      |   / | \
      4  E  -  E
         |     |
         3     9

(note that PEG do support left recursion even if the original packrat
algorithm didn't)

CFG grammars need to be checked for ambiguities and have to be rewritten to
eliminate them whereas PEG do not have this problem (and hence lack a tool
for checking ambiguities).

I do agree that ensuring that a PEG grammar does exactly what you want it
to do is not easy (especially if it's a complex grammar) but "per se" the
PEG itself does not introduce any ambiguity.


Is this what you meant or am I missing something?

-- 
You received this message because you are subscribed to the Google Groups "lojban" group.
To unsubscribe from this group and stop receiving emails from it, send an email to lojban+unsubscribe@googlegroups.com.
To post to this group, send email to lojban@googlegroups.com.
Visit this group at https://groups.google.com/group/lojban.
For more options, visit https://groups.google.com/d/optout.

--f403045cf798eb77c3055e90c167
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On W=
ed, Nov 22, 2017 at 10:29 AM, Gleki Arxokuna <span dir=3D"ltr">&lt;<a href=
=3D"mailto:gleki.is.my.name@gmail.com" target=3D"_blank">gleki.is.my.name@g=
mail.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=
=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding=
-left:1ex"><div dir=3D"ltr"><span class=3D"gmail-"></span><span class=3D"gm=
ail-"></span><div class=3D"gmail_extra"><div class=3D"gmail_quote"><div>PEG=
 has no tools to check for ambiguity, it simply does not support it, it&#39=
;s another grammar with its own drawbacks. It can&#39;t be compared to YACC=
, it&#39;s just another class of grammars.</div><div><br></div><div>If you =
want tools resolving ambiguity then having tools not more powerful than PEG=
 or CFG is not enough.</div></div></div></div></blockquote><div><br></div><=
div><br></div><div>Since the absence of syntactic ambiguity is one of (my) =
requirement for Lojban, let me understand better.</div><div><br></div><div>=
In CFG the source of ambiguity is the at any given moment in parsing one ca=
n choos which alternative path to follow.</div><div> So, for example, the f=
ollowing CFG grammar is ambiguous:</div><div><br></div>E =3D E &#39;+&#39; =
E | E &#39;-&#39; E | N</div><div class=3D"gmail_quote">N =3D &#39;0&#39; |=
 &#39;1&#39; | ... | &#39;9&#39;</div><div class=3D"gmail_quote"><br></div>=
<div class=3D"gmail_quote">because the string &quot;4+3-9&quot; may result =
in two different parse tree:</div><div class=3D"gmail_quote"><br></div><fon=
t face=3D"monospace,monospace">=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0 E=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 E<br>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 / =
| \=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
 / | \<br>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 E=C2=A0 +=C2=A0 E=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 E=C2=A0 -=C2=A0 E<br>=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0 |=C2=A0=C2=A0 / | \=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0 / | \=C2=A0=C2=A0 |<br>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 4=C2=A0 E=C2=
=A0 -=C2=A0 E=C2=A0=C2=A0=C2=A0=C2=A0 E=C2=A0 +=C2=A0 E=C2=A0 9<br>=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 |=C2=A0=C2=A0=C2=A0=C2=A0 |=C2=
=A0=C2=A0=C2=A0=C2=A0 |=C2=A0=C2=A0=C2=A0=C2=A0 |<br>=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0 3=C2=A0=C2=A0=C2=A0=C2=A0 9=C2=A0=C2=A0=C2=A0=
=C2=A0 4=C2=A0=C2=A0=C2=A0=C2=A0 3</font><div class=3D"gmail_quote">=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0 <br></div><div class=3D"gmail_quote"><div>The corr=
esponding PEG would be:</div><div><br></div><div>E =3D E &#39;+&#39; E / E =
&#39;-&#39; E | N<div class=3D"gmail_quote">N =3D &#39;0&#39; / &#39;1&#39;=
 / ... / &#39;9&#39;</div><div class=3D"gmail_quote"><br></div><div class=
=3D"gmail_quote">And there is only parse tree for &quot;4+3+9&quot;<br></di=
v><div class=3D"gmail_quote"><font face=3D"monospace,monospace">=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 E=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0 <br>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 / | \=C2=A0=C2=A0=C2=A0=C2=A0 =
<br>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 E=C2=A0 +=C2=A0 E=C2=A0=C2=A0=C2=A0 <br>=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 |=C2=A0=C2=A0 / | \=C2=A0 <br>=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0 4=C2=A0 E=C2=A0 -=C2=A0 E <br>=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0 |=C2=A0=C2=A0=C2=A0=C2=A0 | <br>=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 3=C2=A0=C2=A0=C2=A0=C2=A0 9 <br></font></div=
><div class=3D"gmail_quote"><br></div><div class=3D"gmail_quote">(note that=
 PEG do support left recursion even if the original packrat algorithm didn&=
#39;t)</div><div class=3D"gmail_quote"><br></div><div class=3D"gmail_quote"=
>CFG grammars need to be checked for ambiguities and have to be rewritten t=
o eliminate them whereas PEG do not have this problem (and hence lack a too=
l for checking ambiguities).</div><div class=3D"gmail_quote"><br></div><div=
 class=3D"gmail_quote">I do agree that ensuring that a PEG grammar does exa=
ctly what you want it to do is not easy (especially if it&#39;s a complex g=
rammar) but &quot;per se&quot; the PEG itself does not introduce any ambigu=
ity.<br></div><div class=3D"gmail_quote"><br></div><div class=3D"gmail_quot=
e"><br></div>Is this what you meant or am I missing something? <br></div></=
div></div><div class=3D"gmail_extra"><br></div></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;lojban&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:lojban+unsubscribe@googlegroups.com">lojban+unsub=
scribe@googlegroups.com</a>.<br />
To post to this group, send email to <a href=3D"mailto:lojban@googlegroups.=
com">lojban@googlegroups.com</a>.<br />
Visit this group at <a href=3D"https://groups.google.com/group/lojban">http=
s://groups.google.com/group/lojban</a>.<br />
For more options, visit <a href=3D"https://groups.google.com/d/optout">http=
s://groups.google.com/d/optout</a>.<br />

--f403045cf798eb77c3055e90c167--