如果您是開發人員，您就使用過程式語言。它們是讓電腦做你想做的事的好方法。也許您甚至已經深入研究過彙編或機器碼程式設計。許多人再也不想回來。但有些人想知道，我怎麼能透過做更多的低階程式來更折磨自己呢？我想更多地了解程式語言是如何製作的！開個玩笑，寫一門新語言並不像聽起來那麼糟糕，所以如果你有一點好奇心，我建議你留下來看看它是關於什麼的。

這篇文章的目的是簡單地介紹如何建立程式語言，以及如何建立自己的特殊語言。甚至可以用自己的名字命名。誰知道。

我還敢打賭，這似乎是一項令人難以置信的艱鉅任務。別擔心，因為我已經考慮過這一點。我盡力相對簡單地解釋了一切，沒有講太多離題的話。在這篇文章結束時，您將能夠建立自己的程式語言（將有幾個部分），但還有更多。了解幕後發生的事情會讓你更好地進行除錯。您將更能理解新的程式語言以及為何它們做出這樣的決定。如果我之前沒有提到的話，你可以擁有一種以你自己的名字命名的程式語言。而且，這真的很有趣。至少對我來說。

編譯器和解釋器

程式語言通常是高階的。也就是說，你看的不是0和1，也不是暫存器和組合程式碼。但是，您的電腦只能辨識 0 和 1，因此它需要一種方法來從您輕鬆讀取的內容轉變為機器可以輕鬆讀取的內容。該翻譯可以透過編譯或解釋來完成。

編譯是將原始語言的整個原始檔轉換為目標語言的過程。出於我們的目的，我們將考慮從全新的、最先進的語言一直編譯到可執行的機器碼。

我的目標是讓「魔法」消失

解釋是或多或少直接執行原始檔中的程式碼的過程。我會讓你覺得這很神奇。

那麼，如何從易於閱讀的原始語言變成難以理解的目標語言呢？

編譯器的階段

編譯器可以透過多種方式分為多個階段，但有一種方法是最常見的。當你第一次看到它時，它的意義不大，但它是這樣的：

哎呀，我選錯了圖，但這樣就可以了。基本上，您獲取原始文件，將其設置為計算機想要的格式（刪除空格之類的內容），將其更改為計算機可以很好地移動的格式，然後從中生成程式碼。還有更多。那是下次，或者如果你的好奇心快要殺死你的話，也可以供你自己研究。

詞法分析

又名“讓原始碼變得漂亮”

考慮以下完全虛構的語言，它基本上只是一個帶有分號的計算器：

  // source.ect
  3 + 3.2;
  5.0 / 1.9;
  6 * 2;

計算機不需要所有這些。空間只適合我們狹隘的頭腦。還有新線？沒有人需要那些。電腦將您看到的程式碼轉換為可以使用的標記流，而不是原始檔案。基本上，它知道3是整數， 3.2是浮點數， +是對這兩個值進行運算的東西。這就是計算機真正需要完成的全部工作。詞法分析器的工作是提供這些標記而不是原始程式。

它的實現方式非常簡單：給詞法分析器（詞法分析器的一種聽起來不那麼自命不凡的說法）一些期望的東西，然後告訴它當它看到這些東西時要做什麼。這些稱為規則。這是一個例子：

int     cout << "I see an integer!" << endl;

當 int 通過詞法分析器並執行此規則時，您將看到一個非常明顯的“我看到一個整數！”感嘆。這不是我們使用詞法分析器的方式，但看到程式碼執行是任意的很有用：沒有規則要求您必須建立某個物件並傳回它，它只是常規的舊程式碼。甚至可以用大括號括起來來使用多條線。

順便說一句，我們將使用稱為FLEX 的東西來進行詞法分析。它使事情變得非常簡單，但是沒有什麼可以阻止您自己編寫一個程式來執行此操作。

為了了解我們如何使用 flex，請看這個例子：

    // scanner.lex
    /* Definitions */
    %{
      #include <iostream>
      using namespace std;
      extern "C" int yylex();
    %}

    /* Rules next */
    %%
    [0-9]+.[0-9]+ cout << "FLOAT: (" << yytext << ")" << endl;
    [0-9]+        cout << "INT: (" << yytext << ")" << endl;
    "+"           cout << "PLUS" << endl;
    "-"           cout << "MINUS" << endl;
    "*"           cout << "TIMES" << endl;
    "/"           cout << "DIVIDED BY" << endl;
    ";"           cout << "SEMICOLON" << endl;
    [\t\r\n\f]    ; /* ignore whitespace */

    %%
    /* Code */

    int main() {
      yylex();
    }

這引入了一些新概念，讓我們回顧一下它們：

%%用於分隔 .lex 檔案的各個部分。第一部分是聲明 - 基本上是使詞法分析器更具可讀性的變數。這也是您導入的位置，由%{和%}包圍。

第二部分是規則，我們之前已經看過。這些基本上是一個大的if else if塊。它將執行最長的匹配行。因此，即使您更改 float 和 int 的順序，float 仍然會匹配，因為匹配3.2的 3 個字元比3的 1 個字元多。請注意，如果這些規則均不匹配，則會採用預設規則，只需將字元列印到標準輸出即可。然後，您可以使用yytext來引用它看到的與該規則相符的內容。

第三部分是程式碼，它只是在執行時執行的 C 或 C++ 原始碼。 yylex();是執行詞法分析器的函數呼叫。您也可以讓它從檔案中讀取輸入，但預設情況下它從標準輸入中讀取。

假設您將這兩個檔案建立為source.ect和scanner.lex 。我們可以使用flex命令建立一個 C++ 程式（假設您已經安裝了flex ），然後編譯它並輸入我們的原始程式碼以達到我們很棒的列印語句。讓我們將其付諸行動吧！

evan:ectlang/ $ flex scanner.lex
evan:ectlang/ $ g++ lex.yy.c -lfl
evan:ectlang/ $ ./a.out < source.ect
INT: (3)
PLUS
FLOAT: (3.2)
SEMICOLON
FLOAT: (5.0)
DIVIDED BY
FLOAT: (1.9)
SEMICOLON
INT: (6)
TIMES
INT: (2)
SEMICOLON
evan:ectlang/ $ 

嘿，酷！您只需編寫將輸入與規則相符的 C++ 程式碼，以便執行某些操作。

現在，編譯器如何使用它？一般來說，每個規則都會返回一些東西，而不是打印一些東西——一個令牌！這些標記可以在編譯器的下一部分中定義...

語法分析器

又名“使漂亮的源程式碼可用”

是時候玩得開心了！一旦我們到達這裡，我們就開始定義程式的結構。解析器只是獲得一個標記流，它必須匹配該流中的元素，以使原始程式碼具有可用的結構。為了做到這一點，它使用了語法，你可能在理論課上看到或聽到你奇怪的朋友閒聊的東西。它們非常強大，並且有很多東西需要了解，但我只會提供您需要了解的關於我們有點愚蠢的解析器的資訊。

基本上，語法將非終結符與終結符和非終結符的某種組合相匹配。終端是樹的葉子；非終端有孩子。如果這沒有意義，請不要擔心，程式碼可能會更容易理解。

我們將使用一個名為Bison 的解析器產生器。這次，為了解釋目的，我將把文件分成幾個部分。首先，聲明：

    // parser.y
    %{
      #include <iostream>
      using namespace std;
      extern "C" void yyerror(char *s);
      extern "C" int yyparse();
    %}

    %union{
      int intVal;
      float floatVal;
    }

    %start program

    %token <intVal> INTEGER_LITERAL
    %token <floatVal> FLOAT_LITERAL
    %token SEMI
    %type <floatVal> exp
    %type <floatVal> statement
    %left PLUS MINUS
    %left MULT DIV

第一部分應該看起來很熟悉：我們正在導入我們想要使用的東西。之後就變得有點棘手了。

聯合是「真正的」C++ 類型到我們將在整個程式中呼叫它的類型的映射。因此，當我們看到intVal時，您可以將頭腦中的值替換為int ，而當我們看到floatVal時，您可以將頭腦中的值替換為float 。稍後你就會明白為什麼。

接下來我們來看看符號。您可以在腦海中將它們分為終結符和非終結符，就像我們之前討論的語法一樣。大寫字母表示終端，因此它們不會繼續擴展。小寫意味著非終結符，因此它們繼續擴展。這只是慣例。

每個聲明（以%開頭）聲明一些符號。首先，我們看到我們從一個非終端program開始。然後，我們定義一些標記。 <>括號定義回傳類型：因此INTEGER_LITERAL終端機回傳intVal 。 SEMI終端不會回傳任何內容。使用type可以對非終結符完成類似的操作，如將exp定義為傳回floatVal的非終結符時所見。

最後我們取得了優先權。我們知道 PEMDAS，或者您可能已經學過的任何其他縮寫詞，它告訴您一些簡單的優先規則：乘法在加法之前，等等。現在，我們以一種奇怪的方式在這裡聲明這一點。首先，清單中的位置越低意味著優先順序越高。其次，您可能想知道left是什麼意思。這就是關聯性：差不多，如果我們有a op b op c ， a和b會在一起，還是b和c會在一起？我們的大多數運算子都執行前者，即a和b首先結合在一起：這稱為左結合性。某些運算子（例如求冪）會執行相反的操作： a^b^c期望您先提高b^c然後再提高a^(b^c) 。不過，我們不會處理這個問題。如果您想了解更多詳細訊息，請查看 Bison 頁面。

好吧，我可能已經厭倦了聲明，這是語法規則：

    // parser.y
    %%
    program: /* empty */
        | program statement { cout << "Result: " << $2 << endl; }
        ;

    statement: exp SEMI

    exp:
        INTEGER_LITERAL { $$ = $1; }
        | FLOAT_LITERAL { $$ = $1; }
        | exp PLUS exp  { $$ = $1 + $3; }
        | exp MINUS exp { $$ = $1 - $3; }
        | exp MULT exp  { $$ = $1 * $3; }
        | exp DIV exp   { $$ = $1 / $3; }
        ;

這就是我們之前講的文法。如果您不熟悉語法，這非常簡單：左側可以變成右側的任何內容，並用|分隔。 （邏輯or ）。如果它可以走多條路徑，那就是不行的，我們稱之為歧義語法。由於我們的優先聲明，這並不含糊 - 如果我們更改它，使 plus 不再保持關聯，而是聲明為像SEMI這樣的token ，我們會看到發生移位/歸約衝突。想知道更多？看看Bison是如何運作的，提示，它使用LR解析演算法。

好的，所以exp可以是以下情況之一： INTEGER_LITERAL 、 FLOAT_LITERAL等。請注意，它也是遞歸的，因此exp可以變成兩個exp 。這允許我們使用複雜的表達式，例如1 + 2 / 3 * 5 。請記住，每個exp都會傳回一個 float 類型。

括號內的內容與我們在詞法分析器中看到的相同：任意 C++ 程式碼，但帶有更奇怪的語法糖。在這種情況下，我們有一些以$開頭的特殊變數。變數$$基本上就是回傳的內容。 $1是第一個參數傳回的內容， $2第二個參數傳回的內容，等等。我所說的「參數」是指語法規則的一部分：因此規則exp PLUS exp有參數 1 exp 、參數 2 PLUS和參數 3 exp 。因此，在程式碼執行中，我們將第一個表達式的結果加到第三個表達式中。

最後，一旦它回到program非終端，它將列印語句的結果。在這種情況下，程式是一堆語句，其中語句是一個表達式，後面跟著一個分號。

現在我們來編寫程式碼部分。這是當我們通過解析器時實際執行的內容：

    // parser.y
    %%
    int main(int argc, char **argv) {
      if (argc < 2) {
        cout << "Provide a filename to parse!" << endl;
        exit(1);
      }
      FILE *sourceFile = fopen(argv[1], "r");

      if (!sourceFile) {
        cout << "Could not open source file " << argv[1] << endl;
        exit(1);
      }

      // Sets input for flex to the file instead of standard in
      yyin = sourceFile;
      // Now let's parse it!
      yyparse();
    }

    // Called on error with message s
    void yyerror(char *s) {
      cerr << s << endl;
    }

好吧，這開始變得有趣了。我們的主函數現在從第一個參數提供的檔案而不是標準輸入中讀取，並且我們加入了一些錯誤程式碼。這是非常不言自明的，並且註釋很好地解釋了正在發生的事情，所以我將把它作為練習留給讀者來弄清楚這一點。您需要知道的是現在我們回到詞法分析器以向解析器提供標記！這是我們的新詞法分析器：

    // scanner.lex
    %{
      extern "C" int yylex();
      #include "parser.tab.c"  // Defines the tokens
    %}

    %%
    [0-9]+        { yylval.intVal = atoi(yytext); return INTEGER_LITERAL; }
    [0-9]+.[0-9]+ { yylval.floatVal = atof(yytext); return FLOAT_LITERAL; }
    "+"           { return PLUS; }
    "-"           { return MINUS; }
    "*"           { return MULT; }
    "/"           { return DIV; }
    ";"           { return SEMI; }
    [ \t\r\n\f]   ; /* ignore whitespace */

嘿嘿，現在確實變小了！我們看到的是，我們回傳的是終端符號，而不是列印。其中一些，例如整數和浮點數，我們首先在繼續之前設定值（ yylval是終端符號的回傳值）。除此之外，它只是為解析器提供了一個終端標記流以供其自行決定使用。

酷，那麼讓我們執行吧！

evan:ectlang/ $ bison parser.y
evan:ectlang/ $ flex scanner.lex
evan:ectlang/ $ g++ lex.yy.c -lfl
evan:ectlang/ $ ./a.out source.ect
Result: 6.2
Result: 2.63158
Result: 12

我們開始了 - 我們的解析器列印出正確的值！但這並不是真正的編譯器，它只是執行 C++ 程式碼來執行我們想要的內容。為了製作編譯器，我們希望將其轉換為機器碼。為此，我們需要加入一點...

直到下次...

我現在意識到這篇文章會比我想像的要長很多，所以我想我應該在這裡結束這篇文章。我們基本上有一個可用的詞法分析器和解析器，所以這是一個很好的停止點。

如果您對最終產品感到好奇，我已將原始程式碼放在我的 Github上。隨著更多帖子的發布，該存儲庫將出現更多活動。

有了我們的詞法分析器和解析器，我們現在可以產生程式碼的中間表示，該中間表示最終可以轉換為真實的機器碼，我將向您展示具體的操作方法。

第 2 部分來了！

其他資源

如果您想了解有關此處介紹的任何內容的更多訊息，我已經連結了一些內容以供您開始使用。我已經講了很多，所以這是我向您展示如何深入研究這些主題的機會。

• Flex 程式碼庫： https://github.com/westes/flex - 我們使用的詞法分析工具。

• Bison 文件： https://www.gnu.org/software/bison/ - 我們使用的解析器產生器。這裡有很棒的文件。

• LALR 解析： https://web.cs.dal.ca/~sjackson/lalr1.html - 關於 LALR(1) 解析器（如 Bison 產生的解析器！）如何運作的精心解釋。

• 解決解析衝突： http://www.cs.ecu.edu/karl/5220/spr16/Notes/Bottom-up/conflict.html - 如何解決shift/reduce或reduce/reduce衝突，就像我們之前看到的那樣。

• Chomsky 層次結構： https://en.wikipedia.org/wiki/Chomsky_hierarchy - 對此沒有詳細介紹，但我們使用了上下文無關語法，以便 Bison 可以編譯它。如果您需要上下文敏感性，那是為了後面的階段。

• 符號表： https://www.tutorialspoint.com/compiler_design/compiler_design_symbol_table.htm - 使用符號表，編譯器如何處理變數。

哦，順便說一句，如果您不喜歡我的編譯器階段，這裡有一個實際的圖表。我仍然保留了符號表和錯誤處理程序。另請注意，許多圖表與此不同，但這最好地說明了我們所關心的內容。

原文出處：https://dev.to/evantypanski/writing-a-simple-programming-language-from-scratch-part-1-54a2