compiler-construction - null 許容プロダクションの削除

Question

私は Pascal のサブセット用の語彙アナライザーの作成に取り組んでいます。これは、コンパイラーの赤いドラゴンの教科書の最後で推奨されているプログラミング プロジェクトです。解析テーブルを作成できるように、文法を LL に変更しています。私は他にぶら下がっているあいまいさを無視しており、それが存在する唯一のあいまいさであると信じています。すべてのイプシロン プロダクションを削除しました。左因数分解に進む前に、イプシロン プロダクションを正しく削除したかどうかについてのフィードバックが必要でした。私はかなり長い間これを見つめてきたので、後で問題を引き起こす何かを見落としていて、それをチェックする人がいないかどうかは本当にわかりません. 私はこれが長い投稿であることを知っています。これを知っている人にチェックしてもらうために他にどこに行くべきか本当にわかりません。お時間をいただき、誠にありがとうございます。

元の文法:

<statement> →
    if <expression> then <statement>
<factor> → id
<program> →
     <program> id (<identifier_list>);
     <declarations>
     <subprogram_declarations>
     <compound_statement>
     .
<identifier_list> →
     id
     | <identifier_list>, id
<declarations> →
     <declarations> var id : <type>;
     |E
<type> → 
     <standard_type>
     |array[num..num] of <standard_type>
<standard type> →
     integer
     | real
<subprogram_declarations> →
     <subprogram_declarations> <subprogram_declaration>;
     |E
<subprogram_declaration> →
     <subprogram_head declarations> 
     <subprogram_declarations> 
     <compound_statement>
<subprogram_head> → 
     function id <arguments> : <standard_type>;
<arguments> → 
    (<parameter_list>)
    | E
<parameter_list> →
     id : <type> 
     | <parameter_list>; id : <type>
<compound statement> →
     begin
     <optional_statements>
     end
<optional_statements> →
     <statement_list>
     | E
<statement_list> →
     <statement>
     |<statement_list>; <statement>
<statement> →
     <variable> assignop <expression>
     | <procedure_statement>
     | <compound_statement>
     | if <expression then statement> else <statement>
     | while <expression> do <statement>
     | if <expression> then <statement>
<variable> → 
     id
     | id [<expression> ]
<expression_list> →
     <expression>
     |<expression_list> , <expression>
<expression> →
     <simple_expression>
     | <simple_expression> relop <simple_expression>
<simple_expression> →
     <term>
     | sign <term>
     | <simple_expression> addop <term>
<term> →
     <factor>
     | <term> mulop <factor>
<factor> →
     id
     | id (<expression_list>)
     | num
     | (<expression>)
     | not <factor>
     | id [<expression>]
<sign> →
     + | -

文法ポスト イプシロン生成の削除

<statement> →
    if <expression> then <statement>
<factor> → id
<program> →
     <program><id (<identifier_list>);
     <declarations>
     <subprogram_declarations>
     .
     |<program> id (<identifier_list>);
      <subprogram_declarations>
      .
     |<program>id (<identifier_list>);
      <declarations>
      .
     |<program> id (<identifier_list>);
      .
     |<program><id (<identifier_list>);
      <declarations>
      <subprogram_declarations>
      begin
      <statement_list>
      end
      .
     |<program> id (<identifier_list>);
      <subprogram_declarations>
      begin
      <statement_list>
      end
      .
     |<program>id (<identifier_list>);
      <declarations>
      begin
      <statement_list>
      end
      .
     |<program> id (<identifier_list>);
      begin
      <statement_list>
      end
      .
<identifier_list> →
     id
     | <identifier_list>, id
<declarations> →
     <declarations> var id : <type>;
<type> → 
     <standard_type>
     |array[num..num] of standard_type
<standard type> →
     <integer>
     | <real>
     <subprogram_declarations> →
     <subprogram_declarations>  <subprogram_declaration>;
<subprogram_declaration> →
     <subprogram_head> <declarations> 
     <subprogram_declarations >
     begin
     <statement_list>
     end
     |<subprogram_head>
      <subprogram_declarations >
      begin
      <statement_list>
      end
     |<subprogram_head> <declarations> 
      begin
      <statement_list>
      end
     |<subprogram_head>
      begin
      <statement_list>
      end
     |<subprogram_head> <declarations> 
      <subprogram_declarations >
     |<subprogram_head>
      <subprogram_declarations >
     |<subprogram_head> <declarations> 
     |<subprogram_head>
<subprogram_head> → 
      function id (<parameter_list>) : <standard_type>;
      |function id : <standard_type>;
<parameter_list> →
     id : <type> 
     |<parameter_list>; id : <type>
<statement_list> →
     <statement>
     |<statement_list>;< statement>
<statement> →
     <variable> assignop <expression>
     | <procedure_statement>
     | <compound_statement>
     | if <expression> then <statement> else <statement>
     | while <expression> do <statement>
     | if <expression> then <statement>
<variable> → 
     id
     |id [<expression>]
<expression_list> →
     <expression>
     |<expression_list> , <expression>
<expression> →
     <simple_expression>
     | <simple_expression> relop <simple_expression>
<simple_expression> →
     <term>
     | <sign> <term>
     | <simple_expression> addop <term>
<term> →
     <factor>
     | <term> mulop <factor>
<factor> →
     id
     | id (<expression_list>)
     | num
     | (<expression>)
     | not <factor>
     | id [<expression>]
<sign> →
     + | -

もちろん、2 番目の文法は大きく異なります。それへの参照を見つけて|を作成することにより、すべてのイプシロンプロダクションを削除しました。それの有無にかかわらずオプション。イプシロンを削除すると、プロダクションに 1 行しか残らなかったため、そのプロダクションを完全に削除し、以前にプロダクションが呼び出された場所にラインを移動しました。たとえば、次のように変更して、この方法で完全に排除しました。

 <subprogram_head> → 
      function id <arguments> : <standard_type>;
 <arguments> → 
      (<parameter_list>)
      | E

に

<subprogram_head> → 
     function id (<parameter_list>) : <standard_type>;
     |function id : <standard_type>;