如何編寫遞歸下降解析器？

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（）函數）。我需要指出正確的方向。謝謝。

來源

2013-02-10 amorimluc

關於此事有很多文字，在神話龍書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++中，您可能希望使用類層次結構（雖然它會是一個非常短暫的，粗糙的層次結構 - 事實上，可以很容易地將所有其他類直接從基類派生出來）。

來源

2013-02-10 04:29:43

不難看出語法中會出現什麼情況，至少如果不知道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; 
}

爲您的分析樹的根。

來源

2013-02-10 04:54:49 mikyra

如何編寫遞歸下降解析器？

回答

相關問題