Changeset 5789

Timestamp:

Dec 19, 2017, 12:17:52 PM (14 months ago)

Author:

cameron

Message:

Further parser bug fixes and restructuring

Location:

icGREP/icgrep-devel/icgrep/re

Files:

• re_parser.cpp (modified) (12 diffs)
• re_parser.h (modified) (6 diffs)
• re_parser_bre.cpp (modified) (4 diffs)
• re_parser_ere.cpp (modified) (4 diffs)
• re_parser_pcre.h (modified) (1 diff)

icGREP/icgrep-devel/icgrep/re/re_parser.cpp

@@ -76 +76 @@
 , fNested(false)
 , mGroupsOpen(0)
-, fSupportNonCaptureGroup(false)
 , mCursor(regular_expression)
 , mCaptureGroupCount(0)
@@ -151 +150 @@
     else return createCC(parse_literal_codepoint());
 }
-                                                          
+    
+    
+RE * RE_Parser::parse_mode_group(bool & closing_paren_parsed) {
+    const ModeFlagSet savedModeFlagSet = fModeFlagSet;
+    while (mCursor.more() && !atany(":)")) {
+        bool negateMode = accept('-');
+        ModeFlagType modeBit;
+        switch (*mCursor) {
+            case 'i': modeBit = CASE_INSENSITIVE_MODE_FLAG; break;
+            case 'g': modeBit = GRAPHEME_CLUSTER_MODE; break;
+            case 'm': modeBit = MULTILINE_MODE_FLAG; break;
+                //case 's': modeBit = DOTALL_MODE_FLAG; break;
+            case 'x': modeBit = IGNORE_SPACE_MODE_FLAG; break;
+            case 'd': modeBit = UNIX_LINES_MODE_FLAG; break;
+            default: ParseFailure("Unsupported mode flag.");
+        }
+        ++mCursor;
+        if (negateMode) {
+            fModeFlagSet &= ~modeBit;
+            negateMode = false;  // for next flag
+        } else {
+            fModeFlagSet |= modeBit;
+        }
+    }
+    if (accept(':')) {
+        RE * group_expr = parse_alt();
+        auto changed = fModeFlagSet ^ savedModeFlagSet;
+        if ((changed & CASE_INSENSITIVE_MODE_FLAG) != 0) {
+            group_expr = makeGroup(Group::Mode::CaseInsensitiveMode, group_expr,
+                                   (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) == 0 ? Group::Sense::Off : Group::Sense::On);
+        }
+        if ((changed & GRAPHEME_CLUSTER_MODE) != 0) {
+            group_expr = makeGroup(Group::Mode::GraphemeMode, group_expr,
+                                   (fModeFlagSet & GRAPHEME_CLUSTER_MODE) == 0 ? Group::Sense::Off : Group::Sense::On);
+        }
+        fModeFlagSet = savedModeFlagSet;
+        closing_paren_parsed = false;
+        return group_expr;
+    } else {  // if *_cursor == ')'
+        require(')');
+        closing_paren_parsed = true;
+        auto changed = fModeFlagSet ^ savedModeFlagSet;
+        if ((changed & (CASE_INSENSITIVE_MODE_FLAG|GRAPHEME_CLUSTER_MODE)) != 0) {
+            RE * group_expr = parse_seq();
+            if ((changed & CASE_INSENSITIVE_MODE_FLAG) != 0) {
+                group_expr = makeGroup(Group::Mode::CaseInsensitiveMode, group_expr,
+                                       (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) == 0 ? Group::Sense::Off : Group::Sense::On);
+            }
+            if ((changed & GRAPHEME_CLUSTER_MODE) != 0) {
+                group_expr = makeGroup(Group::Mode::GraphemeMode, group_expr,
+                                       (fModeFlagSet & GRAPHEME_CLUSTER_MODE) == 0 ? Group::Sense::Off : Group::Sense::On);
+            }
+            return group_expr;
+        }
+        else return makeSeq();
+    }
+
+}
 
 // Parse some kind of parenthesized group.  Input precondition: mCursor
 // after the (
 RE * RE_Parser::parse_group() {
-    const ModeFlagSet savedModeFlagSet = fModeFlagSet;
     mGroupsOpen++;
     RE * group_expr = nullptr;
-    if (*mCursor == '?' && fSupportNonCaptureGroup) {
-        switch (*++mCursor) {
-            case '#':  // comment
-                while (*++mCursor != ')');
-                ++mCursor;
-                return parse_next_item();
-            case ':':  // Non-capturing paren
-                ++mCursor;
-                group_expr = parse_alt();
-                break;
-            case '=':
-                ++mCursor;
-                group_expr = makeLookAheadAssertion(parse_alt());
-                break;
-            case '!':
-                ++mCursor;
-                group_expr = makeNegativeLookAheadAssertion(parse_alt());
-                break;
-            case '>':
-                ++mCursor;
-                group_expr = makeAtomicGroup(parse_alt());
-                break;
-            case '|':
-                ++mCursor;
-                group_expr = makeBranchResetGroup(parse_alt());
-                break;
-            case '<':
-                ++mCursor;
-                if (*mCursor == '=') {
-                    ++mCursor;
-                    group_expr = makeLookBehindAssertion(parse_alt());
-                }
-                else if (*mCursor == '!') {
-                    ++mCursor;
-                    group_expr = makeNegativeLookBehindAssertion(parse_alt());
-                } else {
-                    ParseFailure("Illegal lookbehind assertion syntax.");
-                }
-                break;
-            case '-': case 'd' : case 'i': case 'm': case 's': case 'x': case 'g':
-                while (*mCursor != ')' && *mCursor != ':') {
-                    bool negateMode = false;
-                    ModeFlagType modeBit;
-                    if (*mCursor == '-') {
-                        negateMode = true;
-                        ++mCursor;
-                    }
-                    switch (*mCursor) {
-                        case 'i': modeBit = CASE_INSENSITIVE_MODE_FLAG; break;
-                        case 'g': modeBit = GRAPHEME_CLUSTER_MODE; break;
-                        case 'm': modeBit = MULTILINE_MODE_FLAG; break;
-                        //case 's': modeBit = DOTALL_MODE_FLAG; break;
-                        case 'x': modeBit = IGNORE_SPACE_MODE_FLAG; break;
-                        case 'd': modeBit = UNIX_LINES_MODE_FLAG; break;
-                        default: ParseFailure("Unsupported mode flag.");
-                    }
-                    ++mCursor;
-                    if (negateMode) {
-                        fModeFlagSet &= ~modeBit;
-                        negateMode = false;  // for next flag
-                    } else {
-                        fModeFlagSet |= modeBit;
-                    }
-                }
-                if (*mCursor == ':') {
-                    ++mCursor;
-                    group_expr = parse_alt();
-                    auto changed = fModeFlagSet ^ savedModeFlagSet;
-                    if ((changed & CASE_INSENSITIVE_MODE_FLAG) != 0) {
-                        group_expr = makeGroup(Group::Mode::CaseInsensitiveMode, group_expr,
-                                               (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) == 0 ? Group::Sense::Off : Group::Sense::On);
-                    }
-                    if ((changed & GRAPHEME_CLUSTER_MODE) != 0) {
-                        group_expr = makeGroup(Group::Mode::GraphemeMode, group_expr,
-                                               (fModeFlagSet & GRAPHEME_CLUSTER_MODE) == 0 ? Group::Sense::Off : Group::Sense::On);
-                    }
-                    fModeFlagSet = savedModeFlagSet;
-                    break;
-                } else {  // if *_cursor == ')'
-                    ++mCursor;
-                    auto changed = fModeFlagSet ^ savedModeFlagSet;
-                    if ((changed & (CASE_INSENSITIVE_MODE_FLAG|GRAPHEME_CLUSTER_MODE)) != 0) {
-                        group_expr = parse_seq();
-                        if ((changed & CASE_INSENSITIVE_MODE_FLAG) != 0) {
-                            group_expr = makeGroup(Group::Mode::CaseInsensitiveMode, group_expr,
-                                                   (fModeFlagSet & CASE_INSENSITIVE_MODE_FLAG) == 0 ? Group::Sense::Off : Group::Sense::On);
-                        }
-                        if ((changed & GRAPHEME_CLUSTER_MODE) != 0) {
-                            group_expr = makeGroup(Group::Mode::GraphemeMode, group_expr,
-                                                   (fModeFlagSet & GRAPHEME_CLUSTER_MODE) == 0 ? Group::Sense::Off : Group::Sense::On);
-                        }
-                        return group_expr;
-                    }
-                    else return parse_next_item();
-                }
-            default:
-                ParseFailure("Illegal (? syntax.");
+    if (accept('?')) {
+        if (accept('#')) {
+            while (mCursor.more() && !at(')')) ++mCursor;
+            group_expr = makeSeq();
+        } else if (accept(':')) { // Non-capturing paren
+            group_expr = parse_alt();
+        } else if (accept('=')) { // positive look ahead
+            group_expr = makeLookAheadAssertion(parse_alt());
+        } else if (accept('!')) { // negative look ahead
+            group_expr = makeNegativeLookAheadAssertion(parse_alt());
+        } else if (accept("<=")) { // positive look ahead
+            group_expr = makeLookBehindAssertion(parse_alt());
+        } else if (accept("<!")) { // negative look ahead
+            group_expr = makeNegativeLookBehindAssertion(parse_alt());
+        } else if (accept('>')) { // negative look ahead
+            group_expr = makeAtomicGroup(parse_alt());
+        } else if (accept('|')) { // negative look ahead
+            group_expr = makeBranchResetGroup(parse_alt());
+        } else if (atany("-dimsxg")) { // mode switches
+            bool closing_paren_parsed;
+            group_expr = parse_mode_group(closing_paren_parsed);
+            if (closing_paren_parsed) {
+                mGroupsOpen--;
+                return group_expr;
+            }
+        } else {
+            ParseFailure("Illegal (? syntax.");
         }
     } else { // Capturing paren group.
-        RE * captured = parse_alt();
-        mCaptureGroupCount++;
-        std::string captureName = "\\" + std::to_string(mCaptureGroupCount);
-        Name * const capture  = mMemoizer.memoize(makeCapture(captureName, captured));
-        auto key = std::make_pair("", captureName);
-        mNameMap.insert(std::make_pair(std::move(key), capture));
-        group_expr = capture;
-    }
-    if (*mCursor != ')') {
-        ParseFailure("Closing parenthesis required.");
-    }
+        group_expr = parse_capture_body();
+    }
+    require(')');
     mGroupsOpen--;
-    ++mCursor;
     return group_expr;
 }
-
-// TODO: Set ENABLE_EXTENDED_QUANTIFIERS false for ERE, BRE
+    
+RE * RE_Parser::parse_capture_body() {
+    RE * captured = parse_alt();
+    mCaptureGroupCount++;
+    std::string captureName = "\\" + std::to_string(mCaptureGroupCount);
+    Name * const capture  = mMemoizer.memoize(makeCapture(captureName, captured));
+    auto key = std::make_pair("", captureName);
+    mNameMap.insert(std::make_pair(std::move(key), capture));
+    return capture;
+}
+    
+    RE * RE_Parser::parse_back_reference() {
+        mCursor++;
+        std::string backref = std::string(mCursor.pos()-2, mCursor.pos());
+        auto key = std::make_pair("", backref);
+        auto f = mNameMap.find(key);
+        if (f != mNameMap.end()) {
+            return makeReference(backref, f->second);
+        }
+        else {
+            ParseFailure("Back reference " + backref + " without prior capture group.");
+        }
+    }
+
 #define ENABLE_EXTENDED_QUANTIFIERS true
     
@@ -315 +313 @@
         lb = parse_int();
         if (accept('}')) return std::make_pair(lb, lb);
-        if (!accept(',')) ParseFailure("Expecting , or }");
+        else require(',');
         if (accept('}')) return std::make_pair(lb, Rep::UNBOUNDED_REP);
         ub = parse_int();
         if (ub < lb) ParseFailure("Upper bound less than lower bound");
     }
-    if (accept('}')) return std::make_pair(lb, ub);
-    else ParseFailure("Expecting }");
+    require('}');
+    return std::make_pair(lb, ub);
 }
 
 unsigned RE_Parser::parse_int() {
     unsigned value = 0;
+    if (!isdigit(*mCursor)) ParseFailure("Expecting integer");
     while (isdigit(*mCursor)) {
         value *= 10;
@@ -347 +346 @@
         return parseEscapedSet();
     }
-    else if ((*mCursor == 'x') || (*mCursor == 'o') || (*mCursor == '0')) {
+    else if (atany("xo0")) {
         codepoint_t cp = parse_escaped_codepoint();
         if ((cp >= 0x80) && (cp <= 0xFF)) {
@@ -355 +354 @@
     }
     else if (isdigit(*mCursor)) {
-        mCursor++;
-        std::string backref = std::string(mCursor.pos()-2, mCursor.pos());
-        auto key = std::make_pair("", backref);
-        auto f = mNameMap.find(key);
-        if (f != mNameMap.end()) {
-            return makeReference(backref, f->second);
-        }
-        else {
-            ParseFailure("Back reference " + backref + " without prior capture group.");
-        }
+        return parse_back_reference();
     }
     else {
@@ -625 +615 @@
 
 Name * RE_Parser::parseNamePatternExpression(){
-
-    if (!accept('{')) ParseFailure("Expecting { after \\N");
+    require('{');
     const auto start = mCursor.pos();
     while (mCursor.more()) {
@@ -641 +630 @@
     }
     std::string nameRegexp = "/(?i)" + std::string(start, mCursor.pos());
-    if (!accept('}')) ParseFailure("Expecting } after \\N{...");
+    require('}');
     return createName("na", nameRegexp);
 }
@@ -663 +652 @@
         else have_new_expr = false;
     }
-    if (!accept(']')) ParseFailure("Expecting ]");
+    require(']');
     if (negated) return makeComplement(t1);
     else return t1;
@@ -715 +704 @@
     }
     std::string name = std::string(start, mCursor.pos());
-    if (!accept("=]")) ParseFailure("Posix equivalence class improperly terminated.");
+    require("=]");
     return createName(name);
 }
@@ -724 +713 @@
     }
     std::string name = std::string(start, mCursor.pos());
-    if (!accept(".]")) ParseFailure("Posix equivalence class improperly terminated.");
+    require(".]");
     return createName(name);
 }
@@ -731 +720 @@
     bool negated = accept('^');
     RE * posixSet = parsePropertyExpression();
-    if (!accept(":]")) ParseFailure("Posix set expression improperly terminated.");
+    require(":]");
     if (negated) return makeComplement(posixSet);
     else return posixSet;
@@ -777 +766 @@
         if (!accept('{')) ParseFailure("Malformed octal escape sequence");
         cp_value = parse_octal_codepoint(1, 7);
-        if (!accept('}')) ParseFailure("Malformed octal escape sequence");
+        require('}');
         return cp_value;
     } else if (accept('x')) {
         if (!accept('{')) return parse_hex_codepoint(1,2);  // ICU compatibility
         cp_value = parse_hex_codepoint(1, 6);
-        if (!accept('}')) ParseFailure("Malformed hex escape sequence");
+        require('}');
         return cp_value;
     } else if (accept('u')) {
         if (!accept('{')) return parse_hex_codepoint(4,4);  // ICU compatibility
         cp_value = parse_hex_codepoint(1, 6);
-        if (!accept('}')) ParseFailure("Malformed hex escape sequence");
+        require('}');
         return cp_value;
     } else if (accept('U')) {

icGREP/icgrep-devel/icgrep/re/re_parser.h

@@ -8 +8 @@
 #define RE_PARSER_H
 
-#include <map>                           // for map
-#include <re/re_memoizer.hpp>            // for Memoizer
-#include "re/re_cc.h"                    // for codepoint_t, CC (ptr only)
+#include <map>
+#include <re/re_memoizer.hpp>
+#include "re/re_cc.h"
+
 namespace re { class Name; }
 
@@ -17 +18 @@
 enum RE_Syntax {FixedStrings, BRE, ERE, PCRE, PROSITE};
 
-enum CharsetOperatorKind
-    {intersectOp, setDiffOp, ampChar, hyphenChar, rangeHyphen, posixPropertyOpener, setOpener, setCloser, backSlash, emptyOperator};    
-    
 enum ModeFlagType : unsigned {
     DEFAULT_MODE = 0,
@@ -116 +114 @@
     }
     
+    inline void require(char c) {
+        if (!accept(c)) {
+            if (mCursor.noMore()) ParseFailure("Expecting " + std::string(1, c) + " but end of input encountered");
+            ParseFailure("Expecting " + std::string(1, c) + " but " + std::string(1, *mCursor) + " encountered");
+        }
+    }
+    
     inline bool atany(std::string s) {
         if (mCursor.noMore()) return false;
@@ -134 +139 @@
     
     inline bool accept(std::string s) {
+        Cursor tmp = mCursor;
         for (unsigned i = 0; i < s.length(); i++) {
-            if (mCursor.noMore() || (s[i] != *mCursor)) return false;
-            mCursor++;
-        }
+            if (tmp.noMore() || (s[i] != *tmp)) return false;
+            tmp++;
+        }
+        mCursor = tmp;
         return true;
     }
     
-
+    inline void require(std::string s) {
+        if (!accept(s)) {
+            if (mCursor.noMore()) ParseFailure("Expecting " + s + " but end of input encountered");
+            unsigned long rem = mCursor.remaining();
+            ParseFailure("Expecting " + s + " but " + std::string(mCursor.pos(), mCursor.pos() + std::min(rem, s.length())) + " encountered");
+        }
+    }
+    
     RE_Parser(const std::string & regular_expression);
 
@@ -155 +169 @@
 
     virtual RE * parse_group();
-
+    
+    RE * parse_mode_group(bool & closing_paren_parsed);
+
+    RE * parse_capture_body();
+    
+    RE * parse_back_reference();
+    
     virtual bool isSetEscapeChar(char c);
 
@@ -223 +243 @@
     bool                        fNested;
     unsigned                    mGroupsOpen;
-    bool                        fSupportNonCaptureGroup;
     Cursor                      mCursor;
     unsigned                    mCaptureGroupCount;

icGREP/icgrep-devel/icgrep/re/re_parser_bre.cpp

@@ -13 +13 @@
 #include <re/re_assertion.h>
 #include <re/re_rep.h>
+#include <llvm/Support/raw_ostream.h>
 
 
@@ -29 +30 @@
 RE * RE_Parser_BRE::parse_seq() {
     std::vector<RE *> seq;
-    if (!mCursor.more() || at("\\|") || ((mGroupsOpen > 0) && at("\\)"))) return makeSeq();
+    if (!mCursor.more() || at("\\|") || at("\\)")) return makeSeq();
     for (;;) {
         RE * re = parse_next_item();
@@ -54 +55 @@
 }
 
-// A parenthesized group.  Input precondition: the opening ( has been consumed
+// A parenthesized capture group.  Input precondition: the opening \( has been consumed
 RE * RE_Parser_BRE::parse_group() {
-    // Capturing paren group.
     mGroupsOpen++;
-    RE * captured = parse_alt();
-    mCaptureGroupCount++;
-    std::string captureName = "\\" + std::to_string(mCaptureGroupCount);
-    Name * const capture  = mMemoizer.memoize(makeCapture(captureName, captured));
-    auto key = std::make_pair("", captureName);
-    mNameMap.insert(std::make_pair(std::move(key), capture));
-    if (!accept("\\)")) ParseFailure("Closing parenthesis required.");
+    RE * captured = parse_capture_body();
+    require("\\)");
     mGroupsOpen--;
-    return capture;
+    return captured;
 }
 
@@ -93 +88 @@
         lb = parse_int();
         if (accept("\\}")) return std::make_pair(lb, lb);
-        if (!accept(',')) ParseFailure("Expecting , or }");
+        else require(',');
         if (accept("\\}")) return std::make_pair(lb, Rep::UNBOUNDED_REP);
         ub = parse_int();
         if (ub < lb) ParseFailure("Upper bound less than lower bound");
     }
-    if (accept("\\}")) return std::make_pair(lb, ub);
-    else ParseFailure("Expecting \\}");
+    require("\\}");
+    return std::make_pair(lb, ub);
 }
 

icGREP/icgrep-devel/icgrep/re/re_parser_ere.cpp

@@ -27 +27 @@
 }
 
-// A parenthesized group.  Input precondition: the opening ( has been consumed
+// A parenthesized capture group.  Input precondition: the opening ( has been consumed
 RE * RE_Parser_ERE::parse_group() {
-    // Capturing paren group.
     mGroupsOpen++;
-    RE * captured = parse_alt();
-    mCaptureGroupCount++;
-    std::string captureName = "\\" + std::to_string(mCaptureGroupCount);
-    Name * const capture  = mMemoizer.memoize(makeCapture(captureName, captured));
-    auto key = std::make_pair("", captureName);
-    mNameMap.insert(std::make_pair(std::move(key), capture));
-    if (!accept(')')) ParseFailure("Closing parenthesis required.");
+    RE * captured = parse_capture_body();
+    require(')');
     mGroupsOpen--;
-    return capture;
+    return captured;
 }
 
@@ -49 +43 @@
     if (accept('<')) return makeWordBegin();
     if (accept('>')) return makeWordEnd();
-    if (isdigit(*mCursor)) {
-        mCursor++;
-        std::string backref = std::string(mCursor.pos()-2, mCursor.pos());
-        auto key = std::make_pair("", backref);
-        auto f = mNameMap.find(key);
-        if (f != mNameMap.end()) {
-            return makeReference(backref, f->second);
-        }
-        else {
-            ParseFailure("Back reference " + backref + " without prior capture group.");
-        }
-    }
+    if (isdigit(*mCursor)) return parse_back_reference();
     else {
         return createCC(parse_literal_codepoint());
@@ -70 +53 @@
 // Items represent individual characters or sets of characters.
 // Ranges may be formed by individual character items separated by '-'.
+// Note that there are no backslash escapes for ERE or BRE bracket expressions.
 RE * RE_Parser_ERE::parse_bracket_expr () {
     bool negated = accept('^');
@@ -84 +68 @@
     } while (mCursor.more() && !at(']'));
     RE * t = makeAlt(items.begin(), items.end());
-    if (!accept(']')) ParseFailure("Expecting ]");
+    require(']');
     if (negated) return makeComplement(t);
     else return t;

icGREP/icgrep-devel/icgrep/re/re_parser_pcre.h

@@ -14 +14 @@
     public:
         RE_Parser_PCRE(const std::string & regular_expression) : RE_Parser(regular_expression) {
-            fSupportNonCaptureGroup = true;
             mReSyntax = RE_Syntax ::PCRE;
         }