1

Stephen C. Johnson による Yacc の紹介から:

次のような正しい再帰規則を使用

    seq     :       item
            |       item  seq
            ;

パーサーは少し大きくなり、アイテムは右から左に表示され、縮小されます。さらに深刻なことに、非常に長いシーケンスが読み取られると、パーサーの内部スタックがオーバーフローする危険があります。したがって、ユーザーは妥当な場合は常に左再帰を使用する必要があります。

Yacc が LR パーサーを生成することは知っているので、単純な右再帰文法を手作業で解析してみました。今のところ問題は見えませんでした。誰でもこれらの問題を示す例を挙げられますか?

4

2 に答える 2

2

パーサーのサイズは深刻な問題ではありません (ほとんどの場合)。

ランタイム スタック サイズが問題になる場合があります。問題は、右の再帰規則では、パーサーがシーケンスの最後に到達するまでスタックを減らすことができないことを意味するのに対し、左の再帰規則では、文法が に遭遇するたびseq itemに、スタック上のアイテムの数を減らすことができることです。 .

従来、トークンのスタックは固定され、サイズが制限されていました。したがって、次のような正しい再帰規則を処理します。

IF <cond> THEN
    <stmt-list>
ELSIF <cond> THEN
    <stmt-list>
ELSIF <cond> THEN
    <stmt-list>
ELSE
    <stmt-list>
ENDIF

文法が受け入れることができる ELIF 句のチェーン内の用語の数を制限します。

仮説文法:

if_stmt: if_clause opt_elif_clause_list opt_else_clause ENDIF
    ;
if_clause: IF condition THEN stmt_list
    ;
opt_elif_clause_list: /* Nothing */
    | elif_clause opt_elif_clause_list  /* RR */
    ;
elif_clause: ELIF condition THEN stmt_list 
    ;
opt_else_clause: /* Nothing */
    |   ELSE stmt_list
    ;
stmt_list: stmt
    | stmt_list stmt       /* LR */
    ;

私はかなり前 (10 年以上前) にこれについていくつかのテストを行ったことを覚えているようですが、当時私が使用していた Yacc は、上記と同様の言語文法と組み合わせて、約 300 秒後にELIF句、パーサーが停止しました（スペースの枯渇に気づかずにクラッシュするのではなく、スペースが不足していることを認識して、制御下で停止したと思います）。

于 2013-10-22T19:20:19.513 に答える
2

適切な再帰パーサーがより大きくなると彼が言う理由はまったくわかりません-一般に、ステートマシンで必要な状態が1つ少なくなります（何かがあればそれを小さくする必要があります）が、本当の問題は正しい再帰パーサーが文法には無制限のスタック スペースが必要ですが、左再帰文法には定数スペース (O(n) スペースと O(1) スペース) が必要です。

O(n) と O(1) は大したことのように聞こえるかもしれませんが、何をしているかによっては重要ではないかもしれません。特に、入力全体をメモリに読み取って処理する場合、右再帰と左再帰の O(n) と O(1) の区別を完全に圧倒する O(n) スペースです。パーサー スタックが固定されている特に古いバージョンの yacc を使用している場合は、問題になる可能性がありますが、最近のバージョンの yacc (Berkeley yacc、bison) では、必要に応じてパース スタックが自動的に拡張されるため、利用できる制限は 1 つだけです。メモリー。

于 2013-10-22T23:13:33.820 に答える