7

非常に限定された特別なサーバー側スクリプト言語をサポートする必要がある、非常に基本的な Web サーバーを作成しています。基本的にサポートする必要があるのは、「エコー」、オペランドが 2 つだけの加算/減算/乗算 (除算なし)、日付を出力する単純な「date()」関数、および文字列を連結するための「&」演算子の使用だけです。

例は次のとおりです。

echo "Here is the date: " & date();
echo "9 x 15 = : & 9*15;

トークンを生成するために必要なコードを調べて作成しましたが、正しいトークンを使用しているかどうかわかりません。

以下のトークンを作成しました。

ECHO - The echo command
WHITESPACE - Any whitespace
STRING - A string inside quotations
DATE - The date() function
CONCAT - the & operator for concatenation
MATH - Any instance of binary operation (5+4, 9*2, 8-2, etc)
TERM - The terminal character (;)

私が特に確信が持てない数学のもの。通常、整数専用のトークンを作成し、次に各演算子用にもトークンを作成する人を見かけますが、私は二項演算のみを許可したいので、トークンを 1 つのトークンにグループ化するのが理にかなっていると考えました。すべてを個別に行う場合、「5+4+1」を決して受け入れないようにするために、追加の作業を行う必要があります。

質問 1 は、どのトークンを使用するのが正しい軌道に乗っているかということです。

次の質問は、正しい構文を確保するためにこれらのトークンを次にどうするかということです。私が考えていたアプローチは、基本的に「このトークンを持っていることはわかっています。現在のトークンに基づいて次に許可されるトークンのリストがあります。次のトークンはリストにありますか?」と言うものでした。

それに基づいて、すべてのトークンのリストと、それらの直後に表示するのに有効なトークンのリストを作成しました (簡単にするために空白は含めませんでした)。

ECHO        ->      STRING|MATH|DATE
STRING      ->      TERM|CONCAT
MATH        ->      TERM|CONCAT
DATE        ->      TERM|CONCAT
CONCAT      ->      STRING|MATH|DATE

問題は、これを最適に実装する方法がまったくわからないことです。実際には、トークン間にスペースがあることを確認するために、空白も追跡する必要があります。しかし、それは私が一度に 2 つのトークンを先読みしなければならないことを意味し、これはますます威圧的になっています。また、if ブロックの嫌なセクションだけでなく、「有効な次のトークン」を管理する方法もわかりません。スクリプトを実際に実行する前に、有効な構文をチェックする必要がありますか?それとも、すべてを一度に実行して、予期しないトークンに到達したときにエラーをスローする必要がありますか? この単純な例では、すべてが左から右に解析するだけで常に正常に機能し、実際の優先順位規則はありません (MATH を除いて、間違っているように感じても、それが 1 つのトークンにまとめた理由の一部です)。 '

パーサーの作成に関する私の調査では、「accept()」関数と「expect()」関数の作成に関する多くの参照が見られますが、それらが何をすべきか、またはどのように機能するべきかについての明確な説明が見つかりません。 .

これを実装する方法と、最終的に結果の文字列を実際に作成する方法がわからないだけだと思います。

私は正しい方向に向かっていますか?このような単純なものを最適に実装する方法を理解するのに役立つリソースを知っている人はいますか? 手作業で行う必要があり、ANTLR のようなツールは使用できません。

助けてくれてありがとう。

4

2 に答える 2

2

最初に行う必要があるのは、すべての空白 (文字列内のものを除く) を破棄することです。このようにして、トークンのリストにトークンを追加すると、リストに有効なトークンのみが含まれていることを確認できます。たとえば、次のステートメントを考えてみましょう。

echo "Here is the date: " & date();

トークン化を開始し、最初に空白に基づいてエコーを分離します (はい、空白はここで分離する必要がありますが、その後は役に立ちません)。次に、トークナイザーは二重引用符に遭遇し、終了の二重引用符が見つかるまですべてを読み取り続けます。同様に、&、date、および()の個別のトークンを作成します。

トークン リストには、次のトークンが含まれるようになりました。

echo
"日付は次のとおりです: "
&
日付
()

解析段階では、これらのトークンを読み取ります。パーサーは、トークン リスト内のすべてのトークンをループします。エコーを読み取り、それが有効かどうかをチェックします (言語のルール/関数に基づいて)。次のトークンに進み、それがdate、string、またはmathのいずれかであるかどうかを確認します。同様に、残りのトークンをチェックします。トークンがそこにあるはずがない場合は、構文エラーなどを示すエラーをスローできます。

数学ステートメントのトークン化では、ブラケットに含まれる式と、残りのオペランドおよび演算子を別々に結合するだけです。例: 9/3 + (7-3+1) には、トークン 9、/、3、+、および (7-3+1) があります。すべてのトークンには独自の優先度 (トークン構造体で定義) があるため、優先度が最も高いトークンから優先度が最も低いトークンまで評価を開始できます。このようにして、優先順位の高い式を作成できます。それでも混乱する場合は、お知らせください。サンプルコードを書いておきます。

于 2012-11-09T16:15:05.983 に答える
1

expectパーサーが次のトークンを取得するために行うことであり、トークンが適切な次のトークンでない場合は失敗します。まず、パーサーexpects ECHOまたはWHITESPACE。これらは、有効な開始条件のみです。「ECHO」を見たので、パーサーexpectsはWHITESPACE|STRING|MATH|DATEのいずれかです。それ以外はエラーです。等々。

acceptパーサーが完全な「ステートメント」を認識したときです- ECHO、その後に有効な一連のトークン、その後にTERMが続きます。パーサーは、ECHOコマンドを処理するのに十分な情報を取得しました。

ああ、手書きのパーサー (特に単純なもの) は、ifブロック (またはswitchステートメントのような道徳的な同等物) のコレクションであることが非常によくあります:) yacc や GOLD パーサー ジェネレーターのような文法ジェネレーター (これらは、醜いif、switch、およびステート マシンを生成します)。

編集して詳細を提供します。

責任を整理するために、入力を読み取ってトークンを生成する「レクサー」を作成します。これには、トークンがどのように見えるかを決定することが含まれます。簡単なトークンは「エコー」という言葉です。それほど簡単でないトークンは数学演算です。トークンは、1 つまたは複数の数字、演算子、および 1 つまたは複数の数字で構成され、その間に空白はありません。レクサーは、引用符で囲まれた文字列と date() 関数を形成する文字を理解するだけでなく、空白をスキップすることも処理します。lexer は、読み取ったトークンのタイプとトークンの値 (「MATH」と「9*15」など) の 2 つを返します。

入力を読み取るためのレクサーを使用すると、パーサーはトークンを消費し、それらが適切な順序になっていることを確認します。まず、ECHOトークンを確認する必要があります。そうでない場合は、エラー メッセージで失敗します。その後、STRING、DATE、またはMATHを確認する必要があります。そうでない場合は、エラー メッセージで失敗します。その後、ループして、TERMを監視するか、またはCONCATに続いて別のSTRING、DATE、またはMATHを監視します。TERMが表示された場合は、ループを中断します。TERMもCONCATも表示されない場合は、失敗してエラー メッセージが表示されます。

ECHO コマンドは単純な文法なので、解析しながら処理できます。STRING、DATEまたはMATHを見つけるたびに、それを評価し、すでに持っているものに連結します。TERMが見つかったら、関数を終了し、構築された文字列を返します。

質問？コメント? オムレツ？:)

于 2012-11-09T15:52:33.680 に答える