如何编写递归下降解析器？

问题描述：

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（）函数）。我需要指出正确的方向。谢谢。

关于此事有很多文字，在神话龙书Aho，Sethi，Ullman的“编译器：原理，技术和工具”中。 IIR在Wirth的“算法+数据结构=程序”（可能是他的另一本书）中，对于构建递归下降解析器有一个很清晰的解释。 – vonbrand 2013-02-10 03:22:27

愚蠢的问题：你不能使用像野牛或byacc这样的工具吗？以这种方式编写/维护解析器的源代码要容易得多。这些（和其他）工具提供了独立的C程序（或C++也用于野牛）。 – vonbrand 2013-02-10 03:24:40

老实说，正确地考虑文法并消除左递归是困难的部分，看起来你已经在那里了。这件事情应该该死的 - 在这一点上写*本身*。假设你有一个合适的词法分析器，你可以把每个生产视为一个被调用的函数，并且附带令牌提取以验证沿途的下一条生产路径。做出正确的决定，并且*不* *快捷方式，直到你有充分的工作*第一*。 – WhozCraig 2013-02-10 03:27:21

答

鉴于你已经写的，它主要是从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++中，您可能希望使用类层次结构（虽然它会是一个非常短暂的，粗糙的层次结构 - 事实上，可以很容易地将所有其他类直接从基类派生出来）。

答

不难看出语法中会出现什么情况，至少如果不知道Datalog或不管语言是什么样的话。

它会更容易 - 不仅要阅读未知的内容，还要为自己阅读，如果您使用了不同的终端和制作标记。当然可以找出哪一个是通过狩猎和后退，但它似乎让我有点头晕。

看看你的语法，看起来你不会得到一个相当复杂的树。因为所有项目都是订购的。

我的建议是根据自己的Grammmar即datastructs的树只是型号： DatalogProgram Schmema事实规则和查询，以及表达HeadPredicate和谓语

这样，所有你必须做的，使你的解析器工作看起来像

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; 
} 

....

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

似乎还有其他的东西需要解决，但我认为这是最好的方法。你例如可能要考虑一下在datastruct使用工会像

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; 
}

为您的分析树的根。

如何编写递归下降解析器？

相关推荐