10

私は C のような文法を解析するパーサーを書いていました。

まず、次のようなコードを解析できるようになりました。

a = 1;
b = 2;

ここで、行末のセミコロンをオプションにしたいと思います。

元の YACC ルールは次のとおりです。

stmt: expr ';' { ... }

新しい行が自分で書いたレクサーによって処理される場所 (コードは簡略化されています):

rule(/\r\n|\r|\n/)          { increase_lineno(); return :PASS }

ここでの :PASS 命令は、LEX で何も返さないことと同じです。これは、現在一致しているテキストを破棄して次のルールにスキップします。これは通常、空白で行われるのと同じです。

このため、単純に YACC ルールを次のように変更することはできません。

stmt: expr end_of_stmt { ... }
;
end_of_stmt: ';'
    | '\n'
;

そこで、それに応じてパーサーによってレクサーの状態を動的に変更することにしました。

このような：

stmt: expr { state = :STATEMENT_END } ';' { ... }

そして、新しい行を新しい状態に一致させるレクサー ルールを追加します。

rule(/\r\n|\r|\n/, :STATEMENT_END) { increase_lineno(); state = nil; return ';' }

これは、レクサーが :STATEMENT_END 状態にあるときを意味します。最初に通常どおり行番号を増やし、次に状態を初期状態に設定し、それ自体がセミコロンであるふりをします。

次のコードで実際に動作しないのは奇妙です:

a = 1
b = 2

私はそれをデバッグし、実際には「;」を取得していないことを確認しました 数値 1 の後の改行をスキャンすると期待どおりになり、状態で指定されたルールは実際には実行されません。

そして、新しい状態を設定するコードは、既に新しい行をスキャンして何も返さなかった後に実行されます。つまり、これらの作業は次の順序で行われます。

  1. スキャンa、=および1
  2. 改行をスキャンしてスキップするので、次の値を取得しますb
  3. 挿入されたコード( { state = :STATEMENT_END })が実行されます
  4. エラーの発生 --bここでは予期しない

これは私が期待するものです：

  1. スキャンa、=および1
  2. ルールに一致することがわかったexprので、に減らしますstmt
  3. 挿入されたコードを実行して、新しいレクサー状態を設定します
  4. 改行をスキャンし;、新しい状態一致ルールに従ってを返します
  5. 次の行をスキャンして解析し続けます

イントロスペクションの後、YACC が LALR(1) を使用するために発生した可能性があることがわかりました。このパーサーは、最初に 1 つのトークンを前方に読み取ります。そこまでスキャンすると、まだ状態が設定されていないため、正しいトークンを取得できません。

私の質問は次のとおりです。期待どおりに機能させるにはどうすればよいですか? これについてはわかりません。

ありがとう。

4

2 に答える 2

6

最初に認識すべきことは、このようなオプションの行末記号を使用すると、言語が曖昧になるため、あいまいさを解決する方法を最初に決定する必要があるということです。この場合、主なあいまいさは、中置または前置のいずれかである可能性がある演算子に由来します。例えば：

a = b
-c;

上記を単一の expr-statement として扱いますか、それとも最初のセミコロンが省略された 2 つの別個のステートメントとして扱いますか? C に似た言語の関数呼び出し構文でも、同様のあいまいさが発生する可能性があります。

a = b
(c);

これらを 2 つのステートメントとして解決したい場合は、試したアプローチを使用できます。状態を 1 トークン前に設定するだけです。閉じていない括弧がある場合は状態を設定したくないため、これは注意が必要です。そのため、括弧のネストの深さを記録するために追加の状態変数が必要になり、その場合にのみ挿入半前改行状態を設定します0.

上記のケースを 1 つのステートメントとして解決したい場合は、改行がステートメントを終了するタイミングを決定するために実際にはさらに先読みが必要になるため、事態は複雑になります。少なくとも、改行の後のトークン (および任意のコメントまたはその他の無視されたもの)。この場合、レクサーに余分な先読みをさせることができます。flex を使用していた場合 (明らかにそうではありませんか?)、/演算子 (直接先読みを行う) を使用するか、次のトークンに一致するレクサー ルールまでセミコロンを返すことを延期することをお勧めします。

一般に、この種のトークン状態の記録を行う場合、可能であればレクサー内で完全に行うのが最も簡単だと思います。そのため、パーサーによって時々 (常にではありませんが) 行われる先読みの余分なトークンについて心配する必要はありません。 . この特定のケースでは、簡単な方法は、見られた括弧 ( の場合は +1、 の(場合は -1 )) をレクサーに記録させ、最後のトークンを返すことです。次に、改行ルールで、括弧のレベルが 0 で、最後のトークンが式 (ID または定数または)後置のみの演算子) を終了できるものであった場合、余分な値を返します。;

別のアプローチは、レクサーNEWLINEを独自のトークンとして返すことです。stmt: expr NEWLINE次に、パーサーを変更して、文法内の他のほとんどのトークン間のオプションの改行と同様に受け入れるようにします。これにより、あいまいさがパーサーに直接公開されます (現在は LALR(1) ではありません)。そのため、yacc の演算子の優先順位規則 (トリッキーでエラーが発生しやすい) を使用するか、bison の%glr-parserオプションや btyacc のバックトラッキング機能などを使用して解決する必要があります。あいまいさと直接。

于 2012-06-10T19:16:56.277 に答える
3

あなたが試みていることは確かに可能です。

実際、Ruby はまさにこれを行い、yacc パーサーを備えています。改行はステートメントをソフトターミネートし、セミコロンはオプションであり、ステートメントは「必要な場合」に複数行に自動的に継続されます。

パーサーと字句解析器の間の通信が必要になる場合があります。そうです、従来の yacc は LALR(1) です。

Rubyがどのようにそれを行うのか正確にはわかりません。私の推測では、実際には (あまり) コミュニケーションをとらず、むしろレクサーは明らかに完成していない構造を認識し、括弧と角括弧のバランスが取れるまで黙って改行をスペースとして扱います。また、行が二項演算子またはコンマで終了する場合にも注意し、それらの改行も食べる必要があります。

あくまでも推測ですが、このテクニックはうまくいくと思います。Ruby はオープン ソースです。Matzがどのようにそれを行ったかを正確に知りたい場合は、Ruby をご覧ください。

于 2012-06-10T17:37:40.860 に答える