parsing issue

[Shaheen47]

Greetings,
i am writing a parser for RDF-Turtle and i am having the same issue in two grammars.
i will write simple version of the grammer

_:' (upper |digit) ((upper | '.')* upper)?

and i want to implement it with PEGTL
i tried to implement it as the following

struct BLANK_NODE_LABEL : seq<
    one<'_'>,
    one<':'>,
    sor< upper, digit >,
    opt<
        star<
            sor< upper, one<'.'> >,
            upper
        >
    >
>

it is working for inputs consisting of even number of uppers but not working with inputs consisting of odd number of uppers
for example :

_:A                _:AAA       _:A.A       _:AAA.A     _:AAA.AAAAA                   (working)
_:A A           _:AAAA      _:AA.A     _:A.AA        _:AA.AAAA                      (not working)

it seems that when the parser is having an even number of 'upper' .it consumes one on the first 'sor' which is correct .but in the "opt" part ,instead of consuming it on the 'upper' part outside the 'star' and accepting the grammer.it consume it inside the 'star' part and then gives an parsing error.
how to deal with such a case using PEGTL?
thanks in advance

[d-frey]

I reformatted your grammar, and the problem became apparent: You pass the last upper as a parameter to the star-part. But the grammar has it on the outside, so you need to move it properly. Instead of

opt<
    star<
        sor< upper, one<'.'> >,
        upper
    >
>

you need:

opt<
    star<
        sor< upper, one<'.'> >
    >,
    upper
>

So the star only allows repetition of the sor-part, and the star-part is then followed by upper - and only everything together is optional (opt).

[d-frey]

...and I also just realize that this won't work either. OK, digging deeper: You probably try to write a PEGTL-equivalent of the following rule:

BLANK_NODE_LABEL ::= '_:' (PN_CHARS_U) | [0-9]) ((PN_CHARS | '.' )* PN_CHARS)?

Besides the difference between PN_CHARS_U and PN_CHARS (the latter not being just uppercase characters) you have one major problem in your understanding of grammars: The above is a rule from a CFG (a Context-Free Grammar) and not from a PEG (a Parsing Expression Grammar). They look extremly similar, but they have a different semantic. Hence you need to adapt those rules from CFG to PEG as otherwise the naive translation will never match the optional part as the star is greedy and eats all PN_CHARS and therefore the following PN_CHARS can never match.

A semantically correct version of the above CFG as a PEG might look like this:

BLANK_NODE_LABEL ::= '_:' (PN_CHARS_U) | [0-9]) ('.'* PN_CHARS)*

I'll leave it to you to adapt your PEGTL grammar, feel free to ask if you need more help  🙂

[Shaheen47]

Thanks very much for the help.

[bigerl]

Very interesting indeed. Thank you @d-frey for your great explanations.
Eventually I have one or two follow up question:

1. Do you know of any automated converter from deterministic CFGs to PEGs? Or of a good text book or cheat-sheet to do it by hand?
2. Apparently you found BLANK_NODE_LABEL in the turtle W3C Recommendation. Do you think a PEG is a good choice for parsing it? And can we expect to get a fast and efficient parser for the language by using PEGTL?

[d-frey]

1. No, I don't know of any resources to automate translating CFGs to PEGs. And I am not sure that the result would be an efficient grammar. I just do it manually when needed and once you got the hang of it (PEGs) it's not that hard.
2. I think PEGs are generally preferable over CFGs, but not everyone might agree. I like that PEGs are a formal description of a recursive-decent parser, which is how I think and reason about the actual grammar. I also think that with PEGs in general and even more so with the additional options offered by the PEGTL (convenience rules and, if needed, custom rules) you can write very efficient parsers.

[d-frey]

And one more tip for improving the efficiency: It might be more efficient (and semantically identical) to use

BLANK_NODE_LABEL ::= '_:' (PN_CHARS_U) | [0-9]) ('.'* PN_CHARS+)*

instead of

BLANK_NODE_LABEL ::= '_:' (PN_CHARS_U) | [0-9]) ('.'* PN_CHARS)*