diff options
Diffstat (limited to 'Build/source/libs/icu/icu-xetex/test/intltest/wbnf.cpp')
-rw-r--r-- | Build/source/libs/icu/icu-xetex/test/intltest/wbnf.cpp | 1771 |
1 files changed, 1771 insertions, 0 deletions
diff --git a/Build/source/libs/icu/icu-xetex/test/intltest/wbnf.cpp b/Build/source/libs/icu/icu-xetex/test/intltest/wbnf.cpp new file mode 100644 index 00000000000..7d08de7081b --- /dev/null +++ b/Build/source/libs/icu/icu-xetex/test/intltest/wbnf.cpp @@ -0,0 +1,1771 @@ +/* + ****************************************************************************** + * Copyright (C) 2005-2007, International Business Machines Corporation and * + * others. All Rights Reserved. * + ****************************************************************************** + */ + +#include <stdio.h> +#include <string.h> +#include <stdlib.h> +#include <time.h> + +#include "wbnf.h" + +// Most of this code is meant to test the test code. It's a self test. +// Normally this isn't run. +#define TEST_WBNF_TEST 0 + +/////////////////////////////////////////////////////////// +// +// Constants and the most basic helper classes +// + +static const char DIGIT_CHAR[] = "0123456789"; +static const char WHITE_SPACE[] = {'\t', ' ', '\r', '\n', 0}; +static const char ALPHABET[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"; +static const char SPECIAL[] = "!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~"; + +static inline UBool isInList(const char c /*in*/, const char list[] /*in*/){ + const char * p = list; + for (;*p != 0 && *p != c; p++); + return *p?TRUE:FALSE; +} +static inline UBool isDigit(char c) {return isInList(c, DIGIT_CHAR);} +static inline UBool isWhiteSpace(char c) {return isInList(c, WHITE_SPACE);} +static inline UBool isAlphabet(char c) {return isInList(c, ALPHABET);} +static inline UBool isSpecialAsciiChar(char c) {return isInList(c,SPECIAL);} + + + +/////////////////////////////////////////////////////////// +// +// Helper classes +// + +class Buffer_byte{ +// Utility class, can be treated as an auto expanded array. no boundary check. + + typedef char byte; + byte * start; + byte * current; + int buffer_size; // size unit is byte +public: + inline int content_size(){return current - start;} // size unit is byte + +private: + inline void expand(int add_size = 100){ // size unit is byte + int new_size = buffer_size + add_size; + + int cs_snap = content_size(); + start = (byte *) realloc(start, new_size); // may change the value of start + current = start + cs_snap; + + memset(current, 0, add_size); + buffer_size = new_size; + } + + inline void expand_to(int size){ + int r = size - buffer_size; + if (r > 0) { + expand(r); // simply expand, no block alignment + } + } + Buffer_byte(const Buffer_byte &); + Buffer_byte & operator = (const Buffer_byte &); +public: + Buffer_byte():start(NULL),current(start),buffer_size(0){ + expand(); + } + ~Buffer_byte(){ + free(start); + } + + inline void reset(){ + start != NULL ? memset(start, 0, buffer_size) : 0; + current = start; + } + + // Using memory copy method to append a C array to buffer, + inline void append(const void * c, int size){ // size unit is byte + expand_to(content_size() + size) ; + memcpy(current, c, size); + current = current + size; + } + + byte * buffer(){ + return start; + } +}; + +/* + The class(es) try to work as bulid-in array, so it overloads these two operators + operator type *(); + type & operator[]; + The first is used to auto type convert, the latter is used to select member. + + A small trick is the class does not overload the address-of operator. This + behavior is different from bulid-in array, but it give us the opportunity + to get the address of the class itself. +*/ +//template<typename type> +// class BUFFER{ +// typedef BUFFER name; +#define BUFFER(type, name)\ + class name {\ + private:\ + Buffer_byte buf;\ + public:\ + name & reset() {buf.reset(); return *this;}\ + name & append(type c) {buf.append(&c, sizeof(type)); return *this;}\ + name & append_array(const type * p, int size) {buf.append(p, sizeof(type)*size); return *this;}\ + type & operator [] (int i) { return ((type *) buf.buffer())[i];}\ + operator type *(){return (type *) buf.buffer();} \ + int content_size(){return buf.content_size() / sizeof(type);}\ + } + + +class Pick{ +/* The Pick is the basic language generator element*/ +public: + // generate a string accroding the syntax + // Return a null-terminated c-string. The buffer is owned by callee. + virtual const char* next() = 0; + virtual ~Pick(){}; +}; + +//typedef BUFFER<char> Buffer_char; +//typedef BUFFER<int> Buffer_int; +//typedef BUFFER<Pick *> Buffer_pPick; +BUFFER(char, Buffer_char); +BUFFER(int, Buffer_int); +BUFFER(Pick *, Buffer_pPick); + +class SymbolTable{ +/* Helper class. +* It's a mapping table between 'variable name' and its 'active Pick object' +*/ +private: + Buffer_char name_buffer; // var names storage space + + Buffer_int names; // points to name (offset in name_buffer) + Buffer_pPick refs; // points to Pick + + int get_index(const char *const var_name){ + int len = names.content_size(); + for (int i=0; i< len; i++){ + if (strcmp(var_name, name_buffer + names[i]) == 0){ + return i; + } + } + return -1; + } + +public: + enum RESULT {EMPTY, NO_VAR, NO_REF, HAS_REF}; + + RESULT find(const char *const var_name /*[in] c-string*/, Pick * * ref = NULL /*[out] Pick* */){ + if (!var_name) return EMPTY; // NULL name + + int i = get_index(var_name); + if (i == -1){ + return NO_VAR; // new name + } + if (!refs[i]){ // exist name, no ref + return NO_REF; + } else { + if (ref) { + *ref = refs[i]; + } + return HAS_REF; // exist name, has ref + } + } + + void put(const char *const var_name, Pick *const var_ref = NULL){ + int i = get_index(var_name); + switch(find(var_name)){ + case EMPTY: // NULL name + break; + case NO_VAR: // new name + int offset; + offset = name_buffer.content_size(); + name_buffer.append_array(var_name, strlen(var_name) + 1); + names.append(offset); + refs.append(var_ref); + break; + case NO_REF: // exist name, no ref + refs[i] = var_ref; // link definition with variable + break; + case HAS_REF: // exist name, has ref + if (var_ref){ + refs[i] = var_ref; + } + break; + default: + ; // ASSERT(FALSE); + } + return; + } + + UBool is_complete(){ + int n = names.content_size(); + for (int i=0; i<n; ++i){ + if (refs[i] == NULL){ + return FALSE; + } + } + return TRUE; + } + + void reset(){ + names.reset(); + name_buffer.reset(); + + // release memory here + int s = refs.content_size(); + for (int i=0; i < s; i++){ + delete refs[i]; // TOFIX: point alias/recursion problem + } + refs.reset(); + } + + ~SymbolTable(){ + reset(); + } +}; + + +/* +// Document of class Escaper +// +// ATTENTION: +// From http://icu-project.org/userguide/Collate_Customization.html. +// We get the precedence of escape/quote operations +// +// (highest) 1. backslash \ +// 2. two single quotes '' +// 3. quoting ' ' +// +// ICU Collation should accept following as the same string. +// +// 1) 'ab'c _ +// 2) a\bc \ +// 3) a'b'\c |- They are equal. +// 4) abc _/ +// +// From "two single quotes", we have following deductions +// D1. empty quoting is illgal. (obviously) +// D2. no contact operation between two quotings +// '.''.' is not .. it is .'. +// D3. "two single quotes" cannot contact two quoting simultaneously +// '..''''.' is not ..'. it is ..''. +// NOTICE: +// "two single quotes" can contact before one quoting +// '''.' is '. +// "two single quotes" can literally contact after one quoting +// But, from syntax, it's one quoting including a "two single quotes" +// '.''' is .' +// D4. "two single quotes" cannot solely be included in quoting +// '''' is not ' it is '' +// NOTICE: These are legal +// '.''.' is .'. +// '.''' is .' +// +// dicision +// /\ +// /__\ +// output buffer input buffer +// +// To make our dicision (within an atom operation) without caring input and output buffer, +// following calling pattern (within an atom operation) shall be avoided +// +// P1 open_quoting() then close_quoting() (direct violation) D1 +// P2 close_quoting() then open_quoting() (direct violation) D2 +// P3 empty open_quoting() (indirect violation) D1, D4 +// P4 empty close_quoting() (indirect violation) D2, D3 +// P5 open_quoting() then two single quotes (indirect violation) D4 +// P6 close_quoting() then two single quotes (indirect violation) D3 +// +// two single quotes escaping will not open_ or close_ quoting() +// The choice will not lose some quoing forms. +// +// For open_quoting(), +// we may get this form quoting ''' P5 +// It may raise a bug ''''x +// If we expect +// '''.' let the next char open the quoting +// '.''.' the quoting is already opened by preceding char +// +// For close_quoting() +// we will get this form quoting '.''' P6 +// It may raise a bug '.''''.' +// If we expect +// '.'''\. let the next char close the quoting +// '.''''.' the expectation is wrong! using '.'\''.' instead +// +// It's a hard work to re-adjust generation opportunity for various escaping form. +// We just simply ignore it. +*/ +class Escaper{ +public: + enum CHOICE {YES, NO, RAND}; + enum ESCAPE_FORM {BSLASH_ONLY, QUOTE_ONLY, QUOTE_AND_BSLAH, RAND_ESC}; +private: + class Bool{ // A wrapper class for CHOICE, to auto adapter UBool class + private: + const CHOICE tag; + public: + Bool(CHOICE flag=RAND):tag(flag){} + operator UBool() { // conversion operator + return tag == RAND ? rand()%2 : tag == YES; + //if (tag == RAND){ + // return rand()%2 == 1; + //} else { + // return tag == YES ? TRUE : FALSE; + //} + } + }; +public: + Escaper(CHOICE escapeLiteral = RAND, + CHOICE twoQuotesEscape = RAND, + ESCAPE_FORM escapeForm = RAND_ESC): + escape_form(escapeForm), + escape_literal(escapeLiteral), + two_quotes_escape(twoQuotesEscape), + is_quoting(FALSE){} +private: + Buffer_char str; + ESCAPE_FORM escape_form; + Bool escape_literal; + Bool two_quotes_escape; + UBool quote_escape; + UBool bslash_escape; + UBool is_quoting; + + void set_options(){ + ESCAPE_FORM t = escape_form == RAND_ESC ? (ESCAPE_FORM) (rand()%3) : escape_form; + switch (t){ + case BSLASH_ONLY : + bslash_escape = TRUE; quote_escape = FALSE; break; + case QUOTE_ONLY: + bslash_escape = FALSE;quote_escape = TRUE; break; + case QUOTE_AND_BSLAH: + bslash_escape = TRUE; quote_escape = TRUE; break; + default: + ;// error + } + } + + void reset(){ + str.reset(); + is_quoting = FALSE; + } + + inline void open_quoting(){ + if(is_quoting){ + // do nothing + } else { + str.append('\''); + is_quoting = TRUE; + } + } + inline void close_quoting(){ + if(is_quoting){ + str.append('\''); + is_quoting = FALSE; + } else { + // do nothing + } + } + + // str [in] null-terminated c-string + void append(const char * strToAppend){ + for(;*strToAppend != 0; strToAppend++){ + append(*strToAppend); + } + } + + inline void append(const char c){ + set_options(); + + if (c == '\\'){ + quote_escape ? open_quoting() : close_quoting(); + //bslash_escape always true here + str.append('\\'); + str.append('\\'); + } else if (c == '\''){ + if (two_quotes_escape){ // quoted using two single quotes + // See documents in anonymous.design + str.append('\''); + str.append('\''); + } else{ + quote_escape ? open_quoting() : close_quoting(); + //bslash_escape always true here + str.append('\\'); + str.append('\''); + } + } else if (isSpecialAsciiChar(c) || isWhiteSpace(c)){ + quote_escape ? open_quoting() : close_quoting(); + if (bslash_escape) str.append('\\'); + str.append(c); + } else { //if (isAlphabet(c) || isDigit(c) || TRUE){ // treat others as literal + if (escape_literal){ + quote_escape ? open_quoting() : close_quoting(); + if (bslash_escape) str.append('\\'); + str.append(c); + } else { + close_quoting(); + str.append(c); + } + } + } + +public: + // Return a null-terminate c-string. The buffer is owned by callee. + char * operator()(const char * literal /*c-string*/){ + str.reset(); + for(;*literal != 0; literal++){ + append(*literal); + } + close_quoting(); // P4 exception, to close whole quoting + return str; + } +}; + +class WeightedRand{ +// Return a random number in [0, size) +// Every number has different chance (aka weight) to be selected. +private: + Buffer_int weights; + double total; + WeightedRand(const WeightedRand &); + WeightedRand & operator = (const WeightedRand &); +public: + WeightedRand(Buffer_int * weight_list = NULL, int size = 0){ + if ( weight_list == NULL){ + for (int i=0; i<size; ++i) weights.append(DEFAULT_WEIGHT); + } else { + int s = weight_list->content_size(); + if (s < size){ + weights.append_array( (*weight_list),s); + for (int i=s; i<size; ++i) weights.append(DEFAULT_WEIGHT); + } else { // s >= size + weights.append_array( (*weight_list),size); + } + } + total = 0; + int c = weights.content_size(); + for (int i=0; i<c; ++i){ + total += weights[i]; + } + } + + void append(int weight){ + weights.append(weight); + total += weight; + } + + // Give a random number with the consideration of weight. + // Every random number is associated with a weight. + // It identifies the chance to be selected, + // larger weight has more chance to be selected. + // + // + // ______________________ every slot has equal chance + // + // [____][_][___][______] each item has different slots, hence different chance + // + // + // The algorithms to generate the number is illustrated by preceding figure. + // First, a slot is selected by rand(). Then we translate the slot to corresponding item. + // + int next(){ + // get a random in [0,1] + double reference_mark = (double)rand() / (double)RAND_MAX; + + // get the slot's index, 0 <= mark <= total; + double mark = total * reference_mark; + + // translate the slot to corresponding item + int i=0; + for (;;){ + mark -= weights[i]; // 0 <= mark <= total + if (mark <= 0) + break; + i++; + } + return i; + } +}; + +/////////////////////////////////////////////////////////// +// +// The parser result nodes +// + +class Literal : public Pick { +public: + virtual const char* next(){ + return str; + } + Literal(const char * s /*c-string*/){ + str.append_array(s, strlen(s) + 1); + } +private: + Buffer_char str; //null-terminated c-string +}; + +class Variable : public Pick { +public: + Variable(SymbolTable * symbols, const char * varName, Pick * varRef = NULL){ + this->var_name.append_array(varName, strlen(varName) + 1); + if ((symbol_table = symbols)){ + symbol_table->put(varName, varRef); + } + } + + operator const char *(){ + return var_name; + } + + virtual const char* next(){ + if (symbol_table){ + Pick * var_ref = NULL; + symbol_table->find(var_name, &var_ref); + if (var_ref) { + return var_ref->next(); + } + } + return ""; // dumb string + } +private: + Buffer_char var_name; + SymbolTable * symbol_table; +}; + +class Quote : public Pick{ +public: + Quote(Pick & base):item(base),e(Escaper::NO, Escaper::NO, Escaper::BSLASH_ONLY){ + } + virtual const char* next(){ + return e(item.next()); + } +private: + Pick & item; + Buffer_char str; + Escaper e; +}; + + +class Morph : public Pick{ +/* +The difference between morph and an arbitrary random string is that +a morph changes slowly. When we build collation rules, for example, +it is a much better test if the strings we use are all in the same +'neighborhood'; they share many common characters. +*/ +public: + Morph(Pick & base):item(base){} + + virtual const char* next(){ + current.reset(); + const char * s = item.next(); + current.append_array(s, strlen(s) + 1); + if (last.content_size() == 0) { + str.reset(); + last.reset(); + str.append_array(current, current.content_size()); + last.append_array(current, current.content_size()); + } else { + morph(); + } + return str; + } +private: + Pick & item; + Buffer_char str; + Buffer_char last; + Buffer_char current; + + char * p_last; + char * p_curr; + + void copy_curr(){ + if (*p_curr) { + str.append(*p_curr); + p_curr++; + } + } + + void copy_last(){ + if (*p_last) { + str.append(*p_last); + p_last++; + } + } + + // copy 0, 1, or 2 character(s) to str + void copy(){ + static WeightedRand wr(& Buffer_int().append(DEFAULT_WEIGHT * 10), 5); + + switch (wr.next()){ + case 0: // copy last -- has 10 times chance than others + copy_last(); + break; + case 1: // copy both + copy_curr(); + copy_last(); + break; + case 2: // copy both + copy_last(); + copy_curr(); + break; + case 3: + copy_curr(); + break; + case 4: // copy nothing + break; + default: + // ASSERT(FALSE); + ; + } + } + + void morph(void){ + int min = strlen(last); + int max = strlen(current); + if (min > max){ + int temp = min; + min = max; + max = temp; + } + + int len = min + rand()%(max - min + 1); // min + [0, diff] + p_curr = current; + p_last = last; + str.reset(); + + for (; str.content_size()<len && *p_curr && *p_last;){ + copy(); // copy 0, 1, or 2 character(s) to str + } + + if (str.content_size() == len) { + str.append(0); + final(); + return; + } + + if (str.content_size() > len) { // if the last copy copied two characters + str[len]=0; + final(); + return; + } + + // str.content_size() < len + if (*p_last) { + for (; str.content_size() < len; copy_last()); + } else if (*p_curr){ + for (; str.content_size() < len; copy_curr()); + } + + int last_len = last.content_size(); + for (;str.content_size() < len;){ + str.append(last[rand()%last_len]); + } + str.append(0); + final(); + } + + void final(){ + last.reset(); + last.append_array(current, current.content_size()); + } +}; + +class Sequence : public Pick { +public: + virtual const char* next(){ + str.reset(); + int s = items.content_size(); + for(int i=0; i < s; i++){ + const char * t = items[i]->next(); + str.append_array(t, strlen(t)); + } + str.append(0); // terminal null + return str; + } + + void append (Pick * node){ + items.append(node); + } + + virtual ~Sequence(){ + int s = items.content_size(); + for(int i=0; i < s; i++){ + //How can assure the item is got from heap? + //Let's assume it. + delete items[i]; // TOFIX: point alias/recursion problem + items[i] = NULL; + } + } +private: + Buffer_pPick items; + Buffer_char str; //null-terminated c-string +}; + +class Repeat : public Pick { +private: + Pick * item; + Buffer_char str; + WeightedRand wr; + int min; + int max; + int select_a_count(){ + return min + wr.next(); + } +public: + virtual const char* next(){ + str.reset(); + int c = select_a_count(); + for(int i=0; i< c; i++){ + const char * t = item->next(); + str.append_array(t, strlen(t)); + } + str.append(0); + return str; + } + + Repeat(Pick * base, int minCount =0, int maxCount = 1, Buffer_int * weights = NULL): + wr(weights, maxCount-minCount +1) { + this->item = base; + this->min = minCount; + this->max = maxCount; + } + virtual ~Repeat(){ + delete item; // TOFIX: point alias/recursion problem + item = NULL; + } +}; + + +class Alternation : public Pick { +public: + virtual const char* next(){ + str.reset(); + int i = wr.next(); + const char * t = items[i]->next(); + str.append_array(t, strlen(t) + 1); + return str; + } + virtual ~Alternation(){ + int s = items.content_size(); + for(int i=0; i < s; i++){ + delete items[i]; // TOFIX: point alias/recursion problem + items[i] = NULL; + } + } + + Alternation & append (Pick * node, int weight = DEFAULT_WEIGHT){ + items.append(node); + wr.append(weight); + return *this; + } +private: + Buffer_pPick items; + Buffer_char str; // null-terminated c-string + WeightedRand wr; +}; + +/////////////////////////////////////////////////////////// +// +// The parser +// + +enum TokenType {STRING, VAR, NUMBER, STREAM_END, ERROR, QUESTION, STAR, PLUS, LBRACE, RBRACE, LPAR, RPAR, SEMI, EQ, COMMA, BAR, AT, WAVE, PERCENT}; + +class Scanner{ +friend int DumpScanner(Scanner & s, UBool dumb); +private: + const char * source; + const char * working; + const char * history; // for debug + enum StateType {START, IN_NUM, IN_VAR_FIRST, IN_VAR, IN_QUOTE, IN_QUOTE_BSLASH, IN_BSLASH, IN_STRING, DONE}; + StateType state; + void terminated(TokenType t){ + working--; // return the peeked character + tokenType = t; + token.append(0); // close buffer + state = DONE; + } +public: + // the buffer of "source" is owned by caller + Scanner(const char *src/*[in] c-string*/ = NULL):source(src){ + working = src; + history = working; + state = DONE; + tokenType = ERROR; + } + + //void setSource(const char *const src /*[in] c-string*/){ + // *(&const_cast<const char *>(source)) = src; + //} + + Buffer_char token; + TokenType tokenType; + + TokenType getNextToken(){ + token.reset(); + state = START; + history = working; // for debug + while (state != DONE){ + char c = *working++; + if (c == 0 && state != START){//avoid buffer overflow. for IN_QUOE, IN_ESCAPE + terminated(ERROR); + break; // while + } + switch(state){ + case START: + tokenType = ERROR; + switch(c){ + case '?' : tokenType = QUESTION; break; + case '*' : tokenType = STAR; break; + case '+' : tokenType = PLUS; break; + case '{' : tokenType = LBRACE; break; + case '}' : tokenType = RBRACE; break; + case '(' : tokenType = LPAR; break; + case ')' : tokenType = RPAR; break; + case ';' : tokenType = SEMI; break; + case '=' : tokenType = EQ; break; + case ',' : tokenType = COMMA; break; + case '|' : tokenType = BAR; break; + case '@' : tokenType = AT; break; + case '~' : tokenType = WAVE; break; + case '%' : tokenType = PERCENT; break; + case 0 : tokenType = STREAM_END; working-- /*avoid buffer overflow*/; break; + } + if (tokenType != ERROR){ + token.append(c); + token.append(0); + state = DONE; + break; // START + } + switch(c){ + case '$' : state = IN_VAR_FIRST; token.append(c); break; + case '\'' : state = IN_QUOTE; break; + case '\\' : state = IN_BSLASH; break; + default: + if (isWhiteSpace(c)){ // state = START; //do nothing + } else if (isDigit(c)){ state = IN_NUM; token.append(c); + } else if (isAlphabet(c)){ state = IN_STRING; token.append(c); + } else {terminated(ERROR);} + } + break;//START + case IN_NUM: + if (isDigit(c)){ + token.append(c); + } else { + terminated(NUMBER); + } + break;//IN_NUM + case IN_VAR_FIRST: + if (isAlphabet(c)){ + token.append(c); + state = IN_VAR; + } else { + terminated(ERROR); + } + break; // IN_VAR_FISRT + case IN_VAR: + if (isAlphabet(c) || isDigit(c)){ + token.append(c); + } else { + terminated(VAR); + } + break;//IN_VAR + case IN_STRING: + // About the scanner's behavior for STRING, AT, and ESCAPE: + // All of them can be contacted with each other. + // This means the scanner will eat up as much as possible strings + // (STRING, AT, and ESCAPE) at one time, with no regard of their + // combining sequence. + // + if (c == '\''){ + state = IN_QUOTE; // the first time we see single quote + } else if (c =='\\'){ // back slash character + state = IN_BSLASH; + } else if (isAlphabet(c) || isDigit(c)){ + token.append(c); + } else{ + terminated(STRING); + } + break;//IN_STRING + case IN_QUOTE: + if (c == '\''){ // the second time we see single quote + state = IN_STRING; // see document in IN_STRING + } else if ( c== '\\') { // backslah escape in quote + state = IN_QUOTE_BSLASH; + } else { + token.append(c); // eat up everything, includes back slash + } + break;//IN_QUOTE + case IN_QUOTE_BSLASH: + case IN_BSLASH: + switch (c){ + case 'n' : token.append('\n'); break; + case 'r' : token.append('\r'); break; + case 't' : token.append('\t'); break; + case '\'' : token.append('\''); break; + case '\\' : token.append('\\'); break; + default: token.append(c); // unknown escaping, treat it as literal + } + if (state == IN_BSLASH){ + state = IN_STRING; // see document in IN_STRING + } else { // state == IN_QUOTE_BSLASH + state = IN_QUOTE; + } + break;//IN_BSLASH + case DONE: /* should never happen */ + default: + working--; + tokenType = ERROR; + state = DONE; + break; + }//switch(state) + }//while (state != DONE) + + return tokenType; + } +};//class Scanner + +class Parser{ +friend UBool TestParser(); +friend class TestParserT; +friend class LanguageGenerator_impl; +private: + Scanner s; + TokenType & token; + int min_max; // for the evil infinite + + UBool match(TokenType expected){ + if (token == expected) { + token = s.getNextToken(); + return TRUE; + } else { + //s.dumpCurrentPoint(); + return FALSE; + } + } + + UBool weight(int & value){ + if (token == NUMBER){ + int temp = atoi(s.token); + match(NUMBER); + if (match(PERCENT)){ + value = temp; + return TRUE; + } + } + return FALSE; + } + + UBool repeat (Pick* &node /*in,out*/){ + if (node == NULL) return FALSE; + + int count = -2; + int min = -2; + int max = -2; + UBool question = FALSE; + switch (token){ + case QUESTION: + match(QUESTION); + min = 0; + max = 1; + count = 2; + question = TRUE; + break; + case STAR: + match(STAR); + min = 0; + max = -1; + count = -1; + break; + case PLUS: + match(PLUS); + min = 1; + max = -1; + count = -1; + break; + case LBRACE: + match(LBRACE); + if (token != NUMBER){ + return FALSE; + }else { + min = atoi(s.token); + match(NUMBER); + if (token == RBRACE){ + match(RBRACE); + max = min; + count = 1; + } else if (token == COMMA) { + match(COMMA); + if (token == RBRACE){ + match(RBRACE); + max = -1; + count = -1; + } else if (token == NUMBER) { + max = atoi(s.token); + match(NUMBER); + count = max - min + 1; + if (!match(RBRACE)) { + return FALSE; + } + } else { + return FALSE; + } + } else { + return FALSE; + } + } + break; + default: + return FALSE; + } + + if (count == -2 || min == -2 || max == -2){ + //ASSERT(FALSE); + return FALSE; + } + + // eat up following weights + Buffer_int weights; + int w; + while (weight(w)){ + weights.append(w); + } + + // for the evil infinite + min_max = min_max > min ? min_max : min; + min_max = min_max > max ? min_max : max; + if (min_max > PSEUDO_INFINIT){ + return FALSE; // PSEUDO_INFINIT is less than the real maximum + } + if (max == -1){ // the evil infinite + max = PSEUDO_INFINIT; + } + // for the strange question mark + if (question && weights.content_size() > 0){ + Buffer_int w2; + w2.append(DEFAULT_WEIGHT - weights[0]).append(weights[0]); + node = new Repeat(node,min,max,&w2); + return TRUE; + } + node = new Repeat(node,min,max,&weights); + return TRUE; + } + + UBool core(Pick* &node /*out*/){ + if (node != NULL) return FALSE; //assert node == NULL + + switch(token){ + case LPAR: + match(LPAR); + if(defination(node) && match(RPAR)){ + return TRUE; + } + return FALSE; + case VAR: + node = new Variable(&symbols, s.token); + match(VAR); + return TRUE; + case STRING: + node = new Literal(s.token); + match(STRING); + return TRUE; + default: + return FALSE; + } + } + UBool modified(Pick* &node /*out*/){ + if (node != NULL) return FALSE; //assert node == NULL + + if (!core(node)) { + return FALSE; + } + + for (;;){ + switch(token){ + case WAVE: + match(WAVE); + node = new Morph(*node); + break; + case AT: + match(AT); + node = new Quote(*node); + break; + case QUESTION: + case STAR: + case PLUS: + case LBRACE: + if (!repeat(node)) return FALSE; + break; + case SEMI: // rule definiation closed + case RPAR: // within parenthesis (core closed) + case BAR: // in alternation + case NUMBER: // in alternation, with weight + case LPAR: // in sequence + case VAR: // in sequence + case STRING: // in sequence + return TRUE; + default: + return FALSE; + } + } + } + + + UBool sequence_list(Pick* &node /*in,out*/){ + if (node == NULL) return FALSE; // assert node != NULL + + Sequence* seq = new Sequence(); + Pick * n = node; + + while (token == VAR || token == STRING || token == LPAR){ + seq->append(n); + n = NULL; + if (modified(n)){ + // go on + } else { + goto FAIL; + } + } + + if (token == SEMI || token == RPAR || token == BAR){ + seq->append(n); + node = seq; + return TRUE; + } +FAIL: + delete seq; + return FALSE; + + } + + UBool sequence(Pick* &node /*out*/){ + if (node != NULL) return FALSE; //assert node == NULL + + if (!modified(node)) { + return FALSE; + } + + if (token == VAR || token == STRING || token == LPAR){ + return sequence_list(node); + } else { + return TRUE; // just a modified + } + } + + UBool alternation_list(Pick* &node /*in,out*/){ + if (node == NULL) return FALSE; // assert node != NULL + + Alternation * alt = new Alternation(); + Pick * n = node; + int w = DEFAULT_WEIGHT; + + while (token == NUMBER || token == BAR){ + if(token == NUMBER) { + if (weight(w)){ + if (token == BAR){ + // the middle item, go on + } else { + // the last item or encounter error + break; //while + } + } else { + goto FAIL; + } + } // else token == BAR + match(BAR); + alt->append(n,w); + + n = NULL; + w = DEFAULT_WEIGHT; + if (sequence(n)){ + // go on + } else { + goto FAIL; + } + } + + if (token == SEMI || token == RPAR) { + alt->append(n,w); + node = alt; + return TRUE; + } +FAIL: + delete alt; + return FALSE; + } + + UBool alternation(Pick* &node /*out*/){ + if (node != NULL) return FALSE; //assert node == NULL + + // 'sequence' has higher precedence than 'alternation' + if (!sequence(node)){ + return FALSE; + } + + if (token == BAR || token == NUMBER){ // find a real alternation1, create it. + return alternation_list(node); + } else { + return TRUE; // just a sequence_old + } + } + + + UBool defination(Pick* &node /*out*/){ + if (node != NULL) return FALSE; //assert node == NULL + return alternation(node); + } + + UBool rule(){ + if (token == VAR){ + Buffer_char name; + name.append_array(s.token, strlen(s.token) + 1); + match(VAR); + + if (match(EQ)){ + Pick * t = NULL; + if(defination(t)){ + symbols.put(name, t); + return match(SEMI); + } + } + } + return FALSE; + } +public: + UBool rules(){ + symbols.reset(); + token = s.getNextToken(); + while (rule()){ + } + if (token == STREAM_END){ + return TRUE; + } else { + //s.dumpCurrentPoint(); + return FALSE; + } + } + +public: + SymbolTable symbols; + + Parser(const char *const source):s(source), token(s.tokenType){ + min_max = -2; + } + UBool parse(){ + return rules(); + } + +}; // class Parser + + +/////////////////////////////////////////////////////////// +// +// +// + +int DumpScanner(Scanner & s, UBool dump = TRUE){ + int len = strlen(s.source); + int error_start_offset = s.history - s.source; + if (dump){ + printf("\n=================== DumpScanner ================\n"); + fwrite(s.source, len, 1, stdout); + printf("\n-----parsed-------------------------------------\n"); + fwrite(s.source, s.history - s.source, 1, stdout); + printf("\n-----current------------------------------------\n"); + fwrite(s.history, s.working - s.history, 1, stdout); + printf("\n-----unparsed-----------------------------------\n"); + fwrite(s.working, (s.source + len - s.working), 1, stdout); + printf("\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n"); + } + return error_start_offset; +} + +class LanguageGenerator_impl{ +public: + LanguageGenerator_impl(const char *const bnf_definition, const char *const top_node) + :par(bnf_definition), top_node_name(top_node){ + srand((unsigned)time( NULL )); + } + + LanguageGenerator::PARSE_RESULT parseBNF(UBool debug = TRUE){ + if (par.parse()){ + if (par.symbols.find(top_node_name, &top_node_ref) == SymbolTable::HAS_REF) { + if (par.symbols.is_complete()) { + return LanguageGenerator::OK; + } else { + if (debug) printf("The bnf definition is incomplete.\n"); + return LanguageGenerator::INCOMPLETE; + } + } else { + if (debug) printf("No top node is found.\n"); + return LanguageGenerator::NO_TOP_NODE; + } + } else { + if(debug) { + printf("The bnf definition is wrong\n"); + DumpScanner(par.s, TRUE); + } + return LanguageGenerator::BNF_DEF_WRONG; + } + } + const char * next(){ + return top_node_ref->next(); + } + +private: + Parser par; + const char *const top_node_name; + Pick * top_node_ref; +}; + +LanguageGenerator::LanguageGenerator():lang_gen(NULL){ +} + +LanguageGenerator::~LanguageGenerator(){ + delete lang_gen; +} + +LanguageGenerator::PARSE_RESULT LanguageGenerator::parseBNF(const char *const bnf_definition /*in*/, const char *const top_node/*in*/, UBool debug){ + if (lang_gen){ + delete lang_gen; + } + lang_gen = new LanguageGenerator_impl(bnf_definition, top_node); + PARSE_RESULT r = lang_gen->parseBNF(debug); + if (r != OK){ + delete lang_gen; + lang_gen = NULL; + return r; + } else { + return r; + } +} +const char *LanguageGenerator::next(){ // Return a null-terminated c-string. The buffer is owned by callee. + if (lang_gen){ + return lang_gen->next(); + }else { + return ""; + } +} + +/////////////////////////////////////////////////////////// +// +// The test code for WBNF +// + +#define CALL(fun) \ + if (fun()){ \ + printf("Pass: " #fun "\n");\ + } else { \ + printf("FAILED: !!! " #fun " !!!\n"); \ + } + +#define DUMP_R(fun, var, times) \ + {printf("\n========= " #fun " =============\n"); \ + for (int i=0; i<times; i++) { \ + const char * t = var.next();\ + fwrite(t,strlen(t),1,stdout); \ + printf("\n"); \ + } \ + printf("^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n");} + + + +#if TEST_WBNF_TEST +static UBool TestQuote(){ + const char *const str = "This ' A !,z| qq [] .new\tline"; + //const char *const str_r = "This \\' A '!,'z'|' qq '[]' '.'new\tline"; + //// + //// :( we must quote our string to following C syntax + //// cannot type the literal here, it makes our code rather human unreadable + //// very very unconformable! + //// + ///* + //*/ + + //const char *const s1 = "ab'c"; + //const char (* s1_r1) [] = { "ab''c", // ab''c + // "ab\\'c", // ab\'c + // };// + ///* + // . '.' \. + // .. \.\. '.'\. '.'\. '..' // '.''.' wrong + //*/ + + //const char *const s2 = "a..'.b"; // a..'.b + //const char (*s2_r) [] = { "a'..''.'b" // a'..''.'b + // ,"a'..\\'.'b" // a'..\'.'b + // ,"a'..'\\''.'b" // a'..'\''.'b + // };// + + //const char *const s3 = "a..\\.b"; // a..\.b + //const char (*s3_r) [] = { "a'..\\\\.'b" // a'..\\.'b + // ,"a'..'\\\\'.'b" // a'..'\\'.'b + // };// + + // // no catact operation, no choice, must be compact + + srand((unsigned)time( NULL )); + + //Escaper l(Escaper::NO, Escaper::NO, Escaper::RAND_ESC); + Pick *p = new Literal(str); + Quote q(*p); + + DUMP_R(TestQuote, (*p), 1); + DUMP_R(TestQuote, q, 20); + return FALSE; +} +static UBool TestLiteral(){ + const char * s = "test string99."; + Literal n(s); + const char * r = n.next(); + return strcmp(s,r) == 0; +} + +static UBool TestSequence(){ + Sequence seq; + seq.append(new Literal("abc ")); + seq.append(new Literal(", s")); + + return strcmp(seq.next(), "abc , s") == 0; +} +static UBool TestAlternation(){ + srand((unsigned)time( NULL )); + Alternation alt; + alt.append(new Literal("aaa_10%"),10); + alt.append(new Literal("bbb_0%"),0); + alt.append(new Literal("ccc_10%"),10); + alt.append(new Literal("ddddddd_50%"),50); + + DUMP_R(TestAlternation, alt, 50); + + return FALSE; +} + +static UBool TestBuffer(){ + Buffer_int t; + t.append(1).append(0).append(5); + int s = t.content_size(); + for (int i=0; i<s; ++i){ + printf("%d\n", t[i]); + } + return FALSE; +} + +static UBool TestWeightedRand(){ + srand((unsigned)time( NULL )); + Buffer_int t; + t.append(1).append(0).append(5); + WeightedRand wr(&Buffer_int().append(10).append(0).append(50),4); +// WeightedRand wr(&t,3); + for (int i=0; i< 50; ++i){ + printf("%d\n", wr.next()); + } + return FALSE; +} + +static UBool TestRepeat(){ + srand((unsigned)time( NULL )); + Repeat rep(new Literal("aaa1-5 "), 1, 5); + DUMP_R(TestRepeat, rep, 50); + + Repeat r2(new Literal("b{1,3}1%0%5% "), 1, 3, &Buffer_int().append(1).append(0).append(5)); + DUMP_R(TestRepeat, r2, 50); + + Repeat r3(new Literal("aaa5-5 "), 5, 5); + DUMP_R(TestRepeat, r3, 50); + + return FALSE; +} + +static UBool TestVariable(){ + SymbolTable tab; + Pick * value = new Literal("string1"); + Variable var1(&tab, "x", value); + + Variable var2(&tab, "y"); +// tab.put(var2, value); // TOFIX: point alias/recursion problem + Pick * value2 = new Literal("string2"); + tab.put(var2, value2); + + Pick * value3 = new Literal("string3"); + Variable var3(&tab, "z"); + tab.put("z", value3); + + UBool pass; + pass = strcmp(var1.next(), value->next()) == 0; + pass = pass && strcmp(var2.next(), value2->next()) == 0; + pass = pass && strcmp(var3.next(), value3->next()) == 0; + return pass; +} + +static UBool TestSymbolTable(){ + Literal * n1 = new Literal("string1"); + Literal * n2 = new Literal("string2"); + SymbolTable t; + t.put("abc", n1); + t.put("$aaa", n2); +// t.put("alias", n1); // TOFIX: point alias/recursion problem + t.put("bbb"); + + UBool pass; + pass = t.find(NULL) == SymbolTable::EMPTY; + pass = pass && t.find("ccc") == SymbolTable::NO_VAR; + pass = pass && t.find("bbb") == SymbolTable::NO_REF; + pass = pass && t.find("abc") == SymbolTable::HAS_REF; + pass = pass && t.find("$aaa") == SymbolTable::HAS_REF; + + t.reset(); + pass = pass && t.find("abc") == SymbolTable::NO_VAR; + return pass; +} + + +static UBool TestScanner(void){ + //const char str1[] = "$root = $command{0,5} $reset $mostRules{1,20};"; + //const char str1_r[][20] = {"$root", "=", "$command", "{", "0", ",", "5", "}", + // "$reset", "$mostRules", "{", "1", ",", "20", "}", ";"}; + + const char str2[] = "$p2 =(\\\\ $s $string $s)? 25%;"; + const char str2_r[][20] = {"$p2", "=", "(", "\\", "$s", "$string", "$s", ")", "?", "25", "%", ";"}; + + const char *str = str2; + const char (*str_r)[20] = str2_r; + int tokenNum = sizeof(str2_r)/sizeof(char[20]); + + Scanner t(str); + UBool pass = TRUE; + t.getNextToken(); + int i = 0; + while (pass){ + if (t.tokenType == STREAM_END){ + pass = pass? i == tokenNum : FALSE; + break;//while + } else if (t.tokenType == ERROR){ + pass = FALSE; + break;//while + } else { + pass = strcmp( &(t.token[0]), str_r[i++]) == 0; + t.getNextToken(); + } + } + + //const char ts[] = "$commandList = '['" + //" ( alternate ' ' $alternateOptions" + //" | backwards ' 2'" + //" | normalization ' ' $onoff " + //" | caseLevel ' ' $onoff " + //" | hiraganaQ ' ' $onoff" + //" | caseFirst ' ' $caseFirstOptions" + //" | strength ' ' $strengthOptions" + //" ) ']';" ; + + //Scanner t2(ts); + //pass = TRUE; + //do { + // t2.getNextToken(); + // if (t2.tokenType == ERROR){ + // DumpScanner(t2); + // return FALSE; + // } + //}while (t.tokenType != STREAM_END); + + return pass; +} + +class TestParserT { +public: +UBool operator () (const char *const str, const int exp_error_offset = -1, const UBool dump = TRUE){ + Parser par(str); + if (par.rules()){ + if ( exp_error_offset == -1){ + return TRUE; + }else { + DumpScanner(par.s,dump); + return FALSE; + } + }else { + return DumpScanner(par.s, dump) == exp_error_offset; + } +} +}; + +UBool TestParser(){ + TestParserT test; + + UBool pass = TRUE; + pass = pass && test ("$s = ' ' ? 50%;"); + pass = pass && test("$x = ($var {1,2}) 3%;"); // legal + pass = pass && test("$x = $var {1,2} 3% | b 4%;"); // legal + pass = pass && test("$x = $var {1,2} 3%;"); // legal + pass = pass && test("$m = $c ? 2% 4% | $r 5% | $n 25%;"); // legal + pass = pass && test("$a = b ? 2% | c 5%;"); // legal + pass = pass && test("$x = A B 5% C 10% | D;", 8, FALSE); // illegal 5% + pass = pass && test("$x = aa 45% | bb 5% cc;", 19, FALSE);// illegal cc + pass = pass && test("$x = (b 5%) (c 6%);"); // legal + pass = pass && test("$x = (b 5%) c 6%;", 13, FALSE); // illegal 6% + pass = pass && test("$x = b 5% (c 6%);", 9, FALSE); // illegal (c 6%) + pass = pass && test("$x = b 5% c 6%;", 9, FALSE); // illegal c 6% + pass = pass && test("$x = b 5%;"); // legal + pass = pass && test("$x = aa 45% | bb 5% cc;", 19, FALSE);// illegal cc + pass = pass && test("$x = a | b | c 4% | d 5%;"); // legal + pass = pass && test("$s = ' ' ? 50% abc;"); // legal + pass = pass && test("$s = a | c d | e f;"); // legal + pass = pass && test( "$z = q 0% | p 1% | r 100%;"); // legal How to check parsed tree?? + + pass = pass && test("$s = ' ' ? 50%;"); + pass = pass && test("$relationList = '<' | '<<' | ';' | '<<<' | ',' | '=';"); + pass = pass && test("$p1 = ($string $s '|' $s)? 25%;"); + pass = pass && test("$p2 = (\\\\ $s $string $s)? 25%;"); + pass = pass && test("$rel2 = $p1 $string $s $p2;"); + pass = pass && test("$relation = $relationList $s ($rel1 | $rel2) $crlf;"); + pass = pass && test("$command = $commandList $crlf;"); + pass = pass && test("$reset = '&' $s ($beforeList $s)? 10% ($positionList 100% | $string 10%) $crlf;"); + pass = pass && test("$mostRules = $command 1% | $reset 5% | $relation 25%;"); + pass = pass && test("$root = $command{0,5} $reset $mostRules{1,20};"); + + const char collationBNF[] = + "$s = ' '? 50%;" + "$crlf = '\r\n';" + + "$alternateOptions = non'-'ignorable | shifted;" + "$onoff = on | off;" + "$caseFirstOptions = off | upper | lower;" + "$strengthOptions = '1' | '2' | '3' | '4' | 'I';" + "$commandList = '['" + " ( alternate ' ' $alternateOptions" + " | backwards ' 2'" + " | normalization ' ' $onoff " + " | caseLevel ' ' $onoff " + " | hiraganaQ ' ' $onoff" + " | caseFirst ' ' $caseFirstOptions" + " | strength ' ' $strengthOptions" + " ) ']';" + "$command = $commandList $crlf;" + + "$ignorableTypes = (tertiary | secondary | primary) ' ' ignorable;" + "$allTypes = variable | regular | implicit | trailing | $ignorableTypes;" + "$positionList = '[' (first | last) ' ' $allTypes ']';" + + "$beforeList = '[before ' ('1' | '2' | '3') ']';" + + "$relationList = (" + " '<'" + " | '<<'" + " | ';'" + " | '<<<'" + " | ','" + " | '='" + ");" + "$string = $magic;" + "$rel1 = '[variable top]' $s;" + "$p1 = ($string $s '|' $s)? 25%;" + "$p2 = (\\\\ $s $string $s)? 25%;" + "$rel2 = $p1 $string $s $p2;" + "$relation = $relationList $s ($rel1 | $rel2) $crlf;" + + "$reset = '&' $s ($beforeList $s)? 10% ($positionList 1% | $string 10%) $crlf;" + "$mostRules = $command 1% | $reset 5% | $relation 25%;" + "$root = $command{0,5} $reset $mostRules{1,20};" + ; + + pass = pass && test(collationBNF); + + + return pass; +} + +static UBool TestMorph(){ + srand((unsigned)time( NULL )); + + Alternation * alt = new Alternation(); + + (*alt) + .append(new Literal("a")).append(new Literal("b")).append(new Literal("c")) + .append(new Literal("d")).append(new Literal("e")).append(new Literal("f")) + .append(new Literal("g")).append(new Literal("h")).append(new Literal("i")) + .append(new Literal("j")).append(new Literal("k")).append(new Literal("l")) + .append(new Literal("m")).append(new Literal("n")).append(new Literal("o")) + ; + + Repeat * rep = new Repeat( alt ,5,5 ); + Morph m( *rep); + +// DUMP_R(TestMorph,(*rep),20); + DUMP_R(TestMorph,m,100); + + return FALSE; +} + +#endif + +static UBool TestLanguageGenerator(){ + //LanguageGenerator g; + //const char *const s = "$s = p 0% | q 1%;"; + //g.parseBNF(s, "$s"); + UBool pass; + //= strcmp("q", g.next()) == 0; + + const char *const def = + //"$a = $b;" + //"$b = $c;" + //"$c = $t;" + //"$t = abc $z{1,2};" + //"$k = a | b | c | d | e | f | g ;" + //"$z = q 0% | p 1% | r 1%;" + "$x = a ? 0%;" + ; // end of string +// const char * s = "abczz"; +// +// + LanguageGenerator g; + pass = g.parseBNF(def, "$x",TRUE); +//// LanguageGenerator g(collationBNF, "$root", "$magic", new MagicNode()); +// + if (pass != LanguageGenerator::OK) return FALSE; + + DUMP_R(TestLanguageGenerator, g, 20); + return pass; + + ////UBool pass = strcmp(s,r) == 0; + + //if (pass){ + // printf("TestRandomLanguageGenerator passed.\n"); + //} else { + // printf("TestRandomLanguageGenerator FAILED!!!\n"); + //} + //return pass; +} + +void TestWbnf(void){ + srand((unsigned)time( NULL )); + + //CALL(TestLiteral); + //CALL(TestSequence); + //CALL(TestSymbolTable); + //CALL(TestVariable); + + //TestRepeat(); + //TestAlternation(); + //TestMorph(); + + //TestQuote(); + //TestBuffer(); + //TestWeightedRand(); + + //CALL(TestScanner); + //CALL(TestParser); + CALL(TestLanguageGenerator); +} + |