我正在編譯器（語言接近C），我必須在C中實現它。我的主要問題是如何選擇正確的解析方法，以便在編譯我的編譯器時高效。解析，哪種方法選擇？
這是我目前的語法： http://img11.hostingpics.net/pics/273965Capturedcran20130417192526.png
我在想製作一個自上而下的解析器LL（1）如下所述：http://dragonbook.stanford.edu/lecture-notes/Stanford-CS143/07-Top-Down-Parsing.pdf
難道是考慮這個語法高效的選擇，知道我首先必須刪除左邊的遞歸規則。你有沒有其他建議？
謝謝 Mentinet
最有效的解析器LR-解析器和LR-解析器來實現。你可以去遞歸下降解析技術，因爲它很容易在C
實現有點困難構建解析器的最有效方式是使用一個特定的工具，其目的是構建解析器。他們過去被稱爲編譯器編譯器，但現在焦點已經轉移（擴大）爲語言工作臺，它們爲您提供更多幫助來構建自己的語言。例如，幾乎所有的語言工作平臺都會爲您提供IDE支持和語法高亮語言，只需查看語法即可。他們還非常幫助你調試你的語法和語言（你不希望左遞歸是你問題中最大的問題，是嗎？）。
其中最好的當前支持和開發語言工作臺可以命名：
如果你真的這麼想，或者如果你考慮自己寫一個解析器來娛樂和體驗，最好的現代算法是SGLR,GLL和Packrat。其中的每一個都是半個世紀以來算法研究的精髓，所以不要期望能夠在一瞬間完全理解它們，並且期望從第一批出現的「修復」中找不到任何好處。用。但是，如果您確實想出了一個很好的改進，請不要猶豫與作者分享您的發現或者發佈它！
感謝所有這些建議，但我們最終決定採用完全按照這裏同樣的方法來建立我們自己的遞歸下降解析器：http://www.cs.binghamton.edu/~zdu/parsdemo/recintro.html
事實上，我們改變了語法，以消除左遞歸規則，並且因爲我在第一條消息中顯示的語法不是LL（1），所以我們使用我們的令牌列表（由我們的掃描程序製作）來繼續前進。它看起來很好。
現在我們在這些遞歸函數中構建了一個AST。你有什麼建議嗎？提示？非常感謝你。
您不應在回答中嵌入其他問題，因爲這可能會被刪除爲「不是答案」。詢問另一個單獨的問題，並且[編輯]這個問題只是一個答案，你可以「接受」。 –
很多答案在這裏，但他們弄糊塗了。是的，有LL和LR解析器，但這不是你的選擇。
你有一個語法。有些工具會根據語法爲您自動創建解析器。可敬的Yacc和Bison這樣做。他們創建一個LR解析器（實際上是LALR）。還有一些工具可以爲您創建LL解析器，如ANTLR。像這樣的工具的缺點是它們不靈活。他們自動生成的語法錯誤消息很糟糕，錯誤恢復很難，而較老的則鼓勵你以一種方式考慮代碼 - 這恰好是錯誤的方式。正確的方法是讓解析器吐出一個抽象語法樹，然後讓編譯器從中生成代碼。這些工具要求您混合解析器和編譯器代碼。
當您使用自動化工具像這樣的權力LL，LR和LALR之間的差異確實事。你不能「作弊」來擴大他們的權力。 （在這種情況下，Power意味着能夠爲有效的上下文無關語法生成一個解析器，一個有效的上下文無關文法是爲每個輸入生成一個唯一的，正確的解析樹，或者正確地說它與語法不匹配。）目前沒有可以爲每個有效語法創建解析器的解析器生成器。然而，LR可以處理比任何其他類型更多的語法。無法處理語法並不是一個災難，因爲您可以使用解析器生成器可以接受的形式重新編寫語法。然而，如何實現並不總是顯而易見的，更糟糕的是它會影響抽象語法樹，這意味着解析器中的弱點會影響到代碼的其餘部分 - 就像編譯器一樣。
的原因有LL，LALR和LR解析器是很久以前的事，產生LR解析器無論是在時間和內存方面爲徵稅現代計算機的工作。 （請注意，這是需要生成解析器，只有在您編寫解析器時纔會發生這種情況。生成的解析器運行速度非常快）。但那是前一段時間的looong。生成一個LR（1）解析器對於一種中等複雜語言來說佔用的內存遠遠小於1GB，而在現代計算機上佔用的時間卻不到一秒。出於這個原因，使用LR自動解析器生成器（例如Hyacc）會更好。
另一種選擇是編寫自己的解析器。在這種情況下，只有一個選擇：LL解析器。當這裏的人們說寫LR是困難的時候，他們低估了這種情況。人類幾乎不可能手動創建LR分析器。您可能認爲這意味着如果您編寫自己的解析器，則您被限制使用LL（1）語法。但這不完全正確。由於您正在編寫代碼，因此您可以作弊。您可以預測任意數量的符號，因爲您無需輸出任何內容，直到您準備就緒，抽象語法樹就不必與您使用的語法相匹配。這種作弊能力彌補了LL和LR（1）之間的所有失去的力量，並且經常有一些失敗。
手寫解析器有他們當然缺點。不能保證你的解析器實際上符合你的語法，否則就不會檢查你的語法是否有效（即能夠識別你認爲它的語言）。它們更長，並且在鼓勵您將解析代碼與編譯代碼混合時更糟糕。它們也明顯只用一種語言實現，而解析器生成器通常以幾種不同的語言吐出結果。即使他們不這樣做，一個LR解析表也可以用一個只包含常量的數據結構來表示（比如用JSON），實際的解析器只有100行左右的代碼。但手寫解析器也有好處。由於您編寫了代碼，因此您知道發生了什麼，因此更容易執行錯誤恢復並生成理智的錯誤消息。
最終，權衡往往是這樣的：
我唯一的問題是：爲什麼選C？編譯器通常不是時間關鍵的代碼。如果你願意讓你的編譯器運行得慢一些 - 比如我自己的Lrparsing，那麼有非常好的解析包可以讓你在1/2的代碼中完成工作。請記住，「稍慢一點」在這裏意味着「對人類幾乎不可察覺」。我想答案是「我正在處理的任務指定C」。爲了給你一個想法，當你放鬆需求時，從語法到解析樹的過程變得如此簡單。這個程序：
#!/usr/bin/python
from lrparsing import *
class G(Grammar):
Exp = Ref("Exp")
int = Token(re='[0-9]+')
id = Token(re='[a-zA-Z][a-zA-Z0-9_]*')
ActArgs = List(Exp, ',', 1)
FunCall = id + '(' + Opt(ActArgs) + ')'
Exp = Prio(
id | int | Tokens("[]", "False True") | Token('(') + List(THIS, ',', 1, 2) + ')' |
Token("! -") + THIS,
THIS << Tokens("*/%") << THIS,
THIS << Tokens("+ -") << THIS,
THIS << Tokens("== < > <= >= !=") << THIS,
THIS << Tokens("&&") << THIS,
THIS << Tokens("||") << THIS,
THIS << Tokens(":") << THIS)
Type = (
Tokens("", "Int Bool") |
Token('(') + THIS + ',' + THIS + ')' |
Token('[') + THIS + ']')
Stmt = (
Token('{') + THIS * Many + '}' |
Keyword("if") + '(' + Exp + ')' << THIS + Opt(Keyword('else') + THIS) |
Keyword("while") + '(' + Exp + ')' + THIS |
id + '=' + Exp + ';' |
FunCall + ';' |
Keyword('return') + Opt(Exp) + ';')
FArgs = List(Type + id, ',', 1)
RetType = Type | Keyword('void')
VarDecl = Type + id + '=' + Exp + ';'
FunDecl = (
RetType + id + '(' + Opt(FArgs) + ')' +
'{' + VarDecl * Many + Stmt * Some + '}')
Decl = VarDecl | FunDecl
Prog = Decl * Some
COMMENTS = Token(re="/[*](?:[^*]|[*][^/])*[*]/") | Token(re="//[^\n\r]*")
START = Prog
EXAMPLE = """\
Int factorial(Int n) {
Int result = 1;
while (n > 1) {
result = result * n;
n = n - 1;
}
return result;
}
"""
parse_tree = G.parse(EXAMPLE)
print G.repr_parse_tree(parse_tree)
產生這樣的輸出：
(START (Prog (Decl (FunDecl
(RetType (Type 'Int'))
(id 'factorial') '('
(FArgs
(Type 'Int')
(id 'n')) ')' '{'
(VarDecl
(Type 'Int')
(id 'result') '='
(Exp (int '1')) ';')
(Stmt 'while' '('
(Exp
(Exp (id 'n')) '>'
(Exp (int '1'))) ')'
(Stmt '{'
(Stmt
(id 'result') '='
(Exp
(Exp (id 'result')) '*'
(Exp (id 'n'))) ';')
(Stmt
(id 'n') '='
(Exp
(Exp (id 'n')) '-'
(Exp (int '1'))) ';') '}'))
(Stmt 'return'
(Exp (id 'result')) ';') '}'))))
你需要高效編碼解析器的條款，或者你想代碼是有效的解析方面的東西？在我撰寫需要解析器的東西的近二十年的長期經驗中，解析速度從未如此重要到可衡量的程度。我對解析的AST所做的事一直是決定性能的關鍵因素。 – dasblinkenlight
對我來說最重要的是編碼方面的高效率，因爲我們（我正在一起工作）已經在Clean中做了很多工作，但是我們對這種語言沒有經驗，現在真的很難走得更遠。所以我們有點晚了，我們會有更快的工作，更好。我們還必須建立一個AST。 – mentinet
然後我會使用ANTLR：它構建了非常好的遞歸下降解析器，具有C目標，並且非常容易學習。 – dasblinkenlight