// Reading Brackets #include #include #include using namespace std; /***************************************************************************** * S-expression *****************************************************************************/ /** * 各要素を保持するデータ型 */ struct cell { /** セルのタイプ */ enum type_t { ATOM = 0, LIST = 1, } type; /** 名前 (type == ATOM) */ string name; /** リストの要素 (type == LIST) */ cell *car, *cdr; /** * タイプ ATOM のセルを作成する。 * * @param s 名前 */ cell(const string& s) : type(ATOM), name(s), car(NULL), cdr(NULL) { } /** * リストのセルを作成する。 * * @param car CAR 部 * @param cdr CDR 部 */ cell(cell *car, cell *cdr) : type(LIST), car(car), cdr(cdr) { } }; /** * Pretty Printer * * @param out 出力ストリーム * @param c セル * @return 次に出力するストリーム */ ostream& operator << (ostream& out, const cell *c) { assert(c != NULL); switch(c->type) { case cell::ATOM: return out << c->name; case cell::LIST: { bool first = true; out << '('; for(const cell *cur = c; cur; cur = cur->cdr) { if(first) first = false; else out << ' '; out << cur->car; } return out << ')'; } default: assert(false); } } /** 割り当てられたセルへのポインタをすべて管理するベクタ */ static vector all_cells; /** * セルを登録する * * @param c セル * @return c */ static inline cell *__allocate_cell(cell *c) { all_cells.push_back(c); return c; } #define NEW_CELL(...) __allocate_cell(new cell(__VA_ARGS__)) /** * セルを一気に解放する */ static void destroy_cells() { for(int i = 0; i < all_cells.size(); i++) delete all_cells[i]; all_cells.clear(); } /***************************************************************************** * Lexer *****************************************************************************/ /** * トークン */ struct token { /** タイプ */ enum type_t { ATOM = 0, // atom LIST_HEADER = 1, // header ('a list of') COMMA = 2, // ',' AND = 3, // 'and' EOT = -1, // $ } type; /** 名前 (type == ATOM) */ string name; /** * リストの要素を作成する。 * * @param name 名前 */ token(const string& name) : type(ATOM), name(name) { } /** * トークンを作成する。 * * @param type タイプ */ token(type_t type = EOT) : type(type), name("*") { } }; /** * 次のトークンを取り出す。 * * @param line 入力 * @param cursor [in,out] カーソル位置 * @return トークン */ #ifdef _DEBUG static token _next_token(const string& line, int& cursor) #else static token next_token(const string& line, int& cursor) #endif { // Lexing table const static struct table_t { const char *pattern; const int pat_len; const token::type_t type; } ttbl[] = { //123456789 {"a list of", 9, token::LIST_HEADER}, {"," , 1, token::COMMA}, {"and" , 3, token::AND}, {NULL , 0, token::EOT}, }; // Skip leading spaces while(cursor < line.size() && line[cursor] == ' ') cursor++; if(cursor >= line.size()) // $ return token(token::EOT); if(isupper(line[cursor])) { // atom int tc = cursor; while(tc < line.size() && isupper(line[tc])) tc++; string s = line.substr(cursor, tc - cursor); cursor = tc; return token(s); } // otherwise, check reserved words for(const table_t *p = ttbl; p->pattern; p++) if(cursor + p->pat_len <= line.size() && line.substr(cursor, p->pat_len) == p->pattern) { cursor += p->pat_len; return token(p->type); } cerr << "LEXING ERROR: " << line.substr(cursor) << endl; assert(false); } #ifdef _DEBUG /** * 次のトークンを取り出す。 * * @param line 入力 * @param cursor [in,out] カーソル位置 * @return トークン */ static token next_token(const string& line, int& cursor) { token result = _next_token(line, cursor); cerr << "** " << result.type << " [" << result.name << ']' << endl; return result; } #endif//_DEBUG /** * Lexing を行う。 * * @param s 入力文字列 * @return トークン列 */ vector lex(const string& s) { vector result; int cursor = 0; do { result.push_back(next_token(s, cursor)); } while(result.back().type != token::EOT); return result; } /***************************************************************************** * LR Automaton *****************************************************************************/ /** * オートマトンの状態を保持する構造体。 */ struct state_t { /** 入力の読み込みカーソル */ int cursor; /** 状態スタック */ vector stack; /** 状態データ */ vector data; /** * デフォルトコンストラクタ (開始状態を作る) */ state_t() : cursor(0) { } }; /** * オートマトンの実装 * * @param input 入力トークン列 * @param st 現在の状態 * @param next [out] 遷移可能な状態集合 * @return まだ遷移を続けられるようであれば true、そうでなければ false。 */ bool step(const vector& input, state_t st, vector& next) { enum nfatoken_t { ATOM = token::ATOM, LIST = token::LIST_HEADER, COMMA = token::COMMA, AND = token::AND, EOT = token::EOT, NT_S = 10, NT_L = 11, NT_R = 12, NT_T = 13, }; int state = st.stack.size() ? st.stack.back() : 0; int token = input[st.cursor].type; cell *data = NULL; retry: // reduce のとき戻ってくる #ifdef _DEBUG // DEBUG MODE cerr << "At state " << state << " and token " << token << " and cursor " << st.cursor << endl; #define ERROR() \ { cerr << "Unknown token " << token << " at state " << state << endl; \ return false; } #define TM_SHIFT(newstate) \ { cerr << "SHIFT(TM: " << newstate << ")" << endl; assert(token < 10); \ state_t __st = st; __st.stack.push_back(newstate); \ __st.data.push_back(token == ATOM ? NEW_CELL(input[__st.cursor].name) : NULL); \ __st.cursor++; next.push_back(__st); } #define NT_SHIFT(newstate) \ { cerr << "SHIFT(NT: " << newstate << ")" << endl; assert(token >= 10); \ state_t __st = st; \ __st.stack.push_back(newstate); __st.data.push_back(data); \ next.push_back(__st); } #define DATA(offset) st.data[st.data.size() - (offset)] #define REDUCE(count, lhs, stmt) \ { cerr << "REDUCE(" << count << ", " << lhs << ")" << endl; \ for(int __i = (count); __i-- > 0; ) st.stack.pop_back(); \ data = NULL; stmt; \ for(int __i = (count); __i-- > 0; ) st.data.pop_back(); \ state = st.stack.size() ? st.stack.back() : 0; token = (lhs); goto retry; } #else //!DEBUG #define ERROR() \ { return false; } #define TM_SHIFT(newstate) \ { state_t __st = st; __st.stack.push_back(newstate); \ __st.data.push_back(token == ATOM ? NEW_CELL(input[__st.cursor].name) : NULL); \ __st.cursor++; next.push_back(__st); } #define NT_SHIFT(newstate) \ { state_t __st = st; \ __st.stack.push_back(newstate); __st.data.push_back(data); \ next.push_back(__st); } #define DATA(offset) st.data[st.data.size() - (offset)] #define REDUCE(count, lhs, stmt) \ { for(int __i = (count); __i-- > 0; ) st.stack.pop_back(); \ data = NULL; stmt; \ for(int __i = (count); __i-- > 0; ) st.data.pop_back(); \ state = st.stack.size() ? st.stack.back() : 0; token = (lhs); goto retry; } #endif//!DEBUG switch(state) { case 0: // S ==> . L // L ==> . a_list_of T // L ==> . a_list_of T R //--- // L: shift 1, a_list_of: shift 2 switch(token) { case NT_L: NT_SHIFT(1); break; case LIST: TM_SHIFT(2); break; default: ERROR(); } break; case 1: // S ==> L . //--- // $: accept switch(token) { case EOT: next.push_back(st); return false; default: ERROR(); } break; case 2: // L ==> a_list_of . T // L ==> a_list_of . T R // T ==> . atom // T ==> . L // L ==> . a_list_of T // L ==> . a_list_of T R //--- // T: shift 3, atom: shift 4, L: shift 5, a_list_of: shift 2 switch(token) { case NT_T: NT_SHIFT(3); break; case ATOM: TM_SHIFT(4); break; case NT_L: NT_SHIFT(5); break; case LIST: TM_SHIFT(2); break; default: ERROR(); } break; case 3: // L ==> a_list_of T . { $$ = cons($2, NIL); } // L ==> a_list_of T . R // R ==> . and T // R ==> . , T R //--- // $: reduce 2, R: shift 6, and: shift 7/reduce 2, ,: shift 8/reduce 2 switch(token) { case EOT: REDUCE(2, NT_L, data = NEW_CELL(DATA(1), NULL)); break; case NT_R: NT_SHIFT(6); break; case AND: TM_SHIFT(7); REDUCE(2, NT_L, data = NEW_CELL(DATA(1), NULL)); break; case COMMA: TM_SHIFT(8); REDUCE(2, NT_L, data = NEW_CELL(DATA(1), NULL)); break; default: ERROR(); } break; case 4: // T ==> atom . { $$ = $1; } //--- // $ , and: reduce 1 switch(token) { case EOT: case COMMA: case AND: REDUCE(1, NT_T, data = DATA(1)); break; default: ERROR(); } break; case 5: // T ==> L . { $$ = $1; } //--- // $ , and: reduce 1 switch(token) { case EOT: case COMMA: case AND: REDUCE(1, NT_T, data = DATA(1)); default: ERROR(); } break; case 6: // L ==> a_list_of T R . { $$ = cons($2, $3); } //--- // $ , and: reduce 3 switch(token) { case EOT: case COMMA: case AND: REDUCE(3, NT_L, data = NEW_CELL(DATA(2), DATA(1))); break; default: ERROR(); } break; case 7: // R ==> and . T // T ==> . atom // T ==> . L // L ==> . a_list_of T // L ==> . a_list_of T R //--- // T: shift 9, atom: shift 4, L: shift 5, a_list_of: shift 2 switch(token) { case NT_T: NT_SHIFT(9); break; case ATOM: TM_SHIFT(4); break; case NT_L: NT_SHIFT(5); break; case LIST: TM_SHIFT(2); break; default: ERROR(); } break; case 8: // R => , . T R // T ==> . atom // T ==> . L // L ==> . a_list_of E //--- // T: shift 10, atom: shift 4, L: shift 5, a_list_of: shift 2 switch(token) { case NT_T: NT_SHIFT(10); break; case ATOM: TM_SHIFT(4); break; case NT_L: NT_SHIFT(5); break; case LIST: TM_SHIFT(2); break; default: ERROR(); } break; case 9: // R ==> and T . { $$ = cons($2, NIL); } //--- // $ , and: reduce 2 switch(token) { case EOT: case COMMA: case AND: REDUCE(2, NT_R, data = NEW_CELL(DATA(1), NULL)); break; default: ERROR(); } break; case 10: // R ==> , T . R // R ==> . and T // R ==> . , T R //--- // R: shift 11, and: shift 7, ,: shift 8 switch(token) { case NT_R: NT_SHIFT(11); break; case AND: TM_SHIFT(7); break; case COMMA: TM_SHIFT(8); break; default: ERROR(); } break; case 11: // R ==> , T R . { $$ = cons($2, $3); } //--- // $ , and: reduce 3 switch(token) { case EOT: case COMMA: case AND: REDUCE(3, NT_R, data = NEW_CELL(DATA(2), DATA(1))); break; default: ERROR(); } break; default: assert(false); } #undef REDUCE #undef DATA #undef NT_SHIFT #undef TM_SHIFT #undef ERROR return true; } /***************************************************************************** * ブートストラップ *****************************************************************************/ /** * main */ int main() { int N; string line; cin >> N; getline(cin, line); while(N-- > 0) { getline(cin, line); vector input = lex(line); // Parse by NFA vector states(1); bool more; do { vector next; more = false; #ifdef _DEBUG cerr << "# of states = " << states.size() << endl; #endif//_DEBUG for(int i = 0; i < states.size(); i++) more = step(input, states[i], next) || more; swap(states, next); next.clear(); } while(more); // switch(states.size()) { case 0: cerr << "SYNTAX ERROR" << endl; assert(false); case 1: cout << states[0].data[0] << endl; break; default: cout << "AMBIGUOUS" << endl; #if 1 //def _DEBUG cerr << "candidates:" << endl; for(int i = 0; i < states.size(); i++) cerr << " " << states[i].data[0] << endl; #endif//_DEBUG } destroy_cells(); } }