src/libshared/src/PEG.cpp

   1 ////////////////////////////////////////////////////////////////////////////////
   2 //
   3 // Copyright 2015 - 2017, Paul Beckingham, Federico Hernandez.
   4 //
   5 // Permission is hereby granted, free of charge, to any person obtaining a copy
   6 // of this software and associated documentation files (the "Software"), to deal
   7 // in the Software without restriction, including without limitation the rights
   8 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   9 // copies of the Software, and to permit persons to whom the Software is
  10 // furnished to do so, subject to the following conditions:
  11 //
  12 // The above copyright notice and this permission notice shall be included
  13 // in all copies or substantial portions of the Software.
  14 //
  15 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  16 // OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  18 // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  20 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  21 // SOFTWARE.
  22 //
  23 // http://www.opensource.org/licenses/mit-license.php
  24 //
  25 ////////////////////////////////////////////////////////////////////////////////
  26
  27 #include <cmake.h>
  28 #include <PEG.h>
  29 #include <Lexer.h>
  30 #include <shared.h>
  31 #include <format.h>
  32 #include <iostream>
  33
  34 ////////////////////////////////////////////////////////////////////////////////
  35 std::string PEG::Token::dump () const
  36 {
  37   std::stringstream out;
  38   out << (_lookahead == Token::Lookahead::positive ? "\e[34m&\e[0m" :
  39           _lookahead == Token::Lookahead::negative ? "\e[34m!\e[0m" : "")
  40       << _token
  41       << (_quantifier == Token::Quantifier::zero_or_one  ? "\e[34m?\e[0m" :
  42           _quantifier == Token::Quantifier::one_or_more  ? "\e[34m+\e[0m" :
  43           _quantifier == Token::Quantifier::zero_or_more ? "\e[34m*\e[0m" : "");
  44
  45   for (const auto& tag : _tags)
  46     out << " \e[34m" << tag << "\e[0m";
  47
  48   return out.str ();
  49 }
  50
  51 ////////////////////////////////////////////////////////////////////////////////
  52 void PEG::loadFromFile (File& file)
  53 {
  54   if (! file.exists ())
  55     throw format ("PEG file '{1}' not found.", file._data);
  56
  57   std::string contents;
  58   file.read (contents);
  59
  60   // TODO Instead of simply reading a file, read a file and allow lines that
  61   //      match /^include <path>$/ to represent nested files.
  62
  63   loadFromString (contents);
  64 }
  65
  66 ////////////////////////////////////////////////////////////////////////////////
  67 // Load and parse PEG.
  68 //
  69 // Syntax:
  70 //   rule-name:  alternate1-token1 alternate1-token2
  71 //               alternate2-token1
  72 //
  73 // - Rules are aligned at left margin only, followed by colon.
  74 // - Productions are indented and never at left margin.
  75 // - Blank lines delineate rules.
  76 //
  77 // Details:
  78 // - String literals are always double-quoted.
  79 // - Character literals are alをays single-quoted.
  80 // - "*", "+" and "?" suffixes have POSIX wildcard semantics.
  81 //
  82 void PEG::loadFromString (const std::string& input)
  83 {
  84   // This is a state machine.  Read each line.
  85   std::string rule_name = "";
  86   for (auto& line : loadImports (split (input, '\n')))
  87   {
  88     line = trim (line);
  89
  90     // Eliminate inline comments.
  91     auto hash = line.find ('#');
  92     if (hash != std::string::npos)
  93     {
  94       line.resize (hash);
  95       line = trim (line);
  96
  97       if (line == "")
  98         continue;
  99     }
 100     else
 101     {
 102       line = trim (line);
 103     }
 104
 105     // Skip blank lines with no semantics.
 106     if (line == "" and rule_name == "")
 107       continue;
 108
 109     if (line != "")
 110     {
 111       int token_count = 0;
 112
 113       // Instantiate and configure the Lexer.
 114       Lexer l (line);
 115       l.noDate ();
 116       l.noDuration ();
 117       l.noUUID ();
 118       l.noHexNumber ();
 119       l.noURL ();
 120       l.noPath ();
 121       l.noPattern ();
 122       l.noOperator ();
 123
 124       Lexer::Type type;
 125       std::string token;
 126       while (l.token (token, type))
 127       {
 128         ++token_count;
 129
 130         // Rule definitions end in a colon.
 131         if (token.back () == ':')
 132         {
 133           // Capture the Rule_name.
 134           rule_name = token.substr (0, token.size () - 1);
 135
 136           // If this is the first Rule, capture it as a starting point.
 137           if (_start == "")
 138             _start = rule_name;
 139
 140           _rules[rule_name] = PEG::Rule ();
 141           token_count = 0;
 142         }
 143         // Production definition.
 144         else
 145         {
 146           // If no Production was added yet, add one.
 147           if (token_count <= 1)
 148             _rules[rule_name].push_back (PEG::Production ());
 149
 150           // Decorate the token, if necessary.
 151           std::string::size_type start = 0;
 152           std::string::size_type end = token.length ();
 153
 154           auto q = Token::Quantifier::one;
 155           auto l = Token::Lookahead::none;
 156
 157           if (token.back () == '?')
 158           {
 159             q = Token::Quantifier::zero_or_one;
 160             --end;
 161           }
 162           else if (token.back () == '+')
 163           {
 164             q = Token::Quantifier::one_or_more;
 165             --end;
 166           }
 167           else if (token.back () == '*')
 168           {
 169             q = Token::Quantifier::zero_or_more;
 170             --end;
 171           }
 172
 173           if (token.front () == '&')
 174           {
 175             l = Token::Lookahead::positive;
 176             ++start;
 177           }
 178           else if (token.front () == '!')
 179           {
 180             l = Token::Lookahead::negative;
 181             ++start;
 182           }
 183
 184           PEG::Token t (token.substr (start, end - start));
 185           t._quantifier = q;
 186           t._lookahead = l;
 187
 188           if (type == Lexer::Type::string)
 189           {
 190             t.tag ("literal");
 191             t.tag (token[0] == '\'' ? "character" : "string");
 192           }
 193           else if (t._token.front () == '<' and
 194                    t._token.back ()  == '>')
 195           {
 196             t.tag ("intrinsic");
 197
 198             if (t._token.substr (0, 8) == "<entity:")
 199               t.tag ("entity");
 200
 201             if (t._token.substr (0, 10) == "<external:")
 202               t.tag ("external");
 203           }
 204
 205           // Add the new Token to the most recent Production, of the current
 206           // Rule.
 207           _rules[rule_name].back ().push_back (t);
 208         }
 209       }
 210     }
 211
 212     // A blank line in the input ends the current rule definition.
 213     else
 214       rule_name = "";
 215   }
 216
 217   if (_debug)
 218     std::cout << dump ();
 219
 220   // Validate the parsed grammar.
 221   validate ();
 222 }
 223
 224 ////////////////////////////////////////////////////////////////////////////////
 225 std::map <std::string, PEG::Rule> PEG::syntax () const
 226 {
 227   return _rules;
 228 }
 229
 230 ////////////////////////////////////////////////////////////////////////////////
 231 std::string PEG::firstRule () const
 232 {
 233   return _start;
 234 }
 235
 236 ////////////////////////////////////////////////////////////////////////////////
 237 void PEG::debug ()
 238 {
 239   ++_debug;
 240 }
 241
 242 ////////////////////////////////////////////////////////////////////////////////
 243 void PEG::strict (bool value)
 244 {
 245   _strict = value;
 246 }
 247
 248 ////////////////////////////////////////////////////////////////////////////////
 249 std::string PEG::dump () const
 250 {
 251   std::stringstream out;
 252   out << "PEG\n";
 253
 254   // Show the import files, if any.
 255   if (_imports.size ())
 256   {
 257     for (const auto& import : _imports)
 258       out << "  import " << import << '\n';
 259     out << '\n';
 260   }
 261
 262   // Determine longest rule name, for display alignment.
 263   size_t longest = 0;
 264   for (const auto& rule : _rules)
 265     if (rule.first.length () > longest)
 266       longest = rule.first.length ();
 267
 268   for (const auto& rule : _rules)
 269   {
 270     // Indicate the start Rule.
 271     out << "  "
 272         << (rule.first == _start ? "▶" : " ")
 273         << ' '
 274         << rule.first
 275         << ':'
 276         << std::string (1 + longest - rule.first.length (), ' ');
 277
 278     int count = 0;
 279     for (const auto& production : rule.second)
 280     {
 281       if (count)
 282         out << std::string (6 + longest, ' ');
 283
 284       for (const auto& token : production)
 285         out << token.dump () << ' ';
 286
 287       out << "\n";
 288       ++count;
 289     }
 290
 291     out << "\n";
 292   }
 293
 294   return out.str ();
 295 }
 296
 297 ////////////////////////////////////////////////////////////////////////////////
 298 std::vector <std::string> PEG::loadImports (const std::vector <std::string>& lines)
 299 {
 300   std::vector <std::string> resolved;
 301
 302   for (auto& line : lines)
 303   {
 304     auto copy = trim (line);
 305
 306     auto hash = copy.find ('#');
 307     if (hash != std::string::npos)
 308     {
 309       copy.resize (hash);
 310       copy = trim (copy);
 311     }
 312
 313     if (copy.find ("import ") == 0)
 314     {
 315       File file (trim (copy.substr (7)));
 316       if (file.exists () &&
 317           file.readable ())
 318       {
 319         // Only import files that are not already imported.
 320         if (std::find (_imports.begin (), _imports.end (), file._data) == _imports.end ())
 321         {
 322           _imports.push_back (file._data);
 323
 324           std::vector <std::string> imported;
 325           file.read (imported);
 326           imported = loadImports (imported);
 327
 328           resolved.insert(std::end(resolved), std::begin(imported), std::end(imported));
 329         }
 330       }
 331       else
 332         throw format ("Cannot import '{1}'", file._data);
 333     }
 334     else
 335     {
 336       // Store original line.
 337       resolved.push_back (line);
 338     }
 339   }
 340
 341   return resolved;
 342 }
 343
 344 ////////////////////////////////////////////////////////////////////////////////
 345 void PEG::validate () const
 346 {
 347   if (_start == "")
 348     throw std::string ("There are no rules defined.");
 349
 350   std::vector <std::string> allRules;
 351   std::vector <std::string> allTokens;
 352   std::vector <std::string> allLeftRecursive;
 353   std::vector <std::string> intrinsics;
 354   std::vector <std::string> externals;
 355
 356   for (const auto& rule : _rules)
 357   {
 358     allRules.push_back (rule.first);
 359
 360     for (const auto& production : rule.second)
 361     {
 362       for (const auto& token : production)
 363       {
 364         if (token.hasTag ("intrinsic"))
 365           intrinsics.push_back (token._token);
 366
 367         else if (token.hasTag ("external"))
 368           externals.push_back (token._token);
 369
 370         else if (! token.hasTag ("literal"))
 371           allTokens.push_back (token._token);
 372
 373         if (token._token == production[0]._token and
 374             rule.first == production[0]._token   and
 375             production.size () == 1)
 376           allLeftRecursive.push_back (token._token);
 377       }
 378     }
 379   }
 380
 381   std::vector <std::string> notUsed;
 382   std::vector <std::string> notDefined;
 383   listDiff (allRules, allTokens, notUsed, notDefined);
 384
 385   // Undefined value - these are definitions that appear in token, but are
 386   // not in _rules.
 387   for (const auto& nd : notDefined)
 388     if (std::find (externals.begin (), externals.end (), nd) == externals.end ())
 389       throw format ("Definition '{1}' referenced, but not defined.", nd);
 390
 391   // Circular definitions - these are names in _rules that also appear as
 392   // the only token in any of the alternates for that definition.
 393   for (const auto& lr : allLeftRecursive)
 394     throw format ("Definition '{1}' is left recursive.", lr);
 395
 396   for (const auto& r : allRules)
 397     if (r[0] == '<')
 398       throw format ("Definition '{1}' may not redefine an intrinsic.");
 399
 400   for (const auto& r : allRules)
 401     if (r[0] == '"' or
 402         r[0] == '\'')
 403       throw format ("Definition '{1}' may not be a literal.");
 404
 405   // Unused definitions - these are names in _rules that are never
 406   // referenced as token.
 407   for (const auto& nu : notUsed)
 408   {
 409     if (std::find (externals.begin (), externals.end (), nu) == externals.end () &&
 410         nu != _start)
 411     {
 412       if (_strict)
 413         throw format ("Definition '{1}' is defined, but not referenced.", nu);
 414       else
 415         std::cout << "Warning: Definition '" << nu << "' is defined, but not referenced.\n";
 416     }
 417   }
 418
 419   // Intrinsics must be recognized.
 420   for (auto& intrinsic : intrinsics)
 421     if (intrinsic != "<digit>"                 &&
 422         intrinsic != "<hex>"                   &&
 423         intrinsic != "<punct>"                 &&
 424         intrinsic != "<eol>"                   &&
 425         intrinsic != "<sep>"                   &&
 426         intrinsic != "<ws>"                    &&
 427         intrinsic != "<alpha>"                 &&
 428         intrinsic != "<character>"             &&
 429         intrinsic != "<word>"                  &&
 430         intrinsic != "<token>"                 &&
 431         intrinsic.substr (0, 8)  != "<entity:" &&
 432         intrinsic.substr (0, 10) != "<external:")
 433       throw format ("Specified intrinsic '{1}' is not supported.", intrinsic);
 434 }
 435
 436 ////////////////////////////////////////////////////////////////////////////////