製作詞法分析器

我正在使用Lexical Analyzer程序，並且正在使用Java。我一直在研究這個問題的答案，但直到現在我沒有找到任何答案。這裏是我的問題：製作詞法分析器

輸入：

System.out.println ("Hello World");

所需的輸出：

Lexeme----------------------Token 

System [Key_Word] 

.  [Object_Accessor] 

out [Key_Word] 

. [Object_Accessor] 

println [Key_Word] 

( [left_Parenthesis] 

"Hello World" [String_Literal] 

) [right_Parenthesis] 

; [statement_separator]

我還是一個初學者，所以我希望你們能幫助我在此。謝謝。

來源

2013-07-25 KLoverated

既不需要ANTLR也不需要龍書來手工編寫簡單的詞法分析器。即使是更豐富的語言（比如Java）的詞法分析器也不是手工編寫的非常複雜。顯然，如果你有一個工業任務，你可能需要考慮像ANTLR或某些lex變體這樣的工業強度工具，但爲了學習詞法分析的工作原理，手工編寫一個可能會被證明是一個有用的練習。我假設情況是這樣，因爲你說你還是個初學者。

下面是一個簡單的詞法分析器，用Java編寫，用於類似Scheme的語言子集，是我在看到這個問題後編寫的。我認爲即使你以前從未見過一個詞法分析器，代碼也相對容易理解，因爲將一串字符（在本例中爲String）分解爲一個標記流（在本例中爲List<Token>）並不是硬。如果您有問題，我可以嘗試更深入地解釋。

import java.util.List; 
import java.util.ArrayList; 

/* 
* Lexical analyzer for Scheme-like minilanguage: 
* (define (foo x) (bar (baz x))) 
*/ 
public class Lexer { 
    public static enum Type { 
     // This Scheme-like language has three token types: 
     // open parens, close parens, and an "atom" type 
     LPAREN, RPAREN, ATOM; 
    } 
    public static class Token { 
     public final Type t; 
     public final String c; // contents mainly for atom tokens 
     // could have column and line number fields too, for reporting errors later 
     public Token(Type t, String c) { 
      this.t = t; 
      this.c = c; 
     } 
     public String toString() { 
      if(t == Type.ATOM) { 
       return "ATOM<" + c + ">"; 
      } 
      return t.toString(); 
     } 
    } 

    /* 
    * Given a String, and an index, get the atom starting at that index 
    */ 
    public static String getAtom(String s, int i) { 
     int j = i; 
     for(; j < s.length();) { 
      if(Character.isLetter(s.charAt(j))) { 
       j++; 
      } else { 
       return s.substring(i, j); 
      } 
     } 
     return s.substring(i, j); 
    } 

    public static List<Token> lex(String input) { 
     List<Token> result = new ArrayList<Token>(); 
     for(int i = 0; i < input.length();) { 
      switch(input.charAt(i)) { 
      case '(': 
       result.add(new Token(Type.LPAREN, "(")); 
       i++; 
       break; 
      case ')': 
       result.add(new Token(Type.RPAREN, ")")); 
       i++; 
       break; 
      default: 
       if(Character.isWhitespace(input.charAt(i))) { 
        i++; 
       } else { 
        String atom = getAtom(input, i); 
        i += atom.length(); 
        result.add(new Token(Type.ATOM, atom)); 
       } 
       break; 
      } 
     } 
     return result; 
    } 

    public static void main(String[] args) { 
     if(args.length < 1) { 
      System.out.println("Usage: java Lexer \"((some Scheme) (code to) lex)\"."); 
      return; 
     } 
     List<Token> tokens = lex(args[0]); 
     for(Token t : tokens) { 
      System.out.println(t); 
     } 
    } 
}

使用例：

~/code/scratch $ java Lexer "" 
~/code/scratch $ java Lexer "(" 
LPAREN 
~/code/scratch $ java Lexer "()" 
LPAREN 
RPAREN 
~/code/scratch $ java Lexer "(foo)" 
LPAREN 
ATOM<foo> 
RPAREN 
~/code/scratch $ java Lexer "(foo bar)" 
LPAREN 
ATOM<foo> 
ATOM<bar> 
RPAREN 
~/code/scratch $ java Lexer "(foo (bar))" 
LPAREN 
ATOM<foo> 
LPAREN 
ATOM<bar> 
RPAREN 
RPAREN

一旦你已經寫了一個或兩個簡單的詞法分析器這樣，你會得到這個問題如何分解一個不錯的主意。然後，探索如何使用像lex這樣的自動化工具會很有趣。基於正則表達式的匹配器背後的理論不是太困難，但它需要一段時間才能完全理解。我認爲手工編寫詞法分析器可以激發這項研究並幫助您更好地理解問題，而不是深入理解將正則表達式轉換爲有限自動化（第一個NFA，然後是NFA到DFA）等等。立即採取很多措施，很容易讓人不知所措。

就個人而言，龍書雖然很好且很全面，但其覆蓋面可能不是最容易理解的，因爲它的目標是完整的，不一定是可訪問的。在打開龍書之前，您可能想嘗試其他編譯器文本。這裏有一些免費的書籍，其中有相當不錯的入門報道，恕我直言：

http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf

http://www.diku.dk/~torbenm/Basics/

正則表達式實現的一些文章（自動詞法分析通常使用正則表達式）

http://swtch.com/~rsc/regexp/

我希望有幫助。祝你好運。

來源

2013-07-25 03:50:43 spacemanaki

非常感謝你。這對我幫助很大。我只想問一下，我是否有必要把這些東西當作計算機科學的學生來學習。與我的專業有什麼關係？ – KLoverated

詞法分析是編譯器或解釋器在解析之前所要做的第一步。編譯器（和解釋器）非常有用，沒有它們，我們將不得不整天編寫機器代碼。我不會評論CS學生是否應該研究編譯器。我認爲他們對自己的權利感興趣，如果你是一個好奇的程序員，你可能會想知道他們是如何工作的。 CS中有很多主題，理解編譯可能對你並不感興趣。沒關係。也就是說，編譯器通常與CS相關。 – spacemanaki

非常感謝您分享您的想法。我有興趣研究編譯/編譯過程，因爲我有一天夢想着設計一個。我害怕的是我可能無法很好地理解它。正如我所說我仍然是一個初學者。我開始學習計算機科學，沒有任何計算機編程背景。我總是想知道從哪裏開始。 – KLoverated

詞彙分析本身就是一個話題，通常與編譯器設計和分析一起進行。在嘗試編寫任何代碼之前，您應該閱讀它。我最喜歡關於這個主題的書是Dragon這本書，它應該給你一個編譯器設計的好介紹，甚至爲所有編譯器階段提供僞代碼，你可以很容易地轉換到Java並從那裏移動。

簡而言之，主要思想是解析輸入並使用有限狀態機將其分爲屬於某些類別的標記（括號或關鍵字，例如，在所需的輸出中）。國家機器製造過程實際上是這一分析的唯一難題，龍書將爲您提供有關這件事的深刻見解。

來源

2013-07-25 02:55:04 darxsys

謝謝先生！我非常感謝你的建議。對我來說，深度研究詞法分析對於我更好地理解這個概念非常需要。 – KLoverated

ANTLR 4將使用Java.g4引用語法完成此操作。根據您希望處理Unicode轉義序列的方式遵循語言規範，您有兩個選項。

https://github.com/antlr/grammars-v4/blob/master/java/Java.g4該語法僅將Unicode轉義序列作爲字符串或字符文字中的字符處理。
https://github.com/antlr/antlr4/blob/master/tool/test/org/antlr/v4/test/Java-LR.g4（在使用之前必須重命名爲Java.g4）：該語法要求您將ANTLRInputStream包裝在JavaUnicodeInputStream中，該文件在將它們送入詞法分析器之前根據JLS處理Unicode轉義序列。

編輯：由此語法生成的令牌的名稱與您的表略有不同。

你Key_Word令牌是Identifier
你Object_Accessor令牌DOT
你left_Parenthesis令牌是LPAREN
你String_Literal令牌是StringLiteral
你right_Parenthesis令牌是RPAREN
你statement_separator令牌SEMI

來源

2013-07-25 03:01:00

您可以使用庫像在C Lex & Bison或Antlr在Java中。詞彙分析可以通過製作自動機來完成。我給你舉個小例子：

假設你需要標記一個字符串，其中關鍵字（語言）是{'echo', '.', ' ', 'end')。關鍵字我的意思是語言只包含以下關鍵字。所以，如果我輸入

echo . 
end .

我的詞法分析器應該輸出

echo ECHO 
SPACE 
. DOT 
end END 
SPACE 
. DOT

我們建立自動爲這樣一個標記，我可以

->(SPACE) (Back) 
| 
(S)-------------E->C->H->O->(ECHO) (Back) 
|    | 
.->(DOT)(Back) ->N->D ->(END) (Back to Start)

上述圖示開始是prolly很糟糕，但想法是，你有一個開始狀態代表S現在你消耗E並去其他國家，現在你期望N或C分別來到END和ECHO。你在這個簡單的有限狀態機中不斷消耗字符並達到不同的狀態。最終，您達到某種Emit狀態，例如在消耗E,N,D後，您達到發射狀態END，它會發出令牌，然後您將返回到start狀態。只要您將字符流傳送到您的標記器，此循環就會一直持續。在無效字符上，您可以根據設計引發錯誤或忽略。

來源

2013-07-25 03:11:12 Shivam

製作詞法分析器

回答

相關問題