1

C++ 我不知道如何为以下语法编写递归下降解析器：

<Datalog Program>     ->  Schemes : <Scheme List>     
                         Facts   : <Fact List>
                         Rules   : <Rule List>
                         Queries : <Query List>
                         <EOF>
<Scheme List>         ->  <Scheme> <Scheme List Tail>
<Scheme List Tail>    ->  <Scheme List> | ε
<Scheme>              ->  <Identifier> ( <Identifier List> )
<Identifier List>     ->  <Identifier> <Identifier List Tail>
<Identifier List Tail>->  , <Identifier List> | ε
<Fact List>           ->  <Fact> <Fact List> | ε
<Fact>                ->  <Identifier> ( <Constant List> ) .
<Constant List>       ->  <String> <Constant List Tail>
<Constant List Tail>  ->  , <Constant List> | ε
<Rule List>           ->  <Rule> <Rule List> | ε
<Rule>                ->  <Head Predicate> :- <Predicate List> .
<Head Predicate>      ->  <Identifier> ( <Identifier List> )
<Predicate List>      ->  <Predicate> <Predicate List Tail>
<Predicate List Tail> ->  , <Predicate List> | ε
<Predicate>           ->  <Identifier> ( <Parameter List> )
<Parameter List>      ->  <Parameter> <Parameter List Tail>
<Parameter List Tail> ->  , <Parameter List> | ε
<Parameter>           ->  <String> | <Identifier> | <Expression>
<Expression>          -> ( <Parameter> <Operator> <Parameter> )
<Operator>            -> + | *
<Query List>          ->  <Query> <Query List Tail>
<Query List Tail>     ->  <Query List> | ε
<Query>               ->  <Predicate> ?

这是一个简单的类似数据记录的语法。我在尝试编写解析器时完全迷失了。我已经编写了一个词法分析器，它输出一个带有所有标记的向量。我知道我需要为每个产品编写方法，但我不知道如何将标记连接到解析树中（因此我可以在树完成后运行 toString() 函数）。我需要指出正确的方向。谢谢。

4

2 回答 2

2

鉴于你已经写过，它主要是从 EBNF 到 C++ 源代码的机械翻译，所以（例如），像这样的规则：

<Scheme>              ->  <Identifier> ( <Identifier List> ) 
<Identifier List>     ->  <Identifier> <Identifier List Tail>
<Identifier List Tail>->  , <Identifier List> | ε

翻译成这个一般顺序的东西（虽然要小心——我只是在脑海中输入这个，所以它根本没有经过测试；把它更多地想象成类似于 C 的伪代码而不是任何东西按原样编译）。

bool scheme() { 
    return identifier()        &&
           check_input('(')    &&
           identifier_list()   &&
           check_input(')');
}

bool identifier_list() { 
    if (identifier()) {
        if (check_input(','))
            return identifier_list();
        else
            return true;
    }
    return false;
}

bool identifier() { 
    // you haven't said what's a legal identifier, so for the moment I'm assuming
    // rules roughly like C's.
    int ch;
    std::string id;

    if (!((ch=getinput()) == '_' || isalapha(ch))
        return false;

    do { 
        id += ch;
        ch = getinput();
    } while (isalpha(ch) || isdigit(ch) || ch == '_');
    putback(ch);
    return true;
}

一旦你让它正确识别输入（并构建标识符等，就像我在上面所做的那样，即使我什么也没做），你就可以开始构建一个解析树（或其他任何东西）向树中添加东西当你认出它们时。如果你在 C 中这样做，你通常使用联合。在 C++ 中，您可能希望使用类层次结构来代替（尽管它会是一个非常短而复杂的层次结构——事实上，很容易成为直接从基类派生的所有其他层次结构）。

于 2013-02-10T04:29:43.920 回答
1

至少如果一个人不知道 Datalog 或任何一种语言，就很难看到你的语法发生了什么。

如果您对终端和制作使用了不同的标记，这会容易得多 - 不仅可以为不知情的人阅读，还可以为您自己阅读。通过寻找和向后寻找肯定可以弄清楚哪个是哪个，但这似乎让我有点头晕。

看看你的语法，你似乎不会得到一个相当复杂的树。因为所有物品都是订购的。

我的建议是根据您的语法对树进行建模，即数据结构：DatalogProgram Schmema Fact Rule and Query 以及 Expression HeadPredicate 和 Predicate

这样，您必须做的所有事情才能使您的 Parser 工作看起来像

DatalogProgram parse_datalog_progrem (pos){
   DatalogProgram program = new

   while ( Scheme s = parse_scheme () )
       program.append_scheme (s);

   while ( Fact f = parse_fact () )
       program.append_scheme (f);

   while ( Rule r = parse_rule () )
       program.append_rule (r);

   while ( Query q = parse_query () )
       program.append_query (q);

   return program; 
}

Scheme parse_scheme () {
   Scheme s = new ...
   s.id = parse_identifier ();

   parse ('(')

   while (Identifier i = parse_identifier) {
     s.append_id_list (i);
     if (lookahead != ',')
        break;
     parse (',');
   }
   parse (')');
   return s;
}

....

... 等等。我认为你说对了。

似乎仍有一件事或另一件事需要解决，但我认为这是最好的方法。例如，您可能想考虑在数据结构中使用联合，例如

struct Parameter {
  enum ParamType type;
  union {
     String  str;
     Identifier id;
     Expression expr;
  }
}

离这里还有很长的路要走，但我希望你喜欢这个方向。

..哦和DatalogProgram之类的：

struct DatalogProgram {
  struct Scheme *schemes;
  struct Fact *facts;
  struct Rule *rules;
  struct Query *queries;
}

为您的解析树的根。

于 2013-02-10T04:54:49.180 回答