Re: [Caml-list] Menhir grammar with sequences delimited by same token

[Jacques-Henri Jourdan <jacques-henri.jourdan@normalesup.org>]

[-- Attachment #1.1: Type: text/plain, Size: 2365 bytes --]

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.


-- 

JH


Le 08/05/2016 à 11:33, Dario Teixeira a écrit :
> 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
>
>



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 473 bytes --]