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

Last change on this file was 5835, checked in by nmedfort, 5 weeks ago

Revised RE_Minimizer to use alphabets + minor optimizations to RE functions

File size: 7.0 KB
Line 
1/*
2 *  Copyright (c) 2014-6 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icgrep is a trademark of International Characters.
5 */
6
7#ifndef RE_PARSER_H
8#define RE_PARSER_H
9
10#include <map>
11#include <re/re_memoizer.hpp>
12#include "re/re_cc.h"
13
14namespace re { class Name; }
15
16namespace re {
17
18enum RE_Syntax {FixedStrings, BRE, ERE, PCRE, PROSITE};
19
20enum ModeFlagType : unsigned {
21    DEFAULT_MODE = 0,
22    CASE_INSENSITIVE_MODE_FLAG = 1,
23    MULTILINE_MODE_FLAG = 2,
24    DOTALL_MODE_FLAG = 4,         // not currently implemented
25    IGNORE_SPACE_MODE_FLAG = 8,
26    UNIX_LINES_MODE_FLAG = 16,
27    GRAPHEME_CLUSTER_MODE = 32
28};
29
30using ModeFlagSet = unsigned;
31
32class RE_Parser {
33public:
34
35    static RE * parse(const std::string &input_string, ModeFlagSet initialFlags, RE_Syntax syntax = RE_Syntax::PCRE, bool ByteMode = false);
36
37protected:
38
39    using NameMap = std::map<std::pair<std::string, std::string>, re::Name *>;
40
41    using cursor_t = std::string::const_iterator;
42
43    using char_t = const std::string::value_type;
44
45    struct Cursor {
46        friend class RE_Parser;
47
48        inline Cursor & operator++() {
49            if (LLVM_UNLIKELY(mCursor == mEnd)) {
50                IncompleteRegularExpression();
51            }
52            ++mCursor;
53            return *this;
54        }
55
56        inline Cursor operator++(int) {
57            if (LLVM_UNLIKELY(mCursor == mEnd)) {
58                IncompleteRegularExpression();
59            }
60            Cursor tmp(*this);
61            ++mCursor;
62            return tmp;
63        }
64
65        inline const char_t operator*() const {
66            if (LLVM_UNLIKELY(mCursor == mEnd)) {
67                return 0;
68            }
69            return *mCursor;
70        }
71
72        inline bool noMore() const {
73            return mCursor == mEnd;
74        }
75
76        inline bool more() const {
77            return mCursor != mEnd;
78        }
79
80        inline cursor_t::difference_type remaining() const {
81            return mEnd - mCursor;
82        }
83
84        inline cursor_t pos() const {
85            return mCursor;
86        }
87               
88        Cursor(const std::string & expression) : mCursor(expression.cbegin()), mEnd(expression.cend()), mStart(expression.cbegin()) {}
89        Cursor(const Cursor & cursor) : mCursor(cursor.mCursor), mEnd(cursor.mEnd), mStart(cursor.mStart) {}
90        inline Cursor & operator=(const Cursor & cursor) {
91            mCursor = cursor.mCursor;
92            mEnd = cursor.mEnd;
93            return *this;
94        }
95    private:       
96        LLVM_ATTRIBUTE_NORETURN void IncompleteRegularExpression();
97        LLVM_ATTRIBUTE_NORETURN void ParseFailure(const std::string & errmsg);
98    private:
99        cursor_t    mCursor;
100        cursor_t    mEnd;
101        cursor_t    mStart;
102    };
103
104   
105   
106    inline bool at(char c) {
107        return (mCursor.more()) && (*mCursor == c);
108    }
109   
110    inline bool accept(char c) {
111        if (at(c)) {
112            mCursor++;
113            return true;
114        }
115        return false;
116    }
117   
118    inline void require(char c) {
119        if (!accept(c)) {
120            if (mCursor.noMore()) ParseFailure("Expecting " + std::string(1, c) + " but end of input encountered");
121            ParseFailure("Expecting " + std::string(1, c) + " but " + std::string(1, *mCursor) + " encountered");
122        }
123    }
124   
125    inline bool atany(std::string s) {
126        if (mCursor.noMore()) return false;
127        for (unsigned i = 0; i < s.length(); i++) {
128            if (s[i] == *mCursor) return true;
129        }
130        return false;
131    }
132   
133    inline bool at(std::string s) {
134        Cursor tmp = mCursor;
135        for (unsigned i = 0; i < s.length(); i++) {
136            if (tmp.noMore() || (s[i] != *tmp)) return false;
137            tmp++;
138        }
139        return true;
140    }
141   
142    inline bool accept(std::string s) {
143        Cursor tmp = mCursor;
144        for (unsigned i = 0; i < s.length(); i++) {
145            if (tmp.noMore() || (s[i] != *tmp)) return false;
146            tmp++;
147        }
148        mCursor = tmp;
149        return true;
150    }
151   
152    inline void require(std::string s) {
153        if (!accept(s)) {
154            if (mCursor.noMore()) ParseFailure("Expecting " + s + " but end of input encountered");
155            size_t rem = mCursor.remaining();
156            ParseFailure("Expecting " + s + " but " + std::string(mCursor.pos(), mCursor.pos() + std::min(rem, s.length())) + " encountered");
157        }
158    }
159   
160    inline char get1() { return *mCursor++;}
161
162   
163    RE_Parser(const std::string & regular_expression);
164
165    RE_Parser(const std::string & regular_expression, ModeFlagSet initialFlags);
166
167    virtual RE * parse_RE();
168
169    virtual RE * parse_alt();
170   
171    virtual RE * parse_seq();
172
173    virtual RE * parse_next_item();
174
175    virtual RE * parse_group();
176   
177    RE * parse_mode_group(bool & closing_paren_parsed);
178
179    RE * parse_capture_body();
180   
181    RE * parse_back_reference();
182   
183    virtual bool isSetEscapeChar(char c);
184
185    virtual RE * extend_item(RE * re);
186
187    RE * parseGraphemeBoundary(RE * re);
188
189    virtual std::pair<int, int> parse_range_bound();
190
191    unsigned parse_int();
192
193    virtual RE * parse_escaped();
194
195    virtual RE * parseEscapedSet();
196
197    codepoint_t parse_literal_codepoint();
198   
199    codepoint_t parse_utf8_codepoint();
200
201    virtual RE * parsePropertyExpression();
202
203    Name * parseNamePatternExpression();
204
205    RE * makeComplement(RE * s);
206    RE * makeWordBoundary();
207    RE * makeWordNonBoundary();
208    RE * makeReBoundary(RE * wordC);
209    RE * makeReNonBoundary(RE * wordC);
210    RE * makeWordBegin();
211    RE * makeWordEnd();
212    Name * makeDigitSet();
213    Name * makeAlphaNumeric();
214    Name * makeWhitespaceSet();
215    Name * makeWordSet();
216   
217    Name * createName(std::string value);
218    Name * createName(std::string prop, std::string value);
219
220    RE * parse_extended_bracket_expression();
221    RE * parse_bracketed_items();
222    RE * range_extend(RE * e1);
223   
224    RE * parse_equivalence_class();
225    RE * parse_collation_element();
226    RE * parse_Posix_class();
227    RE * parse_escaped_char_item();
228   
229    RE * makeAtomicGroup(RE * r);
230    RE * makeBranchResetGroup(RE * r);
231
232    codepoint_t parse_codepoint();
233
234    virtual codepoint_t parse_escaped_codepoint();
235
236    codepoint_t parse_hex_codepoint(int mindigits, int maxdigits);
237
238    codepoint_t parse_octal_codepoint(int mindigits, int maxdigits);
239
240    CC * createCC(const codepoint_t cp);
241
242    static std::string canonicalize(const cursor_t begin, const cursor_t end);
243
244    bool isCharAhead(char c);
245
246    LLVM_ATTRIBUTE_NORETURN void InvalidUTF8Encoding();
247
248    LLVM_ATTRIBUTE_NORETURN void ParseFailure(const std::string & errmsg) {
249        mCursor.ParseFailure(errmsg);
250    }
251
252protected:
253    bool                        fByteMode;
254    ModeFlagSet                 fModeFlagSet;
255    bool                        fNested;
256    unsigned                    mGroupsOpen;
257    Cursor                      mCursor;
258    unsigned                    mCaptureGroupCount;
259    RE_Syntax                   mReSyntax;
260    NameMap                     mNameMap;
261    Memoizer                    mMemoizer;
262};
263
264}
265
266#endif // RE_PARSER_H
Note: See TracBrowser for help on using the repository browser.