正則表達式，寫一個玩具編譯器，解析，評論卸妝

Question

我目前正在通過這本書工作我的方式： http://www1.idc.ac.il/tecs/

我目前在部分地方的練習吧是創建一個編譯器很簡單java喜歡語言。 該書總是陳述什麼是必需的，但不是如何（這是一件好事）。我還應該提到它談到的是yacc和lex，並專門說爲了自己學習而避免在本書中的項目中使用它們。

我在chaper 10上，並開始寫分詞器。

1）任何人都可以給我一些一般性的建議 - 是正則表達式來標記源文件的最佳方法嗎？

2）我想在解析之前從源文件中移除註釋 - 這並不難，但大多數編譯器會告訴您錯誤發生在哪行，如果我只是刪除註釋，這會弄亂行數，有沒有簡單的策略，以保持行數，同時仍然刪除垃圾？

在此先感謝！

Answer 1

標記器本身通常使用描述所有可能的有效標記的大型DFA表編寫（例如，標記可以以字母開頭，後跟其他字母/數字後跟非字母或數字後跟由其他號碼和一個非數字/點或一個點後面至少有一個數字，然後是一個非數字等等）。我建立我的方式是識別我的tokenizer將接受的所有正則表達式，將它們轉換爲DFA並將它們合併。

現在要「解析註釋」，當你解析一個標記時，你可以有一個註釋標記（正則表達式來解析註釋，太長而不能用文字描述），當你完成解析這個註釋時，你只需解析一個新的標記，因此忽略它。或者，您可以將它傳遞給編譯器並讓它處理它（或者將其忽略）。無論哪種方式，都可以保留像行號和字符這樣的元數據。

編輯爲DFA理論：

每個正則表達式可被轉換（並轉換）轉換成DFA出於性能的原因。這消除了解析它們的任何回溯。 This link爲您提供了一個如何完成的想法。首先將正則表達式轉換爲NFA（具有回溯的DFA），然後通過膨脹有限自動機來刪除所有回溯節點。

另一種構建DFA的方法是親自使用一些常識。以一個有限的自動機爲例，它可以解析一個標識符或一個數字。這當然是不夠的，因爲你很可能也想添加註釋，但它會給你一個底層結構的概念。

  A-Z  space 
->(Start)----->(I1)------->((Identifier)) 
    |   |^
    |   +-+ 
    |  A-Z0-9 
    | 
    |   space 
    +---->(N1)---+--->((Number)) <----------+ 
     0-9 |^ |       | 
      | | | .  0-9  space | 
      +-+ +--->(N2)----->(N3)--------+ 
      0-9     |^
           +-+ 
           0-9 

所使用的符號的一些注意事項，在DFA開始於（開始）節點，並通過箭頭輸入從文件中讀取移動。在任何一點上，它只能匹配一條路徑。缺少的任何路徑都默認爲「錯誤」節點。 ((Number))和((Identifier))是你的結局，成功的節點。一旦進入這些節點，您將返回您的令牌。因此，從一開始，如果您的令牌以字母開頭，它必須繼續一堆字母或數字，並以「空格」（空格，新行，製表符等）結尾。沒有回溯，如果失敗，令牌化過程失敗並且您可以報告錯誤。你應該閱讀關於錯誤恢復的理論書以繼續解析，這是一個非常大的話題。

但是，如果您的令牌以數字開頭，則必須緊跟一串數字或一個小數點。如果沒有小數點，那麼一個「空格」必須跟隨數字，否則一個數字必須緊跟着一串數字，後跟一個空格。我沒有包括科學記數法，但不難添加。

現在爲了解析速度，將其轉換爲DFA表格，其中所有節點都在垂直和水平線上。事情是這樣的：

   I1   Identifier N1  N2  N3  Number 
start  letter  nothing  number nothing nothing nothing 
I1   letter+number space  nothing nothing nothing nothing 
Identifier nothing  SUCCESS  nothing nothing nothing nothing 
N1   nothing  nothing  number dot  nothing space 
N2   nothing  nothing  nothing nothing number nothing 
N3   nothing  nothing  nothing nothing number space 
Number  nothing  nothing  nothing nothing nothing SUCCESS 

你運行的方法就是你存儲你的起始狀態，並通過表格，你通過文字閱讀您輸入的字符移動。例如，「1.2」的輸入將被解析爲開始→N1→N2→N3→Number→SUCCESS。如果在任何時候點擊了「無」節點，就會出現錯誤。

編輯2：該表應該實際上是node-> character-> node，而不是node-> node->字符，但在這種情況下它工作得很好，無論如何。自從我上次手寫一個編譯器以來已經有一段時間了。

Answer 2

1-是的正則表達式很好地實現標記器。如果使用像lex這樣的生成的標記器，那麼您將每個標記描述爲一個正則表達式。見馬克的答案。

2-詞法分析器通常會跟蹤行/列信息，因爲令牌消耗在令牌處理器中，您使用令牌跟蹤行/列信息，或將其作爲當前狀態。因此，當發現問題時，標記器知道你在哪裏。因此，在處理註釋時，如果處理新行，標記器只會增加line_count。

在Lex中，您還可以擁有解析狀態。多行註釋通常使用這些狀態來實現，因此允許更簡單的正則表達式。一旦你找到匹配的評論開始，例如'/ *'，你就會改變爲評論狀態，你可以設置爲獨立於正常狀態。因此，當您使用文本查找結束註釋標記'* /'時，您不符合正常標記。

這種基於狀態的過程也是過程字符串字面量是允許嵌套年底廠商如「測試\」更多的文本」有用。