From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id AB7987EE88 for ; Sun, 8 May 2016 12:27:08 +0200 (CEST) IronPort-PHdr: 9a23:Qi+4thBuR7clcoktyod5UyQJP3N1i/DPJgcQr6AfoPdwSP79pcbcNUDSrc9gkEXOFd2CrakU2qyP6+u6BCQp2tWojjMrSNR0TRgLiMEbzUQLIfWuLgnFFsPsdDEwB89YVVVorDmROElRH9viNRWJ+iXhpQAbFhi3DwdpPOO9QteU1JTmkbnqsMeOKyxzxxODIppKZC2sqgvQssREyaBDEY0WjiXzn31TZu5NznlpL1/A1zz158O34YIxu38I46FppIZ8VvDxdqE8CLhZFygOMmYv5cStuwOQYxGI4y4+W24PjxdTRijI6gv7FrX2rzH2v+w1jCuTNtTrQKtxWTmk9aYtShj1kisOMRY/93vSg8h9l79D5hW7qEoskMbvfIiJOa8mLevmdtQASD8ZUw== Authentication-Results: mail2-smtp-roc.national.inria.fr; spf=None smtp.pra=jacques-henri.jourdan@normalesup.org; spf=Neutral smtp.mailfrom=jacques-henri.jourdan@normalesup.org; spf=None smtp.helo=postmaster@ulminfo.fr Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of jacques-henri.jourdan@normalesup.org) identity=pra; client-ip=5.135.188.139; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="jacques-henri.jourdan@normalesup.org"; x-sender="jacques-henri.jourdan@normalesup.org"; x-conformance=sidf_compatible Received-SPF: Neutral (mail2-smtp-roc.national.inria.fr: domain of jacques-henri.jourdan@normalesup.org does not assert whether or not 5.135.188.139 is permitted sender) identity=mailfrom; client-ip=5.135.188.139; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="jacques-henri.jourdan@normalesup.org"; x-sender="jacques-henri.jourdan@normalesup.org"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@ulminfo.fr) identity=helo; client-ip=5.135.188.139; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="jacques-henri.jourdan@normalesup.org"; x-sender="postmaster@ulminfo.fr"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0BBAQDQEy9Xiou8hwVegw2BK7lqgXaGEAIIgRM6EgEBAQEBAQEBEQEBAQoUCVCCLYIVAQEEgQkLRlcTCAEBF4gRA74NCIgWglaFCxeEdgWYIoMogWiYI487JwaBa2CBV4klAQEB X-IPAS-Result: A0BBAQDQEy9Xiou8hwVegw2BK7lqgXaGEAIIgRM6EgEBAQEBAQEBEQEBAQoUCVCCLYIVAQEEgQkLRlcTCAEBF4gRA74NCIgWglaFCxeEdgWYIoMogWiYI487JwaBa2CBV4klAQEB X-IronPort-AV: E=Sophos;i="5.24,595,1454972400"; d="asc'?scan'208";a="217284213" Received: from ulminfo.fr ([5.135.188.139]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/ADH-AES256-GCM-SHA384; 08 May 2016 12:27:07 +0200 Received: from nounours.mketjh.fr (unknown [IPv6:2a01:e34:ec02:ace0:eab1:fcff:feb5:7aca]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ulminfo.fr (Postfix) with ESMTPSA id 72F6EC16AF for ; Sun, 8 May 2016 12:27:07 +0200 (CEST) To: caml-list@inria.fr References: <0a49598f1e0c8838fa69cd4d803af83d@nleyten.com> From: Jacques-Henri Jourdan Message-ID: Date: Sun, 8 May 2016 12:27:02 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.0 MIME-Version: 1.0 In-Reply-To: <0a49598f1e0c8838fa69cd4d803af83d@nleyten.com> Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="n8cedKaIVUijNRcb2Oed9O8gHJOgbitbC" Subject: Re: [Caml-list] Menhir grammar with sequences delimited by same token This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --n8cedKaIVUijNRcb2Oed9O8gHJOgbitbC Content-Type: multipart/mixed; boundary="PVj9QsDB5pGaJRh3dfespshdRucFW4JT4" From: Jacques-Henri Jourdan To: caml-list@inria.fr Message-ID: Subject: Re: [Caml-list] Menhir grammar with sequences delimited by same token References: <0a49598f1e0c8838fa69cd4d803af83d@nleyten.com> In-Reply-To: <0a49598f1e0c8838fa69cd4d803af83d@nleyten.com> --PVj9QsDB5pGaJRh3dfespshdRucFW4JT4 Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: quoted-printable Hi, The priority mechanism won't help, because the LR1 automaton does not contain the necessary information for deciding whether to shift or reduce. The solution might be to use parameterized non-terminals, but all the non-exponential solutions I can think of do not pass the termination checker for parameterized non-terminals. I have, however, another proposition : if you allow markup areas not be well nested, then you can simply have an environment recording, for each style, whether it is currently in use or not. --=20 JH Le 08/05/2016 =E0 11:33, Dario Teixeira a =E9crit : > Hi, > > (Sending this to Caml-list because Menhir-list is currently down.) > > I've come across an interesting parsing problem, one for which I > wonder if there is a succinct solution in Menhir. Suppose I want > to parse a markup which uses the same token for delimiting *both* > the beginning and the termination of a bold sequence (and likewise > for an emph sequence). Basically this: > > inline: > | TEXT {Ast.Text $1} > | BOLD inline* BOLD {Ast.Bold $2} > | EMPH inline* EMPH {Ast.Emph $2} > > > Which of course has a shift/reduce conflict: if the token stream is > [BOLD; TEXT; BOLD; ...], what should the parser do upon encountering > the second BOLD -- start a new nesting level, or close the current > one? I can force the latter behaviour by rearranging the grammar > so that an inline sequence within BOLDs cannot contain BOLD itself, > and likewise for EMPH: > > inline: > | TEXT {Ast.Text $1} > | BOLD inline_sans_bold* BOLD {Ast.Bold $2} > | EMPH inline_sans_emph* EMPH {Ast.Emph $2} > > inline_sans_bold: > | TEXT {Ast.Text $1} > | EMPH inline_sans_emph* EMPH {Ast.Emph $2} > > inline_sans_emph: > | TEXT {Ast.Text $1} > | BOLD inline_sans_bold* BOLD {Ast.Bold $2} > > > For this simple example this approach is feasible, but blows up > into silliness for a real-world case where besides BOLD and EMPH I > have many other similar tokens. Does Menhir offer a more succinct > solution to this problem? (I reckon using the priority mechanism > somehow, but exactly how eludes me.) > > Thanks in advance for your time! > Best regards, > Dario Teixeira > > --PVj9QsDB5pGaJRh3dfespshdRucFW4JT4-- --n8cedKaIVUijNRcb2Oed9O8gHJOgbitbC Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 iQEcBAEBCAAGBQJXLxR7AAoJEGHoGlEY1GjFmiAH/1MPzyK4XoQ0mqLB/M3iLpJn vpEK2EqB9oISr9wn65Mg3w/x4nE59p7FKRuVhQpRhSSiel9L0Uo4NbR40CAZvSFF n6GwfQphNT9XnY/7tZuG+DSwIoAZghyu/pIpEhwbVwHJ0zZM2hTCp8tg7XUk6Rzr UzimWGi9uwl8ueoGcBMd5lZTib/gH3iIjr41UC6mxvnsnida1dA0ef7IaXNDBOdS /a5yr68v5wpUttDeuoOUsgDnQhmJiFEt5ctqJ4eC28BXoq35TehbDSqxILSwttDQ ZmqyroAQmgPO5TPmzViG+/Avy1IuZEwYtVKIeyanhgcZ10TYf9H6NJJ6NSD+L5U= =3JTz -----END PGP SIGNATURE----- --n8cedKaIVUijNRcb2Oed9O8gHJOgbitbC--