26

コンパイラの専門家の皆さん、私は再帰降下パーサーを書きたいと思っています。それをコードだけでやりたいのです。他の文法からレクサーとパーサーを生成せず、ドラゴンブックを読むように言わないでください。最終的にはそれに近づきます。

CSS などの合理的な単純な言語のレクサーとパーサーの実装について、ザラザラした詳細に入りたいと思います。そして、私はこれを正しく行いたいです。

これはおそらく一連の質問になるでしょうが、今はレクサーから始めています。CSS のトークン化ルールについては、こちらを参照してください。

私は次のような自己記述コードを見つけました (うまくいけば、このスニペットから残りを推測できます):

public CssToken ReadNext()
{
    int val;
    while ((val = _reader.Read()) != -1)
    {
        var c = (char)val;
        switch (_stack.Top)
        {
            case ParserState.Init:
                if (c == ' ')
                {
                    continue; // ignore
                }
                else if (c == '.')
                {
                    _stack.Transition(ParserState.SubIdent, ParserState.Init);
                }
                break;

            case ParserState.SubIdent:
                if (c == '-')
                {
                    _token.Append(c);
                }
                _stack.Transition(ParserState.SubNMBegin);
                break;

これは何と呼ばれていますか？そして、私は合理的によく理解されているものからどのくらい離れていますか? スタックを使用してある種のステートマシンを実装することは非常にうまく機能していますが、このように続ける方法がわかりません。

私が持っているのは、一度に 1 文字を読み取ることができる入力ストリームです。私は今のところ頭を見ていません。ただキャラクターを読んで、現在の状態に応じてそれで何かをしようとします.

再利用可能なコードのスニペットを作成するというマインド セットに取り組みたいと思っています。このTransitionメソッドは現在、それを行うための手段であり、スタックの現在の状態をポップしてから、逆の順序で引数をプッシュします。そうすれば、私が書くTransition(ParserState.SubIdent, ParserState.Init)と、サブルーチンが「呼び出され」、SubIdent完了すると状態に戻りInitます。

パーサーはほぼ同じ方法で実装されます。現在、このようにすべてを単一の大きなメソッドに含めると、トークンを見つけたときにトークンを簡単に返すことができますが、すべてを単一の大きなメソッドに保持する必要があります。これらのトークン化ルールを別々の方法に分割する良い方法はありますか?

4

5 に答える 5

29

あなたが書いているのはプッシュダウンオートマトンと呼ばれるものです。これは通常、字句解析器を作成するのに必要な能力よりも強力です。CSS のような最新の言語の字句解析器を作成している場合は、確かに過剰です。再帰降下パーサーは、プッシュダウン オートマトンに近い能力を持っていますが、再帰降下パーサーは、記述と理解がはるかに簡単です。ほとんどのパーサー ジェネレーターは、プッシュダウン オートマトンを生成します。

レクサーはほとんどの場合、有限状態マシンとして記述されます。つまり、「スタック」オブジェクトを取り除く以外はコードと同じです。有限ステート マシンは、正規表現と密接に関連しています (実際、それらは相互に同等であることが証明されています)。このようなパーサーを設計する場合、通常は正規表現から開始し、それらを使用して決定論的有限オートマトンを作成します。トランジションに追加のコードを追加して、各トークンの開始と終了を記録します。

これを行うためのツールがあります。このlexツールとその子孫はよく知られており、多くの言語に翻訳されています。ツールチェーンにはANTLRレクサー コンポーネントもあります。私の好みのツールはragel、それをサポートするプラットフォーム上にあります。ほとんどの場合、手作業でレクサーを作成する利点はほとんどなく、これらのツールで生成されたコードはおそらく高速で信頼性が高くなります。

独自のレクサーを手動で記述したい場合、良いものは次のようになります。

function readToken() // note: returns only one token each time
    while !eof
        c = peekChar()
        if c in A-Za-z
            return readIdentifier()
        else if c in 0-9
            return readInteger()
        else if c in ' \n\r\t\v\f'
            nextChar()
        ...
    return EOF

function readIdentifier()
    ident = ""
    while !eof
        c = nextChar()
        if c in A-Za-z0-9
            ident.append(c)
        else
            return Token(Identifier, ident)
            // or maybe...
            return Identifier(ident)

次に、パーサーを再帰降下パーサーとして記述できます。lexer / parser ステージを 1 つに結合しようとしないでください。コードが完全に混乱することになります。(Parsec の作成者によると、速度も遅い)。

于 2010-04-13T20:07:36.163 に答える
5

BNF/EBNF から独自のRecursive Descent Parserを作成する必要があります。私は最近自分自身を書かなければならなかったので、このページはとても役に立ちました. 「コードだけで」の意味がわかりません。独自の再帰パーサーの書き方を知りたいということですか?

それをしたい場合は、まず文法を整えておく必要があります。EBNF/BNF を配置したら、そこからパーサーを非常に簡単に作成できます。

パーサーを書いたときに最初にしたことは、すべてを読み込んでテキストをトークン化することでした。したがって、基本的に、スタックとして扱ったトークンの配列ができあがりました。スタックから値をプルし、必要がない場合はそれをプッシュすることの冗長性/オーバーヘッドを減らすために、peekポップせずにスタックの一番上の値を単に返すメソッドを持つことができます。

アップデート

あなたのコメントに基づいて、Javascript でゼロから再帰降下パーサーを作成する必要がありました。ここでパーサーを見ることができます。関数を検索するだけconstraintsです。tokenize入力をトークン化する独自の関数も作成しました。また、別の便利な関数 (peek前に述べた ) も作成しました。パーサーは、EBNF hereに従って解析します。

パーサーを書いてから何年も経っているので、これを理解するのに少し時間がかかりました (最後にパーサーを書いたのは学校でした! )。私の例があなたの道をさらに進めてくれることを願っています。

別の更新

また、shift-reduce パーサーを使用しようとしている可能性があるため、私の例はあなたが望むものではない可能性があることにも気付きました。あなたは今、トークナイザーを書こうとしていると言いました。私の場合、Javascript で独自のトークナイザーを作成しました。おそらく堅牢ではありませんが、私のニーズには十分でした。

 function tokenize(options) {
            var str = options.str;
            var delimiters = options.delimiters.split("");
            var returnDelimiters = options.returnDelimiters || false;
            var returnEmptyTokens = options.returnEmptyTokens || false;
            var tokens = new Array();
            var lastTokenIndex = 0;

            for(var i = 0; i < str.length; i++) {
                if(exists(delimiters, str[i])) {
                    var token = str.substring(lastTokenIndex, i);

                    if(token.length == 0) {
                        if(returnEmptyTokens) {
                            tokens.push(token);
                        }
                    }

                    else {
                        tokens.push(token);
                    }

                    if(returnDelimiters) {
                        tokens.push(str[i]);
                    }

                    lastTokenIndex = i + 1;
                }
            }

            if(lastTokenIndex < str.length) {
                var token = str.substring(lastTokenIndex, str.length);
                token = token.replace(/^\s+/, "").replace(/\s+$/, "");

                if(token.length == 0) {
                    if(returnEmptyTokens) {
                        tokens.push(token);
                    }
                }

                else {
                    tokens.push(token);
                }
            }

            return tokens;
        }

あなたのコードに基づいて、読み取り、トークン化、および解析を同時に行っているように見えます-シフト削減パーサーが行うことだと思いますか? 私が持っているもののフローは、最初にトークン化してトークンのスタックを構築し、次に再帰降下パーサーを介してトークンを送信します。

于 2010-04-13T19:43:16.343 に答える
5

すべてをゼロから手作業でコーディングする場合は、再帰的な適切なパーサーを使用することを検討します。あなたの投稿では、ソースを解析した後、トークン ストリームで何をするかを実際に言っているわけではありません。

ハンドルを取得することをお勧めするいくつかのこと
1. スキャナー/レクサーの優れた設計。これは、パーサー用にソース コードをトークン化するものです。
2. 次はパーサーです。ソース言語に優れた ebnf がある場合、パーサーは通常、再帰的な適切なパーサーに非常にうまく変換できます。
3. 理解しておく必要があるもう 1 つのデータ構造は、シンボル テーブルです。これは、ハッシュテーブルのように単純にすることも、複雑なレコード構造などを表現できるツリー構造のように複雑にすることもできます。CSS の場合は、この 2 つの間のどこかにあると思います。
4. 最後に、コード生成を処理します。ここには多くのオプションがあります。インタープリターの場合は、コードを解析しながらその場で解釈するだけです。より良いアプローチは、i-code の for を生成してから iterpreter を作成し、後でコンパイラーを作成することです。もちろん、.NET プラットフォームの場合は、IL を直接生成できます (おそらく CSS には適用されません :))


参考のために、私はあなたが深い理論に重きを置いていないことを収集し、私はあなたを責めません. Pascal を気にしないのであれば、複雑なコードなしで基本を理解するための本当に良い出発点は、Jack Crenshaw の「Let's build a compiler」です
http://compilers.iecc.com/crenshaw/
頑張ってください。このプロジェクトを楽しんでいます。

于 2010-04-13T20:09:28.640 に答える
4

トークンスタックを明示的に構築する「shift-reduce」パーサーを実装したいようです。通常の代替手段は「再帰下降」パーサーです。このパーサーでは、プロシージャ呼び出しの深さが、実際のハードウェアスタック上に独自のローカル変数を使用して同じトークンスタックを構築します。

shift-reduceでは、「reduce」という用語は、明示的に維持されているトークンスタックで実行される操作を指します。たとえば、スタックの最上位になっている場合はTerm, Operator, Term、削減ルールを適用しExpressionて、パターンの代わりに使用できます。リダクションルールは、shift-reduceパーサーによって使用されるデータ構造に明示的にエンコードされます。その結果、すべての削減ルールはソースコードの同じ場所にあります。

シフトリデュースアプローチは、再帰下降と比較していくつかの利点をもたらします。主観的なレベルでは、shift-reduceはrecursive-descentよりも読みやすく維持しやすいと思います。より客観的には、shift-reduceは、予期しないトークンが発生したときにパーサーからのより有益なエラーメッセージを許可します。

具体的には、shift-reduceパーサーには「リダクション」を行うためのルールの明示的なエンコードがあるため、パーサーを簡単に拡張して、合法的にどのような種類のトークンをたどることができるかを明確にすることができます。（例：「;期待される」）。再帰下降の実装を簡単に拡張して同じことを行うことはできません。

両方の種類のパーサーに関する優れた本であり、さまざまな種類のshift-reduceを実装する際のトレードオフは、ThomasW.Parsonsによる「IntroductiontoCompilerConstruction」です。

Shift-reduceは「ボトムアップ」構文解析と呼ばれることもあり、再帰下降は「トップダウン」構文解析と呼ばれることもあります。使用されるアナロジーでは、優先順位が最も高いノード（たとえば、乗算式の「因子」）は、構文解析の「最下部」にあると見なされます。これは、「再帰下降」の「下降」で使用されるのと同じアナロジーと一致しています。

于 2010-04-13T19:46:17.633 に答える
3

パーサーを使用して整形式でない式も処理する場合は、再帰下降パーサーが本当に必要です。エラー処理とレポートを使用できるようにするのがはるかに簡単です。

文学については、ニクラウス・ヴィルトの古い作品のいくつかをお勧めします。彼は書き方を知っています。アルゴリズム+データ構造=プログラムは私が使用したものですが、彼のコンパイラー構築はオンラインで見つけることができます。

于 2010-04-13T21:57:09.160 に答える