2

私は過去に再帰降下と PEG のようなパーサーを実装しました。ここでは、次のようなことができます。

Path -> Segment+
Segment -> Slash Name
Segment -> /
Name -> /\w+/
Slash -> /
  • whereSegment+は「1 つ以上に一致する」ことを意味しSegmentます
  • そして、1つ以上の単語文字を一致させるための普通の古い正規表現があります\w+

LR文法/パーサーを使用して、これと同じ種類のことを通常どのように達成しますか? 私が見た LR パーサーの例はすべて非常に基本的なもの1 + 2 * 3で、パターンは非常に単純で、「1 つ以上」の機能 (またはゼロ以上の、またはオプションの)(())()を含まないようです。. 一般に、LR パーサーでどのように行うのですか?*?

それとも、LR 構文解析は最初に字句解析フェーズを必要としますか (つまり、LR パーサーは端末と非端末の「トークン」を必要とします)。そのような 2 つのフェーズなしで LR 解析を行う方法があることを願っています。LRパーサーの定義は、私が読んでいる本/サイトの「入力文字」について語っていますが、さりげなく/微妙に次のような行が表示されます。

文法の終端記号は、字句スキャナによって入力ストリームで検出された複数文字記号または「トークン」です。

そして、スキャナーはどこから来たのですか。

4

3 に答える 3

2

確かに言語のスキャナーレス文法を書くことはできますが、トークンが 1 文字の場合、先読みの 1 トークンは多くないため、ほとんどの場合、LR( 1 ) にはなりません。

一般に、LALR(1) パーサー ジェネレーター (bison など) は、スキャナー ジェネレーター (flex など) と組み合わせて使用​​されます。

于 2015-04-26T06:19:04.720 に答える
1

トークンのストリームで動作するパーサーがある場合は常に、何がトークンのストリームを生成したのかという問題が常に発生します。ほとんどのパーサー ジェネレーターでは、トークンの文法仕様と語彙仕様は分離されています。これは主に、パーサー ジェネレーターとレクサー ジェネレーターの動作方法が異なるためです。

「文法」に正規表現演算子を追加すると便利です。しかし、それらは文脈自由文法の力を拡張するものではありません。

文法で正規表現のような演算子を使用するには、3 つの選択肢があります。

1) 文法全体で一貫して文字レベルで使用します。これを行うと、パーサーは個々の文字であるトークンで動作します。ほとんどのパーサー ジェネレーターの決定は、次の入力ストリーム トークン (この場合は 1 文字) のみに基づいているため、これはほとんどのパーサー ジェネレーターで適切に機能しない可能性があります。これを機能させるには、バックトラッキング パーサーか、代替パースのスペースを介して複数のパスを試行するパーサーが必要です。LR および LL パーサーはこれを行いません。文字ごとの GLR の追加のオーバーヘッドを気にしないのであれば、これが機能するスキャナーレス GLR パーサーがあります。(また、文字レベルで操作する場合は、空白とコメント構文を明示的に指定する可能性があります)。

2) それらを個々のトークン文字シーケンスの仕様として使用します (OP の「名前 -> /w+/」のように)。この形式では、文法と統合された語彙トークン仕様を書くことになります。次に、文法を 2 つの部分に処理できます。字句仕様と、より従来型の BNF です。この考え方は、多くのレクサーおよびパーサー ジェネレーターと互換性があります。それでも表現力は変わらない。

3) 文法要素でのみ正規表現演算子を使用します。これらは、従来の BNF 文法規則に簡単に変換できます。

  Path -> Segment +

次と同等です。

  Path -> Segment 
  Path -> Path Segment

このような変換の後、結果はほとんどのパーサー ジェネレーターと互換性があります。これにより、文法トークンの字句構文がどのように指定されるかは未解決のままになります。

1）と2）を組み合わせたハイブリッドスキームを実装できます。これは、OPが行ったことのようです。

于 2015-06-19T14:31:08.363 に答える