構建解析器（第一部分）

我正在編寫自己的基於JavaScript的編程語言（是的，這很瘋狂，但它僅供學習... 也許？）。好吧，我閱讀有關解析器和第一遍是將源代碼轉換爲記號，如：構建解析器（第一部分）

if(x > 5) 
    return true;

標記者到：

T_IF   "if" 
T_LPAREN  "(" 
T_IDENTIFIER "x" 
T_GT   ">" 
T_NUMBER  "5" 
T_RPAREN  ")" 
T_IDENTIFIER "return" 
T_TRUE  "true" 
T_TERMINATOR ";"

我不知道如果我的邏輯是正確的爲那段時間。在我的解析器那就更好了（或不？），並轉化爲它（是的，多維數組）：

T_IF    "if" 
    T_EXPRESSION  ... 
    T_IDENTIFIER  "x" 
    T_GT    ">" 
    T_NUMBER   "5" 
    T_CLOSURE  ... 
    T_IDENTIFIER  "return" 
    T_TRUE   "true"

我有些疑惑：

是我的方式更好或更糟的是原來的方式？請注意，我的代碼將被讀取和編譯（轉換爲另一種語言，如PHP），而不是一直解釋。
我使用tokenizer之後，我需要做什麼？我真的失去了這個傳球！
有一些很好的教程，瞭解我如何做到這一點？

那麼，是嗎。再見！

來源

2012-02-26 David Rodrigues

+10

嘿，編程語言並不瘋狂。這裏很多人都在做同樣的事情。 – ApprenticeHacker 2012-02-26 11:19:53

你試過龍書嗎？基本上你所謂的傳遞一個是詞法分析階段，其次是實際的語法分析階段 - >理想地輸出某種AST（抽象語法樹），然後你可以語義分析（解析）或轉換成你的目標語言 – stryba 2012-02-26 11:33:18

@IntermediateHacker哈哈...是的，瘋狂的部分對於一個人來說非常複雜。但是，學習是一件非常好的事情，真的。對於專業人士來說，我想這需要一個團隊，所以瘋狂獨自一人。：p – 2012-02-26 11:33:52

通常，您希望將編輯器（也稱爲詞法分析器）的功能與編譯器或解釋器的其他階段分開。其原因是基本的模塊化：每個過程消耗一種東西（例如字符）併產生另一個東西（例如令牌）。

所以你已經把你的角色轉換成了令牌。現在，您想將標記的標記列表轉換爲有意義的嵌套表達式，這就是通常稱爲解析。對於類似JavaScript的語言，您應該查看recursive descent parsing。爲了使用不同優先級的中綴運算符來解析表達式，Pratt parsing非常有用，您可以在特殊情況下使用普通的遞歸下降解析。

爲了給你一個更具體的例子根據你的情況，我假設你可以寫兩個函數：accept(token)和expect(token)，它測試你創建的流中的下一個標記。您將爲語言語法中的每種語句或表達式創建一個函數。下面是Pythonish僞代碼爲statement()功能，比如：

def statement(): 

    if accept("if"): 
    x = expression() 
    y = statement() 
    return IfStatement(x, y) 

    elif accept("return"): 
    x = expression() 
    return ReturnStatement(x) 

    elif accept("{") 
    xs = [] 
    while True: 
     xs.append(statement()) 
     if not accept(";"): 
     break 
    expect("}") 
    return Block(xs) 

    else: 
    error("Invalid statement!")

這給你什麼叫做你的程序，然後你就可以操作（優化和分析），輸出（編輯）的抽象語法樹（AST），或運行（解釋）。

來源

2012-02-26 11:35:49

我的方式好還是壞原來的方式？請注意，我的代碼將被讀取和編譯（轉換爲另一種語言，如PHP），而不是一直解釋。

什麼是原來的方式？有許多不同的方式來實現語言。實際上，我認爲你的確很好，我曾經試圖建立一種自己翻譯成C＃的語言hack programming language。許多語言編譯器轉換爲中間語言，這很常見。

我使用tokenizer之後，我需要做什麼？我真的失去了這個傳球！

標記後，你需要解析它。使用一些很好的詞法分析器/解析器框架，例如Boost.Spirit或Coco或其他。有數百個。或者你可以實現你自己的詞法分析器，但這需要時間和資源。有很多方法來解析代碼，我一般依靠recursive descent parsing。

接下來你需要做代碼生成。這是我認爲最困難的部分。也有一些工具，但如果你願意的話，你可以手動完成，我試着在我的項目中做到這一點，但它非常基本，很有用，代碼爲here和here。

有一些很好的教程，瞭解我如何做到這一點？

正如我剛纔所說，使用工具做到這一點。有很多相當不錯的分析器框架。欲瞭解更多信息，您可以嘗試詢問一些知道這些東西的人。 @DeadMG，在Lounge C++正在建立一種名爲「寬」的編程語言。你可以試着諮詢他。

來源

2012-02-26 11:30:36 ApprenticeHacker

大多數工具包的完整過程分成兩個單獨份

詞法分析器（亦稱標記生成器）
解析器（亦稱語法）

標記生成器將分割輸入數據成令牌。解析器只會對令牌「流」進行操作並構建結構。

你的問題似乎集中在標記器。但是你的第二個解決方案將語法分析器和標記器混合成一個步驟。理論上這也是可能的，但對於初學者來說，它與其他大多數工具/框架相同的方式更容易執行：保持步驟不同。

你的第一個解決辦法：我想你的記號化例子是這樣的：

T_KEYWORD_IF "if" 
T_LPAREN  "(" 
T_IDENTIFIER "x" 
T_GT   ">" 
T_LITARAL  "5" 
T_RPAREN  ")" 
T_KEYWORD_RET "return" 
T_KEYWORD_TRUE "true" 
T_TERMINATOR ";"

在大多數語言關鍵字不能用作方法名，變量名等等。這已在分詞器級別上反映出來（T_KEYWORD_IF，T_KEYWORD_RET,T_KEYWORD_TRUE）。

下一級將藉此流 - 通過應用形式語法 - 將建立一些數據結構（通常被稱爲AST - 抽象語法樹），這可能是這樣的：

IfStatement: 
    Expression: 
     BinaryOperator: 
      Operator:  T_GT 
      LeftOperand: 
       IdentifierExpression: 
        "x" 
      RightOperand: 
       LiteralExpression 
        5 
    IfBlock 
     ReturnStatement 
      ReturnExpression 
       LiteralExpression 
        "true" 
    ElseBlock (empty)

實現手工解析器通常由一些框架完成。通過手工實施類似和的效果通常在一學期的較好部分在大學完成。所以你真的應該使用某種框架。

語法分析器框架的輸入通常是某種BNF中的形式語法。你的「if」部分看起來像這樣：

IfStatement: T_KEYWORD_IF T_LPAREN Expression T_RPAREN Statement ; 

Expression: LiteralExpression | BinaryExpression | IdentifierExpression | ... ; 

BinaryExpression: LeftOperand BinaryOperator RightOperand; 

....

這只是爲了得到這個想法。正確解析真實世界語言（如Javascript ）並非易事。但有趣。

來源

2012-02-26 11:57:51

構建解析器（第一部分）

回答

相關問題