Есть BNF | Цитата | rule_defenition = identifier '=' expr ';';
expr = concat '|' expr | concat;
concat = rep ',' concat | rep;
rep = not '+' | not '*' | not '?' | not;
not = action '^' not | action;
action = atom '[' terminal ']' | atom;
atom = literal | '(' expr ')';
literal = identifier | terminal | '{' terminal '}'; |
для EBNF грамматики + несколько дополнений, а именно | Цитата | | action = atom '[' terminal ']' | atom; |
необходимо использовать в квадратных скобках(далее "action'ы"), после литералов и скобочных выражений("literal | '(' expr ')' | '{' terminal '}'"). Непонятно, почему след. выражения парсятся нормально | Код | stmt = expr_stmt['expr_stmt'] |
if_stmt['if_stmt'] |
while_stmt['while_stmt'] |
continue_stmt['continue_stmt'] |
break_stmt['break_stmt'] |
return_stmt['return_stmt']
; |
а эти нет | Код | if_stmt = 'if', '(', expr['if_cond'], ')',
block,
else_stmt?
; |
Методом тыка, понял что парсер валится, если использовать action'ы не в конце последовательности, а в начале или середине, т.е. вот пример "проблемных" выражений | Код | some_rule = 'a'['some_action'], 'b', 'c', 'd';
some_rule = 'a', 'b'['some_action'], 'c', 'd';
some_rule = 'a', 'b', 'c'['some_action'], 'd'; |
а вот с этим | Код | some_rule = 'a', 'b', 'c', 'd'['some_action']; |
все в порядке, т.к. action используется в конце последовательности. Парсер рукописный, рекурсивно нисходящий. Вот код, если поможет конечно | Код | struct token_t {
type_t type_;
std::size_t line_;
std::size_t pos_;
std::string name_;
std::string data_;
};
struct parse_tree_t;
typedef boost::shared_ptr<parse_tree_t> parse_tree_t_ptr;
struct parse_tree_t {
type_t type_;
std::string data_;
parse_tree_t_ptr left_;
parse_tree_t_ptr right_;
};
typedef std::list<token_t> tokens_t;
tokens_t tokens_;
parse_tree_t_ptr parse_literal() {
token_t token = this->tokens_.front();
if (token.type_ == kIdentifier) {
this->tokens_.pop_front();
// mark rule as "called"
this->called_rules_[token.data_] = token;
parse_tree_t_ptr identifier_node(new parse_tree_t(token));
return identifier_node;
} else if (token.type_ == kTerminal) {
this->tokens_.pop_front();
parse_tree_t_ptr terminal_node(new parse_tree_t(token));
return terminal_node;
} else if (token.type_ == kRange) {
this->tokens_.pop_front();
parse_tree_t_ptr range_node(new parse_tree_t(token));
return range_node;
}
tokens_t tokens;
tokens.push_back(token_t(kIdentifier));
tokens.push_back(token_t(kTerminal));
tokens.push_back(token_t(kRange));
this->error_expecting_got(tokens, token);
parse_tree_t_ptr null_node(new parse_tree_t());
return null_node;
}
parse_tree_t_ptr parse_atom() {
parse_tree_t_ptr node;
if (this->tokens_.front().type_ == kOpenParen) {
this->tokens_.pop_front();
node = this->parse_expr();
if (this->tokens_.front().type_ != kCloseParen) {
this->error_expecting_got(token_t(kCloseParen), this->tokens_.front());
}
this->tokens_.pop_front();
} else {
node = this->parse_literal();
}
return node;
}
parse_tree_t_ptr parse_action() {
parse_tree_t_ptr atom_node = this->parse_atom();
if (this->tokens_.front().type_ == kOpenSquare) {
this->tokens_.pop_front();
if (this->tokens_.front().type_ == kTerminal) {
token_t terminal(this->tokens_.front());
terminal.type_ = kAction;
terminal.data_ = this->tokens_.front().data_;
this->tokens_.pop_front();
if (this->tokens_.front().type_ == kCloseSquare) {
this->tokens_.pop_front();
parse_tree_t_ptr action_node(new parse_tree_t(terminal, atom_node));
return action_node;
} else {
this->error_expecting_got(token_t(kCloseSquare), this->tokens_.front());
}
} else {
this->error_expecting_got(token_t(kTerminal), this->tokens_.front());
}
}
return atom_node;
}
parse_tree_t_ptr parse_not() {
parse_tree_t_ptr left = this->parse_action();
token_t token = this->tokens_.front();
if (token.type_ == kNot) {
this->tokens_.pop_front();
parse_tree_t_ptr right = this->parse_not();
parse_tree_t_ptr not_node(new parse_tree_t(token, left, right));
return not_node;
} else {
return left;
}
parse_tree_t_ptr null_node(new parse_tree_t());
return null_node;
}
parse_tree_t_ptr parse_rep() {
parse_tree_t_ptr not_node = this->parse_not();
token_t token = this->tokens_.front();
if (token.type_ == kOnceOrMore) {
this->tokens_.pop_front();
parse_tree_t_ptr oom_node(new parse_tree_t(token, not_node));
return oom_node;
} else if (token.type_ == kZeroOrMore) {
this->tokens_.pop_front();
parse_tree_t_ptr zom_node(new parse_tree_t(token, not_node));
return zom_node;
} else if (token.type_ == kZeroOrOnce) {
this->tokens_.pop_front();
parse_tree_t_ptr zoo_node(new parse_tree_t(token, not_node));
return zoo_node;
} else {
return not_node;
}
parse_tree_t_ptr null_node(new parse_tree_t());
return null_node;
}
parse_tree_t_ptr parse_concat() {
parse_tree_t_ptr left = this->parse_rep();
token_t token = this->tokens_.front();
if (token.type_ == kConcatenate) {
this->tokens_.pop_front();
parse_tree_t_ptr right = this->parse_concat();
parse_tree_t_ptr concat_node(new parse_tree_t(token, left, right));
return concat_node;
} else {
return left;
}
parse_tree_t_ptr null_node(new parse_tree_t());
return null_node;
}
parse_tree_t_ptr parse_expr() {
parse_tree_t_ptr left = this->parse_concat();
token_t token = this->tokens_.front();
if (token.type_ == kOr) {
this->tokens_.pop_front();
parse_tree_t_ptr right = this->parse_expr();
parse_tree_t_ptr expr_node(new parse_tree_t(token, left, right));
return expr_node;
} else {
return left;
}
parse_tree_t_ptr null_node(new parse_tree_t());
return null_node;
}
parse_tree_t_ptr parse_rule_definition() {
token_t token = this->tokens_.front();
if (token.type_ == kIdentifier) {
token_t tok_identifier = token;
this->tokens_.pop_front();
// mark rule as "defined"
this->defined_rules_[tok_identifier.data_] = tok_identifier;
token = this->tokens_.front();
if (token.type_ == kAssign) {
this->tokens_.pop_front();
parse_tree_t_ptr expr = this->parse_expr();
token = this->tokens_.front();
if (token.type_ != kSemicolon) {
this->error_expecting_got(token_t(kSemicolon), token);
}
this->tokens_.pop_front();
parse_tree_t_ptr identifier_node(new parse_tree_t(tok_identifier));
parse_tree_t_ptr assign_expr = parse_tree_t_ptr(new parse_tree_t(token_t(kAssign), identifier_node, expr));
return assign_expr;
} else {
this->error_expecting_got(token_t(kAssign), token);
}
} else {
this->error_expecting_got("rule definition", token);
}
parse_tree_t_ptr null_node(new parse_tree_t());
return null_node;
} |
Как решить эту проблему? Спасибо. |
BNF для EBNF грамматики 
Загрузка ...
Дата 22.12.2010, 22:58 (
