27

私は現在字句解析プログラムを使用しており、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]

私はまだ初心者なので、皆さんが私を助けてくれることを願っています。ありがとう。

4

6 に答える 6

61

簡単な字句アナライザーを手動で作成するのに、ANTLR も Dragon book も必要ありません。より完全な言語 (Java など) の語彙アナライザーでさえ、手作業で書くのはそれほど複雑ではありません。産業用のタスクがある場合は、ANTLR や lex バリアントなどの産業用ツールを検討することをお勧めしますが、字句解析がどのように機能するかを学習するためには、手動で作成することが有用な演習になる可能性があります。あなたはまだ初心者だと言ったので、これが事実だと思います。

これは、この質問を見た後に私が書いた、Scheme のような言語のサブセット用の Java で書かれた単純な語彙アナライザーです。String文字のストリーム (この場合は a ) をトークンのストリーム(この場合は a ) に分割する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

このような単純なレクサーを 1 つまたは 2 つ作成すると、この問題がどのように分解されるかがよくわかります。次に、lex のような自動化ツールの使用方法を調べるのは興味深いことです。正規表現ベースのマッチャーの背後にある理論はそれほど難しくありませんが、完全に理解するには少し時間がかかります。レクサーを手で書くことは、正規表現を有限自動化 (最初に NFA、次に NFA から DFA) に変換する背後にある理論に飛び込むよりも、勉強する動機を与え、問題を理解するのに役立つと思います。一度にたくさんのことを吸収する必要があり、圧倒されがちです。

個人的には、Dragon book は優れていて非常に徹底していますが、完全なものを目指しており、必ずしもアクセス可能であるとは限らないため、最も理解しやすいとは言えないかもしれません。ドラゴンの本を開く前に、他のいくつかのコンパイラ テキストを試してみることをお勧めします。ここにいくつかの無料の本がありますが、これらは入門的な内容がかなり充実しています。

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

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

正規表現の実装に関するいくつかの記事 (自動字句解析では通常、正規表現が使用されます)

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

それが役立つことを願っています。幸運を。

于 2013-07-25T03:50:43.963 に答える
4

ANTLR 4Java.g4は、参照文法でこれを正確に行います。Unicode エスケープ シーケンスの処理をどの程度厳密に言語仕様に準拠させたいかによって、2 つのオプションがあります。

編集: この文法によって生成されるトークンの名前は、テーブルとは少し異なります。

  • あなたのKey_WordトークンはIdentifier
  • あなたのObject_AccessorトークンはDOT
  • あなたのleft_ParenthesisトークンはLPAREN
  • あなたのString_LiteralトークンはStringLiteral
  • あなたのright_ParenthesisトークンはRPAREN
  • あなたのstatement_separatorトークンはSEMI
于 2013-07-25T03:01:00.990 に答える
3

字句解析はそれ自体がトピックであり、通常はコンパイラの設計と解析と一緒に行われます。何かをコーディングしようとする前に、それについてよく読んでおくべきです。このトピックに関する私のお気に入りの本は、Dragon book です。これは、コンパイラー設計の優れた入門書であり、Java に簡単に変換してそこから移動できるすべてのコンパイラー・フェーズの疑似コードも提供します。

要するに、主なアイデアは、有限状態マシンを使用して、入力を解析し、特定のクラス (たとえば、目的の出力の括弧またはキーワード) に属するトークンに分割することです。ステート マシン構築のプロセスは、実際にはこの分析の唯一の難しい部分であり、Dragon book はこのことについての優れた洞察を提供します。

于 2013-07-25T02:55:04.930 に答える
2

Lex & BisonC やAntlrJavaのようなライブラリを使用できます。字句解析は、オートマトンを作成することで実行できます。小さな例を挙げます：

キーワード (言語) が である文字列をトークン化する必要があるとします{'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)

上の図はおそらく非常に悪いですが、アイデアは、S現在消費Eして別の状態に移動することで表される開始状態を持っているということです。文字を消費し続け、この単純な有限状態マシン内でさまざまな状態に到達します。最終的に、特定の状態に到達します。たとえば、 を消費した後、がトークンを放出する放出状態に到達し、状態に戻ります。このサイクルは、文字ストリームがトークナイザーに届くまで永遠に続きます。無効な文字では、設計に応じてエラーをスローするか無視することができます。NCENDECHOEmitENDENDstart

于 2013-07-25T03:11:12.987 に答える