4

文字ごとの字句アナライザーをどこから書き始めればよいかさえわかりません。与えられたルールと仕様に基づいて、Markdown 言語 (具体的には HTML) の BNF 文法ルールを作成したので、何も追加する必要はありません。ここで、Markdown 言語のソース ファイルの語彙素をトークンに分割する文字単位の字句解析器を設計して実装する必要があります。これが私のBNF文法です：

端末:

#DOCUMENT BEGIN,
#DOCUMENT END
#HEAD BEGIN,
#HEAD END,
#TITLE BEGIN,
#TITLE END,
#PARAGRAPH BEGIN,
#PARAGRAPH END,
#BOLD BEGIN,
#BOLD END,
#ITALICS BEGIN,
#ITALICS END,
#LIST BEGIN,
#LIST END,
#ITEM BEGIN,
#ITEM END,
#LINK BEGIN,
#TEXT,
#ADDRESS,
#LINK END,
#DEFINE BEGIN,
#NAME,
#VALUE,
#DEFINE END,
#USE BEGIN,
#USE END

これらの端末では大文字と小文字が区別されないことに注意してください。

非端末:

<document> ::= #DOCUMENT BEGIN <macro-­‐define> <head> <body> #DOCUMENT END

<head> ::= #HEAD BEGIN <title> #HEAD END | ε

<title> ::= #TITLE BEGIN <text> #TITLE END | ε

<body> ::= <inner-­‐text> <body>
           | <paragraph> <body>
           | <bold> <body>
           | <italics> <body>
           | <list> <body>
           | ε

<paragraph> ::= #PARAGRAPH BEGIN <macro-­‐define> <inner-­‐paragraph> #PARAGRAPH END

<inner-­‐paragraph> ::= <inner-­‐text> <inner-­‐paragraph>
                      | <bold> <inner-­‐paragraph>
                      | <italics> <inner-­‐paragraph>
                      | <list> <inner-­‐paragraph>
                      | ε

<inner-­‐text> ::= <macro-­‐use> <inner-­‐text>
                  | <text> <inner-­‐text>
                  | ε

<macro-­‐define> ::= #DEFINE BEGIN #NAME <text> #VALUE <body> #DEFINE END <macro-­‐define>
                    | ε

<macro-­‐use> ::= #USE BEGIN <text> #USE END | ε

<bold> ::= #BOLD BEGIN <macro-­‐define> <inner-­‐text> #BOLD END

<italics> ::= #ITALICS BEGIN <macro-­‐define> <inner-­‐text> #ITALICS END

<link> ::= #LINK BEGIN #TEXT <text> #ADDRESS <text> #LINK END

<list> ::= #LIST BEGIN #ITEM BEGIN <macro-­‐define> <inner-­‐list> #ITEM END <list-­‐items> #LIST END

<list-­‐items> ::= #ITEM BEGIN <macro-­‐define> <inner-­‐list> #ITEM END <list-­‐items> | ε

<inner-­‐list> ::= | <bold> <inner-­‐list>
                  | <italics> <inner-­‐list>
                  | <list><inner-­‐list>
                  | <inner-­‐text> <inner-­‐list>
                  | ε

<text> ::= Any plain text | ε

「<」、「>」、「&」、「/」などの HTML 文字は、ソース ファイルのどのテキストにも表示されないと想定できます。また、"#" は、Markdown 注釈の 1 つ (#DOCUMENT など) の前にのみ表示されると想定することもできます。DocumentBegin、DocumentEnd、ParagraphBegin、ParagraphEndなどのトークン オブジェクトを表すには、個別の Java クラスを用意するのが最善だと思います。発生した字句エラー (#DOC BEGIN など) は、できるだけ多くの情報とともにコンソールに出力として報告する必要があります。可能な限りエラー情報。コンパイラは、最初のエラーが発生した後に終了する必要があります。エラーが発生した場合、出力ファイルは作成されません。

私の問題は、語彙アナライザーが何をすべきかを知っていますが、正直なところ、コーディング/実装をどこから始めればよいかわかりません。問題が何を求めているのかについてさらに説明が必要な場合は、お気軽にお尋ねください。できる限り説明します。これは、私のクラスに予定されていた大きなプロジェクトの一部でした。この部分を完了できず、多くのポイントを失いましたが、今はそれを理解する必要があるだけなので、テストを受ければそれほど迷うことはありません.

4

2 に答える 2

1

わかりました、これはかなり遅れていますが、ここに行きます。

字句解析器は文法 (および BNF 記法) に関連付けられることがよくありますが、この 2 つは実際には少し異なります。

字句解析器は文字をトークンに変換します。トークンは文法の「アトム」として処理されますが、パーサーはトークンを何らかの中間構造 (通常はツリー) に変換します。字句解析器の部分だけに焦点を当てると、文字を単語に処理するのと同じように、入力のローパス処理と考えることができます。

すでに BNF 文法を持っているので、使用するすべてのトークン (エンド ワード) を既に知っているので、それらをリストにします。アイデアは、どの一連の文字がリスト内の各項目にマップされるかをすばやく決定する方法です。例えば

#, D, E, F, I, N, E, <whitespace> => #DEFINE
#, D, O, C, U, M, E, N, T, <whitespace> => #DOCUMENT
B, E, G, I, N, <whitespace> => BEGIN
E, N, D, <whitespace> => END

解析で忍び寄るいくつかの問題があります。

まず、比較することがたくさんあります。読み込まれた最初の文字は「#」である可能性があり、その場合でも、一致する可能性のあるアイテムが 20 を超えています。これは、次の文字に一致を継続する必要があることを意味します。これが 'D' の場合でも、'#DEFINE' と '#DOCUMENT' の 2 つの一致が可能であることを意味します。

第 2 に、「#BEGIN」を処理した後に「#BEGIN」や「#BEGINNING」などの単語がある場合、次の文字を取得するまで 2 つの単語のどちらかを決定できません。キャラクターの「消費」を考慮したシステムで次のキャラクターを取得すると、次のトークンの処理が複雑になります。ピークまたは先読みが必要になる場合がありますが、生成するトークンを決定するロジックが複雑になります。

第三に、ワイルドカードの「テキスト」トークンがあります。そのトークンはほぼすべてのものと一致する可能性があるため、他のすべてのトークンと照合して、トークン生成ロジックが生成する必要があるトークンを常に認識できるようにする必要があります。

理想的には、トークン ジェネレーター (レクサー) は、次のトークンを「認識する」ための解析に依存しません。ただし、パーサーがレクサーに「ヒント」を与えるほど複雑な言語もあります。この種のシステムを避けることで、よりクリーンなコンパイラーの実装が可能になります。残念ながら、いくつかの既存の言語では、常にこの方法で構築できるとは限りません。

では、何をすべきかについてのアイデアがあることを知っておいてください (おそらく、何らかの意味で既に持っているでしょう)。

消費した文字 (つまり、トークンに完全に変換された文字) を追跡するために、ある種のインデックスが必要です。これにより、誤って文字がトークン ストリームに二重の影響を与えないようにすることができます。先読みする場合は、「先読み」用の 2 つ目のポインターが必要です。おそらく、先読みの量を制限する必要があります (ロジックの難しさを軽減するため)。

次に、不明な数のデータ構造 (トークンと呼ばれる) が必要です。必ずしもそうする必要はありませんが、トークンの開始行番号、開始文字インデックス、終了行番号、および終了文字インデックスを追跡することをお勧めします。これにより、デバッグがはるかに簡単になります。さらに、トークン内の部分文字列を「キャプチャ」することをお勧めします。これを好きなように呼ぶことができますが、トークンの「イメージ」と呼ぶ人もいます。

当然のことながら、パーサーがさまざまなタイプのトークンを区別できる場合は、そのトークンのタイプを何らかの方法でトークンに (または一緒に)格納する必要があります。時折、人はトークンの「価値」の概念を持ち、それも保存されることがあります。

ある程度の努力の後、文字列をレクサーにプッシュしてトークンのストリームを生成できるはずです。幸運を。

于 2013-11-11T03:43:23.013 に答える
0

Javaでこれを行うために私が見つけた最高の（つまり、私が知っている唯一の）語彙アナライザーは、JFlexと呼ばれています。大学では言語をトークン化するために使用し、アプリケーションでドメイン固有言語の構文強調表示を作成するために商業的に使用しました。

JFlex字句解析器

http://jflex.de/

カップパーサー

http://www2.cs.tum.edu/projects/cup/

LALR(1) パーサーについて少し

http://en.wikipedia.org/wiki/LALR_parser

例 (サンプル コード) が必要な場合は、私にメッセージを送ってください。いくつかのメモをお送りします。いくつかの大学のサイト (プリンストンなど) には何かあると思いますが、Google で簡単に検索してもあまり有用なものは表示されませんでした。

乾杯、

ジョン

于 2013-11-11T02:58:52.117 に答える