Star rule problem for empty input

[icze]

Hi,

I found a further problem using PEGTL master on fde02a1.
Here the reduced example where parsing of empty fails:

#include <tao/pegtl.hpp>
#include <tao/pegtl/analyze.hpp>
#include <tao/pegtl/contrib/parse_tree.hpp>
#include <tao/pegtl/contrib/parse_tree_to_dot.hpp>


namespace peg = tao::pegtl;

namespace grammar {

  template< char... Cs > struct padded_string : peg::pad<peg::string<Cs...>, peg::space> {};
  template< char... Cs > struct padded_one : peg::pad<peg::one<Cs...>, peg::space> {};

  struct IDENT : peg::pad< peg::identifier, peg::space > {}; // allow whitespaces
  struct name : peg::seq< IDENT, peg::star< peg::seq < padded_one< '.' >, IDENT > > > {};
  struct component_list : peg::seq< IDENT, peg::star< peg::seq < padded_one< ',' >, IDENT  > > > {};
  struct entry_list : peg::star< peg::seq < name, component_list, padded_one< ';' >  > > {};
  struct composition : peg::seq< entry_list, peg::star< peg::seq < padded_string< 'p', 'u', 'b', 'l', 'i', 'c' >, entry_list > > > {};
  struct content : peg::seq< IDENT, composition, padded_string< 'e', 'n', 'd' >, IDENT > {};


} // namespace grammar


int main(int argc, char** argv)
{
  if (peg::analyze< grammar::content >()) {
    std::cerr << "analyze() found errors in grammar." << std::endl;
    return 1;
  }

  constexpr auto empty{
    "OBJ\n"
    "end OBJ;\n"
    "\n"
  };

  constexpr auto ok{
    "OBJ\n"
    "  name0.x comp0;\n"
    "public\n"
    "  name1 compA, compB;\n"
    "end OBJ\n"
    "\n"
  };

  peg::memory_input<> in( empty, "source" );
  //peg::memory_input<> in(ok, "source");
  try {
    const auto root = peg::parse_tree::parse< grammar::content >(in);
    if (root == nullptr) {
      std::cerr << "parse() failed: root is nullptr" << std::endl;
      return 1;
    }
    peg::parse_tree::print_dot(std::cout, *root);
  }
  catch (const peg::parse_error & e) {
    const auto p = e.positions.front();
    std::cerr << e.what() << std::endl
      << in.line_at(p) << std::endl
      << std::string(p.byte_in_line, ' ') << '^' << std::endl;
    return 1;
  }

  return 0;
}

[d-frey]

Your input for empty contains a semicolon after end OBJ, so the grammar does not match. This is the expected behaviour.

[icze]

Oh sorry, I made a mistake while reducing the grammar. I give you an update when I have a correct reduction.

[icze]

Hi,
hope that I have not made a mistake again.
I'm expecting that in_empty is getting parsed:

#include <tao/pegtl.hpp>
#include <tao/pegtl/analyze.hpp>
#include <tao/pegtl/contrib/parse_tree.hpp>
#include <tao/pegtl/contrib/parse_tree_to_dot.hpp>


namespace peg = tao::pegtl;

namespace grammar {

  template< char... Cs > struct padded_string : peg::pad<peg::string<Cs...>, peg::space> {};
  template< char... Cs > struct padded_one : peg::pad<peg::one<Cs...>, peg::space> {};

  struct IDENT : peg::pad< peg::identifier, peg::space > {}; // allow whitespaces
  struct name : peg::seq< IDENT, peg::star< peg::seq < padded_one< '.' >, IDENT > > > {};
  struct component_list : peg::seq< IDENT, peg::star< peg::seq < padded_one< ',' >, IDENT  > > > {};
  struct entry_list : peg::star< peg::seq < name, component_list, padded_one< ';' >  > > {};
  struct composition : peg::seq< entry_list, peg::star< padded_string< 'p', 'u', 'b', 'l', 'i', 'c' > > > {};
  struct content : peg::star< peg::seq < IDENT, composition, padded_string< 'e', 'n', 'd' >, IDENT, padded_one< ';' > > > {};


} // namespace grammar

bool Parse(peg::memory_input<>& in)
{
  try {
    const auto root = peg::parse_tree::parse< grammar::content >(in);
    if (root == nullptr) {
      std::cerr << "parse() failed: root is nullptr" << std::endl;
      return true;
    }
    peg::parse_tree::print_dot(std::cout, *root);
  }
  catch (const peg::parse_error & e) {
    const auto p = e.positions.front();
    std::cerr << e.what() << std::endl
      << in.line_at(p) << std::endl
      << std::string(p.byte_in_line, ' ') << '^' << std::endl;
    return true;
  }

  return false;
}

int main(int argc, char** argv)
{
  if (peg::analyze< grammar::content >()) {
    std::cerr << "analyze() found errors in grammar." << std::endl;
    return 1;
  }

  peg::memory_input<> in_ok(
    "OBJ\n"
    "public\n"
    "end OBJ;\n"
    "\n",
    "source");

  peg::memory_input<> in_empty(
    "OBJ\n"
    //"public\n"
    "end OBJ;\n"
    "\n",
    "source");

  if (Parse(in_ok)) {
    return 1;
  }
  if (Parse(in_empty)) {
    return 1;
  }
  return 0;
}

And here the output:

digraph parse_tree
{
  x000002D5E7245B30 [ label="ROOT" ]
  x000002D5E7245B30 -> { x000002D5E7243FA0 }
  x000002D5E7243FA0 [ label="struct grammar::content\nOBJ\npublic\nend OBJ;\n\n" ]
  x000002D5E7243FA0 -> { x000002D5E7245DE0 }
  x000002D5E7245DE0 [ label="struct tao::pegtl::seq<struct grammar::IDENT,struct grammar::composition,struct grammar::padded_string<101,110,100>,struct grammar::IDENT,struct grammar::padded_one<59> >\nOBJ\npublic\nend OBJ;\n\n" ]
  x000002D5E7245DE0 -> { x000002D5E7245880, x000002D5E72531A0, x000002D5E725DA80, x000002D5E725D460, x000002D5E725D8C0 }
  x000002D5E7245880 [ label="struct grammar::IDENT\nOBJ\n" ]
  x000002D5E7245880 -> { x000002D5E72555D0, x000002D5E72556B0 }
  x000002D5E72555D0 [ label="struct tao::pegtl::ascii::identifier\nOBJ" ]
  x000002D5E72556B0 [ label="struct tao::pegtl::ascii::space\n\n" ]
  x000002D5E72531A0 [ label="struct grammar::composition\npublic\n" ]
  x000002D5E72531A0 -> { x000002D5E7253280, x000002D5E725D1C0 }
  x000002D5E7253280 [ label="struct grammar::entry_list\n" ]
  x000002D5E725D1C0 [ label="struct tao::pegtl::star<struct grammar::padded_string<112,117,98,108,105,99> >\npublic\n" ]
  x000002D5E725D1C0 -> { x000002D5E725D0E0 }
  x000002D5E725D0E0 [ label="struct grammar::padded_string<112,117,98,108,105,99>\npublic\n" ]
  x000002D5E725D0E0 -> { x000002D5E725D700, x000002D5E725CC80 }
  x000002D5E725D700 [ label="struct tao::pegtl::ascii::string<112,117,98,108,105,99>\npublic" ]
  x000002D5E725CC80 [ label="struct tao::pegtl::ascii::space\n\n" ]
  x000002D5E725DA80 [ label="struct grammar::padded_string<101,110,100>\nend " ]
  x000002D5E725DA80 -> { x000002D5E725D380, x000002D5E725D2A0 }
  x000002D5E725D380 [ label="struct tao::pegtl::ascii::string<101,110,100>\nend" ]
  x000002D5E725D2A0 [ label="struct tao::pegtl::ascii::space\n " ]
  x000002D5E725D460 [ label="struct grammar::IDENT\nOBJ" ]
  x000002D5E725D460 -> { x000002D5E725CF20 }
  x000002D5E725CF20 [ label="struct tao::pegtl::ascii::identifier\nOBJ" ]
  x000002D5E725D8C0 [ label="struct grammar::padded_one<59>\n;\n\n" ]
  x000002D5E725D8C0 -> { x000002D5E725D000, x000002D5E725D7E0, x000002D5E725D540 }
  x000002D5E725D000 [ label="struct tao::pegtl::ascii::one<59>\n;" ]
  x000002D5E725D7E0 [ label="struct tao::pegtl::ascii::space\n\n" ]
  x000002D5E725D540 [ label="struct tao::pegtl::ascii::space\n\n" ]
}
digraph parse_tree
{
  x000002D5E725CC80 [ label="ROOT" ]
  x000002D5E725CC80 -> { x000002D5E725D2A0 }
  x000002D5E725D2A0 [ label="struct grammar::content\n" ]
}

Thanks for your help.

[d-frey]

The library works as expected.

Let's analyze what is happening in your case: The input is OBJ end OBJ; (if I replace newline with space, which is equivalent in this case).

Now the rules are trying to match content = star<entry> with entry = seq< IDENT, composition, "end", IDENT, ";" >. (I hope the pseudo-syntax is OK for you)

The first OBJ is IDENT. Next we try to match composition = seq< entry_list, star< "public" > >. Looking at entry_list = star< name, component_list, ";" >. And here, it matches the end OBJ;-part of the input. name matches end and OBJ matches component_list = seq< IDENT, star<...> >.

Now the problem is that PEGs (unlike CFGs) are truly greedy. composition does eat the end OBJ; and now entry can never succeed as it still expect more input to match, e.g. end IDENT;.

As you have put entry into star<entry> the whole content matches with zero entries. The matching does not consume the whole input, in fact it matches without consuming any input. (You'd need to add eof at the top-level grammar to ensure that no remaining input may occur).

[icze]

Thanks for your explanation, you are right. Perhaps I can make the grammar next week PEG conform (do you know some papers on this topic?) or I have to choose another library :-(. Again, thanks a lot.

[d-frey]

I'm not aware of any paper to help you with that. But in my experience the process of manually converting a grammar from a CFG into a PEG is well worth it: It can be quite involved, but at the end you learn a lot more about how CFGs and PEGs work in general as well as how your specific grammar is constructed.

Often times, I find that with the help of the PEGTL's convenience rules the resulting grammar is much clearer than the original CFG.

As a final hint, make sure you check out the at<> and not_at<> rules, they can be used to disambiguate branches in the grammar. Use them as a last resort, as they lead to slightly
inefficient grammars.

Good luck!