4

Javascript コードで Java/Javascript のような式をトークン化することを検討しています。入力は式を含む文字列になり、出力はトークンの配列である必要があります。

このようなことをするためのベストプラクティスは何ですか? 文字列を反復する必要がありますか、それともこれを行う正規表現はありますか?

サポートできるようにするためにこれが必要です：

  • 数値および文字列リテラル (一重引用符と二重引用符で囲み、引用符でエスケープ)
  • 基本的な数学およびブール演算子と比較演算子 (+、-、​​、/、!、および、not、<、> など)
  • 再帰によるオブジェクト アクセスのドットおよびブラケット表記 (foo.bar、foo['bar']、foo[2][prop])
  • ネスト付き括弧
  • 三項演算子 (foo ? bar : 'baz')
  • 関数呼び出し (foo(bar))

eval()セキュリティ上の理由から、またはそのようなものを使用することは特に避けたいと思います。その上、eval()とにかく私のために表現をトークン化しません。

4

3 に答える 3

11

再帰降下パーサーの書き方を学びます。概念を理解すれば、Java、C++、JavaScript、SystemVerilog など、どの言語でも実行できます。文字列を処理できる場合は、解析できます。

再帰降下構文解析は、手動で簡単にコーディングできる基本的な構文解析手法です。これは、パーサー ジェネレーターにアクセスできない (またはだまされたくない) 場合に便利です。

再帰降下パーサーでは、文法内のすべての規則が規則を解析する手続きに変換されます。他のルールを参照する必要がある場合は、それらを呼び出して実行します。それらは単なるプロシージャです。

簡単な例: 数値、加算、乗算を含む式 (これは演算子の優先順位を示しています)。まず、文法：

expr ::= 用語
         | | expr "+" 項

項 ::= 係数
         | | 項「*」係数

factor ::= /[0-9/+ (ここでは正規表現を使用しています)

次に、パーサーを作成します (これにはレクサーが含まれます。再帰的降下を使用すると、2 つを一緒にスローできます)。私は JavaScript を使ったことがないので、(さびた) Java でこれを試してみましょう:

class Parser {
  string str;
  int idx; // index into string

  Node parseExpr() throws ParseException
  {
    Node op1 = parseTerm();
    Node op2;

    while (idx < str.size() && str.charAt(idx) == '+') {
      idx++;
      op2 = parseTerm();
      op1 = new AddNode(op1, op2);
    }
    return op1;
  }

  Node parseTerm() throws ParseException
  {
    Node op1 = parseFactor();
    Node op2;

    while (idx < str.size() && str.charAt(idx) == '*') {
      idx++;
      op2 = parseFactor();
      op1 = new MultNode(op1, op2);
    }
    return op1;
  }

  Node parseFactor() throws ParseException
  {
    StringBuffer sb = new StringBuffer();
    int old_idx = idx;

    while (idx < str.size() && str.charAt(idx) >= '0' && str.charAt(idx) <= '9') {
      sb.append(str.charAt(idx));
      idx++;
    }
    if (idx == old_idx) {
      throw new ParseException();
    }
    return new NumberNode(sb.toString());
  }
}

各文法規則がどのように手続きに変換されるかを見ることができます。私はこれをテストしていません。それは読者のための演習です。

また、エラー検出についても考慮する必要があります。実際のコンパイラは、解析エラーから回復して、残りの入力を解析する必要があります。このような 1 行の式パーサーは、回復を試みる必要はまったくありませんが、解析エラーが存在することを判断してフラグを立てる必要があります。言語で許可されている場合、これを行う最も簡単な方法は、例外をスローし、パーサーへのエントリ ポイントで例外をキャッチすることです。上記の例では、考えられるすべての解析エラーを検出したわけではありません。

詳細については、Wikipedia で「LL パーサー」および「再帰降下パーサー」を参照してください。冒頭で述べたように、概念を理解できれば (そして、LALR(1) ステート マシン構成クロージャーの背後にある概念に比べて単純です)、任意の言語で小さなタスク用のパーサーを作成する権限が与えられます。初歩的な文字列機能があるためです。パワーをお楽しみください。

于 2009-05-22T18:14:04.143 に答える
0

速度が重要ではない単純な字句解析プログラムの場合、通常、トークンの種類ごとに正規表現を記述し、それぞれを順番に入力の開始点と一致させようと繰り返し試みます。(O(n^2) アルゴリズムに巻き込まれないように注意してください!) lex のようなツールは、正規表現を 1 つのステート マシンに結合するため、より効率的なレクサーを生成します。

于 2009-05-22T17:44:07.437 に答える
0

字句解析器を実装する必要があります。js/ccを使用してそれを行うことも、独自に有限オートマトンを実装することもできます。

正式には、操作する言語は正規表現であるため、正規表現を使用できます。しかし、私はあなたにそれをお勧めしません。

私は js/cc を使用したことがありませんが、最初にそれを使用してみます。それが機能しない場合は、自分で字句解析器を構築しようとします。

于 2009-05-22T17:44:47.777 に答える