8

PS。構文解析理論についてどこで読むのですか？

4

11 に答える 11

12

要約：最短はおそらくAntlrです。

構文解析理論について学ぶためにドラゴンブックに行きたくなります。しかし、私はドラゴンブックとは思わず、あなたは「理論」が何を意味するかについて同じ考えを持っています。Dragon Bookには、手書きのパーサー、パーサージェネレーターなどの作成方法が説明されていますが、代わりにパーサー生成ツールを使用することをお勧めします。

数人の人々がBisonとFlex（またはそれらの古いバージョンのYaccとLex）を提案しました。それらは古い頑固者ですが、あまり使いやすいツールではありません。それらのドキュメント自体は貧弱ではありません。それは、それらを使用する際の偶発的な複雑さに対処するのにまったく役立たないというだけです。それらの内部データは十分にカプセル化されておらず、高度な処理を行うことは非常に困難です。例として、phcでは、非常に難しいため、まだ正しい行番号がありません。No-opステートメントを含めるように文法を変更すると、それらは改善されましたが、それは必要ではないはずの信じられないほどのハックです。

表面上、BisonとFlexは連携して動作しますが、インターフェイスは扱いにくいです。さらに悪いことに、それぞれのバージョンはたくさんあり、他の特定のバージョンとしかうまく機能しません。そして、最後に少なくともチェックしましたが、どのバージョンがどのバージョンに対応しているかについてのドキュメントはかなり貧弱でした。

再帰下降パーサーの作成は簡単ですが、面倒な場合があります。Antlrはあなたのためにそれを行うことができ、それはかなり良いツールセットのようです。このプロジェクトで学んだことは他の多くの言語やプラットフォームに適用できるという利点があります（Antlrは非常に移植性があります）。学ぶべき既存の文法もたくさんあります。

使用している言語は明確ではありませんが、一部の言語には優れた解析フレームワークがあります。特に、HaskellParsecLibraryは非常にエレガントに見えます。C ++を使用している場合は、Spiritを使用したくなるかもしれません。始めるのはとても簡単で、それを使って高度なことをするのは難しいですが、それでも可能です。これは、一般的なC++の私の経験と一致します。始めるのは簡単だと思いますが、それから私はすでにいくつかのパーサーを作成し、コンパイラークラスで構文解析を勉強していました。

簡単に言うと、非常に正当な理由がない限り、Antlrです。

于 2009-10-10T00:00:31.953 に答える
11

DragonBookを読むことは常に良い考えです。しかし、あなたの言語が些細なものでなければ、それを行うための「短い」方法は実際にはないことに注意してください。

于 2009-10-04T13:35:18.390 に答える
5

それはむしろあなたの言語に依存します。一部の非常に単純な言語は、解析がほとんど必要ないため、手動でコーディングできます。他の言語では、 RatsなどのPEGジェネレーターを使用しています。（PEGは、正規表現とLRパーサーの間に位置するパーサー式文法です）またはAntlrやYaccなどの従来のパーサージェネレーター。あまり形式的でない言語には、リンク文法などの確率的手法が必要です。

于 2009-10-04T13:38:41.953 に答える
4

再帰下降パーサーを作成します。これは、YACC / BISONよりも簡単な場合があり、通常はより直感的です。

于 2009-10-04T13:52:35.057 に答える
3

Douglas Crockfordには、JavaScriptで記述されたパーサーの親しみやすい例があります。

于 2009-10-10T00:19:18.677 に答える
2

YACC、さまざまな言語のさまざまな実装があります。

あなたの言語で頑張ってください;-)

于 2009-10-04T13:28:27.953 に答える
2

私のような初心者にはANTLRよりも使いやすいように見えたので、GOLD解析システムを使用しましたが、それでも私のニーズに十分に対応できました。このWebサイトには、ソフトウェアだけでなく、ドキュメント（作業の半分である「文法の書き方」の説明を含む）も含まれています。

于 2009-10-04T13:44:03.443 に答える
2

構文解析にはBisonを、字句解析にはFlexを試してください

言語のバイソン定義は、文脈自由文法の形式です。このトピックに関するウィキペディアの記事は非常に優れており、おそらく開始するのに適した場所です。

于 2009-10-04T13:46:00.073 に答える
1

ANTLRは、次の理由により、コンパイラ理論のバックグラウンドがない人にとって最も簡単です。

  • ANTLRWORKS（ビジュアル解析とASTデバッグ）

  • ANTLRブック（コンパイラ理論の背景は必要ありません）

  • レクサーとパーサーの構文は1つだけです。

于 2009-10-10T08:24:27.307 に答える
1

ホスト言語にパーサージェネレーターを使用するのが最速の方法であり、 DragonBookや{C、ML}シリーズのModernCompilerConstructionなどの本の構文解析理論と組み合わせることができます。

Cを使用yaccし、GNUバージョンbisonが標準のジェネレーターである場合。Antlrは多くの言語で広く使用されており、私が知る限り、Java、C＃、およびC++をサポートしています。他にもほとんどすべての言語があります。

私の現在の個人的なお気に入りは、OCaml用の優れたパーサージェネレーターであるMenhirです。MLスタイルの言語（Ocaml、Standard MLなど）の方言は、一般に、コンパイラーとインタープリターの構築に非常に適しています。

于 2009-10-10T00:32:43.007 に答える
1

式の文法の解析に満足している場合は、独自のパーサーを作成するのは非常に短い場合があります。これは、PEGの妥当なサブセットを取得する単純なPackratパーサーです。

import functools

class peg_parse:
    def __init__(self, grammar):
        self.grammar = {k:[tuple(l) for l in rules] for k,rules in grammar.items()}

    @functools.lru_cache(maxsize=None)
    def unify_key(self, key, text, at=0):
        if key not in self.grammar:
            return (at + len(key), (key, [])) if text[at:].startswith(key) \
                else (at, None)
        rules = self.grammar[key]
        for rule in rules:
            l, res = self.unify_rule(rule, text, at)
            if res is not None: return l, (key, res)
        return (0, None)


    def unify_line(self, parts, text, tfrom):
        results = []
        for part in parts:
            tfrom, res = self.unify_key(part, text, tfrom)
            if res is None: return tfrom, None
            results.append(res)
        return tfrom, results

これは、Python辞書の形式の文法を受け入れ、非終端記号をキーとして、代替を配列の要素として使用し、各代替は一連の式です。以下は文法の例です。

term_grammar = {
    'expr': [
        ['term', 'add_op', 'expr'],
        ['term']],
    'term': [
        ['fact', 'mul_op', 'term'],
        ['fact']],
    'fact': [
        ['digits'],
        ['(','expr',')']],
    'digits': [
        ['digit','digits'],
        ['digit']],
    'digit': [[str(i)] for i in list(range(10))],
    'add_op': [['+'], ['-']],
    'mul_op': [['*'], ['/']]
}

ドライバーは次のとおりです。

import sys
def main(to_parse):
    result = peg_parse(term_grammar).unify_key('expr', to_parse)
    assert (len(to_parse) - result[0]) == 0
    print(result[1])

if __name__ == '__main__': main(sys.argv[1])

このように呼び出すことができます：

python3 parser.py '1+2'
('expr', 
    [('term', 
       [('fact', 
           [('digits', [('digit', [('1', [])])])])]), 
     ('add_op', [('+', [])]), 
     ('expr', 
       [('term', [('fact', [('digits', [('digit', [('2', [])])])])])])])

式文法の解析には注意が必要です。選択肢の順序は重要です（文脈自由文法とは異なり、選択肢は順序付けられた選択肢であり、最初の選択肢が最初に試行され、2番目の選択肢は最初の選択肢が一致しなかった場合にのみ試行されます）。ただし、それらはすべての既知の文脈自由文法を表すことができます。

一方、文脈自由文法を使用することにした場合、アーリーパーサーは最も単純なものの1つです。

于 2018-12-07T10:38:01.257 に答える